## Posted By

nicoptere on 04/06/13

# simple polygon triangulator

/ Published in: PHP

this is an ear clipping triangulation algorithm. original here: http://forum.unity3d.com/threads/27223-Polygon-triangulation-code http://www.unifycommunity.com/wiki/index.php?title=Triangulator

`<?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'; ?>`