Introduction to Polygons

Polygons are a very useful graphical tool. Solid three dimensional shapes can easily be approximated with a few polygons, and, when good shading and texturing are applied, they can look resonably realistic. They can be drawn quickly and take up very little storage space.

Defining a Polygon

A polygon is an enclosed area bounded by at least three sides. There are three types of polygon, all of which need different drawing routines to handle.

Convex Polygon: Your normal standard run of the mill shape. Triangles, squares, hexagons all fit into this category. The internal angles must all be less than 180 degrees.

Concave Polygon: Concave polygons go back on themselves. They can contain inlets and fjords. They all have at least 4 sides.

Complex Polygon: These are all the rest. They can do anything. They can have holes, they can cross themselves, as many times as they like.

A polygon can be defined by a set of points or a set of line segments. The order in which the set of points is listed is important. Different orders mean different polygons. These two polygons are made ou from the same set of points, listed in a different order.

Does a point lie within a polygon?

A point is considered inside the polygon if a line drawn away from that point crosses an odd number of polygon edges. Any line drawn from any point inside any polygon will cross and odd number of lines.
You will have to decide whether you consider crossing a vertex is to be considered as two lines, one line or none.

For a vertex whose two edges go in opposite directions, one up, one down, count the vertex as one crossing. Vertices whose edges go in the same direction, both up or both down, count the vertex as two crossings.

Polygons in 3D

In two dimensions, it is possible to have polygons with any number of vertices. The same is strictly true in 3D, however, people usually restrict them to only three. The reason for this is that three points are required to define a plane. It is very difficult to guarantee that a fourth point lies on that plane, especially after the points have undergone rotations and scaling and floating point errors have crept in.

In three dimensions, polygons have two sides, a back and a front. This is a very important thing to consider when writing a rendering engine. Imagine closed solid made from polygons. Only one side of each polygon will ever be visible. There is no point wasting time drawing the surfaces facing away from you, as you will not be able to see them. It is worth taking a little time to decide which polygons are facing away and ignoring them. It will save about half the rendering time.