1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
function triangulate(v){
function vec(x,y){return [y[0]-x[0], y[1]-x[1]]}
function isIn(p, p0, p1, p2) {//http://jsfiddle.net/PerroAZUL/zdaY8/1/
var A = 1/2 * (-p1[1] * p2[0] + p0[1] * (-p1[0] + p2[0]) + p0[0] * (p1[1] - p2[1]) + p1[0] * p2[1]);
var sign = A < 0 ? -1 : 1;
var s = (p0[1] * p2[0] - p0[0] * p2[1] + (p2[1] - p0[1]) * p[0] + (p0[0] - p2[0]) * p[1]) * sign;
var t = (p0[0] * p1[1] - p0[1] * p1[0] + (p0[1] - p1[1]) * p[0] + (p1[0] - p0[0]) * p[1]) * sign;
return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}
var triangles = [];
while(v.length >=3){
var n = v.length;
for(var i=0;i<n; ++i){
var [A,B,C] = [v[(i-1+n)%n], v[i], v[(i+1)%n]];
if(Math.atan2(...vec(B,A).reverse())-Math.atan2(...vec(B,C).reverse())>Math.PI){
continue
}
var ok = true;
for(var j = i+2; j<i+n;++j){
var q = v[(j+n)%n]
if(isIn(q, A,B,C)){
ok = false;
break;
}
}
if(!ok)continue;
triangles.push( [A,B,C] )
v.splice(i,1)
n = v.length;
break;
}
}
return triangles;
}
//usage
var v = [[0,0],[4,0],[4,1],[1,1],[1,2],[2,2],[2,3],[3,3],[3,2],[4,2],[4,4],[0,4]]
var triangles = triangulate(v)
/*
[ [ [ 0, 0 ], [ 4, 0 ], [ 4, 1 ] ],
[ [ 0, 0 ], [ 4, 1 ], [ 1, 1 ] ],
[ [ 0, 4 ], [ 0, 0 ], [ 1, 1 ] ],
[ [ 0, 4 ], [ 1, 1 ], [ 1, 2 ] ],
[ [ 0, 4 ], [ 1, 2 ], [ 2, 2 ] ],
[ [ 0, 4 ], [ 2, 2 ], [ 2, 3 ] ],
[ [ 0, 4 ], [ 2, 3 ], [ 3, 3 ] ],
[ [ 3, 3 ], [ 3, 2 ], [ 4, 2 ] ],
[ [ 3, 3 ], [ 4, 2 ], [ 4, 4 ] ],
[ [ 0, 4 ], [ 3, 3 ], [ 4, 4 ] ] ];
*/ |
