Zerschneiden eines Polygons

[Hunk86]

Guten Tag zusammen,

ich hab ein beliebiges Polygon und würde dies gerne mit einer Geraden in zwei oder mehr Polygone zerschneiden.

Meiner ansicht nach sollte es so ein Algorithmus grad bei der Zerlegung von Polygonen schon lange geben. Ich hab mir auch schon alle interessanten Schnittpunkte etc berechnet, nur hab ich keine Idee wie diese wieder in Polygone umrechnen kann.

Vorallem bei innenwinkel größer 180 ist dies ein großes Problem.

Kennt da jemand einen fertigen Algorithmus für c++

oder hat eine Idee wie man sowas inteligent lösen kann?

 

[Quafe]

ja nennt sich Hardware-Tessellation und gibs seit 2010

 

[misu]

Ein Polygon ist doch bloß eine Liste von Punkten. Eine Zerlegung kannst du also machen, indem du die Punktliste partitionierst.

Für jede Partition müsstest du dann noch einen Schnitttest machen, um zu schauen, ob du das Polygon im Sinne einer Geraden zerlegt hast.

Als Resultat erhälst du alle zulässig zerlegten Polygone.

Das ganze ist natürlich lahm, aber da musst du dann dein Problem schon ein bischen genauer spezifizieren.

Ergänzung (21. März 2013)

Nachtrag: Viel einfacher. Einfach Punktliste an zwei beliebigen Stellen auftrennen. Die Auftrennungspunkte sind in beiden neuen Teilpolygonen. Beide Abschnitte zwischen den Auftrennungspunkten stellen die neuen Polygone dar. Da sie sich genau zwei Punkte teilen (Die Auftrennungspunkte), teilen sie sich genau eine Gerade, die Schnittgerade.

Bsp.: polygonpinkte a,b,c,d,e,f (a)
a, !b!,c,d,!e!,f => aufgetrennt an b und e
subpoly 1) bcde
subpoly 2) abef
beide beinhalten b und e, was die schnittgerade ist.

 

[Hunk86]

http://stackoverflow.com/questions/3623703/how-can-i-split-a-polygon-by-a-line

im endeffekt ist das dieses problem. Ich dachte nur dass es dafür eigentlich schon fertig Lösungen geben sollte.

Als idee hatte ich z.b. ein clipping verfahren wobei ich die linie als unendlich dünnes Polygon darstelle.

Wollte nur wissen ob vlt jemand doch was besseres dazu kennt

schonmal danke für eure antworten

 

[misu]

Les den Nachtrag zu meinem letzten Post

 

[Hunk86]

stimmt übersehen, ich hätte vlt noch erwähnen sollen dass das Polygon auch Löcher haben kann.

Was die Sache stark verkompliziert.

desweiteren funktioniert dies nicht bei einem convexen Polygon, wenn z.b. die schnittgerade durch ein Punkt geht, bei diesem der innenwinkel größer 180 ist. Bei so einem Fall gibt es 3 Schnittpunkte und eine Polygonaufteilung

 

[misu]

Was du durch Bestimmung der Schnittpunkte (und deren hinzufügen) wahrscheinlich lösen könntest.

Aber ja, das Problem für allgemeine Polygone ist recht kompliziert. Deswegen hat man ja auch fast immer nur konvexe.

 

[maxwell-cs]

in welcher form ist dein polygon denn spezifiziert?