Voronoi-Diagramme

[striderx]

Zur Zeit befasse ich mich mit Voronoi-Diagrammen.

Ein brute-force-Ansatz zum Füllen der Zellen ist ja recht schnell geschrieben, was mir aber fehlt ist ein Algorhitmus zur Bestimmung der Eckpunkte des jeweiligen Hüll-Polygons.

Hat jemand soetwas in seinem Fundus?

[Medium]

Ich wage mal zu bezweifeln, dass es da einen expliziten Algo für gibt. Alle Voronoi bzw. Delauney Algos die ich bisher gesehen habe basieren in einer oder anderer Weise immer auf inkrementellen Verfahren. Bei letzterem hat man nachher zwar wirklich Punkte an der Hand, aber soweit ich weiß sind die zwei Algos zwar dual zueinander, aber man kann nicht auf einfache Weise von der Triangulierung auf die Eckpunkte des bei Voroni enstehendes "Gitters" überführen. Das Einzige was mir da einfiele wäre nachträgliche Vektorisierung. Zwar unelegant, auflösungsabhängig und nicht wirklich präzise, aber mir fällt im Moment nichts schlaueres ein.

[Rollo62]

Leider nichts in Delphi, aber vielleicht ist hier was für dich dabei.
https://kynosarges.org/Tektosyne.html
https://github.com/christianbender/Algorithms-1
http://jeffe.cs.illinois.edu/compgeom/code.html

[striderx]

@Medium

Die nachträglich Vektorisierung wird u. a. auch dadurch schwierig, dass der brute-force-Ansatz keine glatten Kanten erzeugt sondern teilweise starke Treppen. Man könnte versuchen, die Stellen zu finden, an denen drei oder mehr Farben aneinander treffen (Sonderfall Ränder), dann weiß mann aber immer noch nicht, welche solcher Punkte zu welcher Zelle gehören.


@Rollo 62

Danke für die Links, nach einer ersten Prüfung bringen sie mich aber nicht weiter.

[TigerLilly]

Der Algorithmus auf Wikipedia hilft dir nicht?
https://de.wikipedia.org/wiki/Voronoi-Diagramm

Was hast du denn an Daten?

[striderx]

Zitat von TigerLilly:

Der Algorithmus auf Wikipedia hilft dir nicht?
https://de.wikipedia.org/wiki/Voronoi-Diagramm

Was hast du denn an Daten?

Na, wenn da z. B. steht "Berechne KH(P') //Mit geeignetem Algorithmus" dann fehlt mir halt der geeignete Alogrhitmus (und nicht nur an dieser Stelle).

Ich bin mir nicht sicher, was du mit 'Daten' meinst. Ich habe natürlich die Koordinaten der 'Zellkerne ('sites') und die Farben der jeweiligen Zellen (jeweils Farbe des Kerns).

[TigerLilly]

Vielleicht helfen diese Links?

http://tizian.cs.uni-bonn.de/publica...udsonKlein.pdf
http://algo.informatik.uni-freiburg..../slides/11.pdf
https://lernprocessing.wordpress.com...noi-diagramme/
http://www.pi6.fernuni-hagen.de/down...s-vdlap-02.pdf

Aber das war jetzt nur gegoogelt + das hast du wahrscheinlich auch gemacht.

Ach ja:
https://rosettacode.org/wiki/Voronoi_diagram#Delphi