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

?>
 
 

Comments