Ich bin nicht sicher, welches mathematische Konzept dies ist, um meine Frage zu unterstützen. ^^
Nehmen wir an, wir haben PointA als Referenz. Das Problem besteht darin, die Punkte um PointA innerhalb eines bestimmten Radius zu finden (Koordinaten verwenden). Mein Ansatz wäre, die Entfernung jedes Punktes (Pythagoras) zu berechnen und dann mit dem gegebenen Radius zu vergleichen. Ich bin mir sicher, dass dies in Bezug auf die Komplexität lutschen würde.
Welchen Algorithmus können Sie vorschlagen? Ein Beispielcode, der auf Dinge hinweist, würde sehr geschätzt werden. Danke.
Ich würde damit beginnen, eine Box um den Kreis herum zu erstellen und zuerst zu testen, ob etwas in die Box fällt. Dann vermeidest du wahrscheinlich ständig die Berechnung von Quadraten und Quadraten. Wählen Sie eine Kante der Box (sagen Sie die auf der linken Seite) und berechnen Sie ihren x-Wert:
%Vor%Dann alles, was sättigt
%Vor%kann ignoriert werden. Wiederholen Sie etwas ähnliches für alle vier Seiten. In dem Moment, in dem ein Test fehlschlägt, hören Sie auf, an diesem Punkt zu arbeiten. Mach keine unnötigen Berechnungen.
Dies sagt Ihnen, dass ein Punkt nahe, aber nicht unbedingt innerhalb des Radius ist. Als nächstes berechnen:
%Vor%Wenn dies kleiner als Radius * Radius ist (was Sie vorberechnen, um die Verwendung von Quadratwurzeln zu vermeiden), dann haben Sie einen Punkt innerhalb des Radius.
Das ist das Beste, was ich bei der ersten Strukturierung der Daten herausfinden kann.
Wenn Ihre Punkte nicht indiziert sind, ist das eigentlich ein optimaler Algorithmus. Es gibt n Punkte, und es wird O ( n ) Zeit brauchen, um alle zu suchen, wenn kein anderer Index vorhanden ist.
Die eine Mikrooptimierung besteht darin, die sqrt-Operation zu überspringen und die Summe der Quadrate der Koordinatendeltas mit dem Quadrat des gewünschten Radius zu vergleichen.
Wenn Sie mehrere Abfragen für denselben Datensatz ausführen, gibt es verschiedene Indexierungsschemata, die Sie verwenden können, die einige Zeit zum Berechnen benötigen (O (n log n)), aber die Suchvorgänge schneller machen (O (m + log n), wobei m die Anzahl der gefundenen Punkte ist.)
kd-Bäume sind wahrscheinlich der richtige Ort, um dort zu beginnen.
Ihre einzige Komplexität ist hier die Berechnung der Entfernung. Sieben Sie einfach und vereinfachen Sie diese Berechnung und Sie sind optimal.
Wenn Ihr 'Zentrum' A (x, y) ist, dann betrachten Sie für jeden Punkt B (x1, y1):
1 / Wenn B innerhalb Ihrer erforderlichen Entfernung d von Punkt B ist, dann folgt das sowohl x-x1 < d als auch y-y1 < d . Überprüfen Sie zuerst diese Bedingungen, um alle Ausschlüsse für "niedrig hängende Früchte" zu filtern.
2 / Anstatt die Entfernung zu berechnen, berechnen Sie das Quadrat der Entfernung und vergleichen Sie es mit dem Quadrat der maximal zulässigen Entfernung (die Sie natürlich vorberechnen und referenzieren sollten, anstatt jedes Mal neu zu berechnen). Es bedeutet, dass für jeden Punkt keine Quadratwurzel berechnet werden muss.
Das sind ziemlich kleine Optimierungen, aber unter der Annahme, dass die Punkte unsortiert und zufällig sind, ist dies das Beste, was Sie bekommen werden.
Die beste Antwort hängt von der Anzahl der Dimensionen ab. Ich nehme an, Sie arbeiten im 2D- oder 3D-Raum.
Ein einfacher Ansatz wäre, ein einheitliches Gitter der Zellgröße zu bilden, sagen wir r. Dann binde alle Punkte auf ihre jeweiligen Zellen.
Jeder Abfragepunkt schneidet nur eine Handvoll Zellen, z. B. 9. Sie müssen nur die sich kreuzenden Zellen untersuchen, dann.
Ein effizienterer Ansatz wäre es, einen Quadtree oder KD-Baum zu konstruieren (es gibt viele andere Optionen, aber für 2D, Quadree oder KD-Tree würde es tun).
Das Überprüfen von Kreis-Rechteck-Schnittpunkten ist bei hierarchischen Strukturen erforderlich, aber dies wird im KD-Tree nearest neighbour-Algorithmus beschrieben (Sie müssen diesen nur geringfügig ändern).
Wenn Sie wirklich an der Leistung interessiert sind, können Sie mehrere Gitter (verschoben oder gedreht) konstruieren und immer diejenige mit der Zelle auswählen, die am meisten auf den Punkt zentriert ist, so dass die Suche auf die kleinste Anzahl von Zellen beschränkt ist / p>