Ich stelle diese Fragen aus Neugier, denn meine schnelle und schmutzige Umsetzung scheint gut genug zu sein. Aber ich bin gespannt, was eine bessere Umsetzung wäre.
Ich habe eine Grafik von realen Daten. Es gibt keine doppelten X-Werte und der X-Wert erhöht sich mit einer konsistenten Rate im Diagramm, aber die Y-Daten basieren auf der tatsächlichen Ausgabe. Ich möchte den nächsten Punkt in der Grafik von einem beliebigen gegebenen Punkt P programmgesteuert finden. Ich versuche einen effizienten (dh schnellen) Algorithmus dafür zu finden. Ich brauche nicht den genauesten Punkt, ich kann mich mit einem Punkt begnügen, der "fast" der nächste Punkt ist.
Die offensichtlich faule Lösung besteht darin, durch jeden einzelnen Punkt in der Grafik zu inkrementieren, die Entfernung zu berechnen und dann das Minimum der Entfernung zu finden. Dies könnte jedoch theoretisch für große Graphen langsam sein; zu langsam für das, was ich will.
Da ich nur einen ungefähren nächsten Punkt benötige, stelle ich mir vor, dass die ideale schnellste Gleichung die Erzeugung einer Anpassungsgeraden und die Verwendung dieser Linie zur Berechnung des Punktes in Echtzeit beinhalten würde; aber das klingt wie ein potenzieller mathematischer Kopfschmerz, den ich nicht übernehmen werde.
Meine Lösung ist ein Hack, der nur funktioniert, weil ich annehme, dass mein Punkt P nicht willkürlich ist, und ich nehme an, dass P normalerweise nahe an meiner Graphlinie liegt und wenn das passiert, kann ich die entfernten X-Werte aus der Betrachtung streichen. Ich berechne, wie nahe der Punkt auf der Linie ist, die die X-Koordinate mit P teilt, und benutze den Abstand zwischen diesem Punkt und P, um den größten / kleinsten X-Wert zu berechnen, der möglicherweise engere Punkte sein könnte.
Ich kann nicht anders, als zu glauben, dass es einen schnelleren Algorithmus als meine Lösung geben sollte (was nur nützlich ist, weil ich 99% der Zeit vermute, dass mein Punkt P ein Punkt nahe der Linie ist). Ich habe versucht, nach besseren Algorithmen zu suchen, aber ich habe so viele Algorithmen gefunden, die nicht so gut passten, dass es schwer war, das zu finden, was ich suchte, trotz der vielen unsauberen Algorithmen. Hat jemand hier einen Algorithmus, der effizienter wäre? Denken Sie daran, ich brauche keinen vollständigen Algorithmus, da, was ich für meine Bedürfnisse arbeite, ich bin nur neugierig, was die richtige Lösung gewesen wäre.
Wenn Sie eine Datenstruktur verwenden können, sind einige allgemeine Datenstrukturen für die räumliche Suche (einschließlich des nächsten Nachbarn) ...
Der r-Baum kommt in einer Anzahl von Varianten. Es ist sehr eng mit dem B + Baum verwandt, aber mit (abhängig von der Variante) verschiedenen Ordnungen auf den Punkten in den Blattknoten.
Der Hilbert R-Baum verwendet eine strikte Anordnung von Punkten basierend auf der Hilbert-Kurve. Die Hilbert-Kurve (oder eher eine Verallgemeinerung davon) ist sehr gut darin, mehrdimensionale Daten zu ordnen, so dass nahe gelegene Punkte im Raum normalerweise in der linearen Ordnung in der Nähe sind.
Im Prinzip könnte die Hilbert-Ordnung angewendet werden, indem eine einfache Anordnung von Punkten sortiert wird. Die natürliche Clusterbildung würde bedeuten, dass eine Suche in der Regel nur einige ziemlich kurze Abschnitte im Array durchsuchen muss - mit der Komplikation, dass Sie herausfinden müssen, welche Bereiche sie sind.
Ich hatte einen Link für eine gute Arbeit über die Berechnung der Hilbert-Kurve, aber ich habe sie verloren. Eine Ordnung basierend auf Gray-Codes wäre einfacher, aber nicht so effizient beim Clustering. In der Tat gibt es eine tiefe Verbindung zwischen Gray-Codes und Hilbert-Kurven - das Papier, das ich verloren habe, verwendet Gray-Code-Funktionen ziemlich viel.
BEARBEITEN - Ich habe den Link gefunden - Ссылка
Wenn Sie die [x, y] Punkte in einem Quadtree speichern, können Sie den nächsten Punkt finden schnell (etwas wie O (log n)). Ich denke, das ist das Beste, was Sie tun können, ohne Annahmen darüber zu machen, wo der Punkt liegen wird. Anstatt den Algorithmus hier zu wiederholen, werfen Sie einen Blick auf diesen Link .
Ihre Lösung ist ziemlich gut. Wenn Sie untersuchen, wie die Punkte in y variieren, können Sie nicht die Anzahl der Punkte entlang der x-Achse berechnen, die Sie untersuchen müssen, anstatt eine willkürliche zu verwenden.
Tags und Links algorithm computational-geometry