Sorting polygon corners (counter-)clockwise
Author
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.
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
If this is true, the solution is quite simple:
if clockwise then reverse corner order
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.
Author
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
..2O.....
.../..\....
1O....\...
...\.....\..
....\.....\.
...3O---O4
should look after sorting:
..2O.....
.../..\....
1O....\...
...\.....\..
....\.....\.
...4O---O3
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.
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.
Author
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.
Author
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?
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?
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
