Объединение ближайших выпуклых полигонов

Question

У меня есть массив pointclouds (кластер точек, которые, как было определено, находятся в их собственной области).

Цель состоит в том, чтобы объединить эти отдельные кластеры, которые являются либо

я. Пересечение

ii. В пределах некоторого минимального расстояния от eachother

Проверка ii затрудняет это. Чтобы быстро справиться с этим pointcloud, я создаю AABB (выровненные по оси рамки, которые выравниваются вдоль оси X).

Мой текущий метод использовать некоторые свойства разделительного оси теоремы:

1. Создать AABB для каждого PointCloud
2. Для каждого AABB, проверьте, если они накладываются друг на друга, проецируя их на случайной оси, а затем сортируя эти линейные проекции, где они попадают на эту строку o (nlog (n)). Затем я просматриваю этот список, чтобы проверить пересечения O (N) с помощью SAT. Большинство линейных проекций AABB не перекрываются и, следовательно, не пересекаются, и те, которые я могу проверить вручную (потому что отсутствие перекрытия в 1D не гарантирует пересечения, но обратное неверно).

Последняя часть, где я застреваю. Вышеупомянутая 1D-проекция была выполнена для того, чтобы избежать взаимных проверок O (n^2) для пересечений. Но для того, чтобы объединить выпуклые многоугольники, которые находятся в пределах определенного порога, но НЕ пересекаются, я не вижу пути по локальной проверке (N^2).

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

Если вы используете мои шаги от 1 & 2, вы можете предположить, что оставшиеся pointclouds/AABB НЕ пересекаются.

EDIT

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

Answer 1

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

Для порога расстояния минимальное расстояние от AABB со всех сторон должно гарантировать, что пересечение было A/2. Это фиксирует все случаи, когда AABB разделены только в направлении x или y (для диагонального корпуса требуется A * sqrt (2)/4)

Answer 2

Я думаю, что проблема поиска пересекающихся ящиков для заданного набора пересекающихся ящиков называемое «пространственное соединение». Существуют специальные алгоритмы, такие как TOUCH. Однако я обнаружил, что простое повторение через поля и проверка на перекрытие весьма эффективно, если вы используете пространственный индекс. Это означает, что для каждого из полей вы запрашиваете пространственный индекс для пересекающихся ящиков. Классически для этого можно использовать R-Tree или X-Tree.

Лично я получил очень хорошие результаты с помощью PH-Tree (моя собственная реализация Java), например, с наборами данных размером около 1200 000 3D-боксов (6000 пересекающихся ящиков), загрузка индекса и выполнение запросов занимает в общей сложности около 6 секунд на настольный компьютер.

EDIT

Я не уверен, о сложности, но это, кажется, ниже О (п * § п).