Autor |
Beitrag |
sascha (Fstrichvonx)
| Veröffentlicht am Freitag, den 02. März, 2001 - 11:00: |
|
Hi, ich will eine flaeche zeichnen lassen und brauche dafuer den polygonzug, der sie umgibt. Nun hab ich das problem das ich eine flaeche zeichnen soll in der eine oder meherer teilflaechen fehlen, von denen hab ich auch die polygonzuege. muss jetzt also die flaeche, die ueberbleibt, in teilflaechen aufteilen und diese zeichnen. Wie komm ich nun an die polygonzuege ran, die die teilflaechen umschliessen? alle flaechen sind uebrigens konvex. fuer das problem mit nur einen loch hab ich mir schon folgenden algorithmus ausgedacht, waere nett, wenn jemand testen wuerde, ob der mal fehlschlaegt: hab mir folgendes ueberlegt, um die flaeche zwischen zwei konvexen polygonzuegen in neuen polygonzuegen auszudruecken: ich habe zwei konvexe polygonzuege Pa,Pi. konvex soll heissen, die haben keine einknicke, mathematischer: die verbindungslinie eines jeden punktepaares liegt im inneren des polygonzuges, ja? Pi (i wie innen) liegt vollstaendig in Pa (a wie aussen). wenn ich vom nachbarn spreche, dann meine ich den naechsten punkt auf dem polygonzug im uhrzeigersinn gesehen. 1. nehme einen beliebigen punkt von Pa (=P1) 2. gehe von P1 zu dem punkt von Pi, der P1 am dichtesten ist (=P2) 3. denk dir eine linie durch P1P2. 4. schau ob der nachbar von P2 links von dieser linie liegt. (links aus der blickrichtung von P1 nach P2) 5. wenn ja, ist das P3. 5.1. denk dir nun eine linie durch P2P3. 5.2. schau welches der letzte punkt von Pa ist, der links von dieser linie liegt. 5.3. ist das P1? wenn ja, 5.3.1 erster polygonzug vollstaendig. wenn nein 5.3.2 ist das P4 5.3.3 gehe von P3 nach P4, und von P4 auf Pa zu P1 zurueck erster polygonzug vollstaendig. wenn nein, weiter wie in 5.2. (ev. in 5.3.2 P3 statt P4) 6. starte jetzt neu bei dem punkt der der letzte Punkt auf Pa war und gehe zu dem punkt, der der letzte auf P1 war. haut das hin, oder gibt ads nen gegenbeispiel? |
sascha (Fstrichvonx)
| Veröffentlicht am Freitag, den 02. März, 2001 - 11:04: |
|
hab mir ueberlegt, das man die flaeche ja dann in teilflaechen mit je einem loch aufteilen kann, braeuchte dafuer dann einen algorithmus, und mein anderer algorithmus muesste funktionieren, waere fuer eine rege teilnahme sehr dankbar. |
|