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

Question

У меня есть пространственные данные - (x, y) точки на плоскости - которые я разделяю с помощью четырех деревьев. Идея состоит в том, чтобы найти, какие точки являются соседями данной (a, b) точки. Точки являются соседями, если между ними есть некоторое (скажем, 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

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

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

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

Answer 2

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

Answer 3

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

где px - период х.

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