Quickly determining if a closed polyline is clockwise or counterclockwise
Is there a fast way to determine if a closed polyline is clockwise or counterclockwise?
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?
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.
(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 selfintersecting? If not, you're hosed, since it'd have both clockwise and counterclockwise portions in that case.
The good news is I know the polygon to be nonselfintersecting, and I also know that the polygons will always be clockwise when they're "positive" and counterclockwise 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.
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.
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.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
? Techniques for determining speed / efficiency  Elphaba  9  6,359 
Jul 19, 2009 03:42 AM Last Post: DoG 

Quickly refreshing NSViews  Steven  24  12,821 
Nov 13, 2002 07:30 AM Last Post: Steven 