Where does this algorithm for detecting whether a polygon's vertices are given counter clock-wise come from?

Question

There's an algorithm I found online which I have been using (I verified it works correctly for both convex and concave polygons). Let's say we have a simple polygon, angles between edges are different from $180$ degrees. Vertices are given in such a way that $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ form an edge.

For each vertex $(x_i, y_i)$, accumulate the sum of $(x_{i+1} - x_{i}) * (y_{i+1} + y_{i})$. If the sum is negative, then the polygon's vertices are given in counter clock-wise order. Else it's clock-wise order (I don't know about the case where the sum equals $0$, I'm not aware if it even exists).

Note that for the last vertex, index $i+1$ goes back to the first one (as in a loop).

I'd like to know the explanation of why this works. If possible, a proof would be appreciated (an intuitive explanation would be enough though).

I thought this was a math/geometry question rather than algorithmic so I posted it here.

Answer 1

Notice that $(x_{i + 1} - x_i) * (y_{i + 1} + y_i)$ is very similar to the formula for the area of a trapezoid. In fact, this formula's absolute value gives twice the area of the trapezoid under the line segment (with the y "height" of the points as the two bases, the x difference as the height. See 1. for a diagram.) from $(x_i, y_i)$ to $(x_{i + 1},y_{i + 1})$.
It is easy to see that this expression gives a positive value when $x_{i + 1} - x_i$ is positive, and vice versa for negative cases. When evaluating clockwisely, the trapezoids on the "top" side of the polygon are positive, while the trapezoids on the "bottom" side of the polygon are negative. This gives twice the area of the polygon.
When evaluating counter-clockwisely, the roles are reversed and the "top" trapezoids are negative, giving twice the area, but negative. This is why this algorithm works, and never seems to spit out 0. The case with points under the y axis also works - but the proof is more complex.
See 2. for a more detailed explanation on how this algorithm works.
References:

1. https://en.wikipedia.org/wiki/Shoelace_formula#/media/File:Trapez-formel-einf.svg
2. https://en.wikipedia.org/wiki/Shoelace_formula#:~:text=as%20one%20of%20its%20four%20edges

Answer 2

First of all, note that

$$ (x_{i+1} - x_i)(y_{i+1} + y_i) = x_{i+1} y_{i+1} + x_{i+1} y_i - x_i y_{i+1} - x_i y_i. $$

When you add this up over all the pairs of vertices $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$, each time the term $x_{i+1} y_{i+1}$ occurs it is canceled by the $- x_i y_i$ term obtained from the next pair of vertices. So in the end you are left with

$$ \sum (x_{i+1} y_i - x_i y_{i+1}). $$

This is the famous Shoelace Formula already mentioned in another answer. There is additional information under the question Proving the Shoelace Method at the Precalculus Level.