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

Question

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

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

Answer 1

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

Answer 2

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

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

Этот документ дает некоторые дополнительные ссылки вы можете следовать.

Answer 3

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

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

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

Answer 4

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

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

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

Удачи вам!

Answer 5

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

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

Answer 6

Простым решением является прогулка по краю многоугольника.Учитывая текущее ребро О.М. линией, соединяющей точки P0 и P1, следующая точка на границе P2 будет точка с наименьшим А, где

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 7

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

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

Answer 8

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

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

Answer 9

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

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

Answer 10

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

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

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

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