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

Question

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

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

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

• Я нашелалгоритм Рамера-Дугласа-Пекера, который уменьшит количество вершин - но полученный многоугольник не будет содержать все вершины исходного многоугольника.См. Эту статью Ramer-Douglas-Peucker в Википедии

• Я рассмотрел расширение многоугольника (я полагаю, это также известно как смещение внешнего многоугольника).Я нашел следующие вопросы: Расширение многоугольника (только выпуклое) и Раздувание многоугольника .Но я не думаю, что это существенно уменьшит детализацию моего многоугольника.

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

Answer 1

Редактировать

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

---

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

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

Образцы:

Здесь Вы можете запросить копию статьи,

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

НТН!

Answer 2

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

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

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

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

Фактически, после более пристального взгляда, эта идея похожа на идею Висвалингама с приспособлением для удаления кромок.

Answer 3

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

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

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

Похоже, это может сделать работу?

Answer 4

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

Answer 5

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

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

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