order of vertices in 2d polygon...

[miko]

i've got some vertices and i want to draw them as a convex polygon, in other words, i need to determine correct order of vertices in convex polygon. it it possible?

my vertices have only x,y coordinate, there are no duplicates or other evil stuff and always can be arranged to polygon

[SmutMonkey]

Curse this forum. I typed this up once, hit submit, and the board gave an internal server error and my words of wisdom were lost forever.

Oh well, it gave me a chance to think "hmm, that'll come in handy in the next day or so", so I wrote it. Provided the vertices describe a convex polygon you can do the following. (It's in C++ (obviously), it uses my vector3 class, it's probably terrible coding style, the FindPolygon function is a bit of a mess. It's free, what do you expect? )

Before calling into FindPolygon, set all your vertices z values to zero, and create an array of int[numvertices] for the results to get put into.

 
bool FindNextVertex( vector3 *verts, int *indices, int numvertices, vector3 &v0, vector3 &v1, int &nextvertex )
{
	vector3 e0 = v1-v0;
	e0.Normalise();
 
	int bestvertex = 0xffffffff;
	float bestdev = -1e7f;
 
	for ( int i=0; i < numvertices; i++ )
	{
		vector3 e1 = verts[indices[i]]-v1;
		e1.Normalise();
		vector3 cross = e0.CrossProduct(e1);
		if ( cross.z < 0.0f )
		{
			float dev = e0.DotProduct(e1);
			if ( dev > bestdev )
			{
				bestvertex = i;
				bestdev = dev;
			}
		}
	}
 
	if ( bestvertex == 0xffffffff ) return false;
 
	nextvertex = bestvertex;
 
	return true;
}
 
// indices is an output buffer, allocated by caller
bool FindPolygon( vector3 *verts, int numvertices, int *indices )
{
	int *idxs = new int[numvertices];
	for ( int i=0; i < numvertices; i++ ) idxs[i] = i;
 
	// randomise the order of the vertices
	for ( int i=numvertices-1; i > 0; i-- )
	{
		int j = rand() % (i+1);
		if ( i != j )
		{
			int tmp = idxs[i];
			idxs[i] = idxs[j];
			idxs[j] = tmp;
		}
	}
 
	int nextvertex;
	if ( !FindNextVertex( verts, &amp;idxs[1], numvertices-2, verts[idxs[numvertices-1]], verts[idxs[0]], nextvertex ) )
		return false;
 
	indices[0] = idxs[0];
	indices[1] = idxs[nextvertex+1];
 
	for ( int j=nextvertex+1; j < numvertices-1; j++ )
		idxs[j] = idxs[j+1];
 
	for ( int i=2; i < numvertices; i++ )
	{
		if ( !FindNextVertex( verts, &amp;idxs[1], numvertices-i, verts[indices[i-2]], verts[indices[i-1]], nextvertex ) )
			return false;
 
		indices[i] = idxs[nextvertex+1];
 
		for ( int j=nextvertex+1; j < numvertices-1; j++ )
			idxs[j] = idxs[j+1];
	}
 
	return true;
}

Wow, I'm glad I typed this up in VC, typing into this little box is a nightmare.

Oh, the usual disclaimers apply. If your nuclear power station blows up as a result of using this code, don't blame me, it's all at your own risk

[edited for nicer formatting]


[This message has been edited by SmutMonkey (edited 03-13-2004).]

[miko]

yeah, great. thnx