Любые ссылки о том, как реализовать квадродеревья с периодическими ограничениями?

Question

У меня есть пространственные данные — точки (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 какое-то время был занят другим проектом, сейчас проверю ваши ответы!Большое спасибо.

Answer 1

Почему бы не разделить «круг поиска» на круговые диаграммы с углом Пи/2?Посмотрим, смогу ли я передать это с помощью текста и простого изображения.

альтернативный текст http://img168.imageshack.us/img168/8426/circleinquarters.gif

Идея состоит в том, чтобы рассматривать «поиск по кругу» как четыре «круговые диаграммы», поэтому, когда вы выполняете поиск с помощью C(a, b, L), вам необходимо принять во внимание, что при переходе вниз по квадродереву круг не t пересекает только верхний левый угол квадродерева, поэтому в этом случае вам придется разветвиться на четыре ветви (а не только на одну, если бы эта область не была периодической).

Answer 2

xdist = min( (x1-x2) % px, (x2-x1) % px )

где px — период x.

ydist, а остальное оставляем в качестве упражнения для читателя :-)

Answer 3

Кажется, проще сохранить дерево квадрантов как есть, поскольку периодически реплицируется только корневой уровень.Чтобы учесть периодичность, сделайте несколько запросов (x+i*dx,y+j*dy,L) за каждый запрос (x,y,L).Выполните цикл по i,j так, чтобы диск запроса пересекал корневой узел дерева.