Polygonflow: clockwise or counter-clockwise?

[Alex Tweedly]

Jeff Massung wrote:
> Michael,
>
> Sorry, but the problem you are running into is that (in your second example)
>   
The examples were from me (Alex) not Michael :-)
> you are working with a concave polygon instead of convex.
Yes. Exactly. There *are* polygons which are concave. We could all look 
at them and agree on where the inside of the polygon is, and therefore 
all agree on whether the perimeter is defined clockwise or 
anti-clockwise around that interior.
>  I promise, using
> the cross-product is correct.
>   
If you define the problem space to be limited to convex polygons, then 
it is correct. But if you want to handle all (or almost all - see below) 
polygons, then it is not correct.
> Concave polygons get tricky, because the winding actually does - in fact -
> change direction. You - as a human - are simply looking at the resulting,
> whole polygon and making a determination from that, which is actually
> wrong.
>
>   
The conclusion that you arrive at from looking at the whole polygon is 
correct; the winding around the interior is consistent; the direction 
change in co-ordinate space changes, but not relative to the interior.
> You have a couple options:
>
> 1. Perform the cross product across all points from last to first - exactly
> as I originally described, and count the winding directions of each, taking
> the greater of the two.
>
>   
Sorry, that doesn't work consistently either. Picture a regular 12-sided 
figure, with two sides vertical, and defined counter-clockwise. The c-p 
will give the same answer for all 12 vertices. Then draw a much larger 
square around it, such that one of the vertical sides of the square 
overlaps the vertical side of the shape (and the square encloses the 
shape). Now "erase" the line segment which is shared - we now have a 
16-sided figure, and let's define it in the order that the points from 
the original 12-sided figure remain counter-clockwise. (Note that the 
area inside the original figure is now outside this new figure). This 
new  figure is actually (according to humans :-) defined clockwise - but 
the c-p will still give the same answer for all those original points, 
so it would have 10 saying counter-clockwise, and only the 6 new ones 
would say clockwise - and hence get the wrong answer.
> 2. If you know the majority of your polygons are shaped a particular way, an
> often-used trick is to take P(N), P(2), and P(1) and simply use those as a
> quick and dirty test.
>
> Option #1 will produce the desired, correct result, but takes more time.
> Option #2 can very often be wrong, but given your use-cases could be right
> 100% of the time.
>   
Option #1 gives unreliable answers in some cases, such as the example above.
Option #2 gives very unreliable answers

And there are simple (though not super-fast) solution that get the 
answer correct (i.e. agreeing with what a person would say) for all 
cases where people would agree.

There are more complex cases (e.g. self-inverting polygons, which you 
could argue are malformed polygons) where there is probably no correct 
answer.

-- Alex.