Regelmäßiges Polygon

einfaches, nicht überschlagenes, planares, konvexes, regelmäßiges Siebeneck

Ein Polygon (v. griech.: polys = viel + gonos = Winkel) oder auch Vieleck ist ein Begriff aus der Geometrie und dabei insbesondere der Planimetrie. Einfach gesagt erhält man ein Polygon, indem man mindestens drei voneinander verschiedene Punkte in einer Zeichenebene durch Strecken so miteinander verbindet, dass durch den entstandenen Linienzug eine zusammenhängende Fläche (Figur) umschlossen wird. Diese Fläche nennt man Polygon. Dreiecke, Vierecke und Sechsecke sind aus dem Alltag bekannte Beispiele für Polygone.

Mathematische Definition

Ein Polygon ist eine Figur, die durch ein Tupel $P:=\left(P_{1},P_{2},\ldots ,P_{n}\right),P_{i}\in \mathbb {R} ^{m},1\leq i\leq n$ von $n$ Punkten (die Eckpunkte oder kurz Ecken genannt werden) eindeutig definiert wird.

Die Strecken ${\overline {P_{i}P_{i+1}}}\left(i=1,\ldots ,n-1\right)$ und ${\overline {P_{n}P_{1}}}$ bezeichnet man als Seiten oder Kanten des Polygons, alle anderen Verbindungsstrecken ${\overline {P_{i}P_{j}}}$ zweier Polygon-Eckpunkte als Diagonalen.

Meist werden noch weitere Bedingungen vorausgesetzt:

• Das Polygon hat mindestens drei paarweise voneinander verschiedene Eckpunkte.
• Die Kanten schneiden (berühren) einander nur in den Eckpunkten. Andernfalls bezeichnet man das Polygon auch als überschlagen.
• Drei angrenzende Eckpunkte liegen nicht auf einer Geraden. Auch $P_{n},P_{1},P_{2}$ und $P_{n-1},P_{n},P_{1}$ gelten als angrenzende Eckpunkte.
• Falls der Schnitt zweier Kanten entweder leer oder eine Ecke ist, und jede Ecke zu höchstens zwei Kanten gehört (das heißt, es liegt keine Selbstüberschneidung vor), bezeichnet man das Polygon als einfach.

Mathematische Beziehungen

Innenwinkel

In einem nicht überschlagenen, ebenen, konvexen $n$-Eck ist die Summe der Innenwinkel

$\alpha _{1}+...+\alpha _{n}=(n-2)\cdot 180^{\circ }$.

Sind darüber hinaus alle Innenwinkel gleich groß, so haben diese den Wert

$\alpha ={\frac {(n-2)}{n}}\cdot 180^{\circ }$.

Anzahl der Diagonalen

Für konvexe Polygone gilt zur Berechnung der Anzahl der Diagonalen folgende Überlegung:

1. Jede der $n$ Ecken kann durch eine Strecke mit einer der anderen Ecken verbunden werden.
2. Die Verbindung von Ecke $P_{a}$ zur Ecke $P_{b}$ ist mit der Verbindung von $P_{b}$ nach $P_{a}$ identisch.
3. Genau $n$ Verbindungen sind Seiten des Polygons.

Also hat ein konvexes $n$-Eck genau ${\frac {n\cdot (n-1)}{2}}-n$ Diagonalen.

Fläche

Wenn die Eckpunkte des ebenen Polygons durch kartesische Koordinaten $(x_{i},y_{i})$ gegeben sind, kann man die Fläche des Polygons nach der Gaußschen Trapezformel berechnen:

$\mathrm {2} A=\sum _{i=1}^{n}(y_{i}+y_{i+1})\cdot (x_{i}-x_{i+1})$

$\mathrm {2} A=\sum _{i=1}^{n}(x_{i}+x_{i+1})\cdot (y_{i+1}-y_{i})$

Besondere Polygone

Unter den unendlich vielen Polygonen stellen die nachstehend aufgelisteten etwas Besonderes dar. Einige von ihnen können entweder unerwarteterweise exakt (Beispiel 65537-Eck) oder in sehr guter Näherung (Beispiel Siebeneck) mit Zirkel und Lineal konstruiert werden. Andere haben neben der geometrischen eine Bedeutung als Form in der Architektur (Beispiel Pentagon) oder in der Symbolik (Beispiel Pentagramm).

