Schneiden zweier Polygone
-
Hallo!
Folgendes Problem: Ich habe 2 beliebige Polygone, die jeweils n Eckpunkte haben. Beide Polygone liegen überigens in der gleichen Ebene.
Nun, wenn das 1. Polygon das 2.Polygon irgendwie überschneidet, wird beim 2.Polygon diese Schnittfläche weggeschnitten. Also das 2. Polygon hat diese Schnittfläche verloren, hat nun weniger Fläche und schaut anders aus als ursprünglich. Das 1. Polygon verändert seine Form nicht. Beide Polygone besitzen übrigens keine Kreisflächen, also es gibt nur gerad Linien zwischen 2 Punkten.
Kann man sich vielleicht besser vorstellen, wenn man sich das 1. Polygon als Schere
vorstellt, das einen Teil aus dem 2. Polygon herausschneidet. Blödes Beispiel, aber was besseres fällt mir nicht ein.
Wenn diese Beschreibung unklar ist, bitte sagen.
Wenn jemand ein paar gute Vorschläge hat, wäre ich dafür sehr dankbar
-
nightrider schrieb:
Wenn jemand ein paar gute Vorschläge hat, wäre ich dafür sehr dankbar
Vorschläge wofür? Was genau willst Du nicht haben und was willst Du erreichen?
-
Ja genau du hast recht.
Um das mal zu verdeutlichen hab ich in Paint mehr schlecht als recht ein paar bilder gemalen, um sich das vorstellen zu können. Das Dreieck (1. Polygon) soll etwas aus dem 2. Polygon entfernen.Bild 1
Bild 2
Bild 3
Bild 4
Bild 5
Bild 6
Bild 7Ich muss also nach dem Schnitt, neue Eckpunkte am 2. Polygon hinzufügen bzw. löschen.
Die Punkte, die neu hinzukommen, hab ich rot eingekreist.
Die Punkte, die gelöscht werden müssen, hab ich grün eingekreist.
Ich kann diese roten und grünen Punkte prinzipiell bestimmen, soweit bin ich schon.
Das Problem ist nur, wie ich die roten Punkte miteinander verbinden muss. Ich kann ja nicht ohne weiteres sagen, welcher Punkt mit welchem verbunden werden soll.
Als Beispiel nich ein Schnitt, bei dem ich sehr viele rote Punkte habe. Wie kann ich jetzt die Reihenfolge der roten Punkte bestimmen, in der diese verbunden werden müssen??
-
Du mußt zunächst mal die Schnittpunkte bestimmen und die Kanten gegebenenfalls unterteilen. Dann mußte einfach irgendwo auf das Polygon drauf, wo du was rausschneiden willst. Nun läufste auf dem Rand im Uhrzeigersinn los, wenn Du auf ne Kreuzung triffst mußte das Polygon wechseln und auf dem Rand des anderen Polygons laufen. Einfach immer so weit wie möglich rechts abbiegen. Irgendwann biste einmal rum, damit haste dann alle Knoten und Kanten Deines Ergebnispolygons.
Die Details habe ich leider nicht mehr vollständig im Kopf, aber Schnitt/Differenz etc. von einfachen Polygonen (ohne Löcher und sowas) sind absolute Standardoperationen, da gibt's gute Algorithmen dafür. Hat bestimmt der Preparata schon gemacht.
http://www.cs.mcgill.ca/~gstamm/P507/bool_op.html habe ich noch auf die Schnelle gefunden, sieht ganz interessant aus.
-
Tut mir leid, ich hab mir jetzt sicher den Link fünf mal durchgelesen, aber mir wird nicht ganz klar, wie das funktionieren könnte. Mir ist klar, wie man auf die Event Points kommt, nur wie man dann weiter macht, ist mir nicht mehr klar...
Trotzdem danke für dein Bemühen
-
Mal Dir mal ein Beispiel auf. Dann setzt Du irgendwo auf und fährst entlang der Kontur. Bei den Event-Points hast Du ggf. ne Wahl wo's langgehen soll. Je nachdem welche Entscheidungen man da trifft erhält man andere Polygone. Ich denke für Ausschneiden muß man einfach immer rechts abbiegen.
-
Jester schrieb:
Ich denke für Ausschneiden muß man einfach immer rechts abbiegen.
Seh ich auch so. Es sei denn, man startet zufaellig auf einem Punkt, der mit ausgeschnitten wird. Dann erhaelt man auf die Art genau den ausgeschnittenen Bereich.
Also: am Anfang einmal pruefen, ob der Startpunkt ausserhalb der Schere liegt.
-
Je nachdem welche Entscheidungen man da trifft erhält man andere Polygone. Ich denke für Ausschneiden muß man einfach immer rechts abbiegen.
Immer rechts abbiegen klingt für mich auch logisch.
Aber genau da verstehe ich nicht, wie ich entscheiden soll, welcher Punkt am nächsten rechts liegt...
-
Du läufst ja zunächst mal in irgendeine Richtung los. Nun erreichste nen Event-Punkt. Dort treffen sich 4 Kanten. Dadurch, dass Du weißt wo Du hergekommen bist kannste nun entscheiden welche Kante am weitesten Rechts liegt. Zum Beispiel indem Du den Winkel der ausgehenden Kanten mit der Eingangskante vergleichst und die mit dem kleinsten Winkel nimmst.
-
Ja vielen Dank Jester, ich werds mal so probieren.
-
Hallo,
was Jester das sagt taugt nicht viel . Das läuft etwas anders ab.Warum kann euch nicht Mastercam dazu helfen ,wenn die schon Projektpartner sind?
Übrigens so eine Aufgabe gehört noch nicht zu den schwierigen. Wenn du in der Softwareentwicklung für den CNC-Bereich tätig werden willst , dann mußt du so etwas im Schlaf hinzaubern .Hab mir mal eure Homepage angeschaut,
die Projektfeatures sind schon spannend .
Aber das was zeitlich innerhalb einer Diplomarbeit zu realisieren wäre, dürfte sich gerade mal auf den Syntaxeditor beschränken.
Für eine 3D-Simualtion nach dem Stand der Technik bedarf es einige Entwicklungszeit die sich in Jahren aufrechnet.Wünsche dennoch viel Erfolg
-
Was ist an dem Algorithmus denn falsch?
-
Probier ihn aus , oder denkt nach !
Zum einen steht schon die Frage im Raum wo die Polygone anfangen usw..
-
Ja, habs ausprobiert, funktioniert. Und nu?
-
Cam-Entwickler schrieb:
was Jester das sagt taugt nicht viel . Das läuft etwas anders ab.
Na dann erzähl doch mal, klingt ja spannend. Insbesondere würde mich interessieren, warum dieses Standardvorgehen aus der algorithmischen Geometrie nichts taugt.
-
nightrider: ich hab auch noch ein skript gefunden in dem der Algorithmus beschrieben ist. Schick mir ne Mail, wenn Du daran interessiert bist.
-
Na dann erzähl doch mal, klingt ja spannend. Insbesondere würde mich interessieren, warum dieses Standardvorgehen aus der algorithmischen Geometrie nichts taugt.
Weil das kein Standardvorgehen aus der algorithmischen Geometrie ist.
-
Okay, mehr als heiße Luft scheints ja nicht zu geben.
Schade.
-
Okay, mehr als heiße Luft scheints ja nicht zu geben.
Schade.Genau , aber heiße Luft ist besser als kalte.
Mich würde aber mal interessieren wo das Verwendung finden soll ?
-
Ist doch im Prinzip egal, oder? Boolsche Operationen auf einfachen Polygonen sind sehr gut studierte Probleme für die es echte Standardlösungen gibt. Wie schon erwähnt, notfalls ins Buch von Shamos und Preparata schaun. Ich wette aber, dass dieses Problem in jedem (Grundlagen-)Buch über algorithmische Geometrie angeschnitten wird. Das Prinzip ist aber eigentlich immer das Gleiche: Verbindungsgraph aufbauen und Kanten ablaufen.