Polygon

Verschiedene Auffassungen von Polygonen und polygonalen Flächen

Ein Polygon (von altgriechisch πολυγώνιον polygṓnion ‚Vieleck‘; aus πολύς polýs ‚viel‘ und γωνία gōnía ‚Winkel‘) oder auch Vieleck ist in der elementaren Geometrie eine ebene geometrische Figur, die durch einen geschlossenen Streckenzug gebildet wird.

Ein Polygon ist ein zweidimensionales Polytop.

Ein Polygon erhält man, indem in einer Zeichenebene mindestens drei verschiedene (nicht kollineare) Punkte durch Strecken miteinander verbunden werden. Dabei entsteht ein geschlossener Streckenzug (Polygonzug) mit ebenso vielen Ecken, beispielsweise ein Dreieck (3 Punkte, 3 Strecken) oder ein Viereck (4 Punkte, 4 Strecken).

Die umschlossene Fläche wird oft auch als Polygon bezeichnet, so in der Planimetrie.

Definition und Bezeichnungen

Ein Polygon ist eine Figur, die durch ein Tupel $P := \left( P_1, P_2, \dotsc, P_n \right), P_i \in \mathbb{R}^2, 1 \le i \le n$ von verschiedenen Punkten definiert ist.

Die Punkte heißen die Eckpunkte oder kurz Ecken des Polygons, ein Polygon mit Ecken heißt -Eck oder (insbesondere in der englischen Literatur) auch -Gon.
Die Strecken $\overline {P_i P_{i+1}} \left(i=1, \dotsc, n-1 \right)$ und $\overline { P_n P_1 }$ bezeichnet man als Seiten des Polygons.
Alle Verbindungsstrecken zweier Eckpunkte, die keine Seiten sind, nennt man Diagonalen.

Manchmal werden noch weitere Bedingungen für die Definition eines Polygons vorausgesetzt, die aber formal nicht notwendig sind:

Ein Polygon hat mindestens drei paarweise voneinander verschiedene Eckpunkte. Das schließt ein „Zweieck“ aus.
Drei angrenzende Eckpunkte liegen nicht auf einer Geraden. Auch $P_{n}$ , $P_{1}$ , $P_{2}$ und $P_{n-1}$ , $P_{n}$ , $P_{1}$ gelten dabei als angrenzende Eckpunkte. Das schließt Ecken mit gestrecktem Winkel aus.

Klassifikation

Historische Abbildung von Vielecken (1699)

Nach Anzahl der Ecken

Polygone werden typischerweise nach der Zahl der Ecken (Wertigkeit des Polygons) benannt.

Regelmäßiges Polygon

Hat ein Polygon gleiche Seiten und gleiche Innenwinkel, dann wird es als regelmäßiges Polygon oder reguläres Polygon bezeichnet. Viele regelmäßige Polygone lassen sich mit Zirkel und Lineal konstruieren (Konstruierbares Polygon).
Z+L bedeutet: lässt sich mit Zirkel und Lineal konstruieren.

