У меня есть несколько картографических файлов, состоящих из «полилиний» (каждая строка - просто список вершин), представляющих туннели, и я хочу попытаться найти «центральную линию» туннеля (показано примерно красным цветом ниже).
В прошлом у меня был некоторый успех с использованием триангуляции Делоне, но я бы хотел избежать этого метода, поскольку он (в общем) не позволяет легко / часто изменять данные моей карты.
Любые идеи о том, как я мог бы сделать это?
Я работаю в довольно сырой C ++.
Ответы:
Вы нарисовали хорошее приближение к преобразованию медиальной оси. Триангуляция Делоне действительно предлагает хороший подход к ней. (Основная проблема заключается в том, что части МАТ являются частями парабол, а не просто отрезками.)
Я наткнулся на ссылки на рабочий код (обычно на C / C ++, который я помню) в научной литературе. Выполните поиск в Google Scholar и найдите более старые статьи (кажется, что более новые из них посвящены 3D-вычислениям).
источник
Возможно, стоит заглянуть в «скелеты многоугольника».
Пример исходного кода на C ++ можно найти по адресу http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html.
источник