Polygon

A polygon (from the Greek poly, for "many", and gwnos, for "angle") is a closed planar path composed of a finite number of straight line segments. The term polygon sometimes also describes the interior of the polygon (the open area that this path encloses) or the union of both. The straight line segments that make up the polygon are called its sides or edges and the points where the sides meet are the polygon's vertices.

Table of contents

1 Names and types
2 Properties
3 Point in polygon test
4 Related links

Names and types

A simple non-convex hexagon

A complex polygon
Polygons are named according to the number of sides, combining a Greek root with the suffix -gon, e.g. pentagon, dodecagon. The triangle and quadrilateral are exceptions. For larger numbers, mathematicians write the numeral itself, eg 17-gon. A variable can even be used, usually n-gon. This is useful if the number of sides is used in a formula.

Polygon names

Name Sides

triangle 3

quadrilateral 4

pentagon 5

hexagon 6

heptagon 7

octagon 8

nonagon or ennagon 9

decagon 10

hendecagon or undecagon 11

dodecagon 12

hectagon 100

megagon 10⁶

googolgon 10¹⁰⁰

The taxonomic classification of polygons is illustrated by the following tree:

                                      Polygon
                                     /       \\
                                 Simple     Complex
                                /     \\
                           Convex     Concave
                            /
                       Regular

A polygon is simple if it is described by a single, non-intersecting boundary; otherwise it is called complex.
A simple polygon is called convex if it has no internal angles greater than 180° otherwise it is called concave.
A polygon is called regular if all its sides are of equal length and all its angles are equal.

A concyclic or cyclic polygon is a polygon whose vertices all lie on a single circle.

For example, a square is a regular, cyclic quadrilateral.

Properties

We will assume Euclidean geometry throughout.

Any polygon, regular or irregular, complex or simple, has as many angles as it has sides. The sum of the inner angles of a simple n-gon is (n-2)&pi radians (or (n-2)180°), and the inner angle of a regular n-gon is (n-2)π/n radians (or (n-2)180°/n). This can be seen in two different ways:

Moving around a simple n-gon (like a car on a road), the amount one "turns" at a vertex is 180° - the inner angle. "Driving around" the polygon, one makes one full turn, so the sum of these turns must be 360°, from which the formula follows easily. The reasoning also applies if some inner angles are more than 180°: going clockwise around, it means that one sometime turns left instead of right, which is counted as a negative amount one turns.
Any simple n-gon can be considered to be made up of (n-2) triangles, each of which has an angle sum of π radians or 180°.

The area A of a simple polygon can be computed if the cartesian coordinates (x₁, y₁), (x₂, y₂), ..., (x_n, y_n) of its vertices, listed in order as the area is circulated in counter-clockwise fashion, are known. The formula is

A = 1/2 · (x₁y₂ - x₂y₁ + x₂y₃ - x₃y₂ + ... + x_ny₁ - x₁y_n)

= 1/2 · (x₁(y₂ - y_n) + x₂(y₃ - y₁) + x₃(y₄ - y₂) + ... + x_n(y₁ - y_n-1))

The formula was described by Meister in 1769 and by Gauss in 1795. It can be verified by dividing the polygon into triangles, but it can also be seen as a special case of Green's theorem.

If any two simple polygons of equal area are given, then the first can be cut into polygonal pieces which can be reassembled to form the second polygon. This is the Bolyai-Gerwien theorem.

All regular polygons are concyclic, as are all triangles and rectangles (see circumcircle).

The question of which regular polygons can be constructed with ruler and compass alone was settled by Carl Friedrich Gauss in 1796 (sufficiency)and Pierre Wantzel in 1836 (necessity): A regular n-gon can be constructed with ruler and compass if and only if the odd prime factors of n are distinct prime numbers of the form

These prime numbers are the Fermat primes; the only known ones are 3, 5, 17, 257 and 65537.

Point in polygon test

In computer graphics and computational geometry, it is often necessary to determine whether a given point P = (x₀,y₀) lies inside a simple polygon given by a sequence of line segments. The following algorithm counts how often a horizontal half-ray starting at P intersects the polygon; that number is odd if and only if P lies inside the polygon.

Set l := 0 and r := 0
for each line segment L of the polygon do the following:
- if the y-coordinate of one endpoint of L is less than y₀ and the other is greater than or equal to y₀, then:
  - if P lies in the half plane to the left of L, then set l := l + 1, else set r := r + 1 (*)
if both l and r are odd, then P lies inside the polygon; if both l and r are even, then P lies outside the polygon; if one is even and the other is odd, then some error has occurred, e.g. a rounding error or the line segments do not form a closed path.

This algorithm does not always produce the correct answer if P lies directly on the polygon's boundary; if implemented on a computer with floating point arithmetic, the results may also be wrong if the point lies very close to that boundary, because of rounding errors. This is not normally a concern, as speed is much more important than complete accuracy in computer graphics. However, for a formally correct program, one would have to introduce a numerical tolerance eps and test in line (*) whether P lies withing eps of L, in which case the algorithm should stop and report "P lies very close to the boundary."