Polygone zusammenfassen

[bernhard_LA]

ich benötigen einen Algorithmus um effektiv zwei Polygone zusammen zufassen.
Meine Polygone bestehen aus N-Punkten, PointF (Float Werte), was man unter http://msdn.microsoft.com/en-us/libr...(v=vs.85).aspx fiundet sieht sehr interesant aus , ich hätte hierzu gerne den Algorithmus.

[Medium]

Was für einen Algo? Den, der hinter dieser API Funktion steht, oder ein Anwendungsbeispiel für diese? (Am Rande: Die WinAPI Regions arbeiten nur mit Integern.)

[Aphton]

Ein naiver Ansatz wäre, per FloodFill Algorithmus (ohne Färbung) die Ränder entlang zu tracen, bis man an einem Punkt ankommt, wo man schon war.
Ein anderer wäre, eine Boolean Matrix aufzubauen und beide Polygone drinnen abzubilden. Dann wieder die Ränder entlangfahren, bei Änderungen Punkte
aufzeichnen usw usf.

[Memnarch]

Also, wenn du Polygone menst, hast du sicherlich auch Punktarrays.

Erste Frage: Sind die Formen immer Convex oder können sie auch Concave sein?
-> http://www.mathsisfun.com/definitions/convex.html

Convex(mein theoretischer ansatz)
Hier musst du erstmal herausfinden, welche kannten(verbindung zweiterpunkte) sich überlappen.
Am schnittpunkt fügst du dann bei beiden einen zusätzlichen Punkt ein der die Kante damit nochmal unterteilt.

Danach überprüffst du, welche Punkte von Form A in FormB liegen, diese merkst du dir. Danach guckst du, welche Punkte von Form B in Form A liegen, die merkst du dir auch.

Dan löscht du alle gemerkten punkte, und vereinst die schnittpunkte, die direkt übereinanderlagen.

[bernhard_LA]

Hallo Zusammen,


danke schon mal für die Inputs:


a) ich habe als Punkt einen Datentyp

Delphi-Quellcode:

        FPoint = record
                 x : Real;
                 y : Real;
                end;

ich denke die MSDN Lösungen spielen nur deshalb so schnell, weil ich bei Integer und einer gegebenen Screen resolution, ein festes Bitarray als Unterlage eh schon haben und damit dann mit wenigen Zahlen (Pixeln / Pixelzeilen) rechnen kann


b) meine Polygone können schon mal 1000 ... 5000 Stützpunkte haben, alle Algorithmen die Schnittpunkte berechnen werden in meinem Fall vermutlich elend langsam werden ....

[Sir Rufo]

Es gibt eine freie Lib für Polygone mit Integer-Punkten

http://sourceforge.net/p/polyclippin...hi/clipper.pas

Evtl. kannst du die auf Float umschreiben