Структура данных разбиения двоичного пространства на двумерное пространство пончика

Question

У меня есть 2D-карта, которая оборачивается по краям. Поэтому, если вы отойдете от правого края, вы снова появитесь в левой части карты. Аналогично с тремя другими ребрами.

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

Есть ли способ изменить дерево KD для работы с кольцевыми 2D-пространствами?

Answer 1

Структура данных не должна изменяться, но процедура поиска делает. Представьте каждую точку с помощью координат (x, y) в [0, w) * [0, h), где w - ширина карты, h - высота, а * обозначает декартово произведение. Сохраните эти точки в обычном дереве KD.

Фундаментальный примитив для поиска дерева KD, с учетом точки (x, y) и прямоугольника [a, b] * [c, d], определяет расстояние (в квадрате) от точки до прямоугольника. Обычно это g (x, a, b) ² + g (y, c, d) ² , где

g(z, e, f) = e - z if z < e
             0     if e <= z <= f
             z - f if f < z

- это одномерное расстояние от z до [e, f]. В тороидальном пространстве мы слегка модифицируем g, чтобы учесть обтекание.

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e
                0                       if e < z < f
                min(z - f, (e + v) - z) if f < z.

и квадрат расстояния равен g (x, a, b, w) ² + g (y, c, d, h) ² . Я ожидаю, что время выполнения будет сопоставимым для этого варианта. (Я бы повторил повторения, но наихудший случай для обычных деревьев KD в большинстве случаев намного хуже, чем на практике - O (n ^1/2 ) для определения ближайшего соседа в 2D среди n точек .)

Answer 2

Джитамаро предложил, но не объяснил метод, основанный на квадри-дереве «2x размер».Это разумное предположение, за исключением того, что в квадри-дереве используется в четыре раза больше узлов, чем двух, как я объясню ниже, прежде чем предварительно предложить альтернативный метод.

Предположим, что каждая координата (x, y) имеет -.5 < x <= .5 и -.5 < y <= .5, и когда j, k являются целыми числами, точка (x + j, y + k) совпадает с точкой (x, y).Пусть квадродерево T покрывает точки с координатами в диапазоне -1 < x,y <= 1.Каждый раз, когда вы добавляете элемент в (x, y) к T, где -.5 < x,y <= .5, пусть x' = {x-1, если x>0 else x+1}, и y' = {y-1, если y>0 else y+1}.Также добавьте элемент в (x, y '), (x', y ') и (x', y).[Когда вы удалите точки позже, снова вычислите (x ', y') и др. И удалите их тоже.] Легко видеть, что поиск ближайших точек будет работать правильно, пока любая координата поиска вне интервала (-.5,.5] настроена

Если четырёхкратное количество узлов является ограничителем сделок, обратите внимание, что если координаты, как описано выше, используются в поддеревьях выше, скажем, уровне k=3, а относительные координаты сохраняются ниже уровня k, должно быть возможно поддерживать отдельные копии поддеревьев ниже уровня k.То есть каждое поддерево на уровне k будет иметь четырех родителей.(Я не думал об этом достаточно, чтобы знать, работает ли это полностью; отредактирую ответ, если я нахожу, что это не так.)

Answer 3

Quadtree - это KD-дерево с 4-мя листьями. Четырехъядерное дерево не помогает в переносе, потому что его структура данных сама по себе является переносом. Вам просто нужно использовать quadtree 2x размера вашей структуры.