Posted By

nicoptere on 04/06/13


Tagged

polygon triangulation ear-clipping


Versions (?)

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

  1. <?php
  2.  
  3. //returns an array of ints representing the indices of the triangles
  4.  
  5. function triangulate( $points )
  6. {
  7.  
  8. $m_points = array();
  9. $m_points = $points;
  10.  
  11. $n = count( $m_points );
  12. if ( $n < 3 ) return NULL;
  13. if ( $n == 3 ) return array( 0,1,2 );
  14. if ( $n == 4 ) return array( 0,1,2, 0,2,3 );
  15.  
  16. $indices = array();
  17.  
  18. $v = 0;
  19. $vertices = array();
  20.  
  21. if ( get_area( $m_points ) > 0 )
  22. {
  23. for ( $v = 0; $v < $n; $v++ ) array_push( $vertices, $v );
  24. }
  25. else
  26. {
  27. for ( $v = 0; $v < $n; $v++ ) array_push( $vertices, ( $n - 1) - $v );
  28. }
  29.  
  30. $nv = $n;
  31. $count = 2 * $nv;
  32. $m = 0;
  33.  
  34. for ( $m = 0, $v = $nv - 1; $nv > 2; )
  35. {
  36. if ( $count-- <= 0)
  37. {
  38. return $indices;
  39. }
  40.  
  41. $u = $v;
  42. if ( $nv <= $u ) $u = 0;
  43.  
  44. $v = $u + 1;
  45. if ( $nv <= $v ) $v = 0;
  46.  
  47. $w = $v + 1;
  48. if ( $nv <= $w ) $w = 0;
  49.  
  50. $toto = snip( $u, $v, $w, $nv, $vertices, $m_points );
  51.  
  52. if ( snip( $u, $v, $w, $nv, $vertices, $m_points ) == 1 )
  53. {
  54.  
  55. $a; $b; $c; $s; $t;
  56.  
  57. $a = $vertices[ $u ];
  58. $b = $vertices[ $v ];
  59. $c = $vertices[ $w ];
  60.  
  61. array_push( $indices, $a );
  62. array_push( $indices, $b );
  63. array_push( $indices, $c );
  64.  
  65. $m++;
  66. for ($s = $v, $t = $v + 1; $t < $nv; $s++, $t++)
  67. {
  68. $vertices[ $s ] = $vertices[ $t ];
  69. }
  70. $nv--;
  71. $count = 2 * $nv;
  72.  
  73. }
  74. }
  75. return $indices;
  76.  
  77. }
  78.  
  79. function get_area( $m_points ) //retourne la surface signée du triangle
  80. {
  81. $n = count( $m_points );
  82.  
  83. $A = 0;
  84. $p = 0;
  85. $q = 0;
  86.  
  87. for ( $p = $n - 1, $q = 0; $q < $n; $p = $q++ )
  88. {
  89.  
  90. $pval = $m_points[ $p ];
  91. $qval = $m_points[ $q ];
  92. $A = $A + ( $pval->x * $qval->y - $qval->x * $pval->y );
  93.  
  94. }
  95. return ( $A * 0.5 );
  96. }
  97.  
  98.  
  99. function snip( $u, $v, $w, $n, $vertices, $m_points )
  100. {
  101.  
  102. $A = $m_points[ $vertices[ $u ] ];
  103. $B = $m_points[ $vertices[ $v ] ];
  104. $C = $m_points[ $vertices[ $w ] ];
  105.  
  106. if ( .000000001 > ((($B->x - $A->x) * ($C->y - $A->y)) - (($B->y - $A->y) * ($C->x - $A->x)))) return false;
  107.  
  108. for ( $p = 0; $p < $n; $p++)
  109. {
  110.  
  111. if (($p == $u) || ($p == $v) || ($p == $w)) continue;
  112.  
  113. $P = $m_points[ $vertices[ $p ] ];
  114.  
  115. if ( inside_triangle( $A, $B, $C, $P ) == true )return false;
  116.  
  117. }
  118. return true;
  119.  
  120. }
  121.  
  122. function inside_triangle( $A, $B, $C, $P )
  123. {
  124.  
  125. $ax; $ay; $bx; $by; $cx; $cy; $apx; $apy; $bpx; $bpy; $cpx; $cpy; $cCROSSap; $bCROSScp; $aCROSSbp;
  126.  
  127. $ax = $C->x - $B->x; $ay = $C->y - $B->y;
  128. $bx = $A->x - $C->x; $by = $A->y - $C->y;
  129. $cx = $B->x - $A->x; $cy = $B->y - $A->y;
  130.  
  131. $apx = $P->x - $A->x; $apy = $P->y - $A->y;
  132. $bpx = $P->x - $B->x; $bpy = $P->y - $B->y;
  133. $cpx = $P->x - $C->x; $cpy = $P->y - $C->y;
  134.  
  135. $aCROSSbp = $ax * $bpy - $ay * $bpx;
  136. $cCROSSap = $cx * $apy - $cy * $apx;
  137. $bCROSScp = $bx * $cpy - $by * $cpx;
  138.  
  139. return ( ( $aCROSSbp >= 0.0 ) && ($bCROSScp >= 0.0) && ($cCROSSap >= 0.0));
  140.  
  141. }
  142.  
  143. class point
  144. {
  145. var $x = 0;
  146. var $y = 0;
  147.  
  148. function point( $_x, $_y )
  149. {
  150. $this->x = $_x;
  151. $this->y = $_y;
  152. }
  153. }
  154.  
  155.  
  156. //input is an ordered polyline made of points and it must not be self intersecting
  157.  
  158. $points = array( new point( 100, 100 ),
  159. new point( 200, 100 ),
  160. new point( 200, 200 ),
  161. new point( 150, 250 ),
  162. new point( 100, 200 ) );
  163.  
  164. //compute and dump
  165.  
  166. var_dump( triangulate( $points ) );
  167.  
  168. echo '<br/>expected result: 4,0,1,1,2,3,3,4,1';
  169.  
  170. ?>

Report this snippet  

You need to login to post a comment.