Nächster Punkt zu einem bestimmten Punkt

Question

Ich habe eine Menge K von zufällig ausgewählten Pixeln in einem 2D-Bild. Für jedes andere Pixel im Bild muss ich herausfinden, welches Pixel in Menge K ihm am nächsten kommt (mit dem Standardmaß sqrt (dx^2 + dy^2)). Mir ist bewusst, dass es für jedes Pixel mehr als eine Lösung geben kann. Offensichtlich kann es mit roher Gewalt gegen jedes Pixel im Set getan werden, aber ich würde das lieber vermeiden, da es nicht effizient ist. Irgendwelche anderen guten Vorschläge?

Prost.

Answer 1

Vergessen Sie nicht, dass Sie sich nicht mit der Quadratwurzel beschäftigen müssen.

Wenn Sie nur die nächste (und nicht die tatsächliche Entfernung) finden möchten, verwenden Sie einfach dx^2 + dy^2, die Ihnen die Entfernung im Quadrat zu jedem Element geben wird, die genauso nützlich ist.

Wenn Sie keine Datenstruktur haben, die diese Liste von Pixeln umhüllt, müssen Sie nur gegen sie alle testen.

Wenn Sie etwas Flexibilität haben, gibt es viele gute Möglichkeiten, die Arbeitslast zu reduzieren. Machen Sie eine Quadtree, oder halten Sie eine sortierte Liste der Pixel (sortiert nach x und sortiert nach y), um Ihre Suche schneller einzuschränken.

Answer 2

Dies wird die nächste Nachbarsuche genannt. Donald Knuth nannte es das Post-Office-Problem.

Es gibt eine Reihe von Lösungen: lineare Suche, ortssensitives Hashing, Vektorapproximationsdateien und Raumpartitionierung.

Googeln diese sollten helfen.

Answer 3

Je nachdem, wie dicht diese Grafik mit Pixeln gefüllt ist, ist es möglicherweise besser, nur nach dem Ursprungspunkt zu suchen.

Ich habe so etwas für eine grafische Terminal-Emulation programmiert. Am Ende programmierte ich ein Suchmuster in Form einer quadratischen Spirale, die vom Mittelpunkt ausging, und ließ es wachsen, bis es auf etwas traf. Das war ausreichend schnell für den Zweck, sogar auf einer alten CPU.

Answer 4

Noch ein Hinweis: Der Abstand ist immer größer oder gleich jeder Unterschied koordinieren und immer kleiner oder gleich ihrer Summe, das heißt

d >= dx, d >= dy, d <= dx + dy. 

Dies könnte Ihnen helfen, die Sortierung effizienter machen.

Answer 5

, was Sie versuchen zu tun, bauen ein voronoi diagram diese (n log n) in O getan werden kann, mit einem plane sweep

Answer 6

Der Bau von Voronoi Diagrams ein Zweig der Computational Geometry ist. Die Konstruktion von Delaunay Triangulations beinhaltet ähnliche Überlegungen. Sie können möglicherweise eines der folgenden Delaunay algorithms an Ihre Bedürfnisse anpassen.

• Flip Algorithmen
• Incremental
• Teile und herrsche
• Sweepline

Answer 7

Setzen Sie die Punkte in einem KD Baum, nachdem diese es sehr schnell ist der nächste Nachbar zu finden.Siehe this Artikel auf Wikipedia für Details.

Answer 8

Ich werde mit jk und Ewan mit einer Voronoi Diagram übereinstimmen müssen. Dadurch wird das Leerzeichen in Polygonen aufgeteilt. Jeder Punkt in K wird ein Polygon haben, das alle Punkte beschreibt, die ihm am nächsten sind. Jetzt, wenn Sie eine Abfrage eines Punktes erhalten, müssen Sie herausfinden, in welchem ​​Polygon es liegt. Dieses Problem wird Point Location genannt und kann durch den Aufbau einer Trapezoidal Map gelöst werden.

jk bereits verknüpft mit der Erstellung der Voronoi Diagram mit Fortune's algorithm, die O (n log n) Rechenschritte und kostet O (n) Raum. This website zeigt Ihnen, wie Sie eine trapezförmige Map erstellen und abfragen. Sie können auch einige Grenzen dort finden:
Erwartete Erstellungszeit: O (n log n)
Erwartete Speicherkomplexität: O (n)

Aber am wichtigsten ist, erwartete Abfragezeit: O (log n). Dies ist (theoretisch) besser als O (√ n) des kD-Baumes.

Meine Quelle (außer den Links oben) ist: Computational Geometry: algorithms and applications, Kapitel sechs und sieben.

Dort finden Sie detaillierte Informationen zu den beiden Datenstrukturen (inklusive detaillierter Proofs). Die Google Bücher Version hat nur einen Teil von dem, was Sie brauchen, aber die anderen Links sollten für Ihren Zweck ausreichen. Kaufen Sie das Buch einfach, wenn Sie an so etwas interessiert sind (es ist ein gutes Buch).