PDA

View Full Version : how to sort points set by CCW or CW?



jdz_simon
05-11-2004, 08:24 AM
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 !

lxnyce
05-11-2004, 03:56 PM
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.

jdz_simon
05-12-2004, 01:34 AM
Thank you very,very much.If you can provide the verified sourcecode at your convenience,it will be very nice.Thank you again!

jdz_simon
05-12-2004, 01:39 AM
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.

Michael Steinberg
05-12-2004, 06:13 AM
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.

Michael Steinberg
05-12-2004, 06:26 AM
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...

jdz_simon
05-12-2004, 06:36 AM
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.

Michael Steinberg
05-13-2004, 08:47 AM
Then take this as a task to learn it... I don't have that source code at my hands anymore.