|
1 /** |
|
2 * Computes a contour for a given input grid function using the <a |
|
3 * href="http://en.wikipedia.org/wiki/Marching_squares">marching |
|
4 * squares</a> algorithm. Returns the contour polygon as an array of points. |
|
5 * |
|
6 * @param grid a two-input function(x, y) that returns true for values |
|
7 * inside the contour and false for values outside the contour. |
|
8 * @param start an optional starting point [x, y] on the grid. |
|
9 * @returns polygon [[x1, y1], [x2, y2], …] |
|
10 */ |
|
11 d3.geom.contour = function(grid, start) { |
|
12 var s = start || d3_geom_contourStart(grid), // starting point |
|
13 c = [], // contour polygon |
|
14 x = s[0], // current x position |
|
15 y = s[1], // current y position |
|
16 dx = 0, // next x direction |
|
17 dy = 0, // next y direction |
|
18 pdx = NaN, // previous x direction |
|
19 pdy = NaN, // previous y direction |
|
20 i = 0; |
|
21 |
|
22 do { |
|
23 // determine marching squares index |
|
24 i = 0; |
|
25 if (grid(x-1, y-1)) i += 1; |
|
26 if (grid(x, y-1)) i += 2; |
|
27 if (grid(x-1, y )) i += 4; |
|
28 if (grid(x, y )) i += 8; |
|
29 |
|
30 // determine next direction |
|
31 if (i === 6) { |
|
32 dx = pdy === -1 ? -1 : 1; |
|
33 dy = 0; |
|
34 } else if (i === 9) { |
|
35 dx = 0; |
|
36 dy = pdx === 1 ? -1 : 1; |
|
37 } else { |
|
38 dx = d3_geom_contourDx[i]; |
|
39 dy = d3_geom_contourDy[i]; |
|
40 } |
|
41 |
|
42 // update contour polygon |
|
43 if (dx != pdx && dy != pdy) { |
|
44 c.push([x, y]); |
|
45 pdx = dx; |
|
46 pdy = dy; |
|
47 } |
|
48 |
|
49 x += dx; |
|
50 y += dy; |
|
51 } while (s[0] != x || s[1] != y); |
|
52 |
|
53 return c; |
|
54 }; |
|
55 |
|
56 // lookup tables for marching directions |
|
57 var d3_geom_contourDx = [1, 0, 1, 1,-1, 0,-1, 1,0, 0,0,0,-1, 0,-1,NaN], |
|
58 d3_geom_contourDy = [0,-1, 0, 0, 0,-1, 0, 0,1,-1,1,1, 0,-1, 0,NaN]; |
|
59 |
|
60 function d3_geom_contourStart(grid) { |
|
61 var x = 0, |
|
62 y = 0; |
|
63 |
|
64 // search for a starting point; begin at origin |
|
65 // and proceed along outward-expanding diagonals |
|
66 while (true) { |
|
67 if (grid(x,y)) { |
|
68 return [x,y]; |
|
69 } |
|
70 if (x === 0) { |
|
71 x = y + 1; |
|
72 y = 0; |
|
73 } else { |
|
74 x = x - 1; |
|
75 y = y + 1; |
|
76 } |
|
77 } |
|
78 } |