Finden Sie die Mittellinie des Tunnels?

Ich habe einige Kartendateien, die aus 'Polylinien' bestehen (jede Linie ist nur eine Liste von Eckpunkten), die Tunnel darstellen, und ich möchte versuchen, die 'Mittellinie' des Tunnels zu finden (unten ungefähr in Rot dargestellt).

Alt-Text

Ich hatte in der Vergangenheit einige Erfolge mit der Delaunay-Triangulation , möchte diese Methode jedoch vermeiden, da sie (im Allgemeinen) keine einfache / häufige Änderung meiner Kartendaten ermöglicht.

Irgendwelche Ideen, wie ich das schaffen könnte?

Ich arbeite in ziemlich rohem C ++.

geometry algorithm polyline-creation skeleton sje397
quelle

gis.stackexchange.com/q/177/162 befasst sich auch mit dem, wonach Sie suchen: Skelettierungsalgorithmen .

Juli

Ich denke, die Querverbindung mit SO ist relevant, da es auch dort Antworten gibt. Stackoverflow.com/questions/3983613/find-tunnel-center-line

Dr. belisarius

@ julien: Du hast das schon in deiner Antwort verlinkt. Ich lese es durch, aber es beantwortet nicht meine spezifische Frage (die umformuliert werden muss: „Ich weiß bereits, wie man die MAT findet - aber ich frage mich, ob jemand einen Nicht-Delaunay- Algorithmus kennt [dh keine lib - das problem ist nicht meine codierung;)] die für lokalisierte änderungen effizient ist '). Es gab eine Antwort auf SO, die auch nicht ganz antwortete, aber viel Mühe machte und mir viel zu denken gab, also habe ich den Scheck an diesen Kerl vergeben, bis etwas Besseres eintritt. Keine der folgenden Antworten ist so gut (was möglicherweise meine Schuld ist).

sje397

Antworten:

Sie haben eine gute Annäherung an die mediale Achsentransformation gezogen. Die Delaunay-Triangulation bietet in der Tat einen guten Ansatz. (Die Hauptherausforderung besteht darin, dass Teile des MAT Parabelstücke sind, nicht nur Liniensegmente.)

Ich bin in der akademischen Literatur auf Verweise auf Arbeitscode gestoßen (normalerweise in C / C ++, wie ich mich erinnere). Führen Sie eine Suche in Google Scholar durch und suchen Sie nach älteren Artikeln (die neueren scheinen sich auf 3D-Berechnungen zu konzentrieren).

whuber
quelle

Ich habe einen funktionierenden Code mit Delaunay. Ich frage wirklich, ob es noch andere Möglichkeiten gibt.

sje397

@ sje397 Zunächst einmal löst Delaunay das Problem nur annähernd. Allein aus diesem Grund kann es sich lohnen, nach besserem Code zu suchen. Zweitens gibt es in der Tat andere Wege. Ich kann zwei kurz skizzieren: (1) Suche nach der MAT mittels interner Puffer und (2) Durchführung einer Geländeanalyse auf dem euklidischen Distanzgitter der Polylinien. Ich erwähnte auch nicht, weil beide viel ineffizienter sind und schlechtere Ergebnisse liefern. Möglicherweise ist die zweite Methode für eine relativ schnelle dynamische Lösung geeignet.

whuber

Ein Blick in "Polygonskelette" könnte sich lohnen.

Unter http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html finden Sie einige C ++ - Quellcode-Beispiele

Underdunkel
quelle

Danke underdark. Ich werde weiter auf CGAL eingehen. Die Schwierigkeit besteht darin, dass die Neuberechnung nicht teuer sein muss, wenn sich meine Kartendaten ändern.

sje397

CGAL ist ziemlich schnell - eine schnelle Berechnung sollte möglich sein. Ansonsten können Sie sich die sogenannten 'kinetischen Datenstrukturen' ansehen

julien 21.10.10

Das "Skelett" ist ein weiterer Begriff für die MAT. Die Suche nach "medial axis transform" hat meiner Erfahrung nach mehr und bessere Treffer als die Suche nach "skeleton" ergeben.

Whuber

"Skelett" scheint generischer zu sein - MAT ist nur ein spezifischer Algorithmus für das Skelett, oder? Was auch immer, es ist nicht das Thema ...!

Juli

Die Lizenz für CGAL sieht restriktiv aus (dh sehr teuer - dies ist kommerzielle Software).

sje397