Chapter 18

Putting Lines Together: Polylines and Polygons

Figure 18.1 shows a polygon. It is the outline of a shape, drawn with straight line segments. Since such shapes are all a printer or plotter can draw, just about every computer-generated drawing consists of polygons. If we add an “eye” to the bird-shaped polygon from Figure 18.1, and if we apply a sequence of rotations and translations to it, then we arrive at Figure 18.2. It turns out copies of our special bird polygon can cover the whole plane! This technique is also present in the Escher illustration in Figure 6.8.

18.1 Polylines

Straight line segments, called edges, connecting an ordered set of vertices constitute a polyline. The first and last vertices are not necessarily connected. Some 2D examples are illustrated in Sketch 18.1, however, a polyline can be 3D, too. Since the vertices are ordered, the edges are oriented and can be thought of as vectors. Let’s call them edge vectors.

Polylines are a primary output primitive, and thus they are included in graphics standards. One example of a graphics standard is the GKS (Graphical Kernel System); this is a specification of what belongs in a graphics package. The development of PostScript was based on GKS. Polylines have many uses in computer graphics and modeling. Whether in 2D or 3D, they are typically used to outline a shape. The power of polylines to reveal a shape is illustrated in Figure 18.3 in the display of a 3D surface. The surface is evaluated in an organized fashion so that the points can be logically connected as polylines, giving the observer a feeling of the “flow” of the surface. In modeling, a polyline is often used to approximate a complex curve or data, which in turn makes analysis easier and less costly. An example of this is illustrated in Figure 12.3.

18.2 Polygons

When the first and last vertices of a polyline are connected, it is called a polygon. Normally, a polygon is thought to enclose an area. For this reason, unless a remark is made, we will consider planar polygons only. Just as with polylines, polygons constitute an ordered set of vertices and we will continue to use the term edge vectors. Thus, a polygon with n edges is given by an ordered set of 2D points

$p_1,p_2,...p_n$

and has edge vectors vi = pi+1 − pi; i = 1, ..., n. Note that the edge vectors sum to the zero vector.

If you look at the edge vectors carefully, you’ll discover that vn = pn+1 − pn, but there is no vertex pn+1! This apparent problem is resolved by defining pn+1 = p1, a convention called cyclic numbering. We’ll use this convention throughout, and will not mention it every time. We also add one more topological characterization of polygons: the number of vertices equals the number of edges.

Since a polygon is closed, it divides the plane into two parts: a finite part, the polygon’s interior, and an infinite part, the polygon’s exterior.

As you traverse a polygon, you follow the path determined by the vertices and edge vectors. Between vertices, you’ll move along straight lines (the edges), but at the vertices, you’ll have to perform a rotation before resuming another straight line path. The angle ai by which you rotate at vertex pi is called the turning angle or exterior angle at pi. The interior angle is then given by π — ai (see Sketch 18.2).

Polygons are used a lot! For instance, in Chapter 1 we discussed the extents of geometry in a 2D coordinate system. Another name for these extents is a minmax box (see Sketch 18.3). It is a special polygon, namely a rectangle. Another type of polygon studied in Chapter 17 is the triangle. This type of polygon is often used to define a polygonal mesh of a 3D model. The triangles may then be filled with color to produce a shaded image. A polygonal mesh from triangles is illustrated in Figure 17.3, and one from rectangles is illustrated in Figure 8.3.

18.3 Convexity

Polygons are commonly classified by their shape. There are many ways of doing this. One important classification is as convex or nonconvex. The latter is also referred to as concave. Sketch 18.4 gives an example of each. How do you describe the shape of a convex polygon? As in Sketch 18.5, stick nails into the paper at the vertices. Now take a rubberband and stretch it around the nails, then let go. If the rubberband shape follows the outline of the polygon, it is convex. The points on the rubberband define the convex hull. Another definition: take any two points in the polygon (including on the edges) and connect them with a straight line. If the line never leaves the polygon, then it is convex. This must work for all possible pairs of points!

