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

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

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

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

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

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

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

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

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

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

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

  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 имеет инструмент Minimum Bounding Volume с геометрическими типами вогнутого корпуса, сферы, оболочки или выпуклого корпуса. Он может использоваться на любом уровне лицензии.

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

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

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

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

  • синусоидальной волны, которая медленно увеличивает частоту от f1 до f2 в течение заданного времени
  • Interesting Posts

    Попытка создания JTable с правильным заголовком строки

    Когда клиент Apache Kafka выдает исключение «Batch Expired»?

    sizeof class с int, функцией, виртуальной функцией в C ++?

    Как использовать веб-службу WCF через URL-адрес во время выполнения?

    Высокое потребление памяти с помощью Enumerable.Range?

    Значения по умолчанию в C Struct

    Целочисленное значение в TextView

    Ссылки ниже сайта в google search

    Лучший способ проверить, работает ли iPhone приложение в первый раз

    Когда рекомендуется использовать strdup (vs malloc / strcpy)

    Скопируйте все установленные программы и файлы на жесткий диск (который имеет 32-битную Windows 7) и клонируйте / перенесите его на другой компьютер с 64-разрядной версией Windows 7

    Запретить увольнение UIAlertController

    Функция PostgreSQL для последнего вставленного идентификатора

    Сохранение карты с использованием JPA

    Использование wget для рекурсивного извлечения каталога с произвольными файлами в нем

    Давайте будем гением компьютера.