Ich möchte einige König der räumlichen Indizierung Datenstruktur für meine MKAnnotations implementieren.
Momentan ist es schrecklich langsam, wenn ich versuche, sie anhand von Entfernungskriterien zu filtern (3-4k Orte, momentan extrem langsam mit einem einfachen Doppel for ...).
Ich möchte Cluster von MKAnnotations erstellen, um zu entscheiden, ob es sich in der Nähe eines anderen befindet. Außerdem sind diese Orte in einer (Erstellungs-) Reihenfolge und eine "vorherige" / "nächste" Funktionalität wäre erforderlich, um zwischen diesen zu "springen" (dies ist kein Muss).
Ich habe gelesen über kd-tree und r-tree Strukturen und sie beide scheinen die schnelle Entfernung / Nachbar erhalten Option zum Filtern / Clustering zu treffen, aber ich bin mir nicht sicher, welches ist das beste für mich oder wenn es auch andere Optionen sind .
Welchen Algorithmus / welche Datenstruktur sollte ich verwenden?
Update: Ich speichere diese Speicherorte in einer Core Data-Datenbank, sie repräsentieren einen Pfad. Wenn die Karte geöffnet wird, werden sie in ein Array geholt und dann verwende ich dieses Array für Entfernungsberechnungen und Annotationserstellung. Wenn der Benutzer die Karte bewegt / zoomt, durchlaufe ich sie und entscheide, was auf der Karte geändert werden muss, so dass das ganze Zeug statisch ist. Wie ich verstanden habe, wenn ich einen Baum verwende, könnte ich die Orte dort speichern und wenn ein Zoom / Bewegung passiert, suche ich einfach durch und erhalte die in der neuen Region. Ist das wahr ?
Selbst im dynamischen Fall, wenn ich neue Positionen zu diesem Array hinzufügen kann, wäre es eine einzelne Einfügung und es passiert selten.
Es hängt sehr davon ab, wie Ihre Verwendung Muster sind (wie schreibt ich zum Beispiel In-Memory oder auf der Festplatte) und wie Ihre Daten aussehen (also wie sie verteilt werden) .
R-Bäume sind gut, weil sie balanciert sind und eine Aktualisierung erlauben. Der R * -Baum ist meiner Erfahrung nach aufgrund der Split-Strategie deutlich besser als die anderen Varianten. Der Vorteil ist, dass es mehr quadratische Seiten als die anderen Strategien erzeugt, so dass Sie für viele Abfragen weniger Seiten scannen müssen.
kd-Bäume sind gut, wenn Sie in-memory und statisch sind. Die Aktualisierung ist sehr schlecht, Sie müssen den Index ziemlich oft neu erstellen.
Und wenn sich Ihre Daten nicht sehr oft ändern, funktioniert das Laden von Massen für den R-Baum sehr gut. Sie können Sort-Tile-Recursive Bulk loading durchführen, was im Wesentlichen ein (teilweises) alternierendes Sortieren Ihrer Daten auf X und Y erfordert, sodass ein niedriger O(n log n) erforderlich ist, um den Baum zu erstellen. sehr ähnlich zum Massenladen eines kd-Baums, außer dass Sie multi-split statt binary splitting verwenden. Das ist sehr beliebt.
Außerdem können Sie die Anzahl der Objekte auf jeder Seite verfolgen. Wenn Sie Objekte auf einer Karte anzeigen, möchten Sie möglicherweise früh anhalten, wenn eine Seite auf dem Bildschirm zu klein angezeigt wird (d. H. Kleiner als eine Markierung). An dieser Stelle würden Sie diese Seite nicht scannen, sondern nur die Anzahl der Objekte nehmen und diese als gruppierte Markierung anzeigen, bis der Benutzer den Ausschnitt vergrößert.
Bei 2D-Daten mit einer begrenzten Wertdomäne sollten Sie die einfachen Dinge nicht übersehen. Quadretrees können auch wirklich gut funktionieren! Einfachheit kann die Optimierung erheblich vereinfachen. Oder ein klassischer Rasteransatz. Wenn Ihre Benutzer dazu neigen, ihre Annotationen in einem Bereich zu verteilen (und nicht alle an einem Ort zu platzieren), können Sie ganzzahlige x, y-Gitterkoordinaten berechnen und diese dann hashen und für jede Rasterzelle eine Liste erstellen.
Ich bin kein iOS-Entwickler, aber ich habe mir die Dokumente angesehen und folgendes gefunden:
MKMapView.annotationsInMapRect:
Gibt die Annotationsobjekte zurück, die sich im angegebenen Kartenrechteck befinden.
(NSSet *)annotationsInMapRect:(MKMapRect)mapRectParameter
- mapRect : Der Teil der Karte, nach dem Sie nach Anmerkungen suchen möchten.
Rückgabewert Die Gruppe von Anmerkungsobjekten, die sich in mapRect befinden.
Diskussion Diese Methode bietet eine schnelle Möglichkeit zum Abrufen der Anmerkungsobjekte in einem bestimmten Teil der Karte. Diese Methode ist viel schneller als eine lineare Suche der Objekte in der Annotationseigenschaft selbst.
Dies deutet darauf hin, dass die NKMapView bereits Annotationen in einer räumlichen Indexstruktur organisiert. Würde diese Methode Ihre Anforderungen erfüllen?
Wenn nicht, würde ich nach vorhandenen Open-Source-Implementierungen jeder zweidimensionalen räumlichen Indexierungsstruktur suchen und diejenige mit der besten Dokumentation, den saubersten Schnittstellen usw. auswählen, anstatt sich Gedanken über die Effizienz zu machen. Wenn Sie das Codeformular scratchen müssen, wäre ein Quadtree am einfachsten zu implementieren. Auf der anderen Seite scheint der Wikipedia-Artikel auf R-Baum spezifischer auf Kartierung ausgerichtet zu sein als der KD-Baum oder Quadtree .
Tags und Links algorithm ios kdtree mkannotation spatial-index