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

jdz_simon

05-11-2004, 09: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, 04: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, 02: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, 02: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, 07: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, 07: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, 07: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, 09:47 AM

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

dorbie

12-07-2016, 02:53 AM

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

Khronos_webmaster

12-07-2016, 07:27 AM

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"

dorbie

12-13-2016, 10:54 AM

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

Corrected to say dot products (cringe).

Powered by vBulletin® Version 4.2.3 Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.