Ich mache ein Programm, mit dem Sie auf eine Karte klicken können, um eine "Nahaufnahme" der Umgebung zu sehen, z. B. in Google Maps.
Wenn ein Benutzer auf die Karte klickt, erhält er die X- und Y-Koordinate, auf die er geklickt hat.
Nehmen wir an, dass ich ein Array von Booleschen Werten habe, wo diese Nahansichtsbilder sind:
%Vor%Das Programm durchsucht einen Ordner, in dem Bilder benannt werden, an denen die X- und Y-Koordinate des Ortes, an dem sie auf der Karte aufgenommen wurde, angezeigt wird. Der Ordner enthält die folgenden Bilder (und mehr, aber ich werde nur fünf auflisten):
%Vor%Das bedeutet:
%Vor%Wenn ein Benutzer auf das X und Y von beispielsweise 2377,1882 klickt, dann muss das Programm herausfinden, welches Bild am nächsten ist (die Antwort wäre in diesem Fall 2377,1881).
Jede Hilfe wäre willkommen, Danke.
In Anbetracht des Ortes, auf den der Benutzer geklickt hat, könnten Sie mithilfe einer Dijkstra-Suche nach dem nächsten Bild suchen. Grundsätzlich beginnen Sie in immer größeren Rechtecken um den angeklickten Ort nach Bildern zu suchen. Natürlich müssen Sie nur die Grenzen dieser Rechtecke suchen, da Sie den Körper bereits durchsucht haben. Dieser Algorithmus sollte anhalten, sobald ein Bild gefunden wird.
Pseudocode:
%Vor%Beachten Sie, dass ich die Bereichsüberprüfung der Kürze wegen weggelassen habe.
Es gibt ein kleines Problem, aber abhängig von der Anwendung ist dies möglicherweise kein Problem. Es verwendet keine euklidischen Entfernungen, sondern die Manhattan-Metrik. Es findet also nicht unbedingt das nächstliegende Bild, sondern ein Bild höchstens der Quadratwurzel von 2 mal so weit.
Ihre boolean[][] ist keine gute Datenstruktur für dieses Problem, zumindest wenn sie nicht wirklich dicht ist (zB ist normalerweise ein Punkt mit Nahsicht im umgebenden 3 × 3 oder vielleicht 5 × 5 Quadrat verfügbar).
Sie möchten eine 2-D-Karte mit Nearest-Neighbor-Suche. Eine nützliche Datenstruktur für dieses Ziel ist der QuadTree . Dies ist ein Baum von Grad 4, der zur Darstellung von räumlichen Daten verwendet wird. (Ich beschreibe hier die "Region QuadTree mit Punktdaten".)
Grundsätzlich teilt es ein Rechteck in vier Rechtecke mit gleicher Größe und unterteilt jedes der Rechtecke weiter , wenn mehr als ein Punkt darin enthalten ist
.Also ein Knoten in Ihrem Baum ist einer von diesen:
(In Implementierungen können wir leere Blattknoten durch einen Nullzeiger im übergeordneten Element ersetzen.)
Um einen Punkt zu finden (oder "der Knoten, an dem ein Punkt liegen würde"), beginnen wir am Wurzelknoten, schauen, ob unser Punkt Nord / Süd / Ost / West vom Teilungspunkt ist, und gehen zum entsprechenden Kind Knoten. Wir fahren fort, bis wir zu einem Blattknoten gelangen.
Wenn Sie einen neuen Punkt hinzufügen, werden wir entweder mit einem leeren Knoten enden - dann können wir den neuen Punkt hier einfügen. Wenn wir an einem Knoten mit bereits einem Punkt enden, erstellen Sie vier untergeordnete Knoten (indem Sie das Rechteck aufteilen) und fügen Sie beide Punkte zum entsprechenden untergeordneten Knoten hinzu. (Dies kann dasselbe sein, dann rekursiv wiederholen.)
Für die nächste Nachbarsuche werden wir entweder mit einem leeren Knoten enden - dann sichern wir eine Ebene und schauen uns die anderen Kindknoten dieser Eltern an (vergleicht jede Entfernung). Wenn wir einen Kindknoten mit einem Punkt erreichen, messen wir die Entfernung von unserem Suchpunkt zu diesem Punkt. Wenn es kleiner ist als der Abstand zu den Kanten oder dem Knoten, sind wir fertig. Andernfalls müssen wir auch die Punkte in den benachbarten Knoten betrachten und die Ergebnisse hier vergleichen, wobei wir das Minimum nehmen. (Wir werden uns höchstens vier Punkte ansehen müssen.)
Nach dem Auffinden eines Punktes wird der Knoten leer gelassen. Wenn der Elternknoten jetzt nur einen Punkt enthält, ersetzen wir ihn durch einen Ein-Punkt-Blattknoten.
Das Suchen und Hinzufügen / Entfernen erfolgt in der Komplexität der O (Tiefen) -Zeit, wobei die maximale Tiefe durch log ((Kartenlänge + Breite) / minimale Entfernung von zwei Punkten in Ihrer Struktur) begrenzt wird und die durchschnittliche Tiefe hängt mehr oder weniger von der Verteilung der Punkte ab (zB der durchschnittliche Abstand zum nächsten Punkt).
Der benötigte Platz hängt von der Anzahl der Punkte und der durchschnittlichen Tiefe des Baumes ab.
Es gibt einige Varianten dieser Datenstruktur (z. B. das Teilen eines Knotens nur, wenn mehr als X Punkte vorhanden sind oder das Teilen nicht notwendigerweise in der Mitte), um die Speicherplatznutzung zu optimieren und zu große Tiefen des Baums zu vermeiden .
Basierend auf
... du gehst in die falsche Richtung. @ JBSnorros Antwort ist eine ziemlich elegante Art, die Nadel (350 Punkte) im Heuhaufen zu finden (11 Millionen Punkte), aber warum eigentlich den Heuhaufen überhaupt erschaffen?
Was meinen Kommentar zu Ihrer Frage angeht, warum verwenden Sie nicht einfach Pair<Integer,Integer> Klasse, um Koordinaten darzustellen, sie in einem Set zu speichern und zu scannen? Es ist einfacher, schneller, weniger speicherintensiv und für größere Karten way besser skalierbar (unter der Annahme, dass die Sonderziele spärlich sind ...), was eine vernünftige Annahme ist, da sie Punkte von Interesse sind ).
... vertrauen Sie mir, die Euklidische Entfernung zu berechnen ~ 425 mal schlägt um einen 11 Millionen Wert boolean[][] sucht nach dem 1 Wert in 25.950, der von Interesse ist (besonders in einer Worst-Case-Analyse).
Wenn Sie wirklich nicht begeistert von der Idee sind, jedes Mal ~ 425 Werte zu scannen, dann (i) sind Sie mehr OCD als ich ( :P ); (ii) Sie sollten Suche nach nächstgelegenen Nachbarn nachsehen.
Ich weiß nicht, ob du darum bittest. Wenn der Benutzerpunkt P1 {x1, y1} ist und Sie seinen Abstand zu P2 {x2, y2} berechnen möchten, wird die Entfernung mit Pythagoras'Theorem
berechnet %Vor%Wenn Sie nur den nächstgelegenen wissen wollen, können Sie es vermeiden, die Quadratwurzel zu berechnen (je kleiner der Abstand, desto kleiner ist auch das Quadrat, damit es Ihnen genauso geht).
Tags und Links algorithm java computational-geometry