Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 3 of 3

Thread: order of vertices in 2d polygon...

  1. #1
    Intern Contributor
    Join Date
    Apr 2002
    Location
    kremnica, slovakia, europe, earth, sol :-)
    Posts
    99

    order of vertices in 2d polygon...

    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

  2. #2
    Intern Newbie
    Join Date
    Mar 2004
    Location
    Sheffield, Yorkshire, UK
    Posts
    31

    Re: order of vertices in 2d polygon...

    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.

    Code :
     
    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).]

  3. #3
    Intern Contributor
    Join Date
    Apr 2002
    Location
    kremnica, slovakia, europe, earth, sol :-)
    Posts
    99

    Re: order of vertices in 2d polygon...

    yeah, great. thnx

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •