Quelqu'un peut-il suggérer des articles ou des algorithmes sur le calcul des chemins les plus courts dans les espaces euclidiens avec un polygone non convexe comme obstacles?
path-finding
anévrisme
la source
la source
Réponses:
L'approche la plus simple consiste à transformer les polygones non convexes en plusieurs polygones convexes, puis à effectuer une collision convexe normale et à trouver un chemin (via A * ou D * ou autre). Le premier processus est souvent appelé triangulation en géométrie de calcul, et il existe plusieurs façons courantes de le faire.
la source
Ce n'est peut-être pas la réponse exacte à votre question, mais je peux vous suggérer une approche à ce sujet.
En fait, votre problème est lié à deux problèmes.
Et le deuxième problème est intégré au premier. Je peux recommander d'abord de comprendre la recherche aveugle. Voici une présentation très simple à ce sujet: Recherche aveugle
Si vous lisez le document pour construire l'espace d'état, vous devrez générer des points d'état et ils doivent être légaux, ce qui signifie que ces états peuvent être sur votre chemin le plus court afin qu'ils ne doivent pas entrer en collision avec des objets dans votre espace. Désormais, vous pouvez continuer avec les algorithmes de collision euclidienne. Après avoir construit votre espace d'état et votre arbre de recherche restreint par des collisions, vous pouvez choisir l'un des algorithmes de chemin le plus court ou l'un des vôtres ou un hybride modifié.
la source