Simple Polygon Orientation

From CGAFaq

Compute the signed area of the polygon. The orientation is counter-clockwise if this area is positive.

A slightly faster method is based on the observation that it isn't necessary to compute the area. Find the lowest vertex (or, if there is more than one vertex with the same lowest coordinate, the rightmost of those vertices) and then take the cross product of the edges fore and aft of it. Both methods are O(n) for n vertices, but it does seem a waste to add up the total area when a single cross product (of just the right edges) suffices. Code for this is available at ftp://cs.smith.edu/pub/code/polyorient.C (2K).

The reason that the lowest, rightmost (or any other such extreme) point works is that the internal angle at this vertex is necessarily convex, strictly less than pi (even if there are several equally-lowest points).

This method is based on the assumption the the polygon does not have coinciding vertices. If the lowest, rightmost vertex has adjacent zero-length edges it will be necessary to search for non-degenerate edges. Note that if the polygon is already closed (i.e. the first vertex is equal to the last), and the list of vertices is extended by repeating the first vertex after the last, a degenerate edge will result. Note also that tests of vertex equality and zero edge-length may have to take round of errors into account, and it may be diffucult to select appropriate tolerances for these tests. These problems are avoided with the area-sign method.