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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 баллов.

Удачи!

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

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

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

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

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

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

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

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