Algorithmus, um für alle Punkte in Menge A den nächsten Nachbarn in Menge B zu finden

1. Finden Sie das Voronoi-Diagramm für die Punkte von Menge B.
2. Wenden Sie einen Sweep-Zeilenalgorithmus über die Punkte des A- und Voronoi-Diagramms von B an. Überall dort, wo die Sweep-Linie einen bestimmten Punkt abdeckt Aus der Menge A, schauen Sie, zwischen welchen Kanten des Voronoi-Diagramms sich dieser Punkt befindet. Dies ermöglicht zu bestimmen, zu welcher Seite des Voronoi-Diagramms dieser Punkt gehört. Das gibt den nächsten Punkt aus Menge B.

Details für Schritt 2: Behalte alle Kanten des Voronoi-Diagramms, die derzeit von der Sweep-Linie geschnitten werden, in einem bestimmten geordneten Container. Wenn die Sweep-Linie einen Scheitelpunkt des Voronoi-Diagramms abdeckt, entfernen Sie Kanten, die zu diesem Scheitelpunkt gehören, vom / zum Container. Um zu sehen, zwischen welchen Kanten ein Punkt liegt, erhalten Sie im Container die Nachfolger / Vorgänger-Kanten.

Die Zeitkomplexität ist O ((M + N) log M). N = | A |, M = | B |.

Sie können davon profitieren, wenn Sie Bentleys lesen, die "effiziente Programme schreiben", in denen er sich mit einer Fallstudie des Programms für Geschäftsreisenden beschäftigt. Eine der Ersparnisse, die er erkannte, war, dass der Unterschied zwischen zwei Punkten darin bestand, eine Quadratwurzel zu nehmen, die teuer war. Wenn Sie die Quadratwurzel verwenden, erhalten Sie die tatsächliche Entfernung. Wenn Sie nicht die Quadratwurzel verwenden, erhalten Sie eine Zahl, die Sie zum Vergleich mit anderen relativen Werten verwenden können.

Ich empfehle dringend, das Buch zu lesen. Es wird dein Gehirn an den richtigen Ort bringen.

Eine Brute-Force-Lösung könnte sein, ein Dendogramm der nächsten Punkte von Set B zu verwenden. Dann vergleiche jeden Punkt von Set A mit dem Dendogramm. Sie können das Dendogramm auch mit einer Delaunay-Triangulation erstellen.