Inneres eines Polygons: Geometrien korrigieren

Treue Seele

29.04.2011, 12:03

Inneres eines Polygons: Geometrien korrigieren

Hi,

ich habe ein Polygon, innerhalb dessen ich ein weiteres Polygon zeichne, die Kanten dieses inneren Polygons sind dabei immer gleich weit von den Äußeren entfernt.

Das funktioniert schon mal ganz prima, allerding gibt es ein paar Sonderfälle, in denen jetzt zusätzliche Maßnahmen notwendig sind:

(Link)

Ausgangspunkt ist das rote Polygon, aktuell erzeugt meine Funktion als inneres Polygon das violett Gezeichnete. In diesem besonderen Fall sorgt die Regel, dass die Kanten überall den gleichen Abstand haben müssen, für ein Problem: eigentlich ist das sich ergebende, innere Polygon nicht die violette Linie sondern die beiden Dreiecke links und rechts, das Dreieck unten müsste mit allen Kanten wegfallen.

Was ich jetzt suche, ist eine Regel, um sowas zu ermitteln.

Eine Idee wäre es, zu überprüfen, ob sich das Ergebnis-Polygon irgend wo mit sich selbst schneidet. Aber was dann? Wie sehe ich, welche Kanten in mehrere Teile zerlegt (die Linie ganz unten) werden und welche Teile dieser Kante entfernt werden müssen (im Beispiel das Mittelteil der Linie ganz unten)?. Bzw. wie erkenne ich, welche Seite der sich schneidenden Linien "außerhalb" liegen und dewegen entfernt werden müssen?

Es ist jede Art von Denkanstoß willkommen :-)

Zum Seitenanfang

Community-Fossil

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

29.04.2011, 12:43

Eigentlich doch trivial: Wenn sich zwei Kanten schneiden, die sich nicht den gleichen Vertex teilen, dann hast Du einen Sonderfall

Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

29.04.2011, 12:55

Hast du nicht schonmal vor ein paar Wochen genau das Gleiche gefragt!?

Naja, wenn die Vertices des Ausgangspolygons z.B. im Uhrzeigersinn geordnet sind dann sind alle Teilpolygone die du entfernen musst gegen den Uhrzeigersinn und die anderen wieder im Uhrzeigersinn geordnet.

Man kann es sicher auch irgendwie lösen indem man zählt wie oft man am Schnittpunkt zweier Linien vorbeigekommen ist (z.B. gerade Anzahl -> bleibt stehen, ungerade Anzahl -> wird gelöscht, hängt vom Startpunkt ab), aber sich das genau zu überlegen überlass ich mal dir

m4studios

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »dot« (29.04.2011, 13:01)

Zum Seitenanfang

Treue Seele

01.05.2011, 22:45

Zitat von »dot«

Hast du nicht schonmal vor ein paar Wochen genau das Gleiche gefragt!?

Nein, habe ich nicht - da ging es um andere Schnittkanten.

Zitat

Naja, wenn die Vertices des Ausgangspolygons z.B. im Uhrzeigersinn geordnet sind dann sind alle Teilpolygone die du entfernen musst gegen den Uhrzeigersinn und die anderen wieder im Uhrzeigersinn geordnet.

Die Orientierung ist in jedem Fall gleich, daran lässt sich nichts erkennen. D.h. sowohl das innere Polygon als auch die Teilpolygone haben allesamt die gleiche Orientierung.

Zum Seitenanfang

Treue Seele

01.05.2011, 22:46

Zitat von »BlueCobold«

Eigentlich doch trivial: Wenn sich zwei Kanten schneiden, die sich nicht den gleichen Vertex teilen, dann hast Du einen Sonderfall

Ähm nein, es geht ja nicht einfach nur darum zu erkennen, wo sich das innere Polygon mit dem äußeren schneidet - das ist vollkommen irrelevant, da - abhängig von der Form des Polygons - so ein Schnittpunkt ja gar nicht vorkommen muss und trotzdem das innere Polygon "überflüssige" Geometrien erzeugen könnte.

Die Frage ist, wie erkenne ich, dass (im Beispielbild oben) das violette Dreieck, welches sich unten in der Mitte bildet, die Regel mit dem gleichmäßigen Abstand zum Rand bricht und deswegen entfernt werden muss.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Elmi« (01.05.2011, 23:15)

Zum Seitenanfang

Community-Fossil

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

02.05.2011, 06:47

Zitat von »Elmi«

Ähm nein, es geht ja nicht einfach nur darum zu erkennen, wo sich das innere Polygon mit dem äußeren schneidet - das ist vollkommen irrelevant, da - abhängig von der Form des Polygons - so ein Schnittpunkt ja gar nicht vorkommen muss und trotzdem das innere Polygon "überflüssige" Geometrien erzeugen könnte.

Nein. Ich habe nie davon gesprochen, dass das innere Polygon das äußere schneiden muss, sondern dass die Kanten des inneren sich gegenseitig schneiden, obwohl sie kein Vertex teilen. Das ist etwas ganz anderes.
In Deinem Fall da oben musst Du ja auch nicht das komplette violette Polygon entfernen, sondern nur einen Teil davon, Du musst es splitten in 3 Dreiecke von denen eins weg fällt anhand der Regel, die ich bereits beschrieben habe und bei der übrigens auch genau das gilt, was dot schon erwähnte. dot ist allerdings schon einen Schritt weiter als ich, denn vor der Orientierungs-Richtung benötigt man zuerst die Schnitte.

Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Zum Seitenanfang

Treue Seele

02.05.2011, 07:54

OK, hat sich erledigt, ich habe eine Regel gefunden, nach der man ermitteln kann, welche Geometrien überflüssig sind.

Zum Seitenanfang

Community-Fossil

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

02.05.2011, 07:56

Wie ich schon sagte, überflüssig ist dieses Polygon keineswegs, es muss geteilt werden in 3 Dreiecke von denen eines entfernt werden muss.

Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

02.05.2011, 11:57

Zitat von »Elmi«

Zitat

Naja, wenn die Vertices des Ausgangspolygons z.B. im Uhrzeigersinn geordnet sind dann sind alle Teilpolygone die du entfernen musst gegen den Uhrzeigersinn und die anderen wieder im Uhrzeigersinn geordnet.

Die Orientierung ist in jedem Fall gleich, daran lässt sich nichts erkennen. D.h. sowohl das innere Polygon als auch die Teilpolygone haben allesamt die gleiche Orientierung.

Nein, wenn die Vertices anfangs richtig sortiert sind und die neuen Schnittpunkte richtig eingefügt sind dann kannst dus an der Orientierung erkennen. Die Frage ist lediglich wie du die Orientierung am Besten erkennst.

Was mir sonst noch einfällt: Alle Kanten deren Start- und Endpunkte Schnittpunkte des Polygons mit sich selbst sind löschen und mit ihnen die Polygone die diese Kanten verwenden. Ich denke das sollte auch funktionieren.

Zitat von »Elmi«

OK, hat sich erledigt, ich habe eine Regel gefunden, nach der man ermitteln kann, welche Geometrien überflüssig sind.

Und die lautet?

m4studios

Zum Seitenanfang

Community-Fossil