Revision: 63082
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at April 6, 2013 00:46 by nicoptere
Initial Code
<?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'; ?>
Initial URL
Initial Description
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
Initial Title
simple polygon triangulator
Initial Tags
Initial Language
PHP