Hallo zusammen,
ich bastle gerade (spaßeshalber) an einer Umkreissuche für eine Webapplikation und habe auch schon eine Lösung, basierend auf "normaler" Vektor-Geometrie gefunden. Das Problem an dieser Lösung, sie braucht einen kompletten Tabellendurchlauf. Dabei werden die Abstände vom angegebenen Punkt zu jedem Punkt in der Tabelle berechnet und dann mittels einer WHERE-Clause die gewünschten Datensätze die sich innerhalb des gewünschten Umkreises befinden, ausgefiltert. Wenn die Tabelle nur wenig Zeilen hat, mag das noch vertretbar sein, aber bei vielen Zahlen ist das wohl eher Selbstmord...
Um dem laufzeittechnischen Selbstmord zu entgehen, habe ich mich nach einer anderen Lösung (evtl. ohne SQL-DB) umgeguckt und bin auf eine NoSQL-Datenbank (Pincaster) gestoßen, die intern Quadtrees für die Umkreissuche verwendet. Um Pincaster zu testen habe ich alle Orte der GeoDB in die DB geladen und bin wirklich von den Socken, wie toll und vor allem schnell die Queries bearbeitet werden. Da ich auch verstehen will wie Pincaster das mit dem Quadtree löst, hab ich nach weiterführenden Informationen zu Quadtrees gegoogelt, z.B. Pseudocodes, Test-Implementierungen oder alles was mir helfen könnte selbst einen solchen Quadtree aufzubauen - leider habe ich bis jetzt nicht wirklich etwas entsprechendes gefunden. Das System wie Quadtrees funktionieren habe ich soweit schon durchstiegen, aber mir fehlen generell noch Informationen wie der Baum aufgebaut werden muss und wie ich Punkte in einem bestimmten (km) Umkreis (oder sollte ich besser Umquadrat sagen) zu meinem Ursprungspunkt suchen kann.
Habt ihr vielleicht ein Code-Stück aus einem eurer Projekte, ein Skript von der Uni oder ein Buch das ihr mir hierzu empfehlen könnt?
Ich bin für alle Informationen dankbar...
Grüße
metty
Umkreissuche mit Hilfe von Quadtrees
Hallo.
Im Wikipedia-Artikel wird doch eigentlich recht deutlich, wie du den Baum aufbaust: Angenommen, du hast n Punkte, dann berechnest du von diesen die Bounding-Box. Unter Umständen musst du dessen Größe auch geschickt wählen, da die Größe (räumliche Ausdehnung) die abgedeckten Bereich beschränkt. Jetzt unterteilst du die Box in vier gleich große Rechtecke, indem du die Seiten halbierst. Nun musst du prüfen, welche deiner Punkte in welches kleinere Rechteck fallen und diese dort einfügen. Jetzt fährst du mit den kleineren Rechtecken fort, indem du sie jeweils wieder aufteilst. Diese Aufteilung führst du solange durch, bis du dein Abbruchkriterium gefunden hast. Du solltest zum Beispiel immer dann aufhören eine Zelle zu teilen, wenn sie keine Punkte mehr enthält
Typischerweise solltest du aufhören zu unterteilen, wenn nur noch k Punkte in ein Gitter fallen. Wie klein dein k ist, hängt natürlich stark von der Gesamtzahl der Punkte ab und was für Algorithmen du später ausführst. Da musst du ein wenig experimentieren. Und auf jeden Fall solltest du abbrechen, wenn die Größe einer Box/Rechteck eine gewisse Fläche unterschreitet. Sonst teilst du möglicherweise ewig auf (beispielsweise wenn k+1 Punkte die selbe Position haben).
Die Umkreissuche versuche ich mal am Beispiel eines gleichmäßigen Gitterst zu erläutern, welches du über deine Punkte gelegt hast. In jede Gitterzelle können beliebig viele Punkte fallen. Suchst du jetzt alle Punkte im Umkreis von x, so suchst du dir alle Gitterzellen raus, welche x aus, mit dem Suchradius r, erreichbar sind. Innerhalb jeder dieser Zellen musst du nun jeden Punkt prüfen, ob dieser nah genug an x liegt oder nicht. Hier sollte sehr deutlich werden, dass die Wahl der Zellengrößen und insbesondere die Anzahl der Punkte in einer Zelle, entscheiden für die Suchgeschwindigkeit sind. Große Zellen erlauben eine schnelle Suche von Zellen, es dauert jedoch lange eine Zelle zu durchsuchen, das sie potentiell viele Punkte enthält. Ist die Zelle zu klein, schaust du dir unnötig viele Zellen an, der Test auf Punkte geht jedoch schnell. Diese Nachteile werden durch den Quadtree weitestgehend ausgeglichen, da der Raum gleichmäßig aufgeteilt wird. Betrachtest du pro Zelle nicht jeden Punkt einzeln, sondern nimmst einfach alle Punkte, so hast du eine Näherung und kannst sogar sagen, wie gut sie ist (bzw. wie schlecht sie im schlimmsten fall ist).
Die Suche mittels Quadtree erfolgt nun analog: Angenommen, du suchst wieder den Punkt x, dann steigst du rekursiv im Baum ab. Du nimmst aber immer nur die Äste, welche du von x aus auch mittels des Radius r erreichen kannst. Damit schließt du bereits am Anfang sehr viele Punkte aus. Das machst du einfach so lange, bis du bei den Blättern angekommen bist. Die Punkte innerhalb eines Blattes musst du natürlilch wieder einzeln testen, wenn du ein exaktes Ergebnis hast.
Mittels des Baums sparst du zunächst Speicher, das du kein vollständiges Gitter aufbauen musst, sondern nur die relevanten Bereiche speicherst. Und das granuliert nach Anzahl der Punkte. Durch diesen Aufbau sparst du dann auch noch Zeit beim Suchen, da du viele Punkte direkt verwerfen kannst und sie nicht mehr anschauen musst.
Ich hoffe, dass die Ausführungen ein wenig weiter helfen, sonst frage einfach noch einmal nach.
Sebastian
Im Wikipedia-Artikel wird doch eigentlich recht deutlich, wie du den Baum aufbaust: Angenommen, du hast n Punkte, dann berechnest du von diesen die Bounding-Box. Unter Umständen musst du dessen Größe auch geschickt wählen, da die Größe (räumliche Ausdehnung) die abgedeckten Bereich beschränkt. Jetzt unterteilst du die Box in vier gleich große Rechtecke, indem du die Seiten halbierst. Nun musst du prüfen, welche deiner Punkte in welches kleinere Rechteck fallen und diese dort einfügen. Jetzt fährst du mit den kleineren Rechtecken fort, indem du sie jeweils wieder aufteilst. Diese Aufteilung führst du solange durch, bis du dein Abbruchkriterium gefunden hast. Du solltest zum Beispiel immer dann aufhören eine Zelle zu teilen, wenn sie keine Punkte mehr enthält
Typischerweise solltest du aufhören zu unterteilen, wenn nur noch k Punkte in ein Gitter fallen. Wie klein dein k ist, hängt natürlich stark von der Gesamtzahl der Punkte ab und was für Algorithmen du später ausführst. Da musst du ein wenig experimentieren. Und auf jeden Fall solltest du abbrechen, wenn die Größe einer Box/Rechteck eine gewisse Fläche unterschreitet. Sonst teilst du möglicherweise ewig auf (beispielsweise wenn k+1 Punkte die selbe Position haben).Die Umkreissuche versuche ich mal am Beispiel eines gleichmäßigen Gitterst zu erläutern, welches du über deine Punkte gelegt hast. In jede Gitterzelle können beliebig viele Punkte fallen. Suchst du jetzt alle Punkte im Umkreis von x, so suchst du dir alle Gitterzellen raus, welche x aus, mit dem Suchradius r, erreichbar sind. Innerhalb jeder dieser Zellen musst du nun jeden Punkt prüfen, ob dieser nah genug an x liegt oder nicht. Hier sollte sehr deutlich werden, dass die Wahl der Zellengrößen und insbesondere die Anzahl der Punkte in einer Zelle, entscheiden für die Suchgeschwindigkeit sind. Große Zellen erlauben eine schnelle Suche von Zellen, es dauert jedoch lange eine Zelle zu durchsuchen, das sie potentiell viele Punkte enthält. Ist die Zelle zu klein, schaust du dir unnötig viele Zellen an, der Test auf Punkte geht jedoch schnell. Diese Nachteile werden durch den Quadtree weitestgehend ausgeglichen, da der Raum gleichmäßig aufgeteilt wird. Betrachtest du pro Zelle nicht jeden Punkt einzeln, sondern nimmst einfach alle Punkte, so hast du eine Näherung und kannst sogar sagen, wie gut sie ist (bzw. wie schlecht sie im schlimmsten fall ist).
Die Suche mittels Quadtree erfolgt nun analog: Angenommen, du suchst wieder den Punkt x, dann steigst du rekursiv im Baum ab. Du nimmst aber immer nur die Äste, welche du von x aus auch mittels des Radius r erreichen kannst. Damit schließt du bereits am Anfang sehr viele Punkte aus. Das machst du einfach so lange, bis du bei den Blättern angekommen bist. Die Punkte innerhalb eines Blattes musst du natürlilch wieder einzeln testen, wenn du ein exaktes Ergebnis hast.
Mittels des Baums sparst du zunächst Speicher, das du kein vollständiges Gitter aufbauen musst, sondern nur die relevanten Bereiche speicherst. Und das granuliert nach Anzahl der Punkte. Durch diesen Aufbau sparst du dann auch noch Zeit beim Suchen, da du viele Punkte direkt verwerfen kannst und sie nicht mehr anschauen musst.
Ich hoffe, dass die Ausführungen ein wenig weiter helfen, sonst frage einfach noch einmal nach.
Sebastian
Das Leben ist wie ein Tennisball.
Hallo,
vielen Dank für die sehr ausführliche Antwort.
Ich habe jetzt noch ein wenig rumgespielt und habe einen dynamischen QuadTree gebaut. Die Suche nach Punkten in einem bestimmten Umkreis funktioniert auch perfekt schnell. So, wieder was gelernt...
vielen Dank für die sehr ausführliche Antwort.
Ich habe jetzt noch ein wenig rumgespielt und habe einen dynamischen QuadTree gebaut. Die Suche nach Punkten in einem bestimmten Umkreis funktioniert auch perfekt schnell. So, wieder was gelernt...