delaunay.js ES6Ver

delaunay.js

// ref. http://qiita.com/edo_m18/items/7b3c70ed97bac52b2203
(require => {
  require("babel/polyfill");

  function Point(x, y) {
    this.x = x;
    this.y = y;
  }

  Object.assign(Point.prototype, {
    squaredDistance(p) {
      var dx = this.x - p.x;
      var dy = this.y - p.y;
      return dx*dx + dy*dy;
    },

    toString() {
      return JSON.stringify(this);
    }
  });

  function Triangle(p1, p2, p3) {
    console.assert(p1 !== p2 && p2 !== p3 && p3 !== p1);
    this.points = [p1, p2, p3];
  }

  Object.assign(Triangle.prototype, {
    containsPointInCircumcircle(point) {
      var cp = this.centerPoint();
      return cp.squaredDistance(this.points[0]) > cp.squaredDistance(point);
    },

    edges() {
      return [[this.points[0], this.points[1]],
              [this.points[1], this.points[2]],
              [this.points[2], this.points[0]]];
    },

    hasEdge(edge) {
      return this.points.includes(edge[0]) && this.points.includes(edge[1]);
    },

    // http://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay_3958.html
    centerPoint() {
      var x1 = this.points[0].x;
      var x2 = this.points[1].x;
      var x3 = this.points[2].x;
      var y1 = this.points[0].y;
      var y2 = this.points[1].y;
      var y3 = this.points[2].y;

      var c = 2 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
      var x = ((y3 - y1) * (x2*x2 - x1*x1 + y2*y2 - y1*y1) + (y1 - y2) * (x3*x3 - x1*x1 + y3*y3 - y1*y1)) / c;
      var y = ((x1 - x3) * (x2*x2 - x1*x1 + y2*y2 - y1*y1) + (x2 - x1) * (x3*x3 - x1*x1 + y3*y3 - y1*y1)) / c;
      return new Point(x, y);
    },

    toString() {
      return this.points.join();
    },

    equals(t) {
      return this.points.every(p => t.points.includes(p));
    }
  });

  var filterWithRemove = (array, fn) => {
    var res = [];
    for (var i = 0, len = array.length; i < len; i++) {
      var e = array[i];
      if (fn(e, i)) {
        res.push(e);
        array.splice(i--, 1);
        len--;
      }
    }
    return res;
  };

  var randomInt = max => (Math.random() * max)|0;

  var generatePoints = (count, maxX, maxY) =>
      // Array comprehensions is ES7.
      // [for (_ of Array(count)) new Point(randomInt(maxX), randomInt(maxY))];
      Array.apply(null, Array(count)).map(() => new Point(randomInt(maxX), randomInt(maxY)));

  var createSuperTriangle = (width, height) =>
    new Triangle(new Point(0     - Math.ceil(width / 2), 0),
                 new Point(width + Math.ceil(width / 2), 0),
                 new Point(Math.ceil(width / 2), height * 2));

  var resolve = function*(points, superTriangle, render) {
    var triangles = [superTriangle];
    var stack = [];
    for (var point of points) {
      var edges = splitTriangle(triangles, point);
      if (edges) {
        stack.push(...edges);
        yield triangles;
      }

      while (stack.length > 0) {
        var edge = stack.pop();
        var edges = flipEdge(triangles, edge);
        if (edges) {
          stack.push(...edges);
          yield triangles;
        }
      }
    }
    removeSuperTriangle(triangles, superTriangle);
    yield triangles;
  };

  var splitTriangle = (triangles, point) => {
    var hitTriangles = filterWithRemove(triangles, t => t.containsPointInCircumcircle(point));
    if (hitTriangles.length === 0) {
      return null;
    }

    var splitEdges = [];
    for (var t of hitTriangles) {
      for (var edge of t.edges()) {
        triangles.push(new Triangle(edge[0], edge[1], point));
        splitEdges.push(edge);
      }
    }
    return splitEdges;
  };

  var flipEdge = (triangles, edge) => {
    var borderTriangles = filterWithRemove(triangles, t => t.hasEdge(edge));
    if (borderTriangles.length < 2) {
      triangles.push(...borderTriangles);
      return null;
    }

    var t1 = borderTriangles[0];
    var t2 = borderTriangles[1];
    if (t1.equals(t2)) {
      return null;
    }

    var ap = edge[0];
    var bp = edge[1];
    var cp = t1.points.find(p => p !== ap && p !== bp);
    var dp = t2.points.find(p => p !== ap && p !== bp);
    console.assert(new Set([ap, bp, cp, dp]).size === 4, ap, bp, cp, dp, ''+t1.points, ''+t2.points);

    if (!t1.containsPointInCircumcircle(dp)) {
      triangles.push(...borderTriangles);
      return null;
    }
    triangles.push(new Triangle(ap, cp, dp),
                   new Triangle(bp, cp, dp));
    return [[ap, dp], [dp, bp], [bp, cp], [cp, ap]];
  };

  var removeSuperTriangle = (triangles, superTriangle) => {
    filterWithRemove(triangles, t => t.points.some(p => superTriangle.points.includes(p)));
  };

  var render = (context, width, height, points, triangles) => {
    context.clearRect(0, 0, width, height);

    context.strokeStyle = '#f00';
    for (var t of triangles) {
      context.beginPath();
      context.moveTo(t.points[0].x, t.points[0].y);
      context.lineTo(t.points[1].x, t.points[1].y);
      context.lineTo(t.points[2].x, t.points[2].y);
      context.closePath();

      context.fillStyle = triangleColor(t);
      context.stroke();
      context.fill();
    }

    context.fillStyle = '#00f';
    for (var p of points) {
      context.beginPath();
      context.arc(p.x, p.y, 4, 0, 2 * Math.PI);
      context.fill();
    }
  };

  var triangleColor = (() => {
    var colors = new WeakMap();
    return t => {
      if (colors.has(t)) {
        return colors.get(t);
      }
      var c = `rgba(${randomInt(128)}, ${randomInt(128)}, ${randomInt(128)}, .4)`;
      colors.set(t, c);
      return c;
    };
  })();

  var wait = (g, time) => {
    setTimeout(() => {
      g.next();
    }, time);
  };

  var main = (function*() {
    var canvasEl = document.querySelector('canvas');
    var context = canvasEl.getContext('2d');
    var width = canvasEl.width;
    var height = canvasEl.height;

    var points = generatePoints(100, width, height);
    var superTriangle = createSuperTriangle(width, height);

    for (var triangles of resolve(points, superTriangle)) {
      render(context, width, height, points, triangles);
      yield wait(main, 300);
    }
    console.log('end');
  })();
  main.next();

})(typeof require == 'function' ? require : () => {});