comment savoir si une forme est praticable

Question

J'ai un polygone complexe (éventuellement concave) et quelques-uns de ses bords marqués comme points d'entrée/sortie. il est possible qu'à l'intérieur de ce polygone se trouvent un ou plusieurs blocs de forme arbitraire. Quelles approches pourrais-je utiliser pour déterminer si un chemin d'une certaine largeur existe entre une paire d'arêtes d'entrée/sortie? Après avoir lu la question, il ressemble à un type de devoirs - ce n'est pas le cas. Je souhaite juste avoir au moins quelques pistes que je pourrais poursuivre, car c'est nouveau pour moi.

Answer 1

Jetez un coup d'œil à Motion Planning - il y a une mine d'informations là-bas.

Answer 2

Cela dépend si l'itinéraire doit avoir une largeur. Si l'objet qui doit se déplacer a une taille finie, vous devez prendre la différence Minkowski de votre polygone de domaine avec le polygone de l'objet en mouvement, puis vous essayez de le parcourir. Une façon de calculer exactement les chemins est de calculer le graphique de visibilité du polygone. Le graphe de visibilité a des sommets correspondant aux sommets du polygone du domaine (éventuellement avec des trous où se trouvent les obstacles), et deux sommets sont reliés par un bord s'ils peuvent se "voir" entre eux. La forme est passable s'il existe un ensemble d'arêtes joignant une entrée à une sortie. Vous pouvez également calculer des choses comme les chemins les plus courts. Calculer le graphique de la visibilité d'une manière naïve n'est pas difficile, mais lent. Il existe des algorithmes très avancés pour le faire, mais ils (AFAIK) n'ont pas été implémentés. J'ai essayé de le mettre en place il y a quelques années, avec des résultats médiocres. La plupart d'entre eux assument des sommets en position générale, en utilisant l'arithmétique exacte, alors que les applications pratiques utiliseraient des nombres à virgule flottante.