Поддержание динамического дерева может быть не так уж плохо, как вы думаете.
Когда вы вставляете новые точки/линии и т. д. в коллекцию, становится ясно, что вам нужно будет уточнить текущее дерево, но я не понимаю, почему вам придется перестраивать все дерево с нуля каждый раз, когда новый объект был добавлено, как вы предлагаете.
При использовании динамического дерева у вас всегда будет действительное дерево, поэтому вы можете просто использовать быстрый поиск диапазона, поддерживаемый вашим типом дерева, чтобы найти упомянутые вами геометрические объекты.
Для вашей конкретной проблемы:
Вы можете настроить динамическое геометрическое дерево, в котором листовые элементы поддерживают список геометрических объектов (точек и линий), связанных с этим листом.
Когда строка вставляется в коллекцию, она должна быть помещена в списки всех конечных элементов, с которыми она пересекается. Вы можете сделать это эффективно, пройдя подмножество дерева от корня, который пересекается с линией.
Чтобы найти все точки/линии внутри указанного радиального ореола, вам сначала нужно найти все листья в этой области. Опять же, это можно сделать, пройдя подмножество дерева от корня, который заключен или пересекается с ореолом. Поскольку возможно некоторое перекрытие, вам нужно проверить, что объекты, связанные с этим набором листовых элементов, действительно находятся внутри ореола.
После того как вы вставили линию в набор конечных элементов, вы можете определить, пересекается ли она с другой линией, просмотрев все линии, связанные с только что найденным подмножеством конечных элементов. Затем вы можете выполнить тесты пересечения линий на этом подмножестве.
Потенциальный алгоритм динамического уточнения дерева, основанный на верхнем пределе количества объектов, связанных с каждым листом в дереве, может работать следующим образом:
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-деревьями и т. д.
Надеюсь это поможет.
person
Darren Engwirda
schedule
26.01.2012