Krautkanal.com

Veröffentlicht am 2016-09-19 20:48:56 in /prog/

/prog/ 9212: kleinster Abstand zwischen Regionen

mutlu82 Avatar
mutlu82:#9212

Bern, ich habe einige Regionen auf einer Fläche. Sagen wir mal, es gibt eine Karte, z.B eine Tabelle oder 2D-Array für die Fläche; und jede Zelle, die der Anschaulichkeit halber für ein Pixel steht, mit der Zuordnung zur einer Region oder der Leere markiert ist. Wie ist da der Ansatz/Heuristik die minimale direkte (sprich in Sichtweite, also ohne "Hindernisse") Abstände und Pfade zwischen Regionen zu finden?

albertodebo Avatar
albertodebo:#9213

In der 10. Klasse nicht aufgepasst?

Zerlege je 2 Flächen in konvexe Formen (im simpelsten Fall Dreiecke),
für alle Eckpunkte die Distanzen bilden z12=√((x1-x2)²+(y1-y2)²),
merke dir die kleinste Distanz.

craigelimeliah Avatar
craigelimeliah:#9214

>>9213
ich habe keine Formen, ich habe Punkthaufen beliebiger und komplexer Form.

kimcool Avatar
kimcool:#9215

>>9214
Für alle Punkte einer Form zu allen Punkten einer zweiten Form die Distanz zu berechnen und das Minimum suchen geht nicht? Weil?

itskawsar Avatar
itskawsar:#9216

Also wenn A, B und C einfach nur Ansammlungen von Pixeln in einem Raster sind, die jeweil einem entsprechenden Label, dann wäre der naive Ansatz einfach für jeden Pixel in A den Pixel in B zu suchen (zwei for-Schleifen) der die kleinste euklidische Distanz hat.

Hättest du Vektordaten statt Rasterdaten, also die Punkte der Polygone, dann wirst du bestimmt im Bereich der Algorithmischen Geometrie ein Paper oder direkt einen Algorithmus zur minimalen Distanz zwischen zwei Punktmengen bzw. Polygonen.

mizhgan Avatar
mizhgan:#9217

>>9215
>>9216
Das ist der naive Ansatz, ich denke, dass das komplette Ausprobieren nicht so toll zu rechnen wäre.

Bis jetzt dachte ich mir, dass ich da eine Stange Vergleiche spare, wenn ich vorsortiere, also mir erst die Randpunkte jeder Region rauspicke und dann vergleiche.

Bleibt ja nur die Sache mit der direkter Sicht. Es scheint ja echt viele Vergleiche zu geben, wenn ich für jedes Paar(Randpunkt_A, Randpunkt_B) eine Linie Bilde und diese pixelweise durchgehe, ob da nicht zwischen noch Punkte aus C liegen.

Wäre der Ansatz mit einer sich von A steigernder Dilatation eventuell weniger rechenintensiv?

andyisonline Avatar
andyisonline:#9218

Halb-relevant: https://www.youtube.com/watch?v=OERYaFGBPbM

dmackerman Avatar
dmackerman:#9219

und etwas mathematischer Hintergrund
http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html

jqueryalmeida Avatar
jqueryalmeida:#9221

Das gibt einen ganz guten Überblick

>http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/Art_Gallery_Chapter_8.pdf

kriegs Avatar
kriegs:#9247

Hmm... Voronoi-Diagramm berechnen und dann im Voronoi-Diagramm nach der Kante mit dem kleinsten Abstand suchen?

Beachte: Das Voronoi-Diagramm von Linien-Segmenten (und damit Polygonen) besteht aus stückweisen Parabelbögen. Da müsste man dann auf dem Parabelbogen also noch den Punkt mit dem geringsten Abstand suchen (der zu beiden Polygonen gleich ist). Wenn ich mir das so anschaue, scheint das aber glücklicherweise immer der Scheitelpunkt zu sein. Macht für mich auch gefühlt Sinn, aber näher drüber nachgedacht habe ich nicht. Durch diesen Punkt müsste dann die kürzeste Verbindung gehen.

Für C++ hat z.B. Boost eine Implementierung [1] für Voronoi-Diagramme von Punkten und Liniensegmenten mit O(n log n) Laufzeit. Damit hätte der komplette Algorithmus auch eine Laufzeit von O(n log n). Ich denke nicht, dass es noch was effizienteres gibt.

[1] http://www.boost.org/doc/libs/develop/libs/polygon/doc/voronoi_main.htm

Neuste Fäden in diesem Brett: