Alle Verweise auf, wie Quadtrees mit periodischen Grenzen zu implementieren?

Question

I haben räumliche Daten - (x, y) Punkte auf einer Ebene - die ich verwendet habe Quadtrees Partitionierung. Die Idee ist, zu finden, welche Punkte sind Nachbarn zu einem bestimmten (a, b) Punkt. Die Punkte sind Nachbarn, wenn es einige (zum Beispiel L) Abstand zwischen den beiden. Das Problem ist, dass der Raum periodisch ist, dh wenn ein Punkt an der Kante sehr nahe ist (

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

Das ist Punkt (a, b) und (c, d) und (h, i) sollten Nachbarn sein. Die Nachbarn von (a, b) sind die Punkte innerhalb des Kreises mit dem Radius L mit dem Mittelpunkt (a, b).

Papiere, How-to sind alle willkommen.

Danke,

---

Typen:

Vielen Dank für Ihre Antworten, ich habe nicht überprüfen Stackoverflow für eine Weile war an einem anderen Projekt beschäftigt werden sofort Ihre Antworten! Vielen Dank.

Answer 1

Warum nicht teilen Sie Ihre „search circle“ in Kreisdiagramme mit pi / 2 Winkel? Mal sehen, ob ich das durch über Text und ein einfaches Bild erhalten.

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

Die Idee ist es, die „Kreis suchen“, wie er vier „Kreisdiagramme“ zu sehen, also wenn Sie eine Suche mit C tun (a, b, L) müssen Sie berücksichtigen, dass bei der Übergabe in der Quadtree nach unten, die Kreis nicht nur linke obere Ecke des Quadtree schneiden, so dass in diesem Fall, dass Sie würden in vier Zweige haben, verzweigen nach unten (also nicht nur ein, wenn dieser Bereich nicht periodisch ist).

Answer 2

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

wo px ist die x-Periode.

ydist und der Rest wird für den Leser als Übung: -)

Answer 3

Es scheint einfacher, die Quadtree zu halten, wie es ist, da nur die Root-Ebene regelmäßig repliziert wird. Nehmen Periodizität berücksichtigt, tun (x+i*dx,y+j*dy,L) mehrere Anfragen für jede Anforderung (x,y,L). Schleife auf i, j, so dass die Abfragescheibe den Wurzelknoten des Baums schneidet.