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

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)| 
| ================== | ===================| 

То есть точки (а, б) и (в, г) и (H, I) должен быть соседями. Соседи (a, b) - это точки внутри круга с радиусом L с центром (a, b).

Бумаги, практические пожелания.

Спасибо,

---

Ребята:

Спасибо за ваши ответы, Я не проверить StackOverflow некоторое время был занят на другом проекте будет проверить свои ответы прямо сейчас! Большое спасибо.

Answer 1

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

alt text http://img168.imageshack.us/img168/8426/circleinquarters.gif

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

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, так что диск запроса пересекает корневой узел дерева.