Sign in to follow this  
CommanderXXL

Sorting polygon vertices clockwise

Recommended Posts

Hi, i got a problem with my vertex sorting in my polygons. I need to have clockwise ordered vertices for my triangulation code to work. So i assume the problem is within my sorting code. Maybe you can find the problem of my sorting code. If you have a simpler or better performing code for sorting polygons clockwise i would also appreciate to see it.
void	SortClockwise()
{
	// Get center of polygon
	CVector3D Center(GetCenter());

	for(unsigned int aktVert1 = 0; aktVert1 < Vertices.size() - 1; ++aktVert1)
	{
		CVector3D	Pos1(Vertices[aktVert1].Position);
		CVector3D	A(Pos1 - Center);
			
		A.Normalize();
	        
		// Create a plane thru current vertex, center and normal of polygon
		CPlane		Plane(Pos1, Center, Center + Normal);

		float		SmallestAngle	= -1;
		int		Smallest	= -1;
	        
		for(unsigned int aktVert2 = aktVert1 + 1; aktVert2 < Vertices.size(); ++aktVert2)
		{
			CVector3D Pos2(Vertices[aktVert2].Position);
			
			// Test against plane if vert can be the next
			if(Plane.ClassifyPoint(Pos2) == CP_Front)
			{
				CVector3D B(Pos2 - Center);
					
				B.Normalize();

				float Angle = A.Dot(B);

				if(Angle > SmallestAngle)
				{
					SmallestAngle	= Angle;
					Smallest	= aktVert2;
				}
			}
		}
	         
		// Vert with smallest angle is the next
		if(Smallest != -1)
		{
			// Tauschen der Vertices
			CVertex			Temp(Vertices[aktVert1 + 1]);
			Vertices[aktVert1 + 1]	= Vertices[Smallest];
			Vertices[Smallest]	= Temp;
		}
	}
	 
	// Reverse vertices if needed
	CVector3D P1(Vertices[0].Position);
	CVector3D P2(Vertices[1].Position);
	CVector3D P3(Vertices[(unsigned int)Vertices.size() - 1].Position);
	CVector3D AB(P2 - P1); 
	CVector3D BC(P3 - P1);        
	CVector3D Norm(AB.Cross(BC));
		
	if((Normal.Dot(Norm)) < 0)
	{
		vector <CVertex>::iterator	B,E;
		B	= Vertices.begin();
		E	= Vertices.end();

		for(unsigned int i = 0; i < Vertices.size() / 2; ++i)
		{
			--E;
			CVertex TempV	= *E;
			*E				= *B;
			*B				= TempV;			
			++B;			
		}
	}
}


Thanks for any help

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