Wie funktioniert Raumaufteilung Algorithmus für die Suche nach nächsten Nachbarn arbeiten?

Question

Für die nächsten Nachbarn zu finden, Space Partitioning einen der Algorithmen ist. Wie funktioniert es?

Angenommen, ich einen 2D-Satz von Punkten (x und y-Koordinaten), und ich bin ein Punkt (a, b) gegeben. Wie dieser Algorithmus der nächsten Nachbarn herausfinden würde?

Answer 1

Spacial Partitionierung ist eigentlich eine Familie von eng verwandten Algorithmen, die Partition Raum, so dass Anwendungen können die Punkte oder Polygone leichter verarbeiten.

Ich denke, es gibt viele Möglichkeiten, um Ihr Problem zu lösen. Ich weiß nicht, wie komplex Sie bereit sind, Ihre Lösung zu erstellen. Ein einfacher Weg wäre wahrscheinlich einen binären Baum schneiden den Raum in 2. Alle Punkte zu bauen zwischen einigen mittleren Ebene geteilt. Bauen Sie Ihren Baum durch Unterteilung rekursiv, bis Sie aus Punkten ausgeführt werden.

für die nächsten Nachbarn der Suche wird dann optimiert werden, da jede Überquerung des Baumes nach unten verengt den Suchbereich.

In einiger Literatur, sie nennen das ein kd Baum

Answer 2

Diese beiden Videos sollen helfen:

• Zu erklären, wie ein KD Baum aufgebaut ist: http://www.youtube.com/watch?v=T9h2KKJ_Pl8
• Zu erklären, wie ausführen nächste Nachbar Suche: http://www.youtube.com/watch?v=2SbVSxWGtpI