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.
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 Overflow 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?
Got it? No? Me neither. So is there some related problem we do know how to solve?nMaybe 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.
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}) ).
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.
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.
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.
Now consider the area bounded by the lower line segments (figure 9).
When we take the difference between the two areas, we are left with the area of the bounding polygon (figure 10).
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} \ n & = 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}) \ n & = -frac{1}{2} sum_{n=1}^N(x_{n+1} – x_n)(y_{n+1} + y_n) \ 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.nIf 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 whichnleads us back to our original formula
begin{equation}
onumbersum_{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.
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.
