Finde den nächsten Nachbarn in einem Radius

Question

Ich habe eine Reihe von Punkten a in meinem Raum (Geo-Punkte, aber ich kann davon ausgehen, dass sie sich auf einem 2D-Flugzeug befinden).

Ich habe einen anderen Satz von Punkten b .

Für jeden Punkt in b möchte ich jeden Punkt in a in einem Radius r mit dem Zentrum im betrachteten Punkt von B set.

Ich habe es mit kdtree gemacht, dies gibt mir einen sehr schnellen und leichten Algorithmus, um die Datenstruktur zu erstellen und Nachbarn zu finden, aber es gibt nicht jeden Punkt in einem Radius, da er einen Pfad vermeiden könnte das Element in meinem Radius enthält, aber nicht in derselben Teilmenge des Radiuszentrums.

minimales Beispiel von kdtree fehlgeschlagen :

Bei der Erkundung von KDTree befindet sich der Zielpunkt (rot) unter der Linie der Punktzahl 1. Dieser wird zur Erkundung des Punkts unter der Zeile geliefert, dadurch wird der eigentliche Punkt im roten Punktradius verpasst.

Welcher Algorithmus oder eine Datenstruktur ermöglichen 100% Richtigkeit?

Ich weiß, dass ich sicher noch schlimmer werde, aber ich suche nach einem Gleichgewicht zwischen der Suchgeschwindigkeit und voller Richtigkeit.

Answer 1

Der K-D-Baum ist eine gute Datenstruktur, um dies zu lösen.Sie können den Suchverfahren jedoch nicht nur blind auf den Mittelpunkt anwenden, Sie müssen ein bisschen intelligenter sein.

Während Sie den KD-Baum für Ihre Punkte durchsuchen, jedes Mal, wenn Sie das linke oder rechte Kind auswählen müssen, um zu suchen, prüfen Sie, ob die Spaltebene links von Ihrem Kreis vorhanden ist, oder ist das Recht des Kreises.

Wenn sich die Spaltebene links von Ihrem Kreis befindet, müssen Sie weiter im rechten Kind suchen, und umgekehrt.Wenn jedoch die Spaltflugzeug Ihren Kreis schneidet Ihr Kreis, müssen Sie beide kinder suchen.