Jump to content
  • Advertisement
Sign in to follow this  
Jannes

Sorting polygon corners (counter-)clockwise

This topic is 4771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I actually have two questions concerning 2D convex polygons and 3D convex polytopes. I am using OpenGL to display these. I have the corners of the polygon or polytope, but they aren't ordered clockwise or counterclockwise like its needed for OpenGL to render them properly. So my first question is, how you can sort them in a way OpenGL can handle the polygon. My second question is about how to divide a polytope into its 2D polygons where the corners are also not sorted. Would love to have some hints on literature in the web or books, cause i need it for a work in study. Thanks alot.

Share this post


Link to post
Share on other sites
Advertisement
Hmm, maybe I ain't thinking clear as I just come home from work, but wouldn't any polygon's pointes either be listed clockwise or counter-clockwise?
If this is true, the solution is quite simple:
if clockwise then reverse corner order

Share this post


Link to post
Share on other sites
assuming you can measure angles between vectors in a full-circle all you need todo is to pick a refrence vector in your plane the mean of all vertices would probably suffice then you calculate the angle between that point and v0 for each other vertex, sort according to that value and you have your vertice order.

Share this post


Link to post
Share on other sites
From the calculations that are done its not guaranteed that the corners are in right order. They might look like this:



..2O.....
.../..\....
1O....\...
...\.....\..
....\.....\.
...3O---O4

should look after sorting:

..2O.....
.../..\....
1O....\...
...\.....\..
....\.....\.
...4O---O3

Share this post


Link to post
Share on other sites
easy way to sort out the polygons:

N = polygons normal.
C = vector from the center of the convex object to any point on the polygon.

The dot product (N dot C) should be above zero. if not then flip the polygon (reverse the vertex order).

tip: if you are loading the polygons from a file you should remember to save the result of the sorting so you won't have to do it again each time the file is read.

Share this post


Link to post
Share on other sites
Thanks so far, but i dont meant to revert the order of the corners in polygon. They need to be ordered in clockwise or counterclockwise orientation first, cause they arent ordered in any way (think of a set). Reread my second post please.

Share this post


Link to post
Share on other sites
Quote:
Original post by DigitalDelusion
assuming you can measure angles between vectors in a full-circle all you need todo is to pick a refrence vector in your plane the mean of all vertices would probably suffice then you calculate the angle between that point and v0 for each other vertex, sort according to that value and you have your vertice order.


The reference vector should be an inner point of the polygon, right? How can i easily get one?

Share this post


Link to post
Share on other sites
If your polygon points are not ordered at all, how do you know what the polygon it is at all. I.E. how do you know which point is connected to which point with an edge?

Share this post


Link to post
Share on other sites
Quote:
Original post by Jannes
The reference vector should be an inner point of the polygon, right? How can i easily get one?


If the polygon is convex then the mean of all the vertices is good point.

Share this post


Link to post
Share on other sites
If the polygon is not convex then the points don't form a unique description of a polygon anyway, so it would be fair to assume that it's convex. (imagine 5 points in a pentagon, and a 6th point at the center of the 5. The center point could be inserted in between any of the 5 neighbouring pairs around the edge and still form a non-self-intersecting 2D polygon. For the convex case, going clockwise around the center point, as several previous posters said, should be fine.

As for the 3D problem - we still have to assume it is convex, for just the same reason, so any of the convex hull algorithms should do the trick - they will give a set of polygons which together form the surface.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!