Polygonflow: clockwise or counter-clockwise?
massung at gmail.com
Wed Feb 3 17:27:23 CST 2010
Sorry, but the problem you are running into is that (in your second example)
you are working with a concave polygon instead of convex. I promise, using
the cross-product is 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
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.
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.
On Wed, Feb 3, 2010 at 4:55 PM, Alex Tweedly <alex at tweedly.net> wrote:
> Jeff Massung wrote:
>> I assume you are talking about 2D polygons...
>> Just take a 3D cross product of the first two vector (P3 - P2) x (P2 -
>> If the resultant vector is coming out of the screen (Z < 0) then the
>> is counter-clockwise. If it is going into the screen (Z > 0) then the
>> polygon is clockwise.
>> That page may be of help if you don't know what the cross product is.
>> to do the 3D cross product, just use Z=0 for all the points.
> Well, I confess I don't properly remember what the cross-product is, so I
> will go read that page.
> But even without doing so, I am sure that this can't be a correct solution;
> the following two polygons have opposite flow, but P1, P2 and P3 are the
> 0,0; 100,0; 100,100; 0,0 (i.e. a counter-clockwise triangle)
> 0,0; 100,0; 100,100; 200,100; 200,-10; 0,-10; 0,0 (i.e. a clockwise
> I'll post a couple of suggested solutions shortly (once I've got the stack
> running properly)
> -- Alex.
> use-revolution mailing list
> use-revolution at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
More information about the use-livecode