Quickly determining if a closed polyline is clockwise or counter-clockwise

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
Is there a fast way to determine if a closed polyline is clockwise or counter-clockwise?
Quote this message in a reply
Moderator
Posts: 680
Joined: 2002.11
Post: #2
Any guarantees about being concave/convex?

My web site - Games, music, Python stuff
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #3
(Apr 9, 2011 12:32 PM)stevejohnson Wrote:  Any guarantees about being concave/convex?

No, sadly.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #4
So there is an algorithm for determining if a point is in a concave polygon that you could modify I think. You cast a ray in a random direction and record the number of times it intersects the perimeter. If the number is odd, you are inside.

If you record the last perimeter segment that you intersected, then you could use the direction of the segment and the direction of the ray to check the winding I think. I can't really think of any cases where this would fail. It's O(n) runtime, but it wouldn't really use any expensive trig functions.

You do need a point inside the polygon to start though. An easy way to handle that would be to pick a segment on the perimeter. Have the point be the midpoint of the segment, and the ray direction be it's negative normal.

Does this make any sense?

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #5
(Apr 9, 2011 01:24 PM)Skorche Wrote:  You do need a point inside the polygon to start though. An easy way to handle that would be to pick a segment on the perimeter. Have the point be the midpoint of the segment, and the ray direction be it's negative normal.

How will you know the normal if you don't know the winding order, though? I suppose you could check in both possible normal directions, and determine winding based on which one gets an intersection with another segment.

You say there's no guarantee of convexity/concavity; hopefully there's at least a guarantee that it's not self-intersecting? If not, you're hosed, since it'd have both clockwise and counterclockwise portions in that case.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
The good news is I know the polygon to be non-self-intersecting, and I also know that the polygons will always be clockwise when they're "positive" and counter-clockwise when they're "holes" in the positive polygons.

That's about it, though.

So I guess I can trust the segment ordering to pick a point along the negative normal.

I'm going to have to think about this. But I've had a long day unsuccessfully trying to fix a really important graph topology bug... and it's much higher on my priority list than this.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #7
Hmm. That's a good point. I suppose it doesn't really matter though. Instead of making a ray, make a splitting plane and pick either the min or the max extrema point. I *think* you could still find the winding that way, but maybe it would flip the winding if you picked the wrong normal? I'd have to think about it more.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  ? Techniques for determining speed / efficiency Elphaba 9 4,757 Jul 19, 2009 03:42 AM
Last Post: DoG
  Quickly refreshing NSViews Steven 24 11,228 Nov 13, 2002 07:30 AM
Last Post: Steven