The issue of convexity is important, because algorithms that involve polygons can be simplified if the polygons are known to be convex. This is true for algorithms for the problem of polygon clipping. This problem starts with two polygons, and the goal is to find the intersection of the polygon areas. Some examples are illustrated in Sketch 18.6. The intersection area is defined in terms of one or more polygons. If both polygons are convex, then the result will be just one convex polygon. However, if even one polygon is not convex then the result might be two or more, possibly disjoint or nonconvex, polygons. Thus, nonconvex polygons need more record keeping in order to properly define the intersection area(s). Not all algorithms are designed for nonconvex polygons. See [10] for a detailed description of clipping algorithms.

An n-sided convex polygon has a sum of interior angles I equal to

$\begin{array}{rr}\hfill I=\left(n-2\right)\pi .& \hfill \left(18.1\right)\end{array}$

To see this, take one polygon vertex and form triangles with the other vertices, as illustrated in Sketch 18.7. This forms n − 2 triangles. The sum of interior angles of a triangle is known to be π. Thus, we get the above result.

The sum of the exterior angles of a convex polygon is easily found with this result. Each interior and exterior angle sums to π. Suppose the ith interior angle is αi radians, then the exterior angle is π − ai radians. Sum over all angles, and the exterior angle sum E is

$\begin{array}{rr}\hfill E=n\pi -\left(n-2\right)\pi =2\pi .& \hfill \left(18.2\right)\end{array}$

To test if an n-sided polygon is convex, we’ll use the barycenter of the vertices p1,...,pn. The barycenter b is a special barycentric combination (see Sections 17.1 and 17.3):

$b=\frac{1}{n}\left(p_1+...+p_n\right).$

It is the center of gravity of the vertices. We need to construct the implicit line equation for each edge vector in a consistent manner. If the polygon is convex, then the point b will be on the “same” side of every line. The implicit equation will result in all positive or all negative values. (Sketch 3.3 illustrates this concept.) This will not work for some unusual, nonsimple, polygons. (See Section 18.5 and the Exercises.)

Another test for convexity is to check if there is a reentrant angle. This is an interior angle that is greater than π.

18.4 Types of Polygons

There are a variety of special polygons. First, we introduce two terms to help describe these polygons:

• equilateral means that all sides are of equal length, and
• equiangular means that all interior angles at the vertices are equal.

In the following illustrations, edges with the same number of tick marks are of equal length and angles with the same number of arc markings are equal.

A very special polygon is the regular polygon: it is equilateral and equiangular. Examples are illustrated in Sketch 18.8. A regular polygon is also referred to as an n-gon, indicating it has n edges. We list the names of the “classical” n-gons:

• a 3-gon is an equilateral triangle,
• a 4-gon is a square,
• a 5-gon is a regular pentagon,
• a 6-gon is a regular hexagon, and
• an 8-gon is a regular octagon.

An n-gon is commonly used to approximate a circle in computer graphics, as illustrated in Figure 18.4.

A rhombus is equilateral but not equiangular, whereas a rectangle is equiangular but not equilateral. These are illustrated in Sketch 18.9.

18.5 Unusual Polygons

Most often, applications deal with simple polygons, as opposed to nonsimple polygons. A nonsimple polygon, as illustrated in Sketch 18.10, is characterized by edges intersecting other than at the vertices. Topology is the reason nonsimple polygons can cause havoc in some algorithms. For convex and nonconvex simple polygons, as you traverse along the boundary of the polygon, the interior remains on one side. This is not the case for nonsimple polygons. At the mid-edge intersections, the interior switches sides. In more concrete terms, recall how the implicit line equation could be used to determine if a point is on the line, and more generally, which side it is on. Suppose you have developed an algorithm that associates the + side of the line with being inside the polygon. This rule will work fine if the polygon is simple, but not otherwise.

Sometimes nonsimple polygons can arise due to an error. The polygon clipping algorithms, as discussed in Section 18.3, involve sorting vertices to form the final polygon. If this sorting goes haywire, then you could end up with a nonsimple polygon rather than a simple one as desired.

