Нахождение туннельной осевой линии?

19

У меня есть несколько картографических файлов, состоящих из «полилиний» (каждая строка - просто список вершин), представляющих туннели, и я хочу попытаться найти «центральную линию» туннеля (показано примерно красным цветом ниже).

альтернативный текст

В прошлом у меня был некоторый успех с использованием триангуляции Делоне, но я бы хотел избежать этого метода, поскольку он (в общем) не позволяет легко / часто изменять данные моей карты.

Любые идеи о том, как я мог бы сделать это?

Я работаю в довольно сырой C ++.

sje397
источник
gis.stackexchange.com/q/177/162 также занимается тем, что вы ищете: алгоритмами скелетизации .
Жюльен
3
Я думаю, что перекрестная ссылка с SO актуальна, так как там тоже есть ответы stackoverflow.com/questions/3983613/find-tunnel-center-line
Dr. belisarius
@julien: Вы уже связали это в своем ответе. Я прочитал его, но он не отвечает на мой конкретный вопрос (который, перефразируя, таков: «Я уже знаю, как найти МАТ - но мне интересно, знает ли кто-нибудь алгоритм, не относящийся к Делоне? проблема не в моем кодировании;)], которое эффективно для локальных изменений '). Был ответ на SO, который тоже не совсем отвечал, но потребовал много усилий и дал мне много размышлений, поэтому я присудил чек этому парню, пока не появится что-то лучшее. Ни один из приведенных ниже ответов не является настолько хорошим (что вполне может быть моей ошибкой).
sje397

Ответы:

6

Вы нарисовали хорошее приближение к преобразованию медиальной оси. Триангуляция Делоне действительно предлагает хороший подход к ней. (Основная проблема заключается в том, что части МАТ являются частями парабол, а не просто отрезками.)

Я наткнулся на ссылки на рабочий код (обычно на C / C ++, который я помню) в научной литературе. Выполните поиск в Google Scholar и найдите более старые статьи (кажется, что более новые из них посвящены 3D-вычислениям).

Whuber
источник
У меня есть некоторый рабочий код, использующий Делоне. Я действительно спрашиваю, есть ли другие способы.
sje397
1
@ sje397 Прежде всего, Делоне решает проблему только приблизительно, поэтому по одной этой причине стоит поискать лучший код. Во-вторых, действительно есть другие способы. Я могу кратко изложить два из них: (1) поиск MAT с помощью внутренних буферов и (2) выполнение анализа местности на евклидовой сетке расстояний полилиний. Я не упоминал ни того, ни другого, потому что оба они гораздо более неэффективны и дают худшие результаты. Вероятно, второй метод поддается достаточно быстрому динамическому решению.
whuber
4

Возможно, стоит заглянуть в «скелеты многоугольника».

Пример исходного кода на C ++ можно найти по адресу http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html.

Подземье
источник
Спасибо, Подземье. Я буду смотреть дальше в CGAL. Но требование, чтобы пересчет не был дорогим, когда меняются данные моей карты, является трудностью.
sje397
CGAL довольно быстр - вычисление на лету должно быть возможным. В противном случае вы могли бы взглянуть на так называемые «кинетические структуры данных»: cgal.org/Manual/3.3/doc_html/cgal_manual/…
julien
«Скелет» - это еще один термин для МАТ. Поиски «преобразования медиальной оси» дали больше и лучше хитов, чем поиски по «скелету» в моем опыте.
whuber
«скелет» кажется более общим - MAT - это только один конкретный алгоритм для скелета, верно? Как бы то ни было, это не тема ...!
Жюльен
Лицензия на CGAL выглядит ограниченно (т.е. дорого - это коммерческое программное обеспечение).
sje397