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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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