Структура данных / алгоритм объединения похожих объектов

Question

Требования:

Учитывая кучу отрезков в 2D-плоскости, мне нужно объединить все те, которые похожи или равны друг другу.

Например, если мне дали два отрезка (0, 0) - (1, 1) и (1, 1) - (2, 2). Эти две линии связаны и имеют одинаковый наклон. Таким образом, я могу просто объединить эти два в одну строку (0, 0) - (2, 2)

Для отрезков (0, 0) - (1, 1) и (1.01, 1) - (2, 2). Несмотря на то, что их наклоны немного отличаются и они не связаны, это не так хорошо видно человеческим глазам, поэтому я все равно слил бы эти два в (0, 0) - (2, 2) в обмен на производительность.

Для отрезков (0, 0) - (1, 1) и (0.5, 0.5) - (0.6, 0.6). Последнее является лишь частью первого, поэтому можно просто удалить последнее и сохранить только первое.

Очевидно, я могу сделать это жестоким способом O(n^2) но это занимает слишком много времени. Есть ли хороший алгоритм / структура данных, которая может помочь сократить время выполнения?

Попытка:
Дерево диапазона: это выглядит как естественное соответствие, поскольку оно поддерживает запрос диапазона (линии с одинаковым наклоном). Однако вставка / удаление не поддерживаются.

R-дерево: R-дерево поддерживает запросы к элементам, которые находятся рядом с помощью прямоугольника. Используя это, я мог сначала найти все линии, которые находятся внутри ограниченного прямоугольника, и отфильтровать те, которые имеют разность наклона> epsilon или distance> epsilon2. Однако я не могу найти хорошее описание реализации (поиск выглядит хорошо документированным, но вставка / удаление очень расплывчаты)

B tree: B tree выглядит многообещающе, но, похоже, мой вариант использования не является его основным использованием. Не уверен, что это будет правильный путь.

Answer 1

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

Чтобы вычислить проективные координаты для линии, содержащей (a, b) и (c, d), мывстроить конечные точки в проективное пространство как (a, b, 1) и (c, d, 1), а затем вычислить кросс-произведение .Дело в том, что с проективными координатами они не уникальны.Мое наивное предложение состояло бы в том, чтобы использовать единичную сферу в трехмерном пространстве в качестве покрывающего пространства путем нормализации относительно евклидовой нормы и дублирования точки на ее антиподе.

Другими словами, мы отображаем (a, b) - (c, d) в (x', y', z') и (-x', -y', -z'), где (x, y, z) = (b - d, c - a, ad - bc) и x' = x/sqrt(x^2+y^2+z^2) и y' = y/sqrt(x^2+y^2+z^2) и z' = z/sqrt(x^2+y^2+z^2).

Answer 2

Di, вы пробовали с алгоритмом линии развертки ? Вы можете найти / посчитать / обнаружить пересечения отрезков , что определенно звучит как ваш первый шаг (определите, есть ли пересечение, затем проверьте наклоны). Вы можете решить вашу проблему в O ((n + k) logn) (где k - количество пересечений), используя алгоритм Бентли-Оттмана . Вы в основном сортируете отрезки, а затем проводите плоскостью по линии в указанном порядке и останавливаетесь на каждом пересечении.

Еще одна вещь: вы можете рассчитать уклоны, затем вы можете отсортировать лексикографически, сначала по уклону, а затем по координате х (или проецируя на линию с таким уклоном, проходящим через точку 0), а затем обойти сегменты в этом порядок. Затем вы можете выполнить простую «линейную развертку», просто проверьте, как далеко находятся сегменты, и объединитесь. Вы можете добавить к уклону некоторую ошибку, поэтому вы также можете поместить похожие уклоны в один и тот же сегмент.

Answer 3

Проблема с отображением линий Ax + By + C = 0 в (A, B, C) состоит в том, что если два одинаковых отрезка линии с немного разными наклонами очень далеки от начала координат, различия между C становятся большими, что препятствует двум сегменты от кластеризации в один.

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

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

• Сегмент линии AB, бесконечно малый отрезок в A, бесконечно малый отрезок в B -> свойство равенства не выполняется -> никогда не может кластеризовать отрезки как есть -> сначала нужно кластеризовать линии, а затем обработать сегменты
• Линия AB и CD имеют одинаковый наклон. Если отрезки A'B 'и C'D' находятся близко к точке пересечения, они «похожи»; в противном случае они не -> сегменты линии не могут быть обработаны после кластеризации

Отсюда и противоречие.

Мне кажется, что O (N ^ 2), вероятно, лучшее, что вы можете получить, исходя из того факта, что для каждого сегмента линии наихудшим вариантом будет поиск среди всего пакета строк (или оставшихся ). Тем не менее, используя некоторые методы разбиения пространства, вы можете улучшить сложность среднего случая, предполагая, что отрезки линий распределены случайным образом.