Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Page 1 of 2 12 LastLast
Results 1 to 10 of 11

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

  1. #1
    Junior Member Newbie
    Join Date
    Feb 2004
    Location
    jingdezhen,jiangxi,China
    Posts
    15

    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. #2
    Junior Member Newbie
    Join Date
    May 2003
    Location
    USA
    Posts
    26

    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. #3
    Junior Member Newbie
    Join Date
    Feb 2004
    Location
    jingdezhen,jiangxi,China
    Posts
    15

    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. #4
    Junior Member Newbie
    Join Date
    Feb 2004
    Location
    jingdezhen,jiangxi,China
    Posts
    15

    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. #5
    Senior Member OpenGL Pro
    Join Date
    May 2000
    Location
    Hannover, Germany
    Posts
    1,074

    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. #6
    Senior Member OpenGL Pro
    Join Date
    May 2000
    Location
    Hannover, Germany
    Posts
    1,074

    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. #7
    Junior Member Newbie
    Join Date
    Feb 2004
    Location
    jingdezhen,jiangxi,China
    Posts
    15

    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. #8
    Senior Member OpenGL Pro
    Join Date
    May 2000
    Location
    Hannover, Germany
    Posts
    1,074

    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. #9
    Super Moderator OpenGL Guru dorbie's Avatar
    Join Date
    Jul 2000
    Location
    Bay Area, CA, USA
    Posts
    3,971
    Generate edges between points, use dot products between edges to determine angles and winding and order accordingly.
    Last edited by dorbie; 12-13-2016 at 10:54 AM.

  10. #10
    Administrator Regular Contributor Khronos_webmaster's Avatar
    Join Date
    Apr 2007
    Location
    Montreal
    Posts
    184
    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"
    Webmaster Khronos.org and OpenGL.org

Posting Permissions

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