Pre RTree Schritt: Unterteilen eines Satzes von Punkten in rechteckige Bereiche, die jeweils einen Punkt enthält,

Question

meine aktuelle Position gegeben (lat, long) Ich mag die nächsten Nachbarn in einem Sehenswürdigkeiten Problem schnell finden. So will ich eine R-Tree-Datenbank verwenden, die für die schnelle Suche ermöglicht. Doch zunächst muss die Datenbank gefüllt werden - natürlich. Daher müssen die rechteckigen Bereiche I bestimmen, die den Bereich abdeckt, wobei jede Region einen Punkt von Interesse enthält.

Meine Frage ist, wie kann ich die Daten vorverarbeiten, das heißt wie ich unterteilen den Bereich in diese rechteckigen Unterregionen? (Ich möchte rechteckige Bereiche, weil sie leicht zu dem RTree hinzugefügt werden - im Gegensatz zu allgemeineren Voronoi Regionen)

.

/ John

Answer 1

Edit: Der folgende Ansatz funktioniert, ignoriert aber die kritische Funktion der R-Bäume - das ist das Teilungsverhalten von R-Baumknoten ist gut definiert, und erhält einen ausgeglichenen Baum (durch B- baumähnlichen Eigenschaften). Also in der Tat, alles, was Sie tun müssen, ist:

1. Wählen Sie die maximale Anzahl der Rechtecke pro Seite
2. Erstellen Samen Rechtecken (Verwendung Punkte am weitesten entfernt voneinander, Zentroide, was auch immer).
3. Für jeden Punkt, wählen Sie ein Rechteck, um es in
   4. Wenn es bereits in ein einziges Rechteck fällt, setzen Sie es in dort
   5. Wenn dies nicht der Fall, erweitern das Rechteck, das erweitert werden muss, um mindestens (verschiedene Möglichkeiten „am wenigsten“ Exits zu messen - Bereich arbeitet)
   6. Wenn mehrere Rechtecke anwenden - wählen Sie eine Basis auf, wie voll es ist, oder eine andere Heuristik
4. Wenn ein Überlauf auftritt - das quadratische Split verwenden, um Dinge zu bewegen ...
5. Und so weiter, mit R-Tree-Algorithmen direkt aus einem Textbuch.

Ich denke, die Methode, die unten in Ordnung ist Ihre erste Samen Rechtecke für die Suche; aber Sie wollen nicht Ihre gesamte R-Baum auf diese Weise zu bevölkern. Spagat und Neugewichtung die ganze Zeit kann ein bisschen teuer, so dass Sie werden wahrscheinlich wollen ein anständiges Stück der Arbeit mit dem KD-Ansatz tun unten; nur nicht die ganze Arbeit.

---

Der KD-Ansatz: umschließen alles in einem Rechteck

.

Wenn die Anzahl der Punkte im Rechteck ist> Schwelle, fegt in Richtung D, bis die Hälfte der Punkte abdecken.

Teile in Rechtecken links und rechts (oder oben und unten) den Teilungspunkt).

Rufen Sie die gleiche Prozedur rekursiv auf die neuen Rechtecken, mit der nächsten Richtung (wenn Sie nach rechts nach links gehen wurden, werden Sie nun von oben nach unten gehen, und umgekehrt).

Der Vorteil dieser hat über die Teile-in-Quadrate von einem anderen Plakate angeboten Ansatz ist, dass es schief Punktverteilungen besser aufnimmt.

Answer 2

Oracle Spatial Cartridge Dokumentation beschreibt Tessellation Algorithmus, tun können, was Sie wollen. Kurz gesagt:

• umschließen alle Punkte in eckigen
• , wenn Quadrat enthält 1 Punkt - Index Quadrat
• , wenn Platz Punkte nicht enthält - ignorieren
• , wenn Quadrat enthält mehr als 1 Punkt
  • aufgeteilt Platz in 4 gleich große Quadrate und wiederholen Analyse für jeden neuen Platz

Ergebnis sollte wie folgt sein:
alt text http: // Download- uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif

Answer 3

Ich denke, dass Sie ein etwas fehlt in der Problemstellung. Angenommen, Sie haben N Punkte (x, y), so daß jeder Punkt eine eindeutige X- hat und y-Koordinate. Sie können Ihren Bereich in N Rechtecke teilen sich dann nur um es in N vertikalen Spalten geteilt wird. Aber das hilft nicht, Ihnen das nächste POI Problem leicht zu lösen, nicht wahr? Also ich glaube, Sie denken über etwas über die Rechteck-Struktur, die Sie noch nicht artikuliert haben.

Abbildung:

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

Die Zahlen sind POIs und die vertikalen Linien zeigen eine Unterteilung in rechteckige Bereiche 7. Aber klar ist es nicht viel „interessant“ Informationen in der Unterteilung. Gibt es ein zusätzliches Kriterium für die Unterteilung, die Sie nicht erwähnt haben?