Любые ссылки о том, как реализовать квадродеревья с периодическими ограничениями?
-
06-09-2019 - |
Вопрос
У меня есть пространственные данные — точки (x, y) на плоскости, — которые я разделяю с помощью квадродеревьев.Идея состоит в том, чтобы найти, какие точки являются соседями данной точки (a, b).Точки являются соседями, если между ними существует некоторое расстояние (скажем, L).Проблема в том, что пространство периодично, то есть, если точка находится очень близко к краю (< L), эта точка должна быть соседкой точки, близкой к противоположному краю.(Под периодичностью в данном случае я подразумеваю, что плоскость повторяется)
|=================== | ===================|
|(a, b) (c,d)| (a, b) (c,d) |
| | |
| (e,f) | (e, f) |
| (h,i)| (h,i)|
|=================== | ===================|
|(a, b) (c,d)| (a, b) (c,d) |
| | |
| (e,f) | (e, f) |
| (h,i)| (h,i)|
| ================== | ===================|
То есть точки (a,b) и (c, d) и (h, i) должны быть соседями.Соседи (a,b) — это точки внутри круга радиуса L с центром (a,b).
Документы, инструкции приветствуются.
Спасибо,
Ребята:
Спасибо за ваши ответы, я не проверял stackoverflow какое-то время был занят другим проектом, сейчас проверю ваши ответы!Большое спасибо.
Решение
Почему бы не разделить «круг поиска» на круговые диаграммы с углом Пи/2?Посмотрим, смогу ли я передать это с помощью текста и простого изображения.
альтернативный текст http://img168.imageshack.us/img168/8426/circleinquarters.gif
Идея состоит в том, чтобы рассматривать «поиск по кругу» как четыре «круговые диаграммы», поэтому, когда вы выполняете поиск с помощью C(a, b, L), вам необходимо принять во внимание, что при переходе вниз по квадродереву круг не t пересекает только верхний левый угол квадродерева, поэтому в этом случае вам придется разветвиться на четыре ветви (а не только на одну, если бы эта область не была периодической).
Другие советы
xdist = min( (x1-x2) % px, (x2-x1) % px )
где px — период x.
ydist, а остальное оставляем в качестве упражнения для читателя :-)
Кажется, проще сохранить дерево квадрантов как есть, поскольку периодически реплицируется только корневой уровень.Чтобы учесть периодичность, сделайте несколько запросов (x+i*dx,y+j*dy,L)
за каждый запрос (x,y,L)
.Выполните цикл по i,j так, чтобы диск запроса пересекал корневой узел дерева.