Существует ли эффективный алгоритм создания двумерной вогнутой оболочки?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Имея набор (2D) точек из файла ГИС (карты города), мне нужно создать многоугольник, который определяет «контур» этой карты (ее границу).Его входными параметрами будут набор точек и «максимальная длина ребра».Затем он выведет соответствующий (вероятно, невыпуклый) многоугольник.
Лучшим решением, которое я нашел на данный момент, было создание треугольников Делоне, а затем удаление внешних ребер, длина которых превышает максимальную длину ребра.После того, как все внешние ребра стали короче, я просто удаляю внутренние ребра и получаю нужный многоугольник.Проблема в том, что это отнимает очень много времени, и мне интересно, есть ли лучший способ.
Другие советы
Один из бывших студентов нашей лаборатории использовал некоторые применимые методы для своей докторской диссертации.Я считаю, что один из них называется «альфа-формы» и упоминается в следующей статье:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
В этом документе приведены некоторые дополнительные ссылки, которым вы можете следовать.
Парни здесь утверждают, что разработали подход k ближайших соседей для определения вогнутой оболочки набора точек, который ведет себя «почти линейно в зависимости от количества точек».К сожалению, их газета, похоже, очень хорошо охраняется, и вам придется спросить. их для этого.
Вот хороший набор ссылок это включает в себя вышеизложенное и может привести вас к поиску лучшего подхода.
Ответ может быть интересен кому-то еще:Можно применить вариант алгоритма марширующего каре, применяется (1) внутри вогнутой оболочки и (2) затем (например,3) разные Весы что это зависит от средней плотности точек.Масштабы должны быть кратными друг другу, чтобы вы могли построить сетку, которую можно использовать для эффективной выборки.Это позволяет быстро найти пустые сэмплы=квадраты, семплы, полностью находящиеся в «кластере/облаке» точек, и те, что находятся между ними.Последнюю категорию затем можно использовать для легкого определения ломаной линии, которая представляет собой часть вогнутого корпуса.
В этом подходе все линейно, триангуляция не требуется, он не использует альфа-формы и отличается от коммерческого/запатентованного предложения, описанного здесь ( http://www.concavehull.com/ )
Простое решение — обойти край многоугольника.Учитывая текущее ребро границы, соединяющей точки 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), поэтому вам нужно немного отсортировать свой список точек.Вы можете ограничить набор точек, которые необходимо учитывать на каждой итерации, если сортируете точки, скажем, по их направлению от центроида города.
Хороший вопрос!Я вообще это не пробовал, но первым делом я бы попробовал этот итеративный метод:
- Создайте набор N («не содержится») и добавьте все точки из вашего набора в N.
- Выберите случайным образом 3 точки из N, чтобы сформировать исходный многоугольник P.Удалить их из Н.
- Использовать некоторый алгоритм «точка в многоугольнике» и посмотрите на точки в N.Для каждой точки в N, если она теперь содержится в P, удалите ее из N.Как только вы найдете точку в N, которая еще не содержится в P, переходите к шагу 4.Если N станет пустым, все готово.
- Назовите точку, которую вы нашли А.Найдите строку в P, ближайшую к A, и добавьте A в ее середину.
- Вернитесь к шагу 3
Я думаю, что это будет работать, пока оно работает достаточно хорошо — хорошая эвристика для ваших первоначальных трех баллов может помочь.
Удачи!
Вы можете сделать это в QGIS с помощью этого плагина;https://github.com/detlevn/QGIS-ConcaveHull-Plugin
В зависимости от того, как вам нужно взаимодействовать с вашими данными, вероятно, стоит посмотреть, как это было сделано здесь.
Интерактивный SDK Bing Maps V8 имеет опцию вогнутой оболочки в расширенных операциях с фигурами.
В ArcGIS 10.5.1 расширение 3D Analyst имеет инструмент «Минимальный ограничивающий объем» с типами геометрии: вогнутая оболочка, сфера, оболочка или выпуклая оболочка.Его можно использовать на любом уровне лицензии.
Здесь есть алгоритм вогнутой оболочки: https://github.com/mapbox/concaveman
Быстрое приближенное решение (также полезное для выпуклых оболочек) — найти северную и южную границы для каждого небольшого элемента с востока на запад.
В зависимости от желаемой детализации создайте массив верхних/нижних границ фиксированного размера.Для каждой точки вычислите, в каком столбце E-W она находится, а затем обновите верхнюю/нижнюю границу для этого столбца.После того, как вы обработали все точки, вы можете интерполировать верхние/нижние точки для тех столбцов, которые пропущены.
Также стоит заранее быстро проверить очень длинные тонкие формы и решить, следует ли сортировать NS или Ew.
В качестве широко распространенного эталона PostGIS начинается с выпуклой оболочки, а затем прогибается, вы можете увидеть это здесь.
