Wie kann ich den kürzesten Weg in euklidischen Umgebungen mit nicht konvexen Polygonen berechnen?

10

Kann jemand Artikel oder Algorithmen zur Berechnung kürzester Wege in euklidischen Räumen mit nicht konvexem Polygon als Hindernissen vorschlagen?

path-finding aneuryzm
quelle
Beachten Sie, dass Sie das nicht konvexe Polygon durch seinen komplexen Rumpf ersetzen können, es sei denn, Ihr Startpunkt, Endpunkt oder ein anderes Polygon liegt im Raum zwischen einem nicht konvexen Polygon und seiner konvexen Hülle. Einfach zu erkennen, indem Sie einfach ein nicht konvexes Polygon und seine konvexe Hülle zeichnen und dann überlegen, welche kürzesten Wege den Unterschied durchlaufen.
MSalters

Antworten:

3

Der einfachste Ansatz besteht darin, die nicht konvexen Polygone in mehrere konvexe umzuwandeln und dann eine normale konvexe Kollision und Pfadfindung durchzuführen (über A * oder D * oder was auch immer). Der erste Prozess wird in der Berechnungsgeometrie häufig als Triangulation bezeichnet , und es gibt verschiedene gängige Methoden, um dies zu tun.


quelle
3

Dies ist möglicherweise nicht die genaue Antwort auf Ihre Frage, aber ich kann Ihnen einen Ansatz zu diesem Thema vorschlagen.

Eigentlich ist Ihr Problem zwei Probleme zusammen.

  1. Kürzeste Wege finden
  2. Kollisionen finden

Und das zweite Problem ist in das erste eingebettet. Ich kann empfehlen, zuerst die blinde Suche zu verstehen. Hier ist eine sehr einfache Präsentation dazu: Blind Search

Wenn Sie das Dokument zum Erstellen des Statusraums lesen, müssen Sie Statuspunkte generieren. Diese müssen legal sein, dh diese Status können sich auf Ihrem kürzesten Weg befinden, damit sie nicht mit Objekten in Ihrem Bereich kollidieren. Von nun an können Sie mit euklidischen Kollisionsalgorithmen fortfahren. Nachdem Sie Ihren durch Kollisionen eingeschränkten Statusraum und Suchbaum erstellt haben, können Sie einen der Algorithmen mit dem kürzesten Pfad oder einen Ihrer eigenen oder einen modifizierten Hybridalgorithmus auswählen.

Gorki
quelle