• Dreieck
• Viereck
  • Drachenviereck
  • Parallelogramm
  • Quadrat
  • Raute
  • Rechteck
  • Trapez
• Fünfeck (Pentagon)
• Sechseck (Hexagon)
• Siebeneck (Heptagon)
• Achteck (Oktogon)
• Neuneck
• Siebzehneck (Heptadekagon)
• 257-Eck
• 65537-Eck

Spezielle Typen

Vielecke können gleichseitig und/oder gleichwinklig sein; hat ein Vieleck gleiche Seiten und gleiche Winkel, dann wird es als reguläres oder regelmäßiges Vieleck (Isogon) bezeichnet. Ein reguläres $n$-Eck hat stets einen Umkreis mit Radius $r_{\mathrm {u} }$ und einen Inkreis mit Radius $r_{\mathrm {i} }$. Die Länge jeder Seite wird mit $a$ bezeichnet, die Seitenanzahl mit $n$. Daraus ergeben sich folgende Formeln für reguläre, nicht-überschlagene Polygone:

Flächeninhalt

$A=n{\frac {\,a\,r_{i}}{2}}={\frac {n}{2}}\,r_{u}^{2}\,\sin {\frac {2\pi }{n}}={\frac {1}{4}}na^{2}\cot {\frac {180^{\circ }}{n}}={\frac {n\cdot a^{2}}{4\cdot \tan \left({\frac {180^{\circ }}{n}}\right)}}$

Inkreisradius

$r_{i}={\frac {a}{2}}\cot {\frac {180^{\circ }}{n}}={\frac {a}{2\cdot \tan \left({\frac {180^{\circ }}{n}}\right)}}$

Umkreisradius

$r_{u}={\frac {a}{2\cdot \sin \left({\frac {180^{\circ }}{n}}\right)}}$

Nicht überschlagene Vielecke können konvex oder konkav sein.

Man unterscheidet in der Ebene liegende (planare) und im Raum liegende (nicht-planare) Polygone.

Planare überschlagene reguläre Polygone werden wegen ihres Aussehens auch als Sternpolygone bezeichnet.

Regelmäßige Polygone

Wichtige Kenndaten: (r = Radius Umkreis)

Regelmäßige Polygone

