Determining the Winding of a Polygon Given as a Set of Ordered Points

- jnorton - Element 84

When working with spatial data one often needs to work with polygons to demarcate bounding areas. One important concept related to this is winding, which defines the relative order in which the vertex points of a polygon are listed. Winding can be either clockwise (CW) or counter-clockwise (anti-clockwise) (CCW), referring to the direction in which we pass through the vertices while looking down at the coordinate plane.

In figure 1, the vertices of a polygon are listed with CW winding on the left and CCW winding on the right.

CW and CCW Windings

Figure 1 - CW and CCW Windings

Winding is important because it allows us to easily determine which points lie within the bounds of a polygon, among other things. Typically a system that works with polygons will require that all vertices are listed with a particular winding (often CCW). It’s important for such systems to validate any input polygon data to make sure that its winding is correct. Which raises the question,

Given an ordered set of points representing a polygon, how can one determine its winding?

A quick Google search leads to this Stack Overflow answer and the following formula:

\begin{equation} \sum_{n=1}^N(x_{n+1} - x_n)(y_{n+1} + y_n) \end{equation}

Where \((x_n,y_n)\) are the coordinates of \(P_n\) and \((x_{N+1}, y_{N+1}) = (x_1,y_1)\).

The polygon has a CW winding if the quantity in 1 is positive and a CCW winding otherwise.

This formula is easy to calculate, but not necessarily easy to understand. Why does it work? Reading the comments on Stack Overlow lead to the Shoelace Formula which in turn will have you dusting off your Calculus book looking into Green’s Theorem. At which point you might simply decide to accept it. Fortunately, a simpler geometric explanation is available.

Consider the simple polygon shown in figure 3. Ignore the winding for a moment and consider how might we determine the area (in square units) bounded by this polygon?

simple_polygon_trim

Figure 2 - A simple polygon

Got it? No? Me neither. So is there some related problem we do know how to solve? Maybe involving a partial solution to our problem?

Our polygon is made of of several line segments. The area bounded by each segment and the x-axis is a trapezoid, as shown in figure 3.

segment_trapezoid_trim

Figure 3 - Trapezoidal area bounded by line segment and x-axis

Can we determine this area?

Again, let’s try to find a related but simpler problem to solve.Consider the rectangle given in figure 4, in which the top edge passes though the midpoint, \(P_C\), of our line segment at position \( (\frac{x_2 + x_1}{2}, \frac{y_2 + y_1}{2}) \).

segment_trapezoid_rec_trim

Figure 4 - Converting trapezoidal area probl to rectangle area problem

The formula for the area of the rectangle is well known, given by \(base \times height\).

More specifically in this case

\begin{equation} A = (x_2-x_1) \frac{y_1+y_2}{2} \end{equation}

The area of this rectangle is equal to the area of the cross-hatched region + the area of triangle A (figure 4). The area of our trapezoid is equal to the area of the cross-hatched region + the area of triangle B. So if we can prove that triangle A is congruent to triangle B (and therefore have the same area) then we can prove that the rectangle and the trapezoid have the same area.

segment_trapezoid_rec_triangles_trim

Figure 5 - Trapezoid/Rectangle common area

Since point PC is the midpoint of segment P1P2 (thus splitting it evenly in x and y) we know that the triangles have congruent sides as shown in figure 6.

segment_trapezoid_rec_triangles_congruent_trim

Figure 6 - Triangle congruence

From plane geometry we know that two triangles with three congruent sides are congruent (side-side-side) and therefore triangle A is congruent to triangle B. So the area of the rectangle is the same as the area of trapezoid. The formula for the area of the trapezoid is then given by equation 2.

Notice that the sign of the area depends on the order of points given for the line segment:

\begin{equation} \begin{split} A_{12} & = (x_2 - x_1) \frac{y_2 + y_1}{2} \\
& = -1 (x_1 - x_2) \frac{y_2 + y_1}{2} \\
& = -1 (x_1 - x_2) \frac{y_1 + y_2}{2} \\
& = -A_{21} \end{split} \end{equation}

The area is positive if our points are ordered from left (lower x) to right (higher x). This will be important in our final solution to determining the winding.

So we can solve for the area of the trapezoid under the line segment. Does this help us to find the area bounded by the polygon?

Consider the area bounded by the upper line segments in our polygon and x-axis, as shown in figure 8.

upper_segments_trim

Figure 8 - Upper segments area

Now consider the area bounded by the lower line segments (figure 9).

lower_segments_trim

Figure 9 - Lower segments area

When we take the difference between the two areas, we are left with the area of the bounding polygon (figure 10).

all_segments_trim

Figure 10 - Difference between upper and lower bounding areas

So, if we could somehow know which segments were upper segments and which lower, we could subtract the lower bounding areas from the upper bounding areas to get our final answer. It turns out that this is unnecessary.

Remember that the sign of the area under each segment is determined by the order of the points, with \(A_{AB} = -A_{BA}\). So if we traverse our list of points for the polygon in CW order and compute the area under each segment, as we traverse the upper segments we will be moving in the direction of increasing X (left to right). And as we process the lower segments, we will be moving in the direction of decreasing X (right to left). So the areas we calculate for the upper segments will naturally have positive areas, while the areas of the lower segments will be negative. Summing these together will give us the area bounded by the polygon.

\begin{equation} \begin{split} A_{CW} & = \sum_{n=1}^N(x_{n+1} - x_n) \frac{y_{n+1} + y_n}{2} \\
& = \frac{1}{2} \sum_{n=1}^N(x_{n+1} - x_n)(y_{n+1} + y_n) \end{split} \end{equation}

Now, back to our original question of winding. What happens to the area if we traverse the polygon points in the opposite direction, CCW? Each segment area will have the opposite sign of that in equation 3.

\begin{equation} \begin{split} A_{CCW} & = \frac{1}{2} \sum_{n=1}^N(x_n - x_{n+1})(y_n + y_{n+1}) \\
& = -\frac{1}{2} \sum_{n=1}^N(x_{n+1} - x_n)(y_{n+1} + y_n) \\
& = -A_{CW} \end{split} \end{equation}

Finally, we are back to our original question. If we traverse our points in the order given and compute the area using equation 3, if the sign of the area is positive, the points are in CW order. If the sign of the area is negative, the points are in CCW order.

Since all we want to do is to determine the winding, we can drop the 1/2 factor in equation 3 which leads us back to our original formula

\begin{equation} \nonumber \sum_{n=1}^N(x_{n+1} - x_n)(y_{n+1} + y_n) \end{equation}

The nice thing about this formula is that it works for concave polygons as well as convex ones. Consider the concave polygon in figure 10.

concave poly

Figure 10 - Concave polygon

We can see from the area under the top segments and bottom segments (figures 11 and 12) that the difference (figure 13) is still the area inside the polygon as with the convex polygon from figure 2.

concave top

Figure 11 - Area under upper segments

concave bottom

Figure 12 - Area under the lower segments

concave diff

Figure 13 - Difference between top and bottom is area of concave polygon