Polygon ausdehnen

14/09/2007 - 14:34 von Hansi | Report spam
Hallo,

ich versuche, ein Programm zu entwerfen, welches ein Polygon
erhàlt und für das Polygon ein umgebendes Polygon errechnet, dessen
Kanten um z.B. 5mm weiter aussen liegen.

Einsatz ist eine CNC Maschine.
Das Polygon ist das gewünschte Werkstück, der Radius des Fràsers muss
also bei der Berechnung der Fràser-Bahn berücksichtigt werden.
Ein Fràser der 5mm Radius hat muss also exakt 5mm außerhalb des Polygons
fahren.

PS: Das Polygon ist völlig willkürlich, es ist nur definiert, dass nur
ein Polygon berücksichtigt wird, und dass im Polygon keine Kreuzungen
enthalten sind (Polygonkanten schneiden sich nicht).
Einfachstes Beispiel für das Polygon wàren die Aussen-Konturen des
Buchstaben "A".

Vom Polygon kenne ich für jeden Eckpunkt die Koordinaten Pn(x|y).
Vom Fràser kenne ich den Radius (r)

Nun habe ich Formeln gewàlzt, und eine Lösung erarbeitet, welche
aber bei höherer Anzahl von Punkten recht unperformant ist.

Wàre über neue Lösungsansàtze dankbar :-)


Bisherige Lösung:

Jeder Punkt wird mit seinem Vorgànger und Nachfolger betrachtet
P1(x1|y1) ; P2(x2|y2) ; P3(x3|y3)

Der Winkel zwischen P1P2 und x-Achse wird errechnet (alpha)
Der Winkel zwischen P2P3 und y-Achse wird errechnet (beta)
Der Winkel omega = (beta-alpha)/2
Der gesuchte Punkt P2' liegt auf der Geraden vom Punkt p2 im Winkel omega.

Noch ein bisserl Arcussinus und ich komme vom Radius (r) auf
die Entfernung von P2 zu P2'.

Auf der Geraden durch P2 im Winkel omega kann ich nun diese Entfernung
addieren (=P2') und subtrahieren (=P2'')


Nun muss ich noch prüfen, welcher Punkt (P2' oder P2'') "aussen" liegt,
also Thema "Ist Punkt im Polygon". Dazu muss ich nochmals
vom Punkt P2' aus alle Punkte des Polygons verbinden (Vektor)
und die Steigungen summieren. Ist die Summe der Steigungen 0 dann
ist der Punkt im Poly, sonst aussen.

Dass das alles nicht gerade performant abgeht ist klar.

Hab ich da was verschlafen, oder muss das so kompliziert gelöst werden?

Liebe Grüße und Danke!
 

Lesen sie die antworten

#1 Christopher Creutzig
14/09/2007 - 21:05 | Warnen spam
Hansi wrote:

Wàre über neue Lösungsansàtze dankbar :-)



http://en.wikipedia.org/wiki/Parallel_curve
http://citeseer.ist.psu.edu/153548.html

Ach ja, es gibt natürlich auch einen Haufen Artikel in
Fachzeitschriften, die nicht frei verfügbar sind:

http://sciencelinks.jp/j-east/artic...068101.php
http://dx.doi.org/10.1016/0010-4485(95)00078-X
http://dx.doi.org/10.1016/j.compind.2006.06.002

if all this stuff was simple, we'd
probably be doing something else. -- Daniel Lichtblau, s.m.symbolic

Ähnliche fragen