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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

Интерактивный 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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

Удачи!

Answer 9

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

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

Answer 10

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

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

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