Поиск ближайшего соседа в постоянно меняющемся наборе отрезков

Question

У меня есть набор отрезков.Я хочу выполнить над ними следующие операции:

1. Вставить новый отрезок.
2. Найти все отрезки в радиусе R данной точки.
3. Найтивсе точки в пределах радиуса R1 данной точки.
4. Учитывая данный отрезок, найдите, если он пересекает какой-либо из существующих отрезков.Точная точка пересечения не требуется (хотя это, вероятно, ничего не упрощает).

Проблема заключается в алгоритмах, подобных дереву kd / bd или деревьям BSP, в том, что они принимают статический набор точек, и в моем случаеточки будут постоянно пополняться новыми точками, что потребует перестройки дерева.

Какая структура данных / алгоритмы будут наиболее подходить для этой ситуации?

Редактировать: Принял ответ, который является самым простыми решает мою проблему.Спасибо всем!

Answer 1

Поддержание динамического дерева может быть не так плохо, как вы думаете.

Когда вы вставляете новые точки / линии и т. Д. В коллекцию, становится ясно, что вам нужно будет уточнить текущее дерево, но я не понимаю, зачем вам каждый раз перестраивать все дерево с нуля. Как вы предлагаете, была добавлена ​​новая сущность.

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

Для вашей конкретной проблемы:

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

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

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

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

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

function insert(x, y)

find the tree leaf element enclosing the new entitiy at (x,y) based on whatever 
fast search algorithm your tree supports

if (number of entities per leaf > max allowable) do

    refine current leaf element (would typically either be a bisection 
    or quadrisection based on a 2D tree type)

    push all entities from the old leaf element list onto the new child element
    lists, based on the enclosing child element

else

    push new entity onto list for leaf element

endif

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

Я несколько раз использовал этот тип подхода с квадри / октре, и на этом этапе я не могу понять, почему подобный подход не будет работать с деревьями kd и т. Д.

Надеюсь, это поможет.

Answer 2

В то время как пункты 2 и 3 относительно просты, при использовании простого линейного поиска с проверками расстояния при вставке каждой строки пункт 4 немного более сложен.

Я бы предпочел использовать ограниченную триангуляцию длярешить эту проблему, когда все входные строки рассматриваются как ограничения, а триангуляция балансируется с использованием ближайшего соседа, а не критерия Делоне.Это очень хорошо освещено в Триангуляциях и приложениях Ойвинда Хьелле, Мортена Донена и Джозефа О'Руркса Вычислительная геометрия в C Оба имеют доступный источник, включая получение наборов всех пересечений.

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

• Создание произвольной триангуляции (TIN), состоящей из двух треугольников, окружающих экстенты (current +будущее) ваших данных.

• Для каждой новой строки

• Вставьте обе точки в ИНН.Это можно сделать очень быстро, пройдя треугольники, чтобы найти точку вставки, и заменив найденный треугольник на три новых треугольника, основанных на новой точке и старом треугольнике.

• Разрезать отрезок черезTIN, основанный на двух конечных точках, с сохранением списка точек, в которых секция обрезает любые ранее вставленные линии.Добавьте сведения о точках пересечения в список, сохраненный для обеих линий, и вставьте их в TIN.

• Принудительная вставка в качестве ограничения

• Сбалансируйте все пары смежных треугольников, измененных в вышеописанном процессе, используя критерий ближайшего соседа, и повторяйте, пока все треугольники не будут сбалансированы.

Это работает лучше, чем метод на основе сетки для плохо распределенныхданные, но сложнее реализовать.Группировка конечной точки и линий в перекрывающиеся сетки, вероятно, будет хорошей оптимизацией для 2 и 3.

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

Answer 3

Вместо вставки и удаления в дерево вы можете рассчитать кривую, которая полностью заполняет плоскость.Такая кривая уменьшает сложность 2d до сложности 1d, и вы сможете найти ближайшего соседа.Вы можете найти некоторые примеры, такие как кривая z и кривая Гильберта.Вот лучшее описание моей проблемы http://en.wikipedia.org/wiki/Closest_pair_of_points_problem.

Answer 4

Одной из возможностей является разделение вашего пространства на сетку блоков - возможно, 10 по оси Y и 10 по оси X, в общей сложности 100.

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

Когда вы вычисляете линейные сегменты в пределах R одного сегмента, вы можете отмечать только соответствующие соседние поля.

Конечно, вы можете создать несколько карт разной степени детализации, возможно, 100 на 100 меньших блоков. Просто примите во внимание компромисс между временем и обслуживанием в вашем дизайне.

• Обновление позиций сегментов дешево: достаточно делить целые числа на размеры блоков в направлениях x и y. Например, если размер блока равен 20 в обоих направлениях, а ваша новая координата равна 145,30. 145/20 == 7 и 30/20 == 1, поэтому он входит в блок (7,1) для системы на основе 0.