In applications, it is not uncommon to encounter polygons with holes. Such a polygon is illustrated in Sketch 18.11. As you see, this is actually more than one polygon. An example of this, illustrated in Figure 18.5, is a special CAD/CAM (computer-aided manufacturing) surface called a trimmed surface. The polygons define parts of the material to be cut or punched out. This allows other parts to fit to this one.

For trimmed surfaces and other CAD/CAM applications, a certain convention is accepted in order to make more sense out of this multipolygon geometry. The polygons must be oriented a special way. The visible region, or the region that is not cut out, is to the “left.” As a result, the outer boundary is oriented counterclockwise and the inner boundaries are oriented clockwise. More on the visible region in Section 18.9.

18.6 Turning Angles and Winding Numbers

The turning angle of a polygon or polyline is essentially another name for the exterior angle, which is illustrated in Sketch 18.12. Notice that this sketch illustrates the turning angles for a convex and a nonconvex polygon. Here the difference between a turning angle and an exterior angle is illustrated. The turning angle has an orientation as well as an angle measure. All turning angles for a convex polygon have the same orientation, which is not the case for a nonconvex polygon. This fact will allow us to easily differentiate the two types of polygons.

Here is an application of the turning angle. Suppose for now that a given polygon is 2D and lives in the [e1, e2]-plane. Its n vertices are labeled

$p_1,p_2,...p_n.$

We want to know if the polygon is convex. We only need to look at the orientation of the turning angles, not the actual angles. First, let’s embed the 2D vectors in 3D by adding a zero third coordinate, for example:

$p_1=\left[\begin{array}{c}{p}_{1,1}\\ p_{2,1}\\ 0\end{array}\right].$

Recall that the cross product of two vectors in the e1, e2-plane will produce a vector that points “in” or “out,” that is in the +e3 or −e3 direction. Therefore, by taking the cross product of successive edge vectors

$\begin{array}{rr}\hfill u_i=\left(p_{i+1}-p_i\right)\wedge \left(p_{i+2}-p_{i+1}\right),& \hfill \left(18.3\right)\end{array}$

we’ll encounter ui of the form

$\left[\begin{array}{c}0\\ 0\\ u_{3,i}\end{array}\right].$

If the sign of the u3, i value is the same for all angles, then the polygon is convex. A mathematical way to describe this is by using the scalar triple product (see Section 8.5). The turning angle orientation is determined by the scalar

$u_{3,i}=e_3\cdot \left(\left(p_{i+1}-p_i\right)\wedge \left(p_{i+2}-p_{i+1}\right)\right).$

Notice that the sign is dependent upon the traversal direction of the polygon, but only a change of sign is important. The determinant of the 2D vectors would have worked just as well, but the 3D approach is more useful for what follows.

If the polygon lies in an arbitrary plane, having a normal n, then the above convex/concave test is changed only a bit. The cross product in (18.3) produces a vector ui that has direction ±n. Now we need the dot product, n · ui to extract a signed scalar value.

If we actually computed the turning angle at each vertex, we could form an accumulated value called the total turning angle. Recall from (18.2) that the total turning angle for a convex polygon is 2π. For a polygon that is not known to be convex, assign a sign using the scalar triple product as above, to each angle measurement. The sum E will then be used to compute the winding number of the polygon. The winding number W is

$W=\frac{E}{2\pi }.$

Thus, for a convex polygon, the winding number is one. Sketch 18.13 illustrates a few examples. A non-self-intersecting polygon is essentially one loop. A polygon can have more than one loop, with different orientations: clockwise versus counterclockwise. The winding number gets decremented for each clockwise loop and incremented for each counterclockwise loop, or vice versa depending on how you assign signs to your angles.

18.7 Area

