Generieren Sie ein Diagramm von verbundenen konvexen Polygonen
https://stackoverflow.com/questions/4752816
-
13-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, ein dichter Diagramm von Punkten wie zu nehmen, z. B. Dies, und verwandeln Sie es in ein Diagramm von verbundenen konvexen Polygonen. Die Polygone sollten so groß und einfach wie möglich sein, während sie in Verbindung bleiben. Das resultierende Diagramm wird zur Pfadfindung verwendet. Kann mir jemand in die richtige Richtung verweisen?
Lösung
Es ist sehr ärgerlich, dass ich keine Links veröffentlichen kann. Macht es schwierig, ein Lurker zu sein und nur gelegentlich Teilnehmer.
Am Ende habe ich die folgenden Techniken verwendet:
Erstellen Sie zunächst eine Distanztransformation. Ich habe den hier beschriebenen Algorithmus verwendet [nicht verlinken], was zu einem Bild wie diesem [nicht verlinken kann]. Erstellen Sie dann eine Wasserscheide -Transformation der DT, um sie in Gebiete zu teilen. Dies erfordert einige Arbeiten, aber derzeit sieht dies so aus, als würde dies die Mittelpunkte der Polylines verwenden, die jedes Bereich von Bereichen verbinden, um einen Wegpunkt -Diagramm zu erstellen.
Die Wassereinzugsgebiets -Partitionierung ist noch nicht perfekt, beachten Sie das Aliasing -verursachen, aber ich habe 181 Bereiche und 281 Wegpunkte für diese 128x128 -Karte.
Andere Tipps
Dies ist nicht das, wonach Sie gefragt haben, aber hier sind einige andere Ideen zur Lösung dieses Problems mit 2D -Pfad:
Verwenden ein*. Dies ergibt den kürzesten kollisionsfreien Weg. Die Leistung könnte in Ordnung sein, auch ohne die Vereinfachung der Bitmap.
Verwenden ein Roadmap auf Probenahme. Dies ist eine weitere diskretisierte Darstellung als Polygone. Da Ihr Suchraum klein ist, können Sie die gesamte Bitmap durchqueren, um zu überprüfen, ob jeder Punkt mit der Roadmap verbunden werden kann. Wenn ein kompakt Roadmap ist wichtig (aber kurze Wege nicht), die Sichtbarkeit Roadmap Technik kann verwendet werden.
Da Sie sich ohnehin mit der Darstellung der Grafik und der Graph -Suche befassen müssen, scheinen diese Techniken viel einfacher zu sein als die Polygon -Extraktion. Ich habe einige so Fragen zu diesem Problem ausgegraben:
Wenn der Raum von Polygonen abgebildet wurde (möglicherweise mit einem Werkzeug), kann er in konvexe Polygone oder eine andere Darstellung aufgeteilt werden, die durchsucht werden können. Dies wird auch von Lavalle besprochen:
