Linien + Polygone: Überschneidungen finden
-
Wir sind in 2D: Gegeben sind mehrere Polygone (Konturen einer Figur/eines Teils), angegeben durch eine Menge von aufeinanderfolgenden Vektoren (für jedes Vektor: Start- und Endpunkt). Polygone können auch ineinander liegen: dann gibt der innere praktisch ein "Loch" in der figur an, in dem kann seinerseits noch einer liegen usw...
Nun wird das ganze durch eine Linie (immer parallel zu der x- oder y-achse) geschnitten. Es sollen Strecken gefunden werden, die innerhalb der Figur liegen.
Bsp:
http://img512.imageshack.us/img512/7816/hatchproblemdg4.jpgRoten Strecken sind die, die gefunden werden sollen..
Meine versuche bisher ein Algorithmus zu schreiben sind in einem Chaos geendet: es gibt zu viele wenn und aber... Vllt hat jemand ja schon erfahrung mit dem Problem und kann was gutes vorschlagen.
Dank im Voraus
-
Ich würde für jede Kante (Polygone in Kanten auflösen, Kante vom End- zum Startpunkt nicht vergessen) den Schnittpunkt mit der Scanlinie berechnen (Strahlensatz solltest Du ja hinkriegen) und wenn einer existiert diesen in einem geeigneten Container packen. Wenn Du alle Kanten durchhast dann die Elemente im Container sortieren und dann immer gerade/ungerade durch: Erste zu ermittelnde Strecke ist von Punkt 1 zu Punkt 2, zweite von Punkt 3 zu Punkt 4, ...
-
witte schrieb:
Ich würde für jede Kante (Polygone in Kanten auflösen, Kante vom End- zum Startpunkt nicht vergessen) den Schnittpunkt mit der Scanlinie berechnen (Strahlensatz solltest Du ja hinkriegen) und wenn einer existiert diesen in einem geeigneten Container packen. Wenn Du alle Kanten durchhast dann die Elemente im Container sortieren und dann immer gerade/ungerade durch: Erste zu ermittelnde Strecke ist von Punkt 1 zu Punkt 2, zweite von Punkt 3 zu Punkt 4, ...
Ich hab an das gleiche gedacht, aber wenn man genauer hinschaut wirds problematisch: trifft die Linie zB den eckpunkt zwischen 2 kanten, wirds schon doppelt gezählt. Allerdings wäre in dem Fall unklar, ob nun ab hier es innerhalb des Teils ist, oder außerhalb - in dem Beispilbild sieht man einen solchen fall, wo ein eckpunkt getroffen wird und dennoch kein eintritt in den polygon stattfindet, es kann aber auch umgekehrt sein.
Zweiter sonderfall tritt auf, wenn die linie auf einer Kante liegt.
-
Ich bin davon ausgegangen, dass Du eine Zeichenfunktion brauchst, mit der Du unregelmäßige Polygone füllst. Da habe ich mich an ein Algorithmus erinnert den man mir vor vielen Jahren im Studium beigebracht hat. Wenn Du eine Ecke schneidest wird ja die gerade/ungerade-Regel nicht verletzt: Du zeichnest bis an die Ecke 'ran, die Strecke mit Länge 0 (zwischen den beiden Kanten, die die Ecke bilden) wird ausgelassen und dann ab der Ecke (übernächste Strecke) weitergezeichnet. Bzw. die Strecken vor/nach der Ecke werden ausgelassen und nur die Ecke als Punkt gezeichnet. Sollte doch klappen oder? Den Sonderfall dass die Scanlinie eine Strecke komplett schneidet mußt Du so oder so extra behandeln, wenn Du keine DIV/0 oder ∞ haben willst. Dann ignoriere diesen Streckenabschnitt doch. Ich denke viele weitere Sonderfälle wird es nicht geben.
-
schneidet die Linie die ecke, heißt es noch lange nicht dass alles was danach kommt außerhalb des Polygons liegt - die ecke kann ja auch nach oben zeigen und die linie also trotzdem in den poly eintreten...
Ich versuch mal das zu implementieren mit allen sonderfällen. Vllt wird es ja doch nicht so viel wie es zu sein scheint mit allen sonderfällen. Wenn dir was einfällt - immer bescheid sagen
Danke!
PS Mit dem füllen bist du schon auf der richtigen spur - das programm generiert steuerbewegungen für eine CNC-maschiene, es geht ums "Hatching"