Polygon	Seitenlänge $a$	Zentriwinkel $\alpha$	Umfang $u$	Fläche $A$
Dreieck	$a=r\cdot {\sqrt {3}}$	$120^{\circ }$	$u=r\cdot 3\cdot {\sqrt {3}}$	$A=r^{2}\cdot {\frac {3\cdot {\sqrt {3}}}{4}}$ $A\approx r^{2}\cdot 1{,}299038$
Quadrat	$a=r\cdot {\sqrt {2}}$	$90^{\circ }$	$u=r\cdot 4\cdot {\sqrt {2}}$	$A=r^{2}\cdot 2$
Fünfeck	$a=r\cdot {\sqrt {\frac {5-{\sqrt {5}}}{2}}}$	$72^{\circ }$	$u=r\cdot 5\cdot {\sqrt {\frac {5-{\sqrt {5}}}{2}}}$	$A=r^{2}\cdot {\frac {5}{8}}\cdot {\sqrt {10+2{\sqrt {5}}}}$ $A\approx r^{2}\cdot 2{,}377641$
Sechseck	$a=r\,$	$60^{\circ }$	$u=r\cdot 6$	$A={\frac {3}{2}}r^{2}{\sqrt {3}}$ $A\approx r^{2}\cdot 2{,}598076$
Siebeneck	$a\approx r\cdot 0{,}867767$	$51{\frac {3}{7}}^{\circ }$	$u\approx r\cdot 6{,}074372$	$A\approx r^{2}\cdot 2{,}736410$
Achteck	$a=r\cdot {\sqrt {2-{\sqrt {2}}}}$	$45^{\circ }$	$u=r\cdot 8\cdot {\sqrt {2-{\sqrt {2}}}}$ $u\approx r\cdot 6{,}122935$	$A=r^{2}\cdot 2\cdot {\sqrt {2}}$ $A\approx r^{2}\cdot 2{,}828427$
Neuneck	$a\approx r\cdot 0{,}68404029$	$40^{\circ }$	$u\approx r\cdot 6{,}15636258$	$A\approx r^{2}\cdot 2{,}892544$
Zehneck	$a=r\cdot {\frac {1}{2}}\left({\sqrt {5}}-1\right)$ $a\approx r\cdot 0{,}618034$	$36^{\circ }$	$u=r\cdot 5\cdot \left({\sqrt {5}}-1\right)$ $a\approx r\cdot 6{,}180340$	$A=r^{2}\cdot {\frac {5}{4}}{\sqrt {10-2{\sqrt {5}}}}$ $A\approx r^{2}\cdot 2{,}938926$
Zwölfeck	$a=r\cdot {\sqrt {2-{\sqrt {3}}}}$ $a\approx r\cdot 0{,}517638$	$30^{\circ }$	$u=r\cdot 12\cdot {\sqrt {2-{\sqrt {3}}}}$ $a\approx r\cdot 6{,}211657$	$A=r^{2}\cdot 3$
$n$-Eck	$a=2\cdot r\cdot \sin {\frac {180^{\circ }}{n}}$	${\frac {360^{\circ }}{n}}$	$u=2\cdot n\cdot r\cdot \sin {\frac {180^{\circ }}{n}}$	$A={\frac {r^{2}\cdot n}{2}}\cdot \sin {\frac {360^{\circ }}{n}}$
Grenzwert $n\to \infty$ (Kreis)	$\to 0$	$\to 0$	$u=r\cdot 2\cdot \pi$ $u\approx r\cdot 6{,}283185$	$A=r^{2}\cdot \pi$ $A\approx r^{2}\cdot 3{,}141593$

Berühmte Vielecke

• das „Pentagon“ (Sitz des US-Verteidigungsministeriums);
• das Pentagon in Kronach: die Festung Rosenberg zeigt ein Fünfeck als Grundriss;
• Frankreich wird aufgrund seiner geographischen Form auch als Hexagon bezeichnet;
• das karolingische Oktogon im Grundriss des Aachener Doms.

Polygone in der Computergraphik

Datei:Polygon face.jpg

Polygonmodell mit verfeinertem Surfacemodell im Wechsel

In der 3D-Computergrafik meint man mit Polygonen oft Dreiecke, da diese Grundlage für die Berechnung bei der Bildsynthese sind. Dieses Primitiv wird durch drei Vertices, in Form eines dreidimensionalen Vektors, beschrieben.

Mit Hilfe spezieller 3D-Grafiksoftware kann ein Polygon aus beliebigen einzelnen Eckpunkten und Kanten/Segmenten zusammengefügt werden. Sobald ein Linienzug zu einem einfachen Polygon geschlossen wird, verschwinden alle übriggebliebenen Punkte und Segmente und nur das einfache Polygon bleibt übrig. In diesem geschlossenen Polygon wird nun der Kern bzw. das Sichtbarkeitspolygon eingezeichnet. Auch nach dem Schließen des Polygons kann dessen Gestalt weiterverändert werden; der Grafik-Editor erlaubt neben dem Verschieben von Eckpunkten, Kanten oder des gesamten Polygons auch das Rotieren, Skalieren oder Scheren des Polygons in einem Kontextmenü. Eckpunkte und Kanten können auch gelöscht und neue hinzugefügt werden.

Je zahlreicher und kleiner die Polygone sind, desto realistischer kann die künstliche Bildschirmwelt wirken.

Die technische Grafik-Leistung eines Computerspiels bemisst sich zu einem großen Teil nach der Qualität der gleichzeitig darstellbaren Bildpunkte, Farben, bewegten Flächen und Lichtreflexe. Je mehr solcher Attribute ohne sichtbare Zeitverzögerung für jede Perspektivänderung zu berechnen sind, desto räumlicher und plastischer wirkt die Grafik im Spiel. Voraussetzung für eine „wirklichkeitsnahe“ Wiedergabe am Bildschirm ist daher ein schneller Prozessor. Die PlayStation 2 kann theoretisch 70 Millionen Polygone pro Sekunde verarbeiten. Nicht vergleichbar, doch kann moderne 3D-Grafiksoftware mehrere Milliarden Polygone verarbeiten.

