nearest neighbor - k-d-Baum - wikipedia Beweis
Auf dem wikipedia-Eintrag für k-d-Bäume, wird ein Algorithmus vorgestellt, für eine nächste-Nachbar-Suche auf einem k-d-Baum. Was ich nicht verstehe, ist die Erklärung von Schritt 3.2. Wie Sie wissen, gibt es nicht einen Punkt näher, gerade weil der Unterschied zwischen den splitting-Koordinate der Suche nach Punkt und der aktuelle Knoten ist größer als die Differenz zwischen dem splitting-Koordinate der Suche nach Punkt und die aktuelle besten?
Nächste-Nachbar-Suche-Animation
NN-Suche mit einem KD-Baum 2D -Nächsten Nachbar (NN) - Algorithmus
Ziele um den Punkt zu finden in dem Baum
die am nächsten zu einer gegebenen Eingabe
Punkt. Diese Suche kann getan werden
effizient mit dem Baum
Eigenschaften, die zu beseitigen Sie schnell große
Teile des suchraums.
Die Suche nach einem nächsten Nachbarn in einem
kd-Baum wie folgt vorgegangen:
- Beginnend mit dem Wurzelknoten, der Algorithmus bewegt sich nach unten den Baum
rekursiv, in der gleichen Weise, dass es
wenn der Suchpunkt wurden
eingefügt (d.h. es geht rechts oder Links
je nachdem, ob der Punkt
größer oder kleiner als der aktuelle Knoten
in der split dimension).- Sobald der Algorithmus erreicht einen Blatt-Knoten, der es speichert, dass der Knoten Punkt als
die "aktuellen " besten"- Der Algorithmus läuft die Rekursion des Baumes, die Durchführung der
folgenden Schritte auf jedem Knoten:
1. Wenn der aktuelle Knoten ist näher als die aktuellen besten sind, dann ist es
wird die aktuelle am besten.
2. Der Algorithmus überprüft, ob es sein könnte, keine Punkte auf
die andere Seite der splitting-plane
näher an der Suche Punkt
als die zurzeit beste. Konzept,
dies wird durch die sich kreuzenden
splitting-hyperplane mit einem
hypersphäre um die Suche Punkt
das hat einen radius gleich dem aktuellen
nächste Entfernung. Da die
hyperplanes sind alle axis-aligned diese
implementiert ist als ein einfacher Vergleich
um zu sehen, ob der Unterschied zwischen
die splitting-Koordinate der Suche
Punkt und aktuelle Knoten weniger als
die Distanz (Globale Koordinaten)
von der Suche an der aktuellen
best.
1. Wenn die hypersphäre überquert das Flugzeug, es könnte sein
näher die Punkte auf der anderen Seite der
Flugzeug, so muss der Algorithmus nach unten verschieben
der andere Zweig des Baumes, aus dem
aktuellen Knoten suchen, näher
Punkte, die gleiche rekursive
Prozess, da die gesamte Suche.
2. Wenn die hypersphäre nicht den Schnittpunkt mit der splitting plane,
dann der Algorithmus weiter zu Fuß
oben auf dem Baum, und der gesamte Zweig auf
die andere Seite von diesem Knoten ist
beseitigt.- Wenn der Algorithmus beendet ist dieser Prozess für den root-Knoten, dann die
Suche abgeschlossen ist.In der Regel verwendet der Algorithmus mit quadrierten
Entfernungen für den Vergleich zu vermeiden
computing Quadratwurzeln. Darüber hinaus
es kann speichern Sie die Berechnung durch das gedrückt halten der
squared aktuelle beste Entfernung in einer
Variablen für den Vergleich.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Schauen Sie genau auf dem 6. Bild des animation auf dieser Seite.
Als der Algorithmus geht zurück bis die Rekursion ist es möglich, dass es eine engere Stelle auf der anderen Seite des hyperplane, dass es auf. Wir haben überprüft, die eine Hälfte, aber es könnte eine noch engere Punkt auf der anderen Hälfte.
Gut, es stellt sich heraus, dass wir manchmal eine Vereinfachung. Wenn es unmöglich, damit es zu einem Punkt auf der anderen Hälfte näher, als unseren derzeit besten (am nächsten) Punkt, dann können wir überspringen, dass hyperplane Hälfte völlig. Diese Vereinfachung ist in der Abbildung auf der 6. frame.
Herauszufinden, ob diese Vereinfachung möglich ist, erfolgt durch Vergleich der Entfernung von der hyperplane zu unserer Suchmaschine Lage. Da die hyperplane ist ausgerichtet auf die Achsen, die kürzeste Linie, von der Sie zu jedem anderen Punkt wird eine Linie entlang einer dimension, so können wir vergleichen nur die Koordinate der dimension, der hyperplane-splits.
Wenn es weiter von der Suche zeigen Sie auf der hyperplane als von der Suche zeigen Sie auf Ihrer aktuellen nächsten Punkt, dann gibt es keinen Grund zu der Suche nach Vergangenheit, dass die Spaltung koordinieren.
Selbst wenn meine Erklärung nicht hilft, wird die Grafik. Viel Glück auf Ihr Projekt!
Ja, die Beschreibung von NN (Nearest Neighbour) Suche in einem KD-Tree auf Wikipedia ist ein wenig schwer zu Folgen. Es hilft nicht, dass eine viel der top-Google-Suchergebnisse auf NN KD-Baum sucht, sind schlicht und einfach falsch!
Hier einige C++ - code zu zeigen, wie Sie es richtig:
API für die NN-Suche auf einen KD-Baum:
Standard-Distanz-Funktion:
Edit: einige Leute Fragen nach Hilfe bei der Daten-Strukturen (nicht nur der NN-Algorithmus), so hier ist, was ich verwendet habe. Je nach Zweck haben, möchten Sie vielleicht ändern Sie die data-Strukturen leicht. (Anmerkung: aber Sie fast sicher nicht möchten, ändern Sie die NN-Algorithmus.)
KDPoint Klasse:
KDNode Klasse:
KDTree Klasse: (Hinweis: Sie benötigen zum hinzufügen einer member-Funktion zu bauen/füllen Sie Ihren Baum.)
distance(point, node->leaf->point);
Ich denke, dass dies auch füllen des Arrays Punkt mit allen Punkten in diesem Teilbereich? Könnten Sie bitte etwas näher erläutern?