Существует ли эффективный алгоритм для создания 2D вогнутой оболочки?
Имея набор (2D) точек из файла ГИС (карта города), мне нужно сгенерировать многоугольник, который определяет "контур" для этой карты (ее границы). Его входными параметрами будут заданные точки и "максимальная длина ребра". Затем он выведет соответствующий (возможно, невыпуклый) многоугольник.
Наилучшее решение, которое я нашел до сих пор, состояло в том, чтобы сгенерировать треугольники Делоне, а затем удалить внешние ребра, длина которых превышает максимальную длину ребра. После того, как все внешние ребра короче этого, я просто удаляю внутренние ребра и получаю нужный полигон. Проблема в том, что это очень много времени, и мне интересно, есть ли лучший способ.
10 ответов
Эта статья обсуждает Эффективную генерацию простых многоугольников для характеристики формы набора точек на плоскости и предоставляет алгоритм. Здесь также есть Java-апплет, использующий тот же алгоритм.
Один из бывших студентов нашей лаборатории использовал некоторые подходящие методы для своей докторской диссертации. Я полагаю, что один из них называется "альфа-формы" и упоминается в следующей статье:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
Эта статья дает некоторые дополнительные ссылки, которые вы можете следовать.
Ребята здесь утверждают, что разработали подход ближайших соседей к определению вогнутой оболочки набора точек, который ведет себя "почти линейно по количеству точек". К сожалению, их бумага, кажется, очень хорошо охраняется, и вам придется попросить их об этом.
Вот хороший набор ссылок, который включает в себя вышеупомянутое и может привести вас к поиску лучшего подхода.
Ответ может все еще быть интересным для кого-то еще: можно применить вариант алгоритма марширующих квадратов, примененный (1) внутри вогнутого корпуса, и (2) затем на (например, 3) различных масштабах, которые могут зависеть от средней плотности точки. Шкалы должны быть кратными друг другу, поэтому вы строите сетку, которую вы можете использовать для эффективной выборки. Это позволяет быстро находить пустые выборки = квадраты, выборки, которые полностью находятся в "кластере / облаке" точек, и те, которые находятся между ними. Последняя категория затем может быть легко использована для определения ломаной линии, которая представляет собой часть вогнутой оболочки.
В этом подходе все является линейным, триангуляция не требуется, он не использует альфа-формы и отличается от коммерческого / запатентованного предложения, как описано здесь ( http://www.concavehull.com/)
Интерактивный SDK Bing Maps V8 имеет вогнутую опцию корпуса в рамках расширенных операций с фигурами.
В ArcGIS 10.5.1 расширение 3D Analyst имеет инструмент Minimum Bounding Volume с типами геометрии вогнутой оболочки, сферы, огибающей или выпуклой оболочки. Может использоваться на любом уровне лицензии.
Здесь есть вогнутый алгоритм корпуса: https://github.com/mapbox/concaveman
Вы можете сделать это в QGIS с помощью этого плагина; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
В зависимости от того, как вам это нужно для взаимодействия с вашими данными, вероятно, стоит проверить, как это было сделано здесь.
Быстрое приближенное решение (также полезное для выпуклых корпусов) состоит в том, чтобы найти северную и южную границы для каждого небольшого элемента восток-запад.
На основе того, сколько деталей вы хотите, создайте массив фиксированных размеров верхних / нижних границ. Для каждой точки рассчитайте, в каком столбце EW она находится, а затем обновите верхнюю / нижнюю границы для этого столбца. После обработки всех точек вы можете интерполировать верхние / нижние точки для тех столбцов, которые пропустили.
Также стоит заранее сделать быструю проверку для очень длинных тонких форм и выбрать более подходящую для корзины NS или Ew.
Хороший вопрос! Я не пробовал это вообще, но мой первый выстрел был бы таким итеративным методом:
- Создайте набор N ("не содержится") и добавьте все точки в вашем наборе к N.
- Выберите 3 точки из N случайно, чтобы сформировать начальный многоугольник P. Удалите их из N.
- Используйте некоторый алгоритм точка-полигон и посмотрите на точки в N. Для каждой точки в N, если она теперь содержится в P, удалите ее из N. Как только вы найдете точку в N, которая все еще не содержится в P, перейдите к шагу 4. Если N становится пустым, все готово.
- Назовите точку, которую вы нашли A. Найдите линию в P, ближайшую к A, и добавьте A в середине.
- Вернитесь к шагу 3
Я думаю, что это будет работать до тех пор, пока он работает достаточно хорошо - может помочь хорошая эвристика для ваших начальных 3 баллов.
Удачи!
PostGIS начинается с выпуклой оболочки, а затем пропускает ее, вы можете увидеть ее здесь.
Простое решение - пройтись по краю многоугольника. При заданном текущем ребре на границе, соединяющей точки P0 и P1, следующей точкой на границе P2 будет точка с наименьшим возможным A, где
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Затем вы установите
P0 <- P1
P1 <- P2
и повторяйте, пока не вернетесь туда, откуда начали.
Это все еще O(N^2), так что вы захотите немного отсортировать свой список. Вы можете ограничить набор точек, которые необходимо учитывать на каждой итерации, если вы сортируете точки, скажем, по их отношению к центроиду города.