Speicherung von Polygonen und polygonalen Netzen

Vorwort

Zur Speicherung von Polygonen und polyonalen Netzen gibt es eine Reihe bekannter Datenstrukturen. Die bekanntesten Strukturen sind die Eckenliste, Kantenliste, Winged Edge und die doppelt verkettete Kantenliste (doubbly connected halfedge hist).

Eckenliste

Beschreibung der Eckenliste

Bei der Eckenliste werden die Punkte in einer separaten Punktliste abgelegt. Eine Fläche wird dann als eine Liste von Zeigern auf die Punkte in dieser Liste definiert. Dadurch wird eine Trennung zwischen der Geometrie (den Koordinaten der Ecken) und der Topologie (welche Ecken verbinden welche Kanten, welche Kanten begrenzen welche Flächen) realisiert.

Bewertung der Eckenliste

VT:

• Trennung von Geometrie und Topologie
• minimale Redundanzen (Punkte werden nur 1x abgelegt)

NT:

• Kanten werden mehrmals durchlaufen und ausgegeben
• Suche nach zu Kanten gehörenden Facetten nicht effizient möglich (nur mit erschöpfender Suche möglich) Für alle Kanten in F1 (jedes Eckenpaar) suchen wir in allen weiteren Facetten, ob sie enthalten ist, wenn Nein dann Randkante)
• Suchen nach Facetten welche eine Kante / Ecke enthalten ist ineffizient

Kantenliste

Beschreibung der Kantenliste

Die Nachteile der Eckenliste werden bei der Kantenliste dadurch umgangen, dass wir alle Kanten in einer separaten Liste ablegen. Facetten werden hier als Zeiger auf die Kantenliste definiert. Neben dem Anfangs- und Endpunkt werden auch die maximal zwei zugehörigen Facetten für jede Kante abgelegt. Die Reihenfolge der Angabe der Eckpunkte für Kanten legt eine Orientierung fest und bestimmt bei Facetten, wo Innen und wo Außen ist.

Bewertung der Kantenliste

VT:

• Schnelle Bestimmung von Randkanten (Kanten mit nur einem Verweis auf Facette)

NT

• Suchen nach Facetten welche eine Kante / Ecke enthalten ist ineffizient

Zusammenfassung für Ecken- und Kantenliste

Generell gilt für Ecken- und Kantenlisten dass die Suche ausgehend von einer Facette nach untergeordneten Objekten wie Kanten und Ecken sehr effizient durchführbar ist. In umgekehrter Richtung verhält es sich jedoch gegenteilig. So ist z.B. die Suche nach allen Facetten welche eine bestimmte Ecke enthalten immer noch nur durch eine erschöpfende Suche möglich.

Winged Edge nach Baumgart

Beschreibung der Winged-Edge-Liste

Eine Datenstruktur, mit deren Hilfe sehr viele Abfragen effizient bearbeitet werden können ist die Winged-Edge-Darstellung nach Baumgart. Zusätzlich zu den Informationen der Kantenliste werden hier noch Zeiger auf die Kanten abgelegt, die von Anfangs- und Endpunkt der aktuellen Kante abgehen. Aufgrund der Orientierung wird jede Kanten einmal positiv (im Uhrzeigersinn) und einmal negativ (gegen den Uhrzeigersinn) durchlaufen.

Zusammenfassung für die Winged-Edge Liste

Es gibt insgesamt neun Nachbarschaftsbeziehungen, die für polygonale Netze abgefragt werden können. Welche Facette, Kante oder Ecke gehört zu jeder Facette, zu jeder Kante oder zu jeder Ecke? Mit der Winged-Edge-Datenstruktur ist es möglich, in konstanter Zeit abzufragen, welche Ecken oder Facetten zu einer gegebenen Kante gehören. Hat eine Facette k Kanten, können in linearer Zeit diese Kanten nacheinander abgesucht werden (nur bei polygonalen Netzen ohne Änderung der Durchlaufrichtung eines Polygons). Andere Anfragen, insbesondere solche ausgehend von einer Ecke, die nach den Kanten oder Facetten, in denen diese Ecke enthalten ist, suchen, sind deutlich langsamer.

