# Thread: how to sort points set by CCW or CW?

1. ## how to sort points set by CCW or CW?

I just want to map some screenshot in order to explain my trouble,But I can't make it,can you tell me how to upload some pictures in this forum?
a question:If I have an array stored disorderly many points,which is gained from detecting the edges of 0-1 bitmap,how can I turn those points sequence into Clockwise-Ordered points sequence so that I can render the polygon made up of those points via OpenGL commands?
i.e. Assume that the array pt[0]={1,1} pt[1]={0,0},pt[2]={0,1},pt[3]={1,0},pt[4]=......,
I want the CCW sequence,that is,pt[0]={1,1},pt[1]={0,1},pt[2]={0,0},pt[3]={1,0}.....,you know.
Perhaps a sort algorithm!
Thank you !

2. ## Re: how to sort points set by CCW or CW?

I believe this is a computational geometry problem. I am guessing its the same idea as me generating X amount of random points, and forming a polygon out of them by sorting angularly.

You can actually sort the points using a quicksort algorithm (or any other sort algorithm of your choice).

http://cs.smith.edu/~orourke/

The algorithm I am about to describe is from the book in the link above, only using bubble sort.

Given N points
1. Find the bottom most right most point. Move it to position 1 in your point array.
2. Make a line segment from Point 0 and Point I and comare it to see which side point I+1 lies on. If I+1 is on the right hand side, then you have to swap point I and I+1.
3. Do this for I = n-1 points and repeat till you have no swaps.

I would provide source, but it would take me some time to strip it out. Besides, I think if you understand the algorithm it would be best. I hope this is what you're looking for.

3. ## Re: how to sort points set by CCW or CW?

Thank you very,very much.If you can provide the verified sourcecode at your convenience,it will be very nice.Thank you again!

4. ## Re: how to sort points set by CCW or CW?

sorry,the website you provided is unaccessible or wrong,Would you like check out the address for me ? I want to read some profile for my problem .Thank you again.Welcome to China,Welcome to JingDeZhen,which is very famous for ceramic manufacture.

5. ## Re: how to sort points set by CCW or CW?

I actually found it quite nice to have the contour developped right as one step of the contrast-finding algorithm. You have eight directions possible from each pixel of your map where the contour can go on. Numerize them in a winded order (0 being north for example). Find any contour point, preferrably some of the uppermost contour part, you will see later why, then start with direction 0. If there's a contrast as well, then that's the next point, if not, try direction 1 etc. Ultimately you're at the new contrast point and need to find the new direction to go to. There you need to start with the direction (7-last_dir+1)%8. Then find the next point going around the directions from that direction, possibly overflowing and starting at 0 again. Etc.
Afterwards you have only to detect the end of the loop, so check wether you arrive at the first point again.
I don't know if that was exactly what i did back when i was 17, but i hope you get the idea. Damn, i expressed it very badly.

6. ## Re: how to sort points set by CCW or CW?

Ow, and of course the winding you sort the directions in and/or the winding you check for them distiguishes the winding order of the outcoming contour...

7. ## Re: how to sort points set by CCW or CW?

thanks,I do know your method and I draft it on my paper,really it is feasible.But would you give the sourcecode for your algorithm for me ?
I am a newer for algorithm design.

8. ## Re: how to sort points set by CCW or CW?

Then take this as a task to learn it... I don't have that source code at my hands anymore.

9. Generate edges between points, use dot products between edges to determine angles and winding and order accordingly.

10. Someone suggested you might find help here:

"You may refer the book "Advanced graphics programming, Using OpenGL", McReynolds, 1.3.2 Vertex Winding Order, pp.11"

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•