Упрощенные (или гладкие) полигоны, содержащие исходный подробный полигон

У меня есть подробный 2D-многоугольник (представляющий географическую область), который определяется очень большим набором вершин. Я ищу алгоритм, который упростит и сгладит многоугольник (уменьшив количество вершин) с ограничением на то, что область результирующего многоугольника должна содержать все вершины подробного многоугольника.

В контексте, здесь приведен пример края одного сложного многоугольника:

Мои исследования:

Я нашел алгоритм Рамера-Дугласа-Пьюкера, который уменьшит количество вершин, но полученный многоугольник не будет содержать все исходные вершины многоугольника. См. Эту статью Рамер-Дуглас-Пьюкер в Википедии
Я рассмотрел вопрос о расширении многоугольника (я считаю, что это также известно как смещение наружного полигона). Я нашел следующие вопросы: Расширение полигона (только выпуклое) и Раздувание многоугольника. Но я не думаю, что это существенно уменьшит детали моего полигона.

Спасибо за любой совет, который вы можете мне дать!

Ответ 1

Изменить

По состоянию на 2013 год большинство ссылок ниже не функционируют. Тем не менее, я нашел цитируемый документ, включенный алгоритм, все еще доступный на этом (очень медленном) сервере.

Здесь вы можете найти проект, который касается именно ваших проблем. Хотя он работает в основном с областью, "заполненной" точками, вы можете настроить ее на работу с определением типа "периметр" как ваше.

Он использует подход k-ближайших соседей для вычисления области.

Образцы:

Здесь вы можете запросить копию документа.

По-видимому, они планировали предлагать онлайн-сервис для запроса расчетов, но я не тестировал его, и вероятно, он не работает.

НТН!

Ответ 2

Это интересная проблема! Я никогда не пробовал ничего подобного, но вот идея от головы... извиняюсь, если это не имеет смысла или не будет работать:)

Вычислить выпуклую оболочку, которая может быть слишком большой/неточной
Разделите корпус на N срезов, например, соединяя каждую из вершин корпуса с центром
Вычислите пересечение вашего объекта с каждым фрагментом
Повторите рекурсивно для каждого пересечения (вычисление оболочки пересечения и т.д.)

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

Звучит ли это так, как будто это может сработать?

Ответ 3

У меня была очень похожая проблема: мне нужно раздувное упрощение полигонов.

Я сделал простой алгоритм, удалив точку concav (это увеличит размер полигона) или удалит выпуклый край (между 2 выпуклыми точками) и продолжит смежные ребра. В любом случае выполнение одной из этих двух возможностей приведет к удалению одной точки на многоугольнике.

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

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

На самом деле, после более пристального изучения это аналогичная идея, чем та, которая относится к Visvalingam с адаптацией для удаления края.

Ответ 4

В какой-то степени я не уверен, что вы пытаетесь сделать, но, похоже, у вас есть два очень хороших ответа. Один из них - Рамер-Дуглас-Пьюкер (ДП), а другой - альфа-форма (также называемая вогнутым корпусом, невыпуклым корпусом и т.д.). Я нашел более позднюю статью, описывающую альфа-формы и связав ее ниже.

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

http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf

Ответ 5

Я думаю, алгоритм Visvalingams может быть адаптирован для этой цели - пропуская удаление треугольников, которые уменьшат область.