/**

 * Computes a contour for a given input grid function using the <a

 * href="http://en.wikipedia.org/wiki/Marching_squares">marching

 * squares</a> algorithm. Returns the contour polygon as an array of points.

 *

 * @param grid a two-input function(x, y) that returns true for values

 * inside the contour and false for values outside the contour.

 * @param start an optional starting point [x, y] on the grid.

 * @returns polygon [[x1, y1], [x2, y2], …]

 */

d3.geom.contour = function(grid, start) {

  var s = start || d3_geom_contourStart(grid), // starting point

      c = [],    // contour polygon

      x = s[0],  // current x position

      y = s[1],  // current y position

      dx = 0,    // next x direction

      dy = 0,    // next y direction

      pdx = NaN, // previous x direction

      pdy = NaN, // previous y direction

      i = 0;

  do {

    // determine marching squares index

    i = 0;

    if (grid(x-1, y-1)) i += 1;

    if (grid(x,   y-1)) i += 2;

    if (grid(x-1, y  )) i += 4;

    if (grid(x,   y  )) i += 8;

    // determine next direction

    if (i === 6) {

      dx = pdy === -1 ? -1 : 1;

      dy = 0;

    } else if (i === 9) {

      dx = 0;

      dy = pdx === 1 ? -1 : 1;

    } else {

      dx = d3_geom_contourDx[i];

      dy = d3_geom_contourDy[i];

    }

    // update contour polygon

    if (dx != pdx && dy != pdy) {

      c.push([x, y]);

      pdx = dx;

      pdy = dy;

    }

    x += dx;

    y += dy;

  } while (s[0] != x || s[1] != y);

  return c;

};

// lookup tables for marching directions

var d3_geom_contourDx = [1, 0, 1, 1,-1, 0,-1, 1,0, 0,0,0,-1, 0,-1,NaN],

    d3_geom_contourDy = [0,-1, 0, 0, 0,-1, 0, 0,1,-1,1,1, 0,-1, 0,NaN];

function d3_geom_contourStart(grid) {

  var x = 0,

      y = 0;

  // search for a starting point; begin at origin

  // and proceed along outward-expanding diagonals

  while (true) {

    if (grid(x,y)) {

      return [x,y];

    }

    if (x === 0) {

      x = y + 1;

      y = 0;

    } else {

      x = x - 1;

      y = y + 1;

    }

  }

}