Liste regelmäßiger Polygone
Ecken	Bezeichnung	Griechisch	Z+L	Besonderheit
1	Eineck	Monogon	-	Punkt
2	Zweieck	Digon	-	Strecke
3	Dreieck	Trigon	ja	1. Fermatsche Primzahl $3=2^{2^{0}}+1$
4	Viereck	Tetragon	ja	Quadrat
5	Fünfeck	Pentagon	ja	2. Fermatsche Primzahl $5 = 2^{2^1}+1$
6	Sechseck	Hexagon	ja
7	Siebeneck	Heptagon	nein	Näherungskonstruktion möglich
8	Achteck	Oktogon	ja	englisch octagon
9	Neuneck	Nonagon	nein	seltener Enneagon, Näherungskonstruktion möglich
10	Zehneck	Dekagon	ja
11	Elfeck	Hendekagon	nein	Näherungskonstruktion möglich
12	Zwölfeck	Dodekagon	ja
13	Dreizehneck	Tridekagon	nein
14	Vierzehneck	Tetradekagon	nein
15	Fünfzehneck	Pentadekagon	ja
16	Sechzehneck	Hexadekagon	ja
17	Siebzehneck	Heptadekagon	ja	3. Fermatsche Primzahl $17=2^{2^{2}}+1$
18	Achtzehneck	Oktodekagon	nein	englisch octadecagon, octakaidecagon
19	Neunzehneck	Nonadekagon	nein	englisch auch enneadecagon, enneakaidecagon
20	Zwanzigeck	Ikosagon	ja
21	Einundzwanzigeck	Ikosihenagon	nein
24	Vierundzwanzigeck	Ikositetragon	ja
30	Dreißigeck	Triakontagon	ja
40	Vierzigeck	Tetrakontagon	ja
50	Fünfzigeck	Pentakontagon	nein
51	Einundfünfzigeck	Pentakontahenagon	ja
60	Sechzigeck	Hexakontagon	ja
70	Siebzigeck	Heptakontagon	nein
80	Achtzigeck	Oktokontagon	ja	englisch octacontagon
85	Fünfundachtzigeck	Oktokontapentagon	ja	englisch octacontapentagon
90	Neunzigeck	Enneakontagon	nein
100	Hunderteck	Hektogon	nein
257	257-Eck		ja	4. Fermatsche Primzahl $257 = 2^{2^3}+1$
1.000	Tausendeck	Chiliagon
10.000	Zehntausendeck	Myriagon
65.537	65537-Eck		ja	5. Fermatsche Primzahl $65.537 = 2^{2^4}+1$
100.000	Hunderttausendeck
1.000.000	1000000-Eck	Megagon
4.294.967.295	4294967295-Eck		ja	Größte bekannte ungerade Eckenanzahl, die theoretisch mit Zirkel und Lineal konstruierbar ist
$10^{{100}}$	Googoleck	Googolgon		Eckenzahl: eine 1 mit 100 Nullen
∞	Unendlicheck	Apeirogon		Theoretische Grenzform mit unendlich vielen Seiten

Weitere Typen

Klassifikation von Polygonen

Überschlagenes Polygon: Schneiden (berühren) sich die Kanten nicht nur in den Eckpunkten, bezeichnet man das Polygon als überschlagen. Liegt keine Selbstüberschneidung vor, bezeichnet man das Polygon als einfach.

Nicht-überschlagenes Polygon: Nicht überschlagene Vielecke können konvex (alle Innenwinkel sind kleiner als 180°) oder nichtkonvex (mindestens ein Innenwinkel ist größer als 180°) sein.

Planares Polygon: In der Ebene liegendes (planares) Polygon.

Nicht-planares Polygon: Im Raum liegendes (nicht-planares) Polygon.

Polygone können gleichseitig oder gleichwinklig sein:

Regelmäßiges Polygon: Hat ein Polygon sowohl gleiche Seiten als auch gleiche Innenwinkel, dann wird es als regelmäßiges Polygon oder reguläres Polygon bezeichnet.

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

Orthogonales Polygon: Bei orthogonalen Polygonen treffen alle Kanten im rechten Winkel aufeinander (das heißt, der Innenwinkel beträgt an jeder Kante entweder 90° oder 270°).

Eigenschaften

Winkel

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

$\alpha_1+\dotsb+\alpha_n = (n - 2) \cdot 180^\circ$ .

Für die Summe der Außenwinkel gilt dann unabhängig von der Zahl der Ecken

$\alpha_1'+\dotsb+\alpha_n' = 360^\circ$ .

Sind darüber hinaus alle Innen- und Außenwinkel gleich groß, so haben diese den Wert

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

Diagonalen

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

Jede der Ecken kann durch eine Strecke mit einer der anderen Ecken verbunden werden.
Die Verbindung von Ecke zur Ecke ist mit der Verbindung von nach identisch.
Genau Verbindungen sind Seiten des Polygons.

Also hat ein nicht überschlagenes -Eck genau $\tfrac{n \cdot (n-1)}{2} - n = \tfrac{n \cdot (n-3)}{2}$ Diagonalen. Bei einem nichtkonvexen Polygon gibt es (im Bereich eines überstumpfen Innenwinkels) Diagonalen außerhalb des Polygons.

Umfang

Wenn die Eckpunkte eines ebenen einfachen Polygons durch kartesische Koordinaten (x_i, y_i) gegeben sind, kann der Umfang des Polygons durch Addition der mit dem Satz des Pythagoras berechneten Seitenlängen bestimmt werden:

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