Doppelt verkettete Kantenliste (Half Edge)

Beschreibung der Half-Edge-Liste

Die Half-Edge-Datenstruktur ist ein wenig ausgereifter als die Winged-Edge-Liste. Sie erlaubt, die meisten in der folgenden Tabelle aufgeführten Operationen in konstanter Zeit auszuführen, d.h. konstanter Zeit pro gesammelte Information. Wenn man z.B. alle zu einem Eckpunkt benachbarten Kanten herausfinden will, ist die Operation linear bezüglich der Anzahl der benachbarten Kanten aber konstant in der Zeit pro Kante. Half Edge funktioniert nur mit Mannigfaltigkeiten, d.h. jede Kante ist von genau zwei Facetten (zu jeder Halbkante gibt es eine entgegen gesetzte Halbkante) umgeben, d.h. T-Verbindungen, innere Polygone und Brüche sind nicht erlaubt.

Wie der Name schon sagt, werden bei der Half-Edge-Struktur nicht Kanten, sondern Halbkanten abgelegt. Halbkanten sind gerichtet und zwei zusammengehörende Halbkanten (Paar) bilden eine Kante und zeigen in die entgegengesetzte Richtung.

Laufzeitvergleich

Folgende Tabelle zeigt einen Vergleich der asymptotischen Laufzeit in Abhängigkeit der vorhandenen Elemente Ecken, Kanten und Flächen. Es gibt neun mögliche Abfragen auf die Struktur, nämlich "welche Ecke, Kante oder Fläche gehört zu welcher Ecke Kante oder Fläche". Der Vergleich zeigt, wie unterschiedlich gut die Datenstrukturen die Anfrageklassen bearbeiten.

Suchanfrage (gegeben → gesucht)	Eckenliste	Kantenliste	Winged Edge	Half Edge
Kante → Eckpunkte	N/A	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$
Kante → Facetten	N/A	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$
Kante → angrenzende Kanten	N/A	${\mathcal {O}}(k)$	${\mathcal {O}}(k)$	${\mathcal {O}}(k_{v})$
Eckpunkt → Kanten	${\mathcal {O}}(f*k_{f})$	${\mathcal {O}}(k)$	${\mathcal {O}}(k)$	${\mathcal {O}}(k_{v})$
Eckpunkt → Facetten	${\mathcal {O}}(f*k_{f})$	${\mathcal {O}}(k)$	${\mathcal {O}}(k)$	${\mathcal {O}}(k_{v})$
Facette → Kanten	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$
Facette → Eckpunkte	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$
Facette → benachbarte Facette	${\mathcal {O}}(f*k_{f}^{2})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$	${\mathcal {O}}(k_{f})$

Hierbei bezeichnet:

• $k$: Anzahl aller Kanten
• $k_{f}$: Anzahl der Kanten einer Facette
• $k_{v}$: Anzahl der Kanten, welche zu einem Punkt gehören
• $f$: Anzahl aller Facetten

Erläuterung der Anfrageklassen

Zu Kante -> Eckpunkte

• Eckenliste: Nicht möglich (es gibt keine Kanten)
• Kanteliste: direkt über Kanten ablesbar
• Winged Edge: direkt über Eintrag für Kante abzulesen
• Half Edge über Halbkante->vert und pair->vert.

Zu Kante -> Facetten

• Eckenliste: Nicht möglich (es gibt keine Kanten)
• Kantenliste: direkt aus Kanten ablesbar
• Winged Edge: direkt aus Kante ersichtlich
• Half Edge: die angrenzenden Flächen über edge->face und edge->pair->face bestimmen.

Zu Kante -> angrenzende Kanten

• Eckenliste: Nicht möglich (es gibt keine Kanten)
• Kantenliste: für beide Eckpunkte: „Eckpunkt -> Kante“ durchführen
• Winged Edge: siehe Kantenliste
• Half Edge: siehe Kantenliste

Zu Eckpunkt -> Kanten

