## Simple polygon triangulator

Submitted by:Andery Smith

Date added:27 April, 2013

Category:PHP

Returns an array of ints representing the indices of the triangles

Tags: polygon triangulator

Code Snippet:

``    <?php         //returns an array of ints representing the indices of the triangles         function triangulate( \$points )    {         \$m_points = array();    \$m_points = \$points;         \$n = count( \$m_points );    if ( \$n < 3 ) return NULL;    if ( \$n == 3 ) return array( 0,1,2 );    if ( \$n == 4 ) return array( 0,1,2, 0,2,3 );         \$indices = array();         \$v = 0;    \$vertices = array();         if ( get_area( \$m_points ) > 0 )    {    for ( \$v = 0; \$v < \$n; \$v++ ) array_push( \$vertices, \$v );    }    else    {    for ( \$v = 0; \$v < \$n; \$v++ ) array_push( \$vertices, ( \$n - 1) - \$v );    }         \$nv = \$n;    \$count = 2 * \$nv;    \$m = 0;         for ( \$m = 0, \$v = \$nv - 1; \$nv > 2; )    {    if ( \$count-- <= 0)    {    return \$indices;    }         \$u = \$v;    if ( \$nv <= \$u )	\$u = 0;         \$v = \$u + 1;    if ( \$nv <= \$v )	\$v = 0;         \$w = \$v + 1;    if ( \$nv <= \$w )	\$w = 0;         \$toto = snip( \$u, \$v, \$w, \$nv, \$vertices, \$m_points );         if ( snip( \$u, \$v, \$w, \$nv, \$vertices, \$m_points ) == 1 )    {         \$a; \$b; \$c; \$s; \$t;         \$a = \$vertices[ \$u ];    \$b = \$vertices[ \$v ];    \$c = \$vertices[ \$w ];         array_push( \$indices, \$a );    array_push( \$indices, \$b );    array_push( \$indices, \$c );         \$m++;    for (\$s = \$v, \$t = \$v + 1; \$t < \$nv; \$s++, \$t++)    {    \$vertices[ \$s ] = \$vertices[ \$t ];    }    \$nv--;    \$count = 2 * \$nv;         }    }    return \$indices;         }         function get_area( \$m_points ) //retourne la surface signÃ©e du triangle    {    \$n = count( \$m_points );         \$A = 0;    \$p = 0;    \$q = 0;         for ( \$p = \$n - 1, \$q = 0; \$q < \$n; \$p = \$q++ )    {         \$pval = \$m_points[ \$p ];    \$qval = \$m_points[ \$q ];    \$A = \$A + ( \$pval->x * \$qval->y - \$qval->x * \$pval->y );         }    return ( \$A * 0.5 );    }              function snip( \$u, \$v, \$w, \$n, \$vertices, \$m_points )    {         \$A = \$m_points[ \$vertices[ \$u ] ];    \$B = \$m_points[ \$vertices[ \$v ] ];    \$C = \$m_points[ \$vertices[ \$w ] ];         if ( .000000001 > (((\$B->x - \$A->x) * (\$C->y - \$A->y)) - ((\$B->y - \$A->y) * (\$C->x - \$A->x))))	return false;         for ( \$p = 0; \$p < \$n; \$p++)    {         if ((\$p == \$u) || (\$p == \$v) || (\$p == \$w)) continue;         \$P = \$m_points[ \$vertices[ \$p ] ];         if ( inside_triangle( \$A, \$B, \$C, \$P ) == true )return false;         }    return true;         }         function inside_triangle( \$A, \$B, \$C, \$P )    {         \$ax; \$ay; \$bx; \$by; \$cx; \$cy; \$apx; \$apy; \$bpx; \$bpy; \$cpx; \$cpy; \$cCROSSap; \$bCROSScp; \$aCROSSbp;         \$ax = \$C->x - \$B->x; \$ay = \$C->y - \$B->y;    \$bx = \$A->x - \$C->x; \$by = \$A->y - \$C->y;    \$cx = \$B->x - \$A->x; \$cy = \$B->y - \$A->y;         \$apx = \$P->x - \$A->x; \$apy = \$P->y - \$A->y;    \$bpx = \$P->x - \$B->x; \$bpy = \$P->y - \$B->y;    \$cpx = \$P->x - \$C->x; \$cpy = \$P->y - \$C->y;         \$aCROSSbp = \$ax * \$bpy - \$ay * \$bpx;    \$cCROSSap = \$cx * \$apy - \$cy * \$apx;    \$bCROSScp = \$bx * \$cpy - \$by * \$cpx;         return ( ( \$aCROSSbp >= 0.0 ) && (\$bCROSScp >= 0.0) && (\$cCROSSap >= 0.0));         }         class point    {    var \$x = 0;    var \$y = 0;         function point( \$_x, \$_y )    {    \$this->x = \$_x;    \$this->y = \$_y;    }    }              //input is an ordered polyline made of points and it must not be self intersecting         \$points = array( new point( 100, 100 ),    new point( 200, 100 ),    new point( 200, 200 ),    new point( 150, 250 ),    new point( 100, 200 ) );         //compute and dump         var_dump( triangulate( \$points ) );         echo '<br/>expected result: 4,0,1,1,2,3,3,4,1';         ?>``