Quaisquer referências sobre como implementar quadtrees com limites de periódicos?

Question

Eu tenho dados espaciais - (x, y) pontos em um plano - que eu estou de particionamento usando quadtrees. A idéia é encontrar quais os pontos são vizinhos a um determinado (a, b) ponto. Os pontos são vizinhos se houver algum (digamos L) distância entre os dois. O problema é que o espaço é periódica, isto é, se um ponto é muito perto da borda (

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

Isso é pontos (a, b) e (c, d) e (h, i) deve ser vizinhos. Os vizinhos de (a, b) são os pontos dentro do círculo com o raio L com centro (a, b).

Papers, how-to são todos bem-vindos.

Obrigado,

---

Caras:

Obrigado por suas respostas, eu tenho não verificar stackoverflow por um tempo estava ocupado em outro projeto irá verificar suas respostas imediatamente! Muito obrigado.

Answer 1

Por que não dividir o seu "círculo de busca" em gráficos de pizza com ângulo pi / 2? Vamos ver se eu posso conseguir isso através de via texto e uma imagem simples.

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

A idéia é ver a "busca círculo", como quatro "gráficos de pizza", então quando você faz uma busca com C (a, b, L), você precisa levar em conta que ao passar para baixo na quadtree, o círculo não se limita a intersecção canto superior esquerdo da quadtree, portanto, neste caso você teria a ramificar-se em quatro ramos (não apenas um, se esta área não era periódica).

Answer 2

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

onde px é o período x.

ydist eo resto é deixado como um exercício para o leitor: -)

Answer 3

Parece mais simples para manter o quadtree como é, uma vez que apenas o nível de raiz é periodicamente replicado. Para tirar periodicidade em conta, fazer várias solicitações (x+i*dx,y+j*dy,L) para cada (x,y,L) pedido. Laço em i, j tal que o disco consulta cruza o nó raiz da árvore.