Структура данных разбиения двоичного пространства для двумерного пространства пончика
У меня есть 2D-карта, которая оборачивается по краям. Поэтому, если вы отойдете от правого края, вы снова появитесь в левой части карты. Точно так же с тремя другими краями.
Это наследственная проблема для KDTree, которую я использую для поиска элементов в диапазоне точек. Обычно вы проверяете, сталкивается ли гиперсфера с гиперплоскостью, чтобы увидеть, следует ли продолжать поиск с другой стороны дерева, но эта проверка не работает с обтеканием ребер.
Есть ли способ изменить KD Tree для работы с кольцевыми 2D-пространствами?
3 ответа
Структура данных не должна изменяться, но процедура поиска делает. Представьте каждую точку с помощью координат (x, y) в [0, w) * [0, h), где w - ширина карты, h - высота, а * обозначает декартово произведение. Сохраните эти точки в обычном дереве KD.
Фундаментальный примитив для поиска дерева KD, с учетом точки (x, y) и прямоугольника [a, b] * [c, d], определяет расстояние (в квадрате) от точки до прямоугольника. Обычно это g (x, a, b)2 + g (y, c, d)2, где
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)2 + g (y, c, d, h)2. Я ожидаю, что время выполнения будет сопоставимым для этого варианта. (Я бы повторил повторения, но наихудший случай для регулярных деревьев KD гораздо хуже, чем на практике большую часть времени - O (n1/2) для определения ближайшего соседа в 2D среди n точек.)
Джитамаро предложил, но не объяснил метод, основанный на квадри-дереве "2х размер". Это разумное предположение, за исключением того, что в квадри-дереве используется в четыре раза больше узлов, чем двух, как я объясню ниже, прежде чем предварительно предложить альтернативный метод.
Предположим, что каждая координата (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 еще x+1}, а также y' = {y-1 если y>0 еще y+1}, Также добавьте элемент в (x,y'), (x',y') и (x',y). [Когда вы позже удалите точки, снова вычислите (x ', y') и др. И удалите их тоже.] Легко видеть, что поиск ближайших точек будет работать правильно, если любая координата поиска находится вне интервала (-.5,.5] настроен правильно.
Если четырехкратное число узлов является условием прерывания сделки, обратите внимание, что если координаты, как описано выше, используются в поддеревьях, скажем, выше уровня k=3и относительные координаты хранятся ниже уровня k, должно быть возможно поддерживать отдельные копии поддеревьев ниже уровня k, То есть каждое поддерево на уровне k будет иметь четверых родителей. (Я не думал об этом достаточно, чтобы знать, если это полностью работает; отредактирую ответ, если я найду, что это не так.)
Quadtree - это KD-дерево с 4-мя листьями. Четырехъядерное дерево не помогает переносить, потому что его структура данных сама по себе является переносом. Вам просто нужно использовать размер дерева в 2 раза.