Fix Polygon Vertexorder

[serthy]

Sanibonani =)

I have an array of n unsorted points (x,y,z).
These vertices will create a !convex! polygon.
Now I need your help to create an indexlist of these vertices in a sorted way:

Example:

5 points in 3d space: ( A , B , D , C )

	A      B






	C      D

connect them in the unsorted order as they are:

	A------B
	 \    /
	  \  /
	   \/
	   /\
	  /  \
	 /    \
	C------D

now sort them (counter-)clock wise:

	A      B






	D      C

and connect them again: ( A , B , C , D )

	A------B
	|      |
	|      |
	|      |
	|      |
	|      |
	|      |
	C------D

I am currently going over a dotProduct from the center of the polygon, but stucked there...
Maybe arcTan( x / y ) works!?

		sortVertsOnPoly( verts , center )
{
    dots = [];
    idx = [];

    for( i = 0 ; i < verts.size ; i++ )
    {
        v1 = verts[i];                //catch current vert
        v2 = verts[( i + 1 ) % verts.size];    //catch next vert to compare to

        v1 -= center;    //calculate current directions
        v2 -= center;

        dots[i] = ( v1[0] * v2[1] - v1[1] * v2[0] ); //calculate the dot(2D)
        idx[i] = i;    //store the index-information in a different array
    }

    //sort them by their dot-value
    for( i = dots.size ; i > 1 ; i-- )
    {
        for( j = 0 ; j < i - 1 ; j++ )
        {
            if( dots[i] > dots[i + 1] )    
            {
                t = dots[i];    //swap
                dots[i] = dots[i + 1];
                dots[i + 1] = t;

                t = idx[i];        //also swap the index array
                idx[i] = idx[i + 1];
                idx[i + 1] = t;
            }
        }
    }

    return idx;    //return sorted index array
} 
	

EDIT:

or just get vertex #1 as reference and calculate all other angles and compare them:
guess this woll work also... geez, why i didnt get this in my first toughts?!

		    dirs = [];
    dirs[0] = 0;
    dir = vectorNormalize( verts[0] - center );

    for( i = 1 ; i < verts.size ; i++ )
    {
        dirs[i] = aCos( vectorDot( dir , vectorNormalize( verts[i] - center ) ) );
        idx[i] = i;
    } 
	

EDIT: dont mind, im confused, the dot is the almost angle ~.~

[kung foo man]

Sanibonani

Could you provide a full example to test with?

[serthy]

init()
{
	count = 6;
	radius = 100;
	verts = [];

	//create a convex poly 
	for( i = 0 ; i < count ; i++ )
	{
		angle = 360 / count * i;
		verts[i] = ( radius * cos( angle ) , radius * sin( angle ) , 0 );
	}

	order = [];

	//assign the order
	for( i = 0 ; i < verts.size ; i++ )
	{
		order[i] = i;
	}

	//shuffle them
	for( i = 0 ; i < order.size ; i++ )
	{
		j = randomInt( order.size );
		t = order[i];
		order[i] = order[j];
		order[j] = t;
	}

	//show unsortedorder
	s = "\n";

	for( i = 0 ; i < order.size ; i++ )
	{
		s += ( "order[" + i + "] = " + order[i] + "\n" );
	}

	debug( s );

	//get the center
	center = calculatePolyCenter( verts );
	//sort the vertices
	order = sortVertsOnPoly( verts , center );

	//show sorted order
	s = "\n";

	for( i = 0 ; i < verts.size ; i++ )
	{
		s += ( "sorted order[" + i + "] = " + order[i] + "\n" );
	}

	debug( s );
}

sortVertsOnPoly( verts , center )
{
	idx = [];
	idx[0] = 0;
	dirs = [];
	dirs[0] = 0;
	dir = vectorNormalize( verts[0] - center );

	for( i = 1 ; i < verts.size ; i++ )//i should use arctan(y/x) instead here... need abit time to think about it...
	{
		dot = vectorDot( dir , vectorNormalize( verts[i] - center ) );

		if( dot < 0 )
			dirs[i] = 360 - aCos( dot );
		else
			dirs[i] = aCos( dot );

		idx[i] = i;
	}

	swapped = true;

      for( j = 1 ; swapped ; j++ )
	{
            swapped = false;

            for( i = 0 ; i < dirs.size - j ; i++ )
		{
			if( dirs[i] > dirs[i + 1] )	
			{
				t = dirs[i];
				dirs[i] = dirs[i + 1];
				dirs[i + 1] = t;

				t = idx[i];
				idx[i] = idx[i + 1];
				idx[i + 1] = t;

                        swapped = true;
                  }
            }
      }

	return idx;
} 

calculatePolyCenter( verts )
{
	center = ( 0 , 0 , 0 );	
	
	for( i = 0 ; i < verts.size ; i++ )
	{
		center += verts[i];
	}

	return vectorScale( center , 1 / verts.size );
}

