/ 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
original here:
http://forum.unity3d.com/threads/27223-Polygon-triangulation-code
http://www.unifycommunity.com/wiki/index.php?title=Triangulator
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
<?php //returns an array of ints representing the indices of the triangles function triangulate( $points ) { $m_points = $points; if ( $n < 3 ) return NULL; $v = 0; if ( get_area( $m_points ) > 0 ) { } else { } $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 ]; $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 { $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 new point( 200, 100 ), new point( 200, 200 ), new point( 150, 250 ), new point( 100, 200 ) ); //compute and dump echo '<br/>expected result: 4,0,1,1,2,3,3,4,1'; ?>