Sign in to follow this  
Jannes

Sorting polygon corners (counter-)clockwise

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
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
You can search for a Voronoi 2D algorithm and use the graph to iterate over the points in CC or CW order.

A convex hull algorithm is based on Voronoi and in this case voronoi is good enough for you.

Share this post


Link to post
Share on other sites
If I understand what you are saying correctly, you have a number of points that lie on the same plane, and you want to sort them to be CCW. I recently encountered this exact problem, and this is what I did:

Generate two unit vectors that lie on the plane and are 90 degrees apart (in my case, I already had them)
Find the center of all the points, and use it as the origin for the following calculations
Calculate the angle between each point and the first unit vector. Cannot just use the dot product here because this will only give angles from 0 to PI. Must also calculate the dot product with the other unit vector to determine whether the point in question is greater than PI. If it is (ie. dot product is less than zero) than you must change the angle to 2*PI minus it's current value

This probably sounds confusing (doesn't help that I'm usually not very good at explaining things) but this did work for me.

Share this post


Link to post
Share on other sites
Thanks all,

great help, getting near solution now :). One thing i still dont get right is creating the two reference vectors as averisk suggested.

I actually now have a polyhedron in 3D space (given by an unsorted set of corners). I managed to extract all polygoncorners for each facet. So now i need to sort those polygoncorners as said before. For this i create a ref vector r = (r_1,r_2,r_3)
where r_i = - (random_polygon_corner1_i - random_polygon_corner2_i).
this vector should point outside the polygon (cause convex) and is in same plane as the polygon itself. It seems to me as good to take this vector (and calculate angle with cosine theorem) as taking the polygon center. Ok so far? Now should i create a second ref vector to get angles > 90° which is orthogonal to the first ref vector? Please go a bit more in detail how code could look like.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this