// Note: requires coordinates to be counterclockwise and convex!

d3.geom.polygon = function(coordinates) {

  coordinates.area = function() {

    var i = 0,

        n = coordinates.length,

        a = coordinates[n - 1][0] * coordinates[0][1],

        b = coordinates[n - 1][1] * coordinates[0][0];

    while (++i < n) {

      a += coordinates[i - 1][0] * coordinates[i][1];

      b += coordinates[i - 1][1] * coordinates[i][0];

    }

    return (b - a) * .5;

  };

  coordinates.centroid = function(k) {

    var i = -1,

        n = coordinates.length - 1,

        x = 0,

        y = 0,

        a,

        b,

        c;

    if (!arguments.length) k = -1 / (6 * coordinates.area());

    while (++i < n) {

      a = coordinates[i];

      b = coordinates[i + 1];

      c = a[0] * b[1] - b[0] * a[1];

      x += (a[0] + b[0]) * c;

      y += (a[1] + b[1]) * c;

    }

    return [x * k, y * k];

  };

  // The Sutherland-Hodgman clipping algorithm.

  coordinates.clip = function(subject) {

    var input,

        i = -1,

        n = coordinates.length,

        j,

        m,

        a = coordinates[n - 1],

        b,

        c,

        d;

    while (++i < n) {

      input = subject.slice();

      subject.length = 0;

      b = coordinates[i];

      c = input[(m = input.length) - 1];

      j = -1;

      while (++j < m) {

        d = input[j];

        if (d3_geom_polygonInside(d, a, b)) {

          if (!d3_geom_polygonInside(c, a, b)) {

            subject.push(d3_geom_polygonIntersect(c, d, a, b));

          }

          subject.push(d);

        } else if (d3_geom_polygonInside(c, a, b)) {

          subject.push(d3_geom_polygonIntersect(c, d, a, b));

        }

        c = d;

      }

      a = b;

    }

    return subject;

  };

  return coordinates;

};

function d3_geom_polygonInside(p, a, b) {

  return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);

}

// Intersect two infinite lines cd and ab.

function d3_geom_polygonIntersect(c, d, a, b) {

  var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0],

      y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1],

      x13 = x1 - x3,

      x21 = x2 - x1,

      x43 = x4 - x3,

      y13 = y1 - y3,

      y21 = y2 - y1,

      y43 = y4 - y3,

      ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21);

  return [x1 + ua * x21, y1 + ua * y21];

}