Fläche

Wenn die Eckpunkte eines ebenen einfachen Polygons durch kartesische Koordinaten (x_i, y_i) gegeben sind, kann die Fläche des Polygons nach der gaußschen Trapezformel berechnet werden:

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

Hierbei werden die Indizes, die größer als sind, immer modulo betrachtet, das heißt mit $x_{n+1}$ ist $x_{1}$ gemeint:

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

In Determinantenform lautet die gaußsche Trapezformel:

$2A\ =\ \left|\quad {\begin{vmatrix}x_{n}&y_{n}\\x_{1}&y_{1}\end{vmatrix}}+\sum _{i=1}^{n-1}{\begin{vmatrix}x_{i}&y_{i}\\x_{i+1}&y_{i+1}\end{vmatrix}}\quad \right|$

Neben der gaußschen Trapezformel kann die Fläche eines Polygons durch eine vorzeichenbehaftete Summe der Flächeninhalte von Dreiecken berechnet werden, die mit den Kanten des Polygons als Basen und einem festen Punkt (zum Beispiel dem Ursprungspunkt) als Spitze gebildet werden. Die Flächeninhalte der Dreiecke mit einer dem festen Punkt abgewandten Basis (als Kante des Polygons) werden dabei mit negativen Vorzeichen versehen.

Der Flächeninhalt von Gitterpolygonen, deren Ecken alle auf einem Gitter liegen, kann mit dem Satz von Pick berechnet werden.

Algorithmen

Flächeninhalt

Insbesondere für die Programmierung ist die folgende Darstellung der gaußschen Trapezformel besonders geeignet, da sich zum Speichern der Koordinaten Arrays anbieten, die Indizierung von Arrays bei vielen Programmiersprachen ohnehin bei null beginnt und die Modulo-Funktion somit besonders elegant zum Einsatz kommen kann. Die Modulo-Funktion ist hier nötig, um sogenannte Off-by-one-Fehler bei der Array-Indizierung auszuschließen. Dabei sind (x_i, y_i) , $i=0\dotsc n-1$ , $n\in \mathbb {N}$ , die Koordinaten der $n\geq 3$ Eckpunkte des Polygons.

$A={\frac {1}{2}}\left|\sum _{i=0}^{n-1}(y_{i}+y_{i+1{\bmod {n}}})(x_{i}-x_{i+1{\bmod {n}}})\right|$

Der folgende Programmcode soll eine beispielhafte Implementierung – hier in der Programmiersprache C# – zeigen:

public double berechnePolygonFlaeche(double[] x, double[] y)
{
    if ((x == null) || (y == null)) // auf leere Argumente testen
    {
        return 0.0;
    }
    int anzahlDerEcken = Math.Min(x.Length, y.Length);
    if (anzahlDerEcken < 3) // ein Polygon hat mindestens drei Eckpunkte
    {
        return 0.0;
    }
    double flaecheninhalt = 0.0;
    
    // Schleife zwecks Summenbildung
    for (int i = 0; i < anzahlDerEcken; i++)
    {
        // Modulo-Funktion für die Indexe der Koordinaten
        flaecheninhalt += (y[i] + y[(i + 1) % anzahlDerEcken]) * (x[i] - x[(i + 1) % anzahlDerEcken]);
    }
    return Math.Abs(flaecheninhalt / 2.0);
}

Die Koordinaten der Eckpunkte sind dabei in den beiden Arrays x und y gespeichert. Für das Beispiel-5-Eck $((7,0),(8,7),(4,9),(1,6),(1,2))$ , das einen Flächeninhalt von 45 hat, können diese Arrays z.B. wie folgt initialisiert werden:

double[] x = {7.0, 8.0, 4.0, 1.0, 1.0}; // beispielhafte x-Koordinaten des Polygons
double[] y = {0.0, 7.0, 9.0, 6.0, 2.0}; // beispielhafte y-Koordinaten des Polygons

Konvexe Hülle

Konvexe Hülle von Punkten in der Ebene

