Forums Neueste Beiträge
 

Polygonclipping-Eigenschaften

12/08/2008 - 15:11 von Lars Rohwedder | Report spam
Hallo,

ich bin grad dabei, einen Algorithmus, der Polygone an
(achsenparallelen) Rechtecken clippt, zu implementieren. Die geclippten
Polygone (es können ja mehrere werden) können dabei (in der Summe) mehr
oder weniger Eckpunkte als das Ausgangspolygone haben. Nun suche ich
nach einer Formel, die mir angibt, wie viele Eckpunkte dabei maximal
herauskommen können, wenn man ein (nicht überschlagenes) Polygon mit n
Eckpunkten clippt.

Ich habe die vage Erinnerung, dass das Ergebnis irgendwo zwischen 2·n
und 3·n liegen soll, aber leider finde ich weder die genaue Formel noch
die Herleitung dafür. :-(

Durch Rumprobieren habe ich für n=3 sieben Eckpunkte und für n=4 zehn
Eckpunkte bekommen. Einen Beweis, dass dies die maximal erreichbare
Eckpunktzahl ist, habe ich allerdings nicht.

Könnt ihr mir da Tipps geben, die mich weiterbringen?

Lars R.
 

Lesen sie die antworten

#1 Ralf Kusmierz
12/08/2008 - 19:05 | Warnen spam
X-No-Archive: Yes

begin quoting, Lars Rohwedder schrieb:

ich bin grad dabei, einen Algorithmus, der Polygone an
(achsenparallelen) Rechtecken clippt, zu implementieren. Die geclippten
Polygone (es können ja mehrere werden) können dabei (in der Summe) mehr
oder weniger Eckpunkte als das Ausgangspolygone haben. Nun suche ich
nach einer Formel, die mir angibt, wie viele Eckpunkte dabei maximal
herauskommen können, wenn man ein (nicht überschlagenes) Polygon mit n
Eckpunkten clippt.
Ich habe die vage Erinnerung, dass das Ergebnis irgendwo zwischen 2·n
und 3·n liegen soll, aber leider finde ich weder die genaue Formel noch
die Herleitung dafür. :-(
Durch Rumprobieren habe ich für n=3 sieben Eckpunkte und für n=4 zehn
Eckpunkte bekommen. Einen Beweis, dass dies die maximal erreichbare
Eckpunktzahl ist, habe ich allerdings nicht.
Könnt ihr mir da Tipps geben, die mich weiterbringen?



An jeder abgeschnittenen Ecke entstehen zwei neue.

/\ /\ /\
/ \ / \ / \
/ \ / \ / \
/ \ / \ / \
/ /\ \ / /\ \ / /\ \
/ / \ \ / / \ \ / / \ \

/ / \ \ / / \ \ / / \ \
/ / \ \/ / \ \/ / \ \
/ / \ / \ / \ \
/ / \ / \ / \ \
/ / \ / \ / \ \
/ / \/ \/ \ \

Beispiel: Abgeschnittenes Zwölfeck erzeugt oben drei Sechsecke und
unten zwei Dreiecke und zwei Sechsecke, jeweils 18 = 1,5 * 12.


Gruß aus Bremen
Ralf
R60: Substantive werden groß geschrieben. Grammatische Schreibweisen:
adressiert Appell asynchron Atmosphàre Autor bißchen Ellipse Emission
gesamt hàltst Immission interessiert korreliert korrigiert Laie
nàmlich offiziell parallel reell Satellit Standard Stegreif voraus

Ähnliche fragen