Sign in to follow this  
Ludi83

Ordering Vertices on a plan counter clock wise.

Recommended Posts

Hi, here's the problem: I have a list of vertices, which build a plane. The vertices are unordered. What I now need is, that the vertices get ordered counter-clock-wise. E.g. I have the following vertices (1,0,0),(0,1,0),(1,1,0),(0,0,0). What I need is the now, e.g.: (0,0,0),(1,0,0),(1,1,0),(0,1,0). The maximum vertices count is 12. So I could even life with a brute-force method, which tests all combinations to see if the plane is ccw. This is a simple example, as Z is always 0. This won't always be, but it will always be a plane :) Thanks already for the help.

Share this post


Link to post
Share on other sites
The first thing you need is a function to compute the signed angle between two 3D vectors. Such a function can be implemented as follows (the sign is determined using the 'reference' vector argument):
    vector_type c = cross(v1,v2);
value_type angle = std::atan2(double(length(c)),double(dot(v1,v2)));
return dot(c,reference) < value_type(0) ? -angle : angle;
You can then use the following method to sort a set of vertices known to lie in a plane and to form a convex polygon:

1. Compute the normal of the polygon plane as the cross product of any two non-colinear edges.

2. Compute the average of the vertices (the result being a point).

3. Choose a vertex arbitrarily and assign it an angle of '0'.

4. For every other vertex, compute the signed angle (using the polygon normal as the 'reference' argument to the aforementioned function) between the vector from the 'center' vertex to the current vertex, and the vector from the 'center' vertex to the vertex selected in step 3. Assign this angle to the current vertex.

5. Once all vertices have been assigned an angle, sort them according to their angle value.

How to sort is up to you, but if this is a pre-processing step and/or is not particularly performance critical (and you are using C++), using a std::map is quite convenient for this purpose.

Share this post


Link to post
Share on other sites
The problem cannot be solved unambiguously by just an arbitrary set of points on a plane. Jyk's solution for vertex ordering is correct but it can only be used to guarantee the vertices are ccw ordered in one random direction out of a set of two, depending on the edges chosen in step 1.

Share this post


Link to post
Share on other sites
Quote:
Original post by ruistola
Jyk's solution for vertex ordering is correct but it can only be used to guarantee the vertices are ccw ordered in one random direction out of a set of two, depending on the edges chosen in step 1.
Yup, I forget to address the OP's CCW requirement in my post.

@The OP: As suggested in ruistola's post, you'll need to apply an additional criterion to sort the vertices in a 'CCW' order. For example, you might know that you want the polygon to 'face' in a certain direction (say, away from the interior of a convex object), in which case you could flip the normal if (as computed in step 1 of my previous post) it points in the wrong direction.

Share this post


Link to post
Share on other sites
I have one problem with the code: The results are unpredicable when the average of all vertices is zero (which happens actually often in my).

I append my code if there could be some error.

Here's how I calculate the average:


Vector3D average(0,0,0);
for(int i = 0; i < vertexcount; i++)
{
average += geolevel->GetPositionArray()[i];
}
average /= vertexcount;






Here's the angle calculation:


VectorAngle va[kMaxPortalVertexCount];
va[0].angle = 0.0f;
va[0].vector = geolevel->GetPositionArray()[0];

// 4.
for(int i = 1; i < vertexcount; i++)
{
float angle1 = CalcAngle(geolevel->GetPositionArray()[i].Normalize(), average, normal);
float angle2 = CalcAngle(geolevel->GetPositionArray()[0].Normalize(), average, normal);
va[i].angle = angle1 + angle2;
va[i].vector = geolevel->GetPositionArray()[i];
}





Angle calculation:


float CalcAngle(const Vector3D &v1, const Vector3D &v2, const Vector3D &normal)
{
Vector3D c;
c = Cross(v1, v2);
float angle = atan2(Magnitude(c), Dot(v1, v2));
return Dot(c, normal) < 0 ? -angle : angle;
}



Share this post


Link to post
Share on other sites
This bit of code:
for(int i = 1; i < vertexcount; i++)
{
float angle1 = CalcAngle(geolevel->GetPositionArray()[i].Normalize(), average, normal);
float angle2 = CalcAngle(geolevel->GetPositionArray()[0].Normalize(), average, normal);
va[i].angle = angle1 + angle2;
va[i].vector = geolevel->GetPositionArray()[i];
}
Does not appear to be correct. I'll try to sketch out a version that should work:
// Note: The change to size_t and pre-increment here is incidental.
for (size_t i = 1; i < vertexcount; ++i) {
va[i].angle = CalcAngle(array[0] - average, array[i] - average, normal);
va[i].vector = array[i];
}
'array' is just your 'geolevel' array, which I was too lazy to type out.

I would give the above a try and see if it doesn't give you the results you're after. If after that it's still not working, post the revised code and I'll take another look.

[Edited by - jyk on November 11, 2006 8:05:21 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Ludi83
...it's working now.
Heh, then you must have caught and fixed my mistake where I typed '1' instead of 'i' :-) Anyway, glad it's working (I edited my previous post to fix the error).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Heh, then you must have caught and fixed my mistake where I typed '1' instead of 'i' :-)


Yes and no. When I read it, I thought that it's wrong. Five minutes later, I applied your code without the use of my brain and with the error, but then I fixed it short after that.

Damn brain :)

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