Algorithmen für die Ermittlung der konvexen Hülle von Punkten in der Ebene haben als untere Schranke eine asymptotische Laufzeit von $\Omega (n\log n)$ . Der Beweis erfolgt durch Reduktion auf das Sortieren von Zahlen (Sortierverfahren). Liegen nur der Punkte auf dem Rand der konvexen Hülle, ist die Schranke bei $\Omega (n\log k)$ .

Es gibt mehrere Algorithmen zur Bestimmung der konvexen Hülle:

Graham-Scan-Algorithmus
Gift-Wrapping-Algorithmus
QuickHull
Inkrementeller Algorithmus
Chans Algorithmus

Punkt im Polygon

Die Anzahl der Schnittpunkte des Strahls mit den Kanten gibt an, ob sich der Punkt innerhalb oder außerhalb des Polygons befindet.

Es gibt einen einfachen Algorithmus, mit dem geprüft werden kann, ob sich ein Punkt innerhalb eines Polygons in der Ebene befindet:

Es wird eine horizontaler Strahl durch den untersuchten Punkt gelegt und untersucht, wie oft sich der Strahl mit den Kanten des Polygons schneidet. Der Punkt befindet sich innerhalb des Polygons, wenn die Anzahl der Schnittpunkte rechts vom Punkt ungerade ist. Wenn die Anzahl gerade ist, befindet sich der Punkt außerhalb.

Das folgende Computerprogramm in der Programmiersprache C# zeigt eine mögliche Implementierung:

		// Bestimmt, ob sich ein Punkt mit den Koordinaten (x, y) innerhalb des Polygons befindet
		public bool PunktIstInnerhalb(PointF[] ecken, int x, int y)
		{
			int anzahlDerSchnittpunkte = 0;
			int anzahlDerEcken = ecken.Length;
			
			// Ermittelt die Anzahl der Schnittpunkte des Strahls mit den Kanten des Polygons
			for (int i = 0; i < anzahlDerEcken; i++)
			{
			    // Die Ecken der untersuchten Kante
				PointF ecke1 = ecken[i];
				PointF ecke2 = ecken[(i + 1) % anzahlDerEcken];
				double x1 = ecke1.X;
				double y1 = ecke1.Y;
				double x2 = ecke2.X;
				double y2 = ecke2.Y;
				
    			// Prüft, ob der Strahl die Kante des Polygons schneidet
				if (x < x1 && x > x2 || x > x1 && x < x2 && y > (x * y1 - x * y2 - x2 * y1 + x1 * y2) / (x1 - x2))
				{
					anzahlDerSchnittpunkte++;
				}
			}
			// Wenn die Anzahl ungerade ist, gib true zurück
			// Wenn die Anzahl gerade ist, gib false zurück
			return anzahlDerSchnittpunkte % 2 == 1; // Modulo-Operation für Division durch 2
		}

Verwendung

In der Informatik sind wichtige Approximationen komplexer Polygone die konvexe Hülle und das minimal umgebende Rechteck. In Algorithmen wird oft erst anhand der Approximation auf einen möglichen nichtleeren Schnitt mit einem anderen geometrischen Objekt getestet (oder dieser ausgeschlossen), erst anschließend das ganze Polygon in den Speicher geladen und ein exakter Schnitt berechnet.

In der 3D-Computergrafik werden neben anderen Verfahren der geometrischen Modellierung beliebige (auch gekrümmte) Oberflächen als Polygonnetz modelliert. Dreiecksnetze eignen sich besonders gut zur schnellen Darstellung von Oberflächen, können allerdings nicht so gut durch Subdivision Surfaces interpoliert werden. Zur Speicherung von polygonalen Netzen gibt es eine Reihe bekannter Datenstrukturen.

Beispiele für Polygone im Maschinenbau

Weiterhin wird der Begriff Polygon auch analog für die Verwendung als formschlüssige polygonale Welle-Nabe-Verbindung im Maschinenbau genutzt. Hierbei sind beliebige Polygonprofile denkbar.

Beispiele für Polygone in der Geographie

US-Bundesstaaten mit polygonalen Umrissen

Die Grenzen der US-Bundesstaaten Colorado und Wyoming umranden näherungsweise jeweils ein Rechteck und damit ein konvexes Polygon.

Die Staaten New Mexico und Utah haben jeweils die Form eines konkaven Polygons.

Siehe auch

Basierend auf einem Artikel in:

Wikipedia.de