A simple method for calculating the area of a 2D polygon is to use the signed area of a triangle as in Section 4.9. First, triangulate the polygon. For example, choose one vertex of the polygon and form all triangles from it and successive pairs of vertices, as is illustrated in Sketch 18.14. The sum of the signed areas of the triangles results in the area of the polygon. For this method to work, we must form the triangles with a consistent orientation. For example, in Sketch 18.14, triangles (p1, p2, p3), (p1, p3, p 4, and (p1, p4, p5) are all counterclockwise or right-handed, and therefore have positive area. More precisely, if we form vi = pi − p1, then the area of the polygon in Sketch 18.14 is

$A=\frac{1}{2}\left(\det \left[v_2,v_3\right]+\det \left[v_3,v_4\right]+\det \left[v_4,v_5\right]\right).$

In general, if a polygon has n vertices, then this area calculation becomes

$\begin{array}{rr}\hfill A=\frac{1}{2}\left(\det \left[v_2,v_3\right]+...+\det \left[v_{n-1},v_n\right]\right).& \hfill \left(18.4\right)\end{array}$

The use of signed area makes this idea work for nonconvex polygons as in Sketch 18.15. As illustrated in the sketch, the negative areas cancel duplicate and extraneous areas.

Equation (18.4) takes an interesting form if its terms are expanded. We observe that the determinants that represent edges of triangles within the polygon cancel. So this leaves us with

$\begin{array}{rr}\hfill A=\frac{1}{2}\left(\det \left[p_1,p_2\right]+...+\det \left[p_{n-1},p_n\right]+\det \left[p_n,p_1\right]\right).& \hfill \left(18.5\right)\end{array}$

Equation (18.5) seems to have lost all geometric meaning because it involves the determinant of point pairs, but we can recapture geometric meaning if we consider each point to be pi − o.

Is (18.4) or (18.5) the preferred form? The amount of computation for each equation is similar; however, there is one drawback of (18.5).

If the polygon is far from the origin then numerical problems can occur because the vectors pi and pi+1 will be close to parallel. The form in (18.4) essentially builds a local frame in which to compute the area. For debugging and making sense of intermediate computations, (18.4) is easier to work with. This is a nice example of how reducing an equation to its “simplest” form is not always “optimal”!

An interesting observation is that (18.5) may be written as a generalized determinant. The coordinates of the vertices are

$p_i=\left[\begin{array}{r}\hfill p{}_{1,i}\\ \hfill p{}_{2,i}\end{array}\right].$

The area is computed as follows,

$A=\frac{1}{2}\left|\begin{array}{rrrrr}\hfill p_{1,1}& \hfill p_{1,2}& \hfill ...& \hfill p_{1,n}& \hfill p_{1,1}\\ \hfill p_{2,1}& \hfill p_{2,2}& \hfill ...& \hfill p_{2,n}& \hfill p_{2,1}\end{array}\right|,$

which is computed by adding the products of all “downward” diagonals, and subtracting the products of all “upward” diagonals.

Example 18.1

Let

$\begin{array}{rrrr}\hfill p_1=\left[\begin{array}{r}\hfill 0\\ \hfill 0\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 1\\ \hfill 0\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 1\\ \hfill 1\end{array}\right],& \hfill p_4=\left[\begin{array}{r}\hfill 0\\ \hfill 1\end{array}\right].\end{array}$

We have

$A=\frac{1}{2}\left|\begin{array}{rrrrr}\hfill 0& \hfill 1& \hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1& \hfill 1& \hfill 0\end{array}\right|=\frac{1}{2}\left[0+1+1+0-0-0-0-0\right]=1.$

Since our polygon was a square, this is as expected.

But now take

$\begin{array}{rrrr}\hfill p_1=\left[\begin{array}{r}\hfill 0\\ \hfill 0\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 1\\ \hfill 1\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 0\\ \hfill 1\end{array}\right],& \hfill p_4=\left[\begin{array}{r}\hfill 1\\ \hfill 0\end{array}\right].\end{array}$

This is a nonsimple polygon! Its area computes to

$A=\frac{1}{2}\left|\begin{array}{rrrrr}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill 1& \hfill 1& \hfill 1& \hfill 0\end{array}\right|=\frac{1}{2}\left[0+1+0+0-0-0-1-0\right]=0.$

Draw a sketch and convince yourself this is correct.

Planar polygons are sometimes specified by 3D points. We can adjust the area formula (18.4) accordingly. Recall that the cross product of two vectors results in a vector whose length equals the area of the parallelogram spanned by the two vectors. So we will replace each determinant by a cross product

$\begin{array}{rrrr}\hfill u_i=v_i\wedge v_{i+1}& \hfill \text{for}& \hfill i=2,n-1& \hfill \left(18.6\right)\end{array}$

and as before, each vi = pi − p1. Suppose the (unit) normal to the polygon is n. Notice that n and all ui share the same direction, therefore ||u|| = u · n. Now we can rewrite (18.5) for 3D points,

$\begin{array}{rr}\hfill A=\frac{1}{2}n\cdot \left(u_2+...+u_{n-1}\right),& \hfill \left(18.7\right)\end{array}$

with the ui defined in (18.6). Notice that (18.7) is a sum of scalar triple products, which were introduced in Section 8.5.

Example 18.2

Take the four coplanar 3D points

$\begin{array}{rrrr}\hfill p_1=\left[\begin{array}{r}\hfill 0\\ \hfill 2\\ \hfill 0\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 2\\ \hfill 0\\ \hfill 0\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 2\\ \hfill 0\\ \hfill 3\end{array}\right],& \hfill p_4=\left[\begin{array}{r}\hfill 0\\ \hfill 2\\ \hfill 3\end{array}\right].\end{array}$

Compute the area with (18.7), and note that the normal

$n=\left[\begin{array}{c}-1/\sqrt{2}\\ -1/\sqrt{2}\\ 0\end{array}\right].$

First compute

$\begin{array}{ccc}{v}_2=\left[\begin{array}{r}\hfill 2\\ \hfill -2\\ \hfill 0\end{array}\right],& v_3=\left[\begin{array}{r}\hfill 2\\ \hfill -2\\ \hfill 3\end{array}\right],& v_4=\left[\begin{array}{c}0\\ 0\\ 3\end{array}\right],\end{array}$

and then compute the cross products:

$\begin{array}{rrr}\hfill u_2=v_2\wedge v_3=\left[\begin{array}{r}\hfill -6\\ \hfill -6\\ \hfill 0\end{array}\right]& \hfill \text{and}& \hfill u_3=v_3\wedge v_4=\left[\begin{array}{r}\hfill -6\\ \hfill -6\\ \hfill 0\end{array}\right]\end{array}.$

Then the area is

$A=\frac{1}{2}n\cdot \left(u_2+u_3\right)=6\sqrt{2}.$

(The equality $\sqrt{2}/2=1/\sqrt{2}$ was used to eliminate the denominator.) You may also realize that our simple example polygon is just a rectangle, and so you have another way to check the area.

In Section 8.6, we looked at calculating normals to a polygonal mesh specifically for computer graphics lighting models. The results of this section are useful for this task as well. By removing the dot product with the normal, (18.7) provides us with a method of computing a good average normal to a nonplanar polygon:

$n=\frac{\left(u_2+u_3+...+u_{n-2}\right)}{||u_2+u_3+...+u_{n-2}||}.$

This normal estimation method is a weighted average based on the areas of the triangles. To eliminate this weighting, normalize each ui before summing them.

Example 18.3

What is an estimate normal to the nonplanar polygon

$\begin{array}{rrrr}\hfill p_1=\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 1\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 1\\ \hfill 0\\ \hfill 0\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 1\\ \hfill 1\\ \hfill 1\end{array}\right],& \hfill p_4=\left[\begin{array}{r}\hfill 0\\ \hfill 1\\ \hfill 0\end{array}\right]?\end{array}$

