Avoid Area() to compute clockwiseness

[alexisnaveros]

There are a couple places where the code computes the Area() of a given list of vertices to determine if a contour is clockwise or counterclockwise. That seems like a good idea, but unfortunately, it is not reliable.

The reason is simple: if the shape/contour has millions of vertices, adding up a ton of tiny values (of both signs) into a "double" has no accuracy whatsoever. The sign of the result is determined by what values still manage to accumulate beyond a certain point, and where the sum had started along the contour.

Trust me on this, I have faced that problem before. :) I know two tricks to solve this satisfactorily:

#⁠0: If you know the shape/contour has proper topology (not crossing over itself, ideally no duplicate points), you can simply locate a top/bottom most vertex, and check its two connected edges, like this:
http://www.rayforce.net/clipper2stuff/clockwiseness.c

#⁠1: Or, instead of a double precision float, you can use Shewchuk summation to accumulate the result. Besides being a bit slow, it is critical that the compiler must NOT be allowed to reorder any operation while optimizing. See the
__attribute__((__optimize__("no-associative-math", "no-unsafe-math-optimizations", "no-fast-math"))) attribute for GCC in that code:
http://www.rayforce.net/clipper2stuff/mathshewchuk.h

You might not have seen that problem yet, but you can be sure that it will happen if people push millions of vertices... Thanks!

[AngusJohnson]

Trust me on this, I have faced that problem before. :) I know two tricks to solve this satisfactorily:

And trust me, I know a few tricks too 😜. And in the past (in earlier versions of Clipper1) I did use the method you've indicated.
But it too isn't always reliable because very occasionally polygons will have tiny self-intersections (due to rounding) that muck up the orientation. In short there's no perfect solution. However, I can see that with the areas you're describing, the Area calculation isn't reliable either. So with that in mind, and given that Clipper2 does a better job at removing these self-intersections, I'd be happy to review this.