|
1 // Note: requires coordinates to be counterclockwise and convex! |
|
2 d3.geom.polygon = function(coordinates) { |
|
3 |
|
4 coordinates.area = function() { |
|
5 var i = 0, |
|
6 n = coordinates.length, |
|
7 a = coordinates[n - 1][0] * coordinates[0][1], |
|
8 b = coordinates[n - 1][1] * coordinates[0][0]; |
|
9 while (++i < n) { |
|
10 a += coordinates[i - 1][0] * coordinates[i][1]; |
|
11 b += coordinates[i - 1][1] * coordinates[i][0]; |
|
12 } |
|
13 return (b - a) * .5; |
|
14 }; |
|
15 |
|
16 coordinates.centroid = function(k) { |
|
17 var i = -1, |
|
18 n = coordinates.length - 1, |
|
19 x = 0, |
|
20 y = 0, |
|
21 a, |
|
22 b, |
|
23 c; |
|
24 if (!arguments.length) k = -1 / (6 * coordinates.area()); |
|
25 while (++i < n) { |
|
26 a = coordinates[i]; |
|
27 b = coordinates[i + 1]; |
|
28 c = a[0] * b[1] - b[0] * a[1]; |
|
29 x += (a[0] + b[0]) * c; |
|
30 y += (a[1] + b[1]) * c; |
|
31 } |
|
32 return [x * k, y * k]; |
|
33 }; |
|
34 |
|
35 // The Sutherland-Hodgman clipping algorithm. |
|
36 coordinates.clip = function(subject) { |
|
37 var input, |
|
38 i = -1, |
|
39 n = coordinates.length, |
|
40 j, |
|
41 m, |
|
42 a = coordinates[n - 1], |
|
43 b, |
|
44 c, |
|
45 d; |
|
46 while (++i < n) { |
|
47 input = subject.slice(); |
|
48 subject.length = 0; |
|
49 b = coordinates[i]; |
|
50 c = input[(m = input.length) - 1]; |
|
51 j = -1; |
|
52 while (++j < m) { |
|
53 d = input[j]; |
|
54 if (d3_geom_polygonInside(d, a, b)) { |
|
55 if (!d3_geom_polygonInside(c, a, b)) { |
|
56 subject.push(d3_geom_polygonIntersect(c, d, a, b)); |
|
57 } |
|
58 subject.push(d); |
|
59 } else if (d3_geom_polygonInside(c, a, b)) { |
|
60 subject.push(d3_geom_polygonIntersect(c, d, a, b)); |
|
61 } |
|
62 c = d; |
|
63 } |
|
64 a = b; |
|
65 } |
|
66 return subject; |
|
67 }; |
|
68 |
|
69 return coordinates; |
|
70 }; |
|
71 |
|
72 function d3_geom_polygonInside(p, a, b) { |
|
73 return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]); |
|
74 } |
|
75 |
|
76 // Intersect two infinite lines cd and ab. |
|
77 function d3_geom_polygonIntersect(c, d, a, b) { |
|
78 var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0], |
|
79 y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1], |
|
80 x13 = x1 - x3, |
|
81 x21 = x2 - x1, |
|
82 x43 = x4 - x3, |
|
83 y13 = y1 - y3, |
|
84 y21 = y2 - y1, |
|
85 y43 = y4 - y3, |
|
86 ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21); |
|
87 return [x1 + ua * x21, y1 + ua * y21]; |
|
88 } |