Game Development Reference
In-Depth Information
The edges of most simple polygons do not intersect each other. If the
edges do intersect, the polygon is considered a self-intersecting polygon.
An example of a self-intersecting polygon is shown in Figure 9.27.
Figure 9.27
A self-intersecting polygon
Most people usually find it easier to arrange things so that self-intersecting
polygons are either avoided, or simply rejected. In most situations, this is
not a huge burden on the user.
9.7.2
Convex versus Concave Polygons
Non-self-intersecting simple polygons may be further classified as either
convex or concave. Giving a precise definition for “convex” is actually
somewhat tricky because there are many sticky degenerate cases. For most
polygons, the following commonly used definitions are equivalent, although
some degenerate polygons may be classified as convex according to one
definition and concave according to another.
•
Intuitively, a convex polygon doesn't have any “dents.” A concave
polygon has at least one vertex that is a “dent,” which is called a
point of concavity (see
Figure 9.28)
.
•
In a convex polygon, the line between any two points in the polygon
is completely contained within the polygon. In a concave polygon,
there is at least one pair of points in the polygon for which the line
between the points is partially outside the polygon.
•
As we move around the perimeter of a convex polygon, at each vertex
we will turn in the same direction. In a concave polygon, we will
make some left-hand turns and some right-hand turns. We will turn
the opposite direction at the point(s) of concavity. (Note that this
applies to non-self-intersecting polygons only.)
Search WWH ::
Custom Search