Есть ли эффективный алгоритм для создания 2D вогнутого корпуса?
Имея набор (2D) точек из файла ГИС (карта города), мне нужно сгенерировать многоугольник, определяющий «контур» этой карты (ее границу). Его входными параметрами будут набор точек и «максимальная длина кромки». Затем он выведет соответствующий (возможно, невыпуклый) многоугольник.
Лучшим решением, которое я нашел до сих пор, было создание треугольников Делоне, а затем удаление внешних ребер, которые длиннее максимальной длины ребра. После того, как все внешние ребра будут короче, я просто удаляю внутренние ребра и получаю нужный многоугольник. Проблема в том, что это занимает очень много времени, и мне интересно, есть ли способ лучше.
Да, у меня есть файл ГИС, но мне нужно написать алгоритм (возможно, на C или C++), он должен быть помещен в уже существующую программу, и для этого не следует использовать внешние инструменты (например, ArcGIS), это должен быть самодостаточным.
На самом деле, я не думаю, что у ArcGIS есть встроенный алгоритм, позволяющий делать то, что он хочет. ArcGIS может создавать выпуклые оболочки, но вогнутые намного сложнее.
Не могли бы вы более точно определить вашу проблему? :) С 5 баллами: 4 угла квадрата и его центр. Какой была бы ваша граница? Если ваша максимальная длина края позволяла центр, совершенно произвольно, какой из 4 краев квадрата вы бы «согнули», чтобы включить среднюю точку.
В приведенном вами примере ответом всегда будет квадрат. Как правило, учитывая каждую точку и расстояния до двух ближайших других точек, вы можете предположить, что максимальная длина ребра никогда не будет меньше второй, поэтому никогда не должно быть «осиротевших» точек.
@Fabio Ceconello - Вы когда-нибудь реализовывали алгоритм для этого?
Да, именно так, как я упомянул в вопросе (с треугольниками Делоне). Позже я немного поработал над концепцией альфа-форм, указанной ниже nsanders, но прежде чем я заставил ее работать, приоритет проблемы был понижен, и я перешел к другой.
Делоне имеет правильную сложность (O (n log n)). Сомневаюсь, что асимптотически вы сможете добиться большего.
Вы приняли ответ всего через 9 лет!
@peterh Я сразу принял ответ, но позже по какой-то причине он был удален, поэтому, когда я заметил, что принял другой ответ, это было бы моим «вторым лучшим».
@peterh Я считаю, что не следует принимать ответ, пока кто-то не предоставит правильный код. Если Фабио опубликует хотя бы фрагмент своего кода, я бы проголосовал за его любой из этих ответов и проголосовал бы против всех остальных, чтобы переместить его вверх по списку.
Кроме того, я смущен вашим решением. Вам приходилось вручную удалять края или ваше решение было автоматическим? (т.е. код решил все от начала до конца) По крайней мере, похоже, что вы должны были выбрать «максимальную длину края» методом проб и ошибок, а не каким-либо алгоритмическим способом.
@peterh думает об этом, я думаю, ты прав, я оставлю это без принятого ответа. Что касается фрагмента, мне придется вернуться к некоторому старому коду, и я даже не помню, насколько маленьким (или большим) будет такой фрагмент и сколько мне придется отредактировать, чтобы сделать его понятным. Если есть возможность, выложу.
@frank Это не было вручную, это было частью автоматизированного инструмента для обработки карт для приложения GPS-навигации. В моем конкретном случае это было действительно произвольно - точки были углами улиц, а полученный многоугольник был контуром города. Я использовал произвольное значение, которое дало бы мне достаточно подробный многоугольник, который не был бы слишком тяжелым для рендеринга. Я думаю, что так и должно быть, вы должны определить максимальную длину в соответствии с потребностями вашего приложения - я не понимаю, как вы могли бы заранее рассчитать ее автоматически.
@FabioCeconello Нет! Если ответ отвечает на вопрос, примите его! Я был так счастлив, что нашел самый длинный принятый вопрос, я не хотел, чтобы вы его отклонили!
Ответы 10
Один из бывших студентов нашей лаборатории использовал некоторые применимые методы для своей кандидатской диссертации. Я считаю, что одна из них называется «альфа-формы» и упоминается в следующей статье:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
В этой статье даются некоторые дальнейшие ссылки, за которыми вы можете следовать.
Альфа-формы основаны на триангуляции Делоне, поэтому обязательно потребуется одно вычисление триангуляции Делоне.
Мне кажется, альфа-формы - это всего лишь концепция.
Быстрое приближенное решение (также полезно для выпуклой оболочки) - найти северные и южные границы для каждого небольшого элемента с востока на запад.
В зависимости от того, сколько деталей вы хотите, создайте массив фиксированного размера верхней / нижней границ. Для каждой точки вычислите, в каком столбце E-W она находится, а затем обновите верхнюю / нижнюю границы для этого столбца. После обработки всех точек вы можете интерполировать верхнюю / нижнюю точки для тех столбцов, которые пропущены.
Также стоит заранее сделать быструю проверку на очень длинные тонкие формы и решить, следует ли использовать бункер NS или Ew.
Хороший вопрос! Я вообще этого не пробовал, но первым делом я хотел бы воспользоваться этим итеративным методом:
- Создайте набор N («не содержится») и добавьте все точки в вашем наборе к N.
- Выберите 3 точки из N случайным образом, чтобы сформировать начальный многоугольник P. Удалите их из N.
- Используйте некоторый алгоритм точки в многоугольнике и посмотрите на точки в N. Для каждой точки в N, если она теперь содержится в P, удалите ее из N. Как только вы найдете точку в N, которая все еще не содержится в P, переходите к шагу 4. Если N становится пустым, все готово.
- Назовите найденную точку A. Найдите линию в P, ближайшую к A, и добавьте A в ее середину.
- Вернитесь к шагу 3
Я думаю, что это будет работать, если оно работает достаточно хорошо - может помочь хорошая эвристика для ваших начальных 3 баллов.
Удачи!
Ребята из здесь утверждают, что разработали подход k ближайших соседей для определения вогнутой оболочки набора точек, который ведет себя «почти линейно в зависимости от количества точек». К сожалению, их газета, кажется, очень хорошо охраняется, и вам придется попросить об этом их.
Вот хороший набор ссылок, который включает вышеупомянутое и может помочь вам найти лучший подход.
Похоже, это и есть статья, о которой идет речь: repositorium.sdum.uminho.pt/bitstream/1822/6429/1/… Идея исключительно умная и простая - это просто прямая модификация техники сканирования Грэма для выпуклых нулей, насколько я понимаю. Нет необходимости искать триангуляцию Делоне и т. д.
Упомянутое название статьи - «Вогнутая оболочка: подход k-ближайших соседей для вычисления области, занятой набором точек». Он доступен здесь: repositorium.sdum.uminho.pt/handle/1822/6429
Простое решение - обойти край многоугольника. Учитывая текущее ребро на границе, соединяющей точки 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) внутри вогнутой оболочки и (2) затем (например, 3) к другому напольные весы, который зависит от средней плотности точек. Масштабы должны быть кратными друг другу, например, вы создаете сетку, которую можете использовать для эффективной выборки. Это позволяет быстро находить пустые сэмплы = квадраты, сэмплы, полностью попадающие в «кластер / облако» точек, и те, которые находятся между ними. Последнюю категорию затем можно использовать для простого определения ломаной линии, которая представляет собой часть вогнутого корпуса.
В этом подходе все линейно, триангуляция не требуется, он не использует альфа-формы и отличается от коммерческого / запатентованного предложения, описанного здесь (http://www.concavehull.com/)
В документе Этот обсуждается Эффективное создание простых многоугольников для описания формы набора точек на плоскости. и приводится алгоритм. Также существует Java-апплет, использующий тот же алгоритм здесь.
Ссылка мертва. Исходный код Java, похоже, находится в ambientspatial.net/ddo/?p=143
Вы можете сделать это в QGIS с помощью этого плагина; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
В зависимости от того, как вам нужно взаимодействовать с вашими данными, возможно, стоит проверить, как это было сделано здесь.
Как широко распространенная ссылка, PostGIS начинается с выпуклой оболочки, а затем прогибается, вы можете увидеть это здесь.
В интерактивном SDK Bing Maps V8 есть опция вогнутого корпуса в расширенных операциях с фигурами.
В ArcGIS 10.5.1 дополнительный модуль 3D Analyst имеет инструмент Минимальный ограничивающий объем с геометрическими типами вогнутой оболочки, сферы, оболочки или выпуклой оболочки. Его можно использовать на любом уровне лицензии.
Здесь есть алгоритм вогнутой оболочки: https://github.com/mapbox/concaveman
Вы говорите, что у вас есть файл ГИС - разве вы не используете картографическое приложение / программное обеспечение ГИС? Я знаю, что сервер ArcGIS с радостью использует любое количество точек и построит карту, наложенную на получившийся многоугольник.