Calculate

$\begin{array}{rr}\hfill u_2=\left[\begin{array}{c}1\\ -1\\ 1\end{array}\right],& \hfill u_3=\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right],\end{array}$

and the normal is

$n=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right].$

18.8 Application: Planarity Test

Suppose someone sends you a CAD file that contains a polygon. For your application, the polygon must be 2D; however, it is oriented arbitrarily in 3D. How do you verify that the data points are coplanar?

There are many ways to solve this problem, although some solutions have clear advantages over the others. Some considerations when comparing algorithms include:

• numerical stability,
• speed,
• ability to define a meaningful tolerance,
• size of data set, and
• maintainability of the algorithm.

The order of importance is arguable.

Let’s look at three possible methods to solve this planarity test and then compare them.

• Volume test: Choose the first polygon vertex as a base point. Form vectors to the next three vertices. Use the scalar triple product to calculate the volume spanned by these three vectors. If it is less than a given tolerance, then the four points are coplanar. Continue for all other sets.
• Plane test: Construct the plane through the first three vertices. Check if all of the other vertices lie in this plane, within a given tolerance.
• A verage normal test: Find the centroid c of all points. Compute all normals ni = [pi − c] Λ [pi+1 − c]. Check if all angles formed by two subsequent normals are below a given angle tolerance.

