Идентификация исходного ребра объединяющего многоугольника

Question

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

Существует ли эффективный способ узнать для каждого ребра этого большого гигантского объединенного многоугольника, какой из них принадлежит какому ребру меньшего многоугольника?

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

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

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

Скриншот этого приведен ниже:

Answer 1

Вот одно из решений.

Возьмите каждый оригинальный край. Они могут быть (более) определены 3 вещами:

1. Вектор, указывающий направление
2. Начальная точка
3. Конечная точка

Первым шагом является нормализация векторов (например, умножение на скаляр так, чтобы большее абсолютное значение x и y было 1). Затем сохраните все свои ребра в хеш, ключи которого являются этими векторами, а значения - массив ребер с этим вектором. (Если у вас есть много ребер, вы можете рассмотреть возможность использования дерева интервалов для ребер.)

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

Обратите внимание, что хотя это решение позволит вам довольно эффективно находить случаи, когда ребро проходит вдоль границы, оно будет пропускать случаи, когда многоугольник только касается границы объединенного многоугольника в одном углу. Надеюсь, это не имеет значения для вас.

Answer 2

Поскольку наивный подход не работает из-за появления новых ребер и вершин в объединении (см. Старый ответ и комментарии), нам потребуется использовать более сложную структуру данных.

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

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

INPUT: край выходного многоугольника E1 с конечными точками V1 и V2.

ВЫХОД: ребро из входных полигонов, где оба ребра V1 и V2 находятся на ребре.

• Получить набор ребер из входного набора, ограничивающие прямоугольники которого содержат как V1, так и V2 (или, другими словами, ограничивающий прямоугольник, образованный V1, V2)
• Поиск грубой силы для ребра, на котором лежат оба V1 и V2.

Второй шаг очевиден. Есть несколько мест, чтобы посмотреть на первое. Дерево K-D (объемный объект) выглядит так, как будто бы оно решило проблему. Или, может быть, R-дерево. Также проверьте stackoverflow для похожих вопросов . К сожалению, я не очень разбираюсь в пространственных алгоритмах, чтобы предложить подходящий.

---

СТАРЫЙ ОТВЕТ:

Я не думаю, что вам нужны какие-то причудливые структуры данных для обработки дела. Я предполагаю, что координаты вершин в объединении идентичны координатам в вашем исходном наборе. Таким образом, вы можете сделать что-то вроде: создать список вершин для ваших входных данных, где каждая вершина записывает полигон (ы), которому она принадлежит. Сделайте их легко доступными для поиска: наивным подходом будет отсортировать их сначала по одной координате, а затем по другой. Таким образом, вы можете найти любую вершину в O (log n).

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

Окончательной оптимизацией является предварительный расчет: просто запустите приведенный выше алгоритм и запишите результаты для каждого ребра, а затем избавьтесь от всех таблиц вершин и ребер. Если вам не нужна предварительно вычисленная таблица, вы можете отфильтровать исходный набор вершин для вершин, которые не отображаются в объединении.

Answer 3

Вы можете сделать BSP или более бетон quadtree , с ребрами полигонов. Для каждого ребра помните, в каком полигоне (ах) он используется.

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

Позволяет иметь n ребер в исходных многоугольниках и m ребер в выходном многоугольнике. Для создания дерева O(n log n) необходимо и для поиска перекрытия ребер O(m log n) необходимо. Всего O((m+n)*log n).

Примечание: если целое ребро используется в 2 начальных полигонах, то оно не находится на границе выходного полигона. При этом вы можете удалить дублированные края из дерева квадрантов. Не обязательно.

Можно сделать это по-другому. Создайте четверку выходных ребер многоугольника и найдите каждое ребро начальных многоугольников. Время работы составляет O((m+n)*log m), что быстрее. Но с верхним подходом вы можете извлечь больше информации из входных полигонов, если она понадобится вам в будущем.