Вопрос по computational-geometry, algorithm, polygon, geometry, gis –  можно адаптировать для этой цели - пропустив удаление треугольников, которые бы уменьшили площадь.

33

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

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

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

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

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

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

Я имею в виду, что получающийся многоугольник должен иметь меньше вершин, ноплощадь он должен содержать все вершины, которые были в подробном многоугольнике. Благодарю. mbrenig
Должен ли окончательный набор вершин быть частью исходного набора, или вы можете подделать набор «новых» и разных вершин? Dr. belisarius
Меня смущает это предложение: «Я ищу алгоритм, который упростит и сгладит многоугольник (уменьшая количество вершин) с ограничением на то, что результирующий многоугольник должен содержать все вершины подробного многоугольника». Как вы уменьшаете количество вершин, но сохраняете их все? Merlyn Morgan-Graham
Является ли производительность проблемой здесь? Dr. belisarius
Если бы новый многоугольник имел совершенно разные вершины с подробным многоугольником, это было бы хорошо, если бы ребра нового многоугольника не слишком далеко от исходных ребер. например Я не хочу выпуклый корпус или гигантский круг, содержащий оригинальный многоугольник. mbrenig

Ваш Ответ

5   ответов
0

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

18

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

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

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

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

Образцы:

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

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

НТН!

Благодарю. Это выглядит очень многообещающе. Я хотел бы реализовать это сам, так что придется посмотреть, смогу ли я получить эту бумагу. Планируй работать в эту субботу - буду держать тебя в курсе mbrenig
@mbrenig Если у вас есть пользователь ACM, я думаю, что вы можете получить бумагу там. Кроме того, я уверен, что вы сможете найти похожие статьи в сети, если авторы не ответят на ваш запрос. Удачи! Dr. belisarius
1

но вот эта идея с головы до головы ... извиняюсь, если это не имеет смысла или не сработает :)

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

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

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

Вот что я имел в виду:docs.google.com/drawings/..., Кажется, что после 1 уровня мы получаем больше деталей с результатом, становящимся вогнутым, но я не уверен, что произойдет, если мы повторим шаги 3 и 4, разрезая каждый маленький корпус. Gromix
@mbrenig - Вы когда-нибудь выясняли ответ? У меня есть связанный вопрос @gis.stackexchange.com/questions/31354/... GeorgeC
Спасибо! Я не думаю, что правильно понимаю пункты (3) или (4). Но даже в этом случае, если у меня выпуклая оболочка, и я возьму некоторое пересечение (с исходным многоугольником), чтобы сделать его вогнутым ... когда вы снова сделаете его выпуклым на шаге (4) - не закончите ли вы тем же выпуклым корпусом ты начал с? mbrenig
Это также, вероятно, будет работать лучше всего, если у вас есть небольшие ступенчатые линии (сглаженные путем создания корпусов) и крупные выдавливания (уточненные путем разрезания корпусов). Я не уверен в результатах на скриншоте, который вы добавили. Gromix
Возможно, вогнутый корпус будет лучшим вариантом, чем выпуклый?gis.stackexchange.com/questions/1200/... radek
0

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

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

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

1

мне нужно было надувать упрощение полигонов.

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

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

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

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

Похожие вопросы