Polygone schneiden

[juniorA]

moin, moin,

stehe wieder einmal auf den Schlauch.
Suche eine Funktion wie man 2 Polygone addiert und 2 Polygone subtrahiert. Bei der Subtraktion können dabei mehrere Polygone rauskommen, wenn ich z.B. Ein U in der Mitte waagerecht mit einen Balken schneide.

[Bjoerk]

Was man da zunächst mal braucht ist eine function, die den Schnittpunkt von 2 Geraden ermittelt. Den Rest habe ich nicht verstanden.

[juniorA]

Leider ist dieses nur die habe Miete.
Stell Dir vor, Du legst zwei Polygone übereinander welche eine L Form haben und die sollen Subtrahiert

IIII IIIIIIIIII IIII
I I I Poly2 I I I
I I IIIIIII I I I
I I - I I = I I
I IIIIIII I I I III
I Poly1 I I I I I
IIIIIIIIII IIII IIIIII

oder addiert werden

IIII IIIIIIIIII IIIIIIIIII
I I I Poly2 I I I
I I IIIIIII I I IIII I
I I + I I = I I I I
I IIIIIII I I I IIII I
I Poly1 I I I I I
IIIIIIIIII IIII IIIIIIIIII

[Sir Rufo]

Zitat von juniorA:

Leider ist dieses nur die habe Miete.
Stell Dir vor, Du legst zwei Polygone übereinander welche eine L Form haben und die sollen Subtrahiert

Code:

IIII             IIIIIIIIII       IIII
I  I             I Poly2  I       I  I
I  I             IIIIIII  I       I  I 
I  I         -         I  I     = I  I
I  IIIIIII             I  I       I  III 
I  Poly1 I             I  I       I    I
IIIIIIIIII             IIII       IIIIII

oder addiert werden

Code:

IIII             IIIIIIIIII       IIIIIIIIII
I  I             I Poly2  I       I        I 
I  I             IIIIIII  I       I  IIII  I 
I  I         +         I  I     = I  I  I  I
I  IIIIIII             I  I       I  IIII  I 
I  Poly1 I             I  I       I        I
IIIIIIIIII             IIII       IIIIIIIIII

Mit Code-Tags wird es halbwegs verständlich. Ein Bild wäre wohl besser geeignet (kann hier auch direkt hochgeladen werden)

[Uwe Raabe]

Das ist nicht mal eben so zu beantworten. Wenn du bereit bist, dich einzuarbeiten: vor langer Zeit habe ich sowas in der Art mal für die Klasse TGLMultiPolygon in GLScene implementiert.

[juniorA]

Habe gerade gesehen, dass die Skizze nicht OK ist also

[Namenloser]

Das wird vermutlich wirklich nicht mal eben schnell gemacht sein. Ich habe auch seit Monaten (arbeite aber nur selten daran) sowas ähnliches in Arbeit, wobei es bei mir etwas anders ist: Ich will eigentlich ein Polygon in Dreiecke zerlegen – aber da ich auch Polygone unterstützen möchte, die sich selbst schneiden, habe ich da ein ähnliches Problem.

Vielleicht ist es hilfreich, sich vorher mal anzusehen, wie überhaupt definiert ist, ob ein Punkt sich innerhalb eines Polygons befindet. Empfehlenswerte Lektüre.

Dann kann man sich überlegen, was sich daran ändert, wenn man ein Polygon zu einem anderen hinzuaddiert – wie unterscheidet sich die Wirkung der Linien dieses Polygons? Skizzen auf Papier helfen immer. Noch ein Tipp: Es könnte helfen, ein Polygon nur als einen Haufen Strecken anzusehen und nicht als ein zusammenhängendes Gebilde – damit sind Polygone, die aus mehreren, getrennten „Inseln“ bestehen, kein Spezialfall mehr.

Damit müsste man sich was zusammenbasteln können.

[Popov]

Also die Antwort bezieht sich weniger auf Polygone als auf Schriften (sind aber auch Polygone). Ich hab mich mal dafür interessiert wie Schriften berechnet werden. So enthält der Buchstabe "B" drei Polygone, also das B ohne Öffnungen und die zwei Halbkreise. Hier hört es aber schon wieder auf mit den Polygonen. Diese werden in Pixel umgerechnet und - ich glaube mit XOR - berechnet. Wo nicht ist, ist False. Wo nur ein Polygon ist, ist True. Überschneiden sich zwei Polygone, ist an der Stelle wieder False. So führt jede neue Lage zum erneuten Wechsel der Farbe.

[Sir Rufo]

Hier etwas akademische Lektüre dazu.

Und wer keine Zeit dafür hat, der geht direkt hierhin

[Aphton]

Noch mehr Quellen, zum Nachlesen:
Quelle 1
Quelle 2