Существует ли эффективный алгоритм для создания двумерного вогнутого корпуса?

Имея набор (2D) точек из файла ГИС (карта города), мне нужно сгенерировать полигон, который определяет "контур" для этого отображения (его границы). Его входными параметрами были бы установленные точки и "максимальная длина края". Затем он выведет соответствующий (вероятно, невыпуклый) многоугольник.

Лучшим решением, которое я нашел до сих пор, было создание треугольников Delaunay, а затем удаление внешних краев, длина которых больше максимальной длины. После того, как все внешние края короче этого, я просто удаляю внутренние ребра и получаю нужный многоугольник. Проблема в том, что это очень трудоемко, и мне интересно, есть ли лучший способ.

Ответ 1

В этом документе обсуждается Эффективная генерация простых многоугольников для характеристики формы множества точек на плоскости и обеспечивает алгоритм. Там также апплет Java, использующий тот же алгоритм здесь.

Ответ 2

Один из бывших учеников нашей лаборатории использовал некоторые применимые методы для своей докторской диссертации. Я считаю, что один из них называется "альфа-формы" и упоминается в следующей статье:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

В этой статье приводятся некоторые дополнительные ссылки, которые вы можете следовать.

Ответ 3

Ребята здесь утверждают, что разработали подход ближайших соседей ak для определения вогнутого корпуса набора точек, который ведет себя почти линейно на количество точек ". К сожалению, их бумага, кажется, очень хорошо охраняется, и вам нужно будет спросить для нее.

Здесь хороший набор ссылок, который включает вышеизложенное и может привести к тому, что вы найдете лучший подход.

Ответ 4

Ответ может быть интересным для кого-то еще: можно применить вариацию алгоритма маршевого квадрата, применяемого (1) внутри вогнутого корпуса, и (2) затем включить (например, 3) разные шкалы, которые зависят от средней плотности точек. Масштабы должны быть кратными друг другу, поэтому вы создаете сетку, которую вы можете использовать для эффективной выборки. Это позволяет быстро найти пустые образцы = квадраты, образцы, которые полностью находятся в "кластере/облаке" точек, и те, которые находятся между ними. Последняя категория затем может быть использована, чтобы легко определить полилинию, представляющую часть вогнутого корпуса.

В этом подходе все линейно, не требуется триангуляция, он не использует альфа-формы и отличается от коммерческого/запатентованного предложения, как описано здесь (http://www.concavehull.com/)

Ответ 5

Хороший вопрос! Я не пробовал это вообще, но первым моим выстрелом был бы этот итеративный метод:

Создайте набор N ( "не содержащий" ) и добавьте все точки в вашем наборе в N.
Выберите 3 точки из N в случайном порядке, чтобы сформировать исходный многоугольник P. Удалите их из N.
Используйте некоторый алгоритм с точки в полигоне и посмотрите точки в N. Для каждой точки в N, если она теперь содержится в P, удалите его из N. Как только вы найдете точку в N, которая все еще не содержится в P, переходите к шагу 4. Если N становится пустым, все готово.
Вызовите точку, которую вы нашли A. Найдите строку в P, ближайшую к A, и добавьте A в середину.
Вернитесь к шагу 3

Я думаю, что он будет работать до тех пор, пока он будет работать достаточно хорошо - хорошая эвристика для ваших начальных 3 баллов может помочь.

Удачи!

Ответ 6

Простым решением является прогулка по краю многоугольника. Учитывая текущий край ограничных соединяющих точек 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), поэтому вы хотите немного отсортировать свой список. Вы можете ограничить множество точек, которые необходимо учитывать на каждой итерации, если вы сортируете точки, скажем, их опоры из центра города.

Ответ 7

Вы можете сделать это в QGIS с этим подключением; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

В зависимости от того, как вам нужно взаимодействовать с вашими данными, возможно, стоит проверить, как это было сделано здесь.

Ответ 8

Как дико принятая ссылка, PostGIS начинается с выпуклой оболочки, а затем пещера ее, вы можете увидеть ее здесь.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

Ответ 9

Интерактивный SDK Bing Maps V8 имеет вогнутый корпус в расширенных операциях формы.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

В ArcGIS 10.5.1 расширение 3D Analyst имеет инструмент Minimum Bounding Volume с геометрическими типами вогнутого корпуса, сферы, оболочки или выпуклого корпуса. Он может использоваться на любом уровне лицензии.

Здесь есть алгоритм вогнутого корпуса: https://github.com/mapbox/concaveman

Ответ 10

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

В зависимости от того, сколько деталей вы хотите, создайте массив фиксированного размера верхних/нижних границ. Для каждой точки вычислите, в каком столбце E-W она находится, а затем обновите верхнюю/нижнюю границы для этого столбца. После обработки всех точек вы можете интерполировать верхние/нижние точки для пропущенных столбцов.

Также стоит сделать быструю проверку заранее для очень длинных тонких фигур и принятия решения о загрузке NS NS или Ew.