Quickly determining if a closed polyline is clockwise or counter-clockwise - Printable Version +- iDevGames Forums ( http://www.idevgames.com/forums)+-- Forum: Development Zone ( /forum-3.html)+--- Forum: Game Programming Fundamentals ( /forum-7.html)+--- Thread: Quickly determining if a closed polyline is clockwise or counter-clockwise ( /thread-8814.html) |

Quickly determining if a closed polyline is clockwise or counter-clockwise - TomorrowPlusX - Apr 9, 2011 11:56 AM
Is there a fast way to determine if a closed polyline is clockwise or counter-clockwise? RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - stevejohnson - Apr 9, 2011 12:32 PM
Any guarantees about being concave/convex? RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - TomorrowPlusX - Apr 9, 2011 12:44 PM
(Apr 9, 2011 12:32 PM)stevejohnson Wrote: Any guarantees about being concave/convex? No, sadly. RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - Skorche - Apr 9, 2011 01:24 PM
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? RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - ThemsAllTook - Apr 9, 2011 01:40 PM
(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. RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - TomorrowPlusX - Apr 9, 2011 01:53 PM
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. RE: Quickly determining if a closed polyline is clockwise or counter-clockwise - Skorche - Apr 9, 2011 04:03 PM
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. |