Kami no Itte ga ore ni zettai naru!
algorithm for making vertices in CCW order
Author
You calculate the center point of the polygon, by adding up all the vertices and deviding by the number of vertices (like finding the ''average'' point)
Then you can find vectors from the center point to any vertex in the polygon.
By comparing 2 vectors (with dotProduct), you can determine the angle between the 2 vectors.
So, starting with any vertex in the poly, find a vector by subtracting it from the center point. Find vectors similarly for all other vertices in the poly.
Taking any arbitrary vertex as the ''first'' vertex, you can determine the next vertex by seeing which vector has the smallest angle with your start one.
This way, you get your vertices ordered, although you dont know if they are CW or CCW at this point. By looking at the normal of the poly, you can tell if you need to reverse your verts or not, depending on whether you want CW or CCW.
I havnt implemented it yet, and there are probably a bunch of quirks and special cases I havnt thought of, but I dont think these will affect the time complexity of the algorith, except by a constant factor, and it is not NP as far as I can tell.
Then you can find vectors from the center point to any vertex in the polygon.
By comparing 2 vectors (with dotProduct), you can determine the angle between the 2 vectors.
So, starting with any vertex in the poly, find a vector by subtracting it from the center point. Find vectors similarly for all other vertices in the poly.
Taking any arbitrary vertex as the ''first'' vertex, you can determine the next vertex by seeing which vector has the smallest angle with your start one.
This way, you get your vertices ordered, although you dont know if they are CW or CCW at this point. By looking at the normal of the poly, you can tell if you need to reverse your verts or not, depending on whether you want CW or CCW.
I havnt implemented it yet, and there are probably a bunch of quirks and special cases I havnt thought of, but I dont think these will affect the time complexity of the algorith, except by a constant factor, and it is not NP as far as I can tell.
If your polygon is simple convex, it should work.
For an arbitrary, possibly concave or self-intersecting
polygon, the problem of ordering into CW or CCW is quite
a bit harder (if even possible).
For one thing, finding the "center" of the polygon is, um,
not easy.
I mentioned NP because your original problem didn''t have
the convex constraint.
Try the following (number denotes a vertex):
.................
.............1...
.................
...4....3........
.................
.............2...
.................
The polygon is supposed to look like 1324 (in CW order).
Now imagine for 100+ points.
Kami no Itte ga ore ni zettai naru!
For an arbitrary, possibly concave or self-intersecting
polygon, the problem of ordering into CW or CCW is quite
a bit harder (if even possible).
For one thing, finding the "center" of the polygon is, um,
not easy.
I mentioned NP because your original problem didn''t have
the convex constraint.
Try the following (number denotes a vertex):
.................
.............1...
.................
...4....3........
.................
.............2...
.................
The polygon is supposed to look like 1324 (in CW order).
Now imagine for 100+ points.
Kami no Itte ga ore ni zettai naru!
Author
Its true I didnt mention that my polys were convex in my original post, but I did say it in a subsequent post. Besides, isnt it safe to assume that everyone''s polys are convex unless otherwise stated? I mean, who uses concave polys in games anyway?
Seriously though, I thought it was rare to use for example a square instead of a triangle, let alone some weirdo concave shape.
Finding the center for convex polys is as simple as finding the average of all the vertices, as I mentioned. It doesnt even have to really be the exact center for my purposes, just a point that is inside the polygon. It just so happens that for convex polys, its easy enough to find the exact center that you might as well do it.
Thanks for all your input. I might post back here again before my task is complete.
Seriously though, I thought it was rare to use for example a square instead of a triangle, let alone some weirdo concave shape.
Finding the center for convex polys is as simple as finding the average of all the vertices, as I mentioned. It doesnt even have to really be the exact center for my purposes, just a point that is inside the polygon. It just so happens that for convex polys, its easy enough to find the exact center that you might as well do it.
Thanks for all your input. I might post back here again before my task is complete.
Here's some code I wrote to do the sorting of vertices. Sorry its not commented, its just one of things I wrote and forgot about. My polygon3d struct used linked lists for the vertices so it may be a bit hard to follow, but im sure if you spend some time with it, itll make sense.
Stefan Hajnoczi originally wrote a version in his paper here:
http://folk.uio.no/stefanha/MAPFiles.pdf
Stefan's original version had an issue where the angle between the vectors formed by the center of the polygon and two vertices of the polygon would end up being smaller than the angle between the current vertex and the vertex thats supposed to be next in order. Hard to explain really, but it would end up with incorrectly ordered vertices. I found a fix to the problem and implemented it in my code, but its been so long since I wrote this, I forgot what the fix boiled down to and how it differed from his code.
I have both versions still in code and I think my version searched for the largest angle rather than the smallest.
One last thing, this might actually sort them in CW order. Heh, I really dont remember.
In any event, I hope this helps.
-=[ Megahertz ]=-
[edited by - Megahertz on January 12, 2004 1:32:43 PM]
[edited by - Megahertz on January 12, 2004 7:03:33 PM]
int SortVertices2 (Polygon3d *poly){ double BiggestAngle; double dp; Vertex3d *Biggest=NULL;; Vector3d a; Vector3d b; Vector3d an; Vector3d bn; Vertex3d *tempvert1; Vertex3d *tempvert2; tempvert1=poly->vertexlist; a.x=tempvert1->next->vertex.x-tempvert1->vertex.x; a.y=tempvert1->next->vertex.y-tempvert1->vertex.y; a.z=tempvert1->next->vertex.z-tempvert1->vertex.z; an.x=a.x; an.y=a.y; an.z=a.z; a=Normalize(&a); for (int i=0; i<poly->num_pts-1; i++) { BiggestAngle=1; tempvert2=tempvert1->next; for (int j=i+1; j<poly->num_pts; j++) { b.x=tempvert2->vertex.x-tempvert1->vertex.x; b.y=tempvert2->vertex.y-tempvert1->vertex.y; b.z=tempvert2->vertex.z-tempvert1->vertex.z; bn.x=b.x; bn.y=b.y; bn.z=b.z; b=Normalize(&b); dp=DotProduct(&a,&b); if (dp<BiggestAngle) { BiggestAngle=dp; Biggest=tempvert2; } tempvert2=tempvert2->next; } a.x=tempvert1->vertex.x-Biggest->vertex.x; a.y=tempvert1->vertex.y-Biggest->vertex.y; a.z=tempvert1->vertex.z-Biggest->vertex.z; an.x=a.x; an.y=a.y; an.z=a.z; a=Normalize(&a); SwapVertices (tempvert1->next,Biggest); tempvert1=tempvert1->next; } return 1;}Stefan Hajnoczi originally wrote a version in his paper here:
http://folk.uio.no/stefanha/MAPFiles.pdf
Stefan's original version had an issue where the angle between the vectors formed by the center of the polygon and two vertices of the polygon would end up being smaller than the angle between the current vertex and the vertex thats supposed to be next in order. Hard to explain really, but it would end up with incorrectly ordered vertices. I found a fix to the problem and implemented it in my code, but its been so long since I wrote this, I forgot what the fix boiled down to and how it differed from his code.
I have both versions still in code and I think my version searched for the largest angle rather than the smallest.
One last thing, this might actually sort them in CW order. Heh, I really dont remember.
In any event, I hope this helps.
-=[ Megahertz ]=-
[edited by - Megahertz on January 12, 2004 1:32:43 PM]
[edited by - Megahertz on January 12, 2004 7:03:33 PM]
Ok I looked over my code and figured out how mine works =)
Basically rather than using a center point as a base for the vectors, I basically pick 2 vertices, then create a vector using these 2 vertices. I then iterate through the other vertices and find biggest angle between the two vectors I can find. Once I do, I know that the last segment I created with the 3rd vertex is the first edge of the polygon. From there I just continue using the other vertices to create vectors and compare the angles, every time i find the biggest angle, that segment is the next edge of the polygon.
This method will only work with convex polygons as far as I can tell.
-=[ Megahertz ]=-
Basically rather than using a center point as a base for the vectors, I basically pick 2 vertices, then create a vector using these 2 vertices. I then iterate through the other vertices and find biggest angle between the two vectors I can find. Once I do, I know that the last segment I created with the 3rd vertex is the first edge of the polygon. From there I just continue using the other vertices to create vectors and compare the angles, every time i find the biggest angle, that segment is the next edge of the polygon.
This method will only work with convex polygons as far as I can tell.
-=[ Megahertz ]=-
Author
Thanks, Megahertz! That helps a whack.
I havnt had a chance yet to look through your code in detail, but one thing I noticed is that you use a variable called biggestAngle and in your explanation I think you even said that you look for the biggest angle.
As far as I know, this is incorrect. Im not saying its an incorrect way of doing it, just that you seem to be confused.
The dotProduct funcion will return a float value between -1 and 1. These values can be mapped to degree angles that we are more used to. For example:
-1 is 180 degrees
0 is 90 degrees
+1 is 0 degrees
So when you say "biggestAngle", and you are referring to the -1 to +1 value returned by this code:
dp=DotProduct(&a,&b);
, then I think what you actually mean is "smallestAngle", since they are inversely related. For example, the biggest value of "biggestAngle", as you call it, would be +1, which is actually 0 degrees, which is the smallest angle.
Anyway, aside from that I expect to learn a lot from your code, esecially with regard to that special case where you can get the wrong vertex as you said.
Thanks again. If you like, I can post my final version when I get it working (complete with comments! oohhh! ahhh!)
[edited by - AndreTheGiant on January 12, 2004 5:00:38 PM]
I havnt had a chance yet to look through your code in detail, but one thing I noticed is that you use a variable called biggestAngle and in your explanation I think you even said that you look for the biggest angle.
As far as I know, this is incorrect. Im not saying its an incorrect way of doing it, just that you seem to be confused.
The dotProduct funcion will return a float value between -1 and 1. These values can be mapped to degree angles that we are more used to. For example:
-1 is 180 degrees
0 is 90 degrees
+1 is 0 degrees
So when you say "biggestAngle", and you are referring to the -1 to +1 value returned by this code:
dp=DotProduct(&a,&b);
, then I think what you actually mean is "smallestAngle", since they are inversely related. For example, the biggest value of "biggestAngle", as you call it, would be +1, which is actually 0 degrees, which is the smallest angle.
Anyway, aside from that I expect to learn a lot from your code, esecially with regard to that special case where you can get the wrong vertex as you said.
Thanks again. If you like, I can post my final version when I get it working (complete with comments! oohhh! ahhh!)
[edited by - AndreTheGiant on January 12, 2004 5:00:38 PM]
Dot product is given by
u * v = Len(u) * Len(v) * cos(angle between u and v)
so to get the cosine you should divide by Len(u)*Len(v)
The problem is that dot-product give you no info about versus; in practice if a second vertex is CW or CCW you get the same result (because cos(-x)=cos(x) )
You should use also the cross product to resolve this...
given two 2D vector in (x,y) plane the cross product is
u ^ v = ((ux*vy)-(uy*vx)) z = K z // z is the versor that goes from your monitor to your face...
Note that K is also proportional to sin(angle between u and v)
and it's positive if v is CCW from u, negative if v is CW and zero if u and v are parallel (0 and 180 degree)
Application of math
Consider a point O that is inside your polygon and consider an arbitrary vector (for example v = (0,1) )
For every vertex compute the angle between u = (vertex-O) and v
and use this value to 'sort' your vertices
L = Len(u)*Len(v)
cosa = (u*v)/L
sina = ((ux*vy)-(uy*vx))/L
to get the angle...
If the angle is positive u is CW and vicevers if the angle is negative u is CCW; in the case the angle is negative you can add 2PI to this value to convert angles to positive values; simply use this value to sort vertices in CW order or invert the list and get CCW.
To extend to 3D your problem you should compute the extended cross product w = u^v and normalize it.
Compute the plane-normal n of your poly (select 3 arbitrary vertices and put n = (P2-P0)^(P1-P0) and normalize it).
Then compute K = w*n (dot prod)-> K give you sina.
Compute the 'normalized' dot product
cosa=(u*v)/(Len(u)*Len(v))
Use sina, cosa to get the angle, add 2PI if it is negative, sort in descending order (CCW).
The problem in 3D is that you cannot really sort your vertices in CW or CCW order because...it depends from the observer! If you go behind the poly the order is inverted.
However you can disable the back face culling...
That's all, sorry for my english...
[edited by - blizzard999 on January 12, 2004 7:19:24 PM]
u * v = Len(u) * Len(v) * cos(angle between u and v)
so to get the cosine you should divide by Len(u)*Len(v)
The problem is that dot-product give you no info about versus; in practice if a second vertex is CW or CCW you get the same result (because cos(-x)=cos(x) )
You should use also the cross product to resolve this...
given two 2D vector in (x,y) plane the cross product is
u ^ v = ((ux*vy)-(uy*vx)) z = K z // z is the versor that goes from your monitor to your face...
Note that K is also proportional to sin(angle between u and v)
and it's positive if v is CCW from u, negative if v is CW and zero if u and v are parallel (0 and 180 degree)
Application of math
Consider a point O that is inside your polygon and consider an arbitrary vector (for example v = (0,1) )
For every vertex compute the angle between u = (vertex-O) and v
and use this value to 'sort' your vertices
L = Len(u)*Len(v)
cosa = (u*v)/L
sina = ((ux*vy)-(uy*vx))/L
to get the angle...
REAL Math::GetAngle(REAL cosa, REAL sina){ cosa = Clamp((REAL)-1, cosa, (REAL)1); REAL angle = ACos(cosa); return(sina<0 ? -angle : angle );}If the angle is positive u is CW and vicevers if the angle is negative u is CCW; in the case the angle is negative you can add 2PI to this value to convert angles to positive values; simply use this value to sort vertices in CW order or invert the list and get CCW.
To extend to 3D your problem you should compute the extended cross product w = u^v and normalize it.
Compute the plane-normal n of your poly (select 3 arbitrary vertices and put n = (P2-P0)^(P1-P0) and normalize it).
Then compute K = w*n (dot prod)-> K give you sina.
Compute the 'normalized' dot product
cosa=(u*v)/(Len(u)*Len(v))
Use sina, cosa to get the angle, add 2PI if it is negative, sort in descending order (CCW).
The problem in 3D is that you cannot really sort your vertices in CW or CCW order because...it depends from the observer! If you go behind the poly the order is inverted.
However you can disable the back face culling...
That's all, sorry for my english...
[edited by - blizzard999 on January 12, 2004 7:19:24 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
