Znalezienie linii środkowej tunelu?

Mam kilka plików map składających się z „polilinii” (każda linia jest tylko listą wierzchołków) reprezentujących tunele i chcę spróbować znaleźć „środkową linię” tunelu (z grubsza zaznaczoną na czerwono poniżej).

alternatywny tekst

W przeszłości miałem pewien sukces przy użyciu triangulacji Delaunaya, ale chciałbym uniknąć tej metody, ponieważ (ogólnie) nie pozwala ona na łatwą / częstą modyfikację moich danych mapy.

Jakieś pomysły na to, jak mogę to zrobić?

Pracuję w dość surowym C ++.

— sje397
źródło

gis.stackexchange.com/q/177/162 zajmuje się także tym, czego szukasz: algorytmami szkieletowania .

— Julien

Myślę, że połączenie krzyżowe z SO jest istotne, ponieważ są tam również odpowiedzi stackoverflow.com/questions/3983613/find-tunnel-center-line

— Dr. belisarius

@julien: Podałeś już to w swojej odpowiedzi. Przeczytałem to, ale nie odpowiada na moje konkretne pytanie (które, inaczej mówiąc, brzmi: „Wiem już, jak znaleźć MAT - ale zastanawiam się, czy ktoś zna algorytm inny niż Delaunay [tj. Nie lib - problemem nie jest moje kodowanie;)], które jest wydajne dla zlokalizowanych zmian '). Na SO było odpowiedź, która nie do końca odpowiadała, ale wymagała wiele wysiłku i dała mi wiele do przemyślenia, więc wystawiłem czek temu facetowi, dopóki nie pojawi się coś lepszego. Żadna z poniższych odpowiedzi nie jest tak dobra (co może być moją winą).

— sje397,

Odpowiedzi:

Zrobiłeś dobre przybliżenie do transformacji osi środkowej. Triangulacja Delaunaya rzeczywiście oferuje do niej dobre podejście. (Głównym wyzwaniem jest to, że części MAT to fragmenty paraboli, a nie tylko odcinki linii).

W literaturze akademickiej natknąłem się na odniesienia do działającego kodu (zwykle w C / C ++, które pamiętam). Wyszukaj w Google Scholar i poszukaj starszych artykułów (wydaje się, że nowsze koncentrują się na obliczeniach 3D).

— Whuber
źródło

Mam trochę działającego kodu, używając Delaunay. Naprawdę pytam, czy istnieją inne sposoby.

— sje397

@ sje397 Po pierwsze, Delaunay rozwiązuje problem tylko w przybliżeniu, dlatego tylko z tego powodu warto poszukać lepszego kodu. Po drugie, istnieją rzeczywiście inne sposoby. Mogę krótko zarysować dwa: (1) poszukiwanie MAT za pomocą wewnętrznych buforów i (2) przeprowadzić analizę terenu na siatce odległości euklidesowej polilinii. Nie wspomniałem też o tym, ponieważ oba są znacznie bardziej nieefektywne i dają gorsze wyniki. Można sobie wyobrazić, że drugi sposób można zastosować do dość szybkiego rozwiązania dynamicznego.

— whuber

Warto spojrzeć na „szkielety wielokątów”.

Próbka źródła C ++ znajduje się na stronie http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

— podmrok
źródło

Dzięki podmrok. Przyjrzę się bliżej CGAL. Ale trudność polega na tym, że ponowne obliczanie nie jest drogie, gdy zmieniają się moje dane mapy.

— sje397

CGAL jest dość szybki - obliczenia w locie powinny być możliwe. W przeciwnym razie, można spojrzeć na tak zwanych struktur danych kinetycznych ': cgal.org/Manual/3.3/doc_html/cgal_manual/...

— julien

„Szkielet” to kolejny termin na MAT. Wyszukiwanie „transformacji osi środkowej” przyniosło więcej i więcej trafień niż wyszukiwanie „szkieletu” z mojego doświadczenia.

— whuber

„szkielet” wydaje się bardziej ogólny - MAT jest tylko jednym specyficznym algorytmem dla szkieletu, prawda? Cokolwiek, to nie jest temat ...!

— Julien

Licencja na CGAL wygląda na restrykcyjną (tj. Drogie - jest to oprogramowanie komercyjne).

— sje397