1 /*************************************** 2 * Copyright 2011, 2012 GlobWeb contributors. 3 * 4 * This file is part of GlobWeb. 5 * 6 * GlobWeb is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * GlobWeb is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with GlobWeb. If not, see <http://www.gnu.org/licenses/>. 18 ***************************************/ 19 20 define( function() { 21 22 /** 23 Triangulator code taken from http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml 24 Does not manage holes 25 Seems to be O(n^3)! 26 */ 27 var EPSILON = 0.0000000001; 28 29 /* 30 Compute the signed area of a polygon 31 */ 32 var Area = function(contour) 33 { 34 var n = contour.length; 35 var A=0.0; 36 for(var p=n-1,q=0; q<n; p=q++) 37 { 38 A+= contour[p][0]*contour[q][1] - contour[q][0]*contour[p][1]; 39 } 40 return A*0.5; 41 } 42 43 /* 44 InsideTriangle decides if a point P is Inside of the triangle 45 defined by A, B, C. 46 */ 47 var InsideTriangle = function(Ax, Ay, 48 Bx, By, 49 Cx, Cy, 50 Px, Py) 51 52 { 53 var ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy; 54 var cCROSSap, bCROSScp, aCROSSbp; 55 56 ax = Cx - Bx; ay = Cy - By; 57 bx = Ax - Cx; by = Ay - Cy; 58 cx = Bx - Ax; cy = By - Ay; 59 apx= Px - Ax; apy= Py - Ay; 60 bpx= Px - Bx; bpy= Py - By; 61 cpx= Px - Cx; cpy= Py - Cy; 62 63 aCROSSbp = ax*bpy - ay*bpx; 64 cCROSSap = cx*apy - cy*apx; 65 bCROSScp = bx*cpy - by*cpx; 66 67 return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0)); 68 }; 69 70 /* 71 Check if the giben triangle (u,v,w) is a ear : not other vertex inside 72 */ 73 var Snip = function(contour, u, v, w, n, V) 74 { 75 var p; 76 var Ax, Ay, Bx, By, Cx, Cy, Px, Py; 77 78 Ax = contour[V[u]][0]; 79 Ay = contour[V[u]][1]; 80 81 Bx = contour[V[v]][0]; 82 By = contour[V[v]][1]; 83 84 Cx = contour[V[w]][0]; 85 Cy = contour[V[w]][1]; 86 87 if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false; 88 89 for (p=0;p<n;p++) 90 { 91 if( (p == u) || (p == v) || (p == w) ) continue; 92 Px = contour[V[p]][0]; 93 Py = contour[V[p]][1]; 94 if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false; 95 } 96 97 return true; 98 } 99 100 /* 101 Process triangulation on the given contour 102 */ 103 var Process = function( contour ) 104 { 105 /* allocate and initialize list of Vertices in polygon */ 106 107 var n = contour.length; 108 if ( contour[0][0] == contour[n-1][0] && contour[0][1] == contour[n-1][1] ) 109 n--; 110 111 if ( n < 3 ) return null; 112 113 var V = new Array(n); 114 115 /* we want a counter-clockwise polygon in V */ 116 117 if ( 0.0 < Area(contour) ) 118 for (var v=0; v<n; v++) V[v] = v; 119 else 120 for(var v=0; v<n; v++) V[v] = (n-1)-v; 121 122 var nv = n; 123 124 var results = []; 125 126 /* remove nv-2 Vertices, creating 1 triangle every time */ 127 var count = 2*nv; /* error detection */ 128 129 for (var m=0, v=nv-1; nv>2; ) 130 { 131 /* if we loop, it is probably a non-simple polygon */ 132 if (0 >= (count--)) 133 { 134 //** Triangulate: ERROR - probable bad polygon! 135 return null; 136 } 137 138 /* three consecutive vertices in current polygon, <u,v,w> */ 139 var u = v ; if (nv <= u) u = 0; /* previous */ 140 v = u+1; if (nv <= v) v = 0; /* new v */ 141 var w = v+1; if (nv <= w) w = 0; /* next */ 142 143 if ( Snip(contour,u,v,w,nv,V) ) 144 { 145 var a,b,c,s,t; 146 147 /* true names of the vertices */ 148 a = V[u]; b = V[v]; c = V[w]; 149 150 /* output Triangle */ 151 results.push( a ); 152 results.push( b ); 153 results.push( c ); 154 155 m++; 156 157 /* remove v from remaining polygon */ 158 for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--; 159 160 /* resest error detection counter */ 161 count = 2*nv; 162 } 163 } 164 165 return results; 166 } 167 168 return { 169 process: Process 170 }; 171 172 }); 173