vectorScale( v , s )
{
	return ( v[0] * s , v[1] * s , v[2] * s );
}

debug( x )
{
iPrintLn( "debug: " + x );
}

[serthy]

solved:

instead of the dotproduct you should use the arcus tangenz to calculate the angle for comparison:

		    t = aTan( ( verts[i][0] - verts[0][0] ) / ( verts[i][1] - verts[0][1] ) );

    if( t < 0 )
        t += 180;

    dirs[i] = t; 
	

[IzNoGoD]

Dont use tangens. Use vectorproduct, not dotproduct.

Same hack I used in navmesh, use it with 2d-inputs.

ispointinsidenode(point,node)
{
	//DONT CHECK HEIGHT OF POINT. IMPORTANT!
	//now, for each child of [node] find another connected child of [node]
	first=undefined;
	previous=undefined;
	posneg=0;
	inside=true;
	child=level.child[node.child[0]];
	for(iterations=0;iterations<node.child.size&&(!isdefined(first)||first.num!=child.num);iterations++)
	{
		for(i=0;i<child.conn.size;i++)
		{
			if(isinarray(child.conn[i],node.child))
			{
				//this connection is one of the node ones
				if(!isdefined(first))
					first=child;
				if(!isdefined(previous)||previous.num!=child.conn[i])
				{
					//not one that has already been checked
					previous=child;
					child=level.child[child.conn[i]];
					ans=vectorprod2d(point-previous.origin,child.origin-previous.origin);
					if(posneg==0)
					{
						if(ans<0)
							posneg=-1;
						else if(ans>0)
							posneg=1;
					}
					else if(ans*posneg<0)
						return false;
				}
			}
		}
	}
	return true;
}

with

vectorprod2d(vec1,vec2) 
{
	num=vec1[0]*vec2[1]-vec1[1]*vec2[0];
	return num;
}

If you have 2 lines and do a vectorprod2d on them, it will become positive if the second line is going "more right" than the first. Negative if "more left" (directions might be flipped though, but always same result)
This should be lighter than tangens.

[serthy]

okay, does vectorprod2d returns values which are sortable?
didnt tested it right now, but seems to work on the first view

[IzNoGoD]

Pick 3 random points
Make a triangle out of them.

Get another point
for all 3 points you already had:
draw vector from point to newpoint
draw 2 vectors from point to other 2 points
vectorprod2d each of those 2 lines with the line to newpoint
If one of them is positive and one of them is neg, ignore
Other 2 points will have both positive or both negative outcome
create new triangle with those 2 and newpoint

get another new point
look to which of the triangles it is closest (average coordinates of all points of all triangles)

repeat above procedure

If at some point above statements become false, its not a convex polygon.

At the end youll be left with a shitload of triangles. You need to sort those then (linkedlist i suppose to create the triangles)

Just pick a random start point, add to list and remove from original list (to prevent duplicates)
get rightmost connected point (multiple triangles can be connected to one point, thus multiple points connected to it), add to list, remove from original
repeat until original list is empty.

return list.

Good luck

Edit: method only works for 2d stuff, not 3d.

[serthy]

made something here, used only while navmesh creation, so it doesnt need to have a good performance.
works also for randomly added verteices, no need to keep the order

		sortVertsOnNode( node )
{
    if( node.verts.size <= 3 ) //sort a line/point genious?
        return node.verts; //sure not!

    ids = [];
    srt = [];
    ids[0] = 0;
    srt[0] = 0;

    dir = vectorNormalize( level.verts[node.verts[0]].origin - node.origin ); 
         
    for( i = 1 ; i < node.verts.size ; i++ )
    {
        d = vectorNormalize( level.verts[node.verts[i]].origin - node.origin ); 
                dot = vectorDot( dir , d );

        a = 57.2957795 * aCos( dot ); //1 rad = 57.2957795 deg

        if( ( dir[0] * d[1] ) - ( d[0] * dir[1] ) < 0 ) 
            a = 360 - a;

        ids[i] = i;
        srt[i] = a;
    }         

        //sort the shit out of them
    for( i = 0 ; i < node.verts.size ; i++ )
    {
        for( j = 0 ; j < node.verts.size - 1 ; j++ )
        {
            if( srt[j] > srt[j + 1] )
            {
                t = ids[j];
                ids[j] = ids[j + 1];
                ids[j + 1] = t;

                t = srt[j];
                srt[j] = srt[j + 1];
                srt[j + 1] = t;
            }
        }
    }

    verts = [];

    for( i = 0 ; i < ids.size ; i++ )
    {
        verts[i] = node.verts[ids[i]];
    }

    return verts; //gotta catch 'em all!
} 
	

just to mark this as solved