If we compare these three methods, we see that they employ different kinds of tolerances: for volumes, distances, and angles. Which of these is preferable must depend on the application at hand. Clearly the plane test is the fastest of the three; yet it has a problem if the first three vertices are close to being collinear.

18.9 Application: Inside or Outside?

Another important concept for 2D polygons is the inside/outside test or visibility test. The problem is this: Given a polygon in the [e1, e2]-plane and a point p, determine if the point lies inside the polygon.

One obvious application for this is polygon fill for raster device software, e.g., as with PostScript. Each pixel must be checked to see if it is in the polygon and should be colored. The inside/outside test is also encountered in CAD with trimmed surfaces, which were introduced in Section 18.5. With both applications it is not uncommon to have a polygon with one or more holes, as illustrated in Sketch 18.11. In the PostScript fill application, nonsimple polygons are not unusual either.1

We will present two similar algorithms, producing different results in some special cases. However we choose to solve this problem, we will want to incorporate a trivial reject test. This simply means that if a point is “obviously” not in the polygon, then we output that result immediately, i.e., with a minimal amount of calculation. In this problem, trivial reject refers to constructing a minmax box around the polygon. If a point lies outside of this minmax box then it may be trivially rejected. As you see, this involves simple comparison of e1- and e2-coordinates.

18.9.1 Even-Odd Rule

From a point p, construct a line in parametric form with vector r in any direction. The parametric line is

$l\left(t\right)=p+tr.$

This is illustrated in Sketch 18.16. Count the number of intersections this line has with the polygon edges for t ≥ 0 only. This is why the vector is sometimes referred to as a ray. The number of intersections will be odd if p is inside and even if p is outside. Figure 18.6 illustrates the results of this rule with the polygon fill application.

It can happen that l(t) coincides with an edge of the polygon or passes through a vertex. Either a more elaborate counting scheme must be developed, or you can choose a different r. As a rule, it is better to not choose r parallel to the e1- or e2-axis because the polygons often have edges parallel to these axes.

18.9.2 Nonzero Winding Number

In Section 18.6 the winding number was introduced. Here is another use for it. This method proceeds similarly to the even-odd rule. Construct a parametric line at a point p and intersect the polygon edges. Again, consider only those intersections for t ≥ 0. The counting method depends on the orientation of the polygon edges. Start with a winding number of zero. Following Sketch 18.17, if a polygon edge is oriented “right to left” then add one to the winding number. If a polygon edge is oriented “left to right” then subtract one from the winding number. If the final result is zero then the point is outside the polygon. Figure 18.7 illustrates the results of this rule with the same polygons used in the even-odd rule. As with the previous rule, if you encounter edges head-on, then choose a different ray.

The differences in the algorithms are interesting. The PostScript language uses the nonzero winding number rule as the default. The authors (of the PostScript language) feel that this produces better results for the polygon fill application, but the even-odd rule is available with a special command. PostScript must deal with the most general (and crazy) polygons. In the trimmed surface application, the polygons must be simple and polygons cannot intersect; therefore, either algorithm is suitable.

