ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4439687
Jetzt (Chat):
46 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-

ZFX
Coding-Foren
Algorithmen und Datenstrukturen
unsortierte konvexe Polygone clippen
Normal
AutorThema
B.G.Michi Offline
ZFX'ler


Registriert seit:
07.03.2006

Bayern
409978663
unsortierte konvexe Polygone clippenNach oben.
Hallo,

ich brauch mal wieder eure Hilfe:
Gegeben sind die Eckpunkte 2er Polygone, allerdings sind diese nicht im/gegen den Uhrzeigersinn sortiert (es ist bekannt welche Punkte zu Polygon1 und welche zu Polygon2 gehören). Beide Polygone liegen in einer Ebene.

Nun brauche ich das Schnittpolygon.
Im www hab ich nur Beispiele gefunden, die sortierte Polygone clippen, ich hatte nur die Idee die beiden Polygone zu sortieren (ala. Winkel zum Mittelpunkt finden, Quicksort oder sowas), allerdings kommt mir das etwas aufwändig vor.

Gibt es vlt. eine bessere Möglichkeit zum Clipping oder zum Sortieren?

thx JFF_B.G.Michi
19.12.2008, 14:53:23 Uhr
Lord Delvin Offline
ZFX'ler


Registriert seit:
05.07.2003

Baden-Württemberg
166781460
Re: unsortierte konvexe Polygone clippenNach oben.
Müssten die Polygone nicht in irgendeiner Graph-ähnlichen Form gegeben sein? Dann müsstest du ja nur entlang des Kreises laufen, den die Randpunkte bilden.

Sach mal was zur internen Repräsentation. dann is der Tipp vermutlich leichter zu geben.
19.12.2008, 23:59:35 Uhr
B.G.Michi Offline
ZFX'ler


Registriert seit:
07.03.2006

Bayern
409978663
Re: unsortierte konvexe Polygone clippenNach oben.
Graph-ähnliche Form? eigentlich isses nur ne listen von Punkten

Code:
std::vector Polygon;


aber hald nicht z.B. für das Viereck ABCD
Polygon[0]=A; Polgon[1]=B; ...
sondern hald durcheinander:
Polygon[0]=C; Polygon[1]=A; ...
20.12.2008, 15:58:22 Uhr
klickverbot Offline
ZFX'ler


Registriert seit:
24.08.2008

Österreich
Re: unsortierte konvexe Polygone clippenNach oben.
Und wie willst du definieren, zwischen welchen Eckpunkten die Kanten verlaufen? Jeweils zwischen den nächstgelegenen?

1 Mal gendert, zuletzt am 20.12.2008, 19:32:01 Uhr von klickverbot.
20.12.2008, 19:31:27 Uhr
B.G.Michi Offline
ZFX'ler


Registriert seit:
07.03.2006

Bayern
409978663
Re: unsortierte konvexe Polygone clippenNach oben.
dadurch das es sich um ein konvexes Polygon handelt gibt es nur eine möglichkeit in welcher Reihenfolge die Eckpunkte verbunden werden können. (das war was ich mit sortieren gemeint habe)
20.12.2008, 19:37:01 Uhr
Lord Delvin Offline
ZFX'ler


Registriert seit:
05.07.2003

Baden-Württemberg
166781460
Re: unsortierte konvexe Polygone clippenNach oben.
Aber willst du dann nicht eigentlich ne konvexe Hülle um eine Punktmenge?
Oder vielleicht sowas ähnliches...ich glaub du solltest dir das mit der konvexen Hülle mal anschaun und wenns das nicht ist, mal n Zettel und n papier nehmen und schaun ob das, was du willst überhaupt eindeutig aus deinen Daten hervor geht.
Gruß
LordD
20.12.2008, 20:06:27 Uhr
klickverbot Offline
ZFX'ler


Registriert seit:
24.08.2008

Österreich
Re: unsortierte konvexe Polygone clippenNach oben.
Die Einschränkung auf konvexe Polygone hatte ich überlesen.

Aus dem Bauch heraus würde ich sagen, dass das Problem eindeutig lösbar ist, mit einem fertigen Algorithmus kann ich dir aber leider auch nicht dienen.
20.12.2008, 20:28:56 Uhr
B.G.Michi Offline
ZFX'ler


Registriert seit:
07.03.2006

Bayern
409978663
Re: unsortierte konvexe Polygone clippenNach oben.
nochmal zur verdeutlichung, war vlt. auch von mir etwas schwammig erklärt:
http://img187.imageshack.us/img187/6368/polyox3.jpg

gegeben sind die beiden Polygone in folgender Form:
Code:
std::vector PolygonA; // {a1,a2,a3,...}
std::vector PolygonB; // {b1,b2,b3,...}


alle Punkte liegen in einer Ebene

gesucht ist das PolygonC:
{b1,c2,a6,a3,a5,c1,b4}

im Moment sortiere ich die einzelnen Polygone mit Hilfe der Winkel zu deren Mittelpunkten und clippe sie dann gegeneinander, allerdings hatte ich gehofft es gäbe vlt einen Algo der das etwas geschickter löst.

1 Mal gendert, zuletzt am 20.12.2008, 22:10:57 Uhr von B.G.Michi.
20.12.2008, 22:10:33 Uhr
Lord Delvin Offline
ZFX'ler


Registriert seit:
05.07.2003

Baden-Württemberg
166781460
Re: unsortierte konvexe Polygone clippenNach oben.
Das geht mit Punkten eigentlich garnicht, aber wenn du die Kanten betrachtest is es total billig, also probier mal das:

-Du transformierst die Kreisdarstellung von Punkten in eine Kantenmenge pro Kreis.
-Du läufst in einen Kreis solange die Kanten entlang bis du einen Knoten findest, der in beiden Kreisen vorkommt ab da:
-Solange du nicht wieder bei einem markierten Knoten bist fügst du alle Knoten des momentanen Kreises ein und markierst diese, bis du einen Knoten findest, der in zwei Kreisen vorkommt.
--Wenn du einen derartigen Knoten findest, dann musst du zwischen den Kreisen wechseln, die du entlangläufst.

Also ich denke es läuft auf sowas hinaus wie ein temporäres
struct{
nummer;
isInA;
isInB;
seen;
}
Für jeden Knoten in A u B.


Dann solltest du genau den roten Kreis erhalten.

Probiers mal aufm Papier aus und sach mir ob's funktioniert und das ist, was du machen wolltest.
Gruß
Timm
22.12.2008, 17:05:53 Uhr
B.G.Michi Offline
ZFX'ler


Registriert seit:
07.03.2006

Bayern
409978663
Re: unsortierte konvexe Polygone clippenNach oben.
es ist nur so dass c1 und c2 (im oberen bild) nicht schon gegeben sind, ich sortiere jetzt hald die polygone und schneide dann von einem nacheinander die punkte weg die außerhalb der kante des anderen liegen, funktioniert ganz gut soweit

ich hatte hald gehofft, dass ich um das sortieren rumkomm xD
22.12.2008, 19:14:40 Uhr
Normal


ZFX Community Software, Version 0.9.1
Copyright 2002-2003 by Steffen Engel