Sign in to follow this  
Spa8nky

Given a set of points and a normal, how can I arrange the points in a CCW order?

Recommended Posts

If I have a set of random points and a normal, is it possible to order the points counter clockwise based on the direction of the normal?

Share this post


Link to post
Share on other sites
No you need a point of reference around which to order the points along with a normal. A ray for instance would suffice. Once you have one though projecting to the plane then ordering the points is simple. One way I've done it before was to use a quicksort algorithm that partitions via a dot product. (Cuts the number of points in which to order by half every time).

Share this post


Link to post
Share on other sites
That's cool. I have a point of collision and a normal so I can now create a ray.

How would I proceed from here?

EDIT: You must have edited your post during my reply or maybe I didn't catch the quicksort algorithm sentence when reading your post.

Would you mind posting the point sorting algorithm?

[Edited by - Spa8nky on March 13, 2010 8:38:24 PM]

Share this post


Link to post
Share on other sites
Oh man you got lucky. I wrote a test for it apparently. Source for 2D circle sort. There's probably a better way actually. I wrote that algorithm without researching really. You should be able to throw it into whatever algorithm you're writing though.

Share this post


Link to post
Share on other sites
Thank you very much. I'm delving into it now and it will no doubt come in handy as part of my geometry toolset.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this