If you happen to know that you are dealing only with convex polygons, another inside/outside test is available. Check which side of the edges the point p is on. If it is on the same side for all edges, then p is inside the polygon. All you have to do is to compute all determinants of the form

$\left|\left(p_i-p\right)\left(p_{i+1}-p\right)\right|.$

If they are all of the same sign, p is inside the polygon.

18.10 Exercises

1. What is the sum of the interior angles of a six-sided polygon? What is the sum of the exterior angles?

2. What type of polygon is equiangular and equilateral?

3. Which polygon is equilateral but not equiangular?

4. Develop an algorithm that determines whether or not a polygon is simple.

5. Calculate the winding number of the polygon with the following vertices:

   $\begin{array}{lll}{p}_1=\left[\begin{array}{c}0\\ 0\end{array}\right],& p_2=\left[\begin{array}{r}\hfill -2\\ \hfill 0\end{array}\right],& p_3=\left[\begin{array}{r}\hfill -2\\ \hfill 2\end{array}\right],\\ p_4=\left[\begin{array}{c}0\\ 2\end{array}\right],& p_5=\left[\begin{array}{c}2\\ 2\end{array}\right],& p_6=\left[\begin{array}{r}\hfill 2\\ \hfill -2\end{array}\right],\\ p_7=\left[\begin{array}{r}\hfill 3\\ \hfill -2\end{array}\right],& p_8=\left[\begin{array}{r}\hfill 3\\ \hfill -1\end{array}\right],& p_9=\left[\begin{array}{r}\hfill 0\\ \hfill -1\end{array}\right].\end{array}$

6. Compute the area of the polygon with the following vertices:

   $\begin{array}{c}\begin{array}{rrr}\hfill p_1=\left[\begin{array}{r}\hfill -1\\ \hfill 0\end{array}\right],& \hfill p_2=\left[\begin{array}{c}0\\ 1\end{array}\right],& \hfill p_3=\left[\begin{array}{c}1\\ 0\end{array}\right],\end{array}\\ \begin{array}{cc}{p}_4=\left[\begin{array}{c}1\\ 2\end{array}\right],& p_5=\left[\begin{array}{r}\hfill -1\\ \hfill 2\end{array}\right].\end{array}\end{array}$

   Use both methods from Section 18.7.

7. Give an example of a nonsimple polygon that will pass the test for convexity, which uses the barycenter from Section 18.3.

8. Find an estimate normal to the nonplanar polygon

   $\begin{array}{rrrr}\hfill p_1=\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 1\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 1\\ \hfill 0\\ \hfill 0\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 1\\ \hfill 1\\ \hfill 1\end{array}\right],& \hfill p_4=\left[\begin{array}{r}\hfill 0\\ \hfill 1\\ \hfill 0\end{array}\right].\end{array}$

9. The following points are the vertices of a polygon that should lie in a plane:

   $\begin{array}{lll}\hfill p_1=\left[\begin{array}{r}\hfill 2\\ \hfill 0\\ \hfill -2\end{array}\right],& \hfill p_2=\left[\begin{array}{r}\hfill 3\\ \hfill 2\\ \hfill -4\end{array}\right],& \hfill p_3=\left[\begin{array}{r}\hfill 2\\ \hfill 4\\ \hfill -4\end{array}\right],\\ \hfill p_4=\left[\begin{array}{r}\hfill 0\\ \hfill 3\\ \hfill -1\end{array}\right],& \hfill p_5=\left[\begin{array}{r}\hfill 0\\ \hfill 2\\ \hfill -1\end{array}\right],& \hfill p_6=\left[\begin{array}{r}\hfill 0\\ \hfill 0\\ \hfill 0\end{array}\right].\end{array}$

   However, one point lies outside this plane. Which point is the outlier?2 Which planarity test is the most suited to this problem?

1As an example, take Figure 3.4. The lines inside the bounding rectangle are the edges of a nonsimple polygon.

2This term is frequently used to refer to noisy, inaccurate data from a laser scanner.