• Eckenliste: Da es sich um geschlossene Polygone handelt, hat jede Facette (genauso viele Kanten wie Punkte) Kanten, diese müssen zu jeder Fläche bestimmt werden und nachgeschaut werden, ob die gegebene Ecke darin enthalten ist
• Kantenliste: einfach alle Kanten durchlaufen
• Winged Edge: Startkante zum Punkt ermitteln, dann über „Vorgänger rechts“ suchen solange bis keine Kante mehr da ist, dann wieder bei Startkante beginnen und in andere Richtung laufen.
• Half Edge: über vert->edge erste Kante holen, danach entgegen gesetzte Kante holen und links weiterlaufen. Dies so lange machen, bis links keine Nachfolgerkante da ist, dann wieder mit vert->edge anfangen und diesmal so lange nach rechts laufen, bis keine Nachbarkante mehr vorhanden ist.

Zu Eckpunkt -> Facetten

• Eckenliste: Einfach für alle Facetten die Kanten durchgehen, und schauen, ob der gesuchte Eckpunkt enthalten ist.
• Kantenliste: „Eckpunkt -> Kante“ ausführen und aus diesen Kanten dann direkt die zugehörige Facette lesen.
• Winged Edge: einfach nur die Kanten zum Punkt ermitteln und in konstanter Zeit die dazugehörigen Flächen ermitteln.
• Half Edge: siehe Kantenliste

Zu Facette -> Kanten

• Eckenliste: Alle Kanten einer Facette jeweils paarweise bilden
• Kantenliste: direkt aus Facetten ablesbar
• Winged Edge: siehe Half Edge
• Half Edge: Bei Startkante der Facette beginnen und nach links laufen. Gehört die nachfolgende Kante zur gleichen Facette dann in gleicher Laufrichtung weitermachen. Wird das erst mal kein Nachfolger gefunden kehrt man die Laufrichtung um. Gehört der Nachfolger zur gleichen Facette, dann in dieser Laufrichtung weitermachen, an-sonsten abbrechen. Die Laufrichtung kann sich mehrmals ändern. Irgendwann wird man bei der Startkante angekommen sein. Dann kann man aufhören.

Zu Facette -> Eckpunkte

• Eckenliste: Einfach direkt aus Facetten auslesen
• Kantenliste: „Facette -> Kanten“ ausführen und in konstanter Zeit die zugehörigen Eckpunkte auslesen
• Winged Edge: siehe Half Edge
• Half Edge: “Facette -> Kanten” ausführen und aus den Kanten die Punkte herauslesen, doppelte Punkte rausschmeißen.

Zu Facette -> benachbarte Facette

• Eckenliste: Alle Kanten der zu überprüfenden Facette ermitteln und für jede Kante schauen, ob die anderen Facetten diese Kante auch enthalten.
• Kantenliste: „Facette -> Kanten“ ausführen und dann direkt aus den Kanten die zugehörigen Facetten ablesen
• Winged Edge: „Facette -> Kanten“ ausführen und zu jeder Kante die angrenzende Fläche auslesen
• Half Edge: siehe Winged Edge

Zusammenfassung

Wie man sieht, sind die Winged Edge und die Half Edge Struktur von den enthaltenen Informationen nahezu identisch. Sie weisen deshalb auch fast die gleichen Laufzeiten für das Suchen auf. Half Edge ist in den Anfragen 3-5 etwas besser. Hier müssen aufgrund des Zeigers eines Punktes auf eine zugehörige Startkante beim Suchen aller Kanten eines Punktes auch nur diese angefasst werden. Die Eckenliste scheidet von vornherein aus und die Kantenliste ist vom Suchen her genauso gut wie die Winged Edge Liste, benötigt jedoch etwas mehr Speicherplatz, da bei Winged Edge zu einer Facette nur eine Startkante abgelegt werden muss.

Siehe auch

• Polyeder, Polytop, Winkelsumme, Außenwinkel
• Satz von Pick (für Polygone auf dem Gitter)
• Häufigkeitspolygon
• konstruierbare Polygone
• Graham Scan

Weblinks

• Zur Mathematik unregelmäßiger Polygone
• In siebzig Millionen Polygonen um die Welt
• Sichtbarkeit in einfachen Polygonen
• Rasterung von Polygonen