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).
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 ++.
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).
źródło
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
źródło