ucnv/canvas-delaunay-triangulation.html

## canvas-delaunay-triangulation.html
<html>
<head><title>Canvas Delaunay Triangulation</title></head>
<body></body>
<script type="text/javascript">
var img = new Image();
img.onload = init;
img.src = './bg_10.jpg';

var display, source;
var points = [], drew = [];

function init() {
  var c1 = document.createElement('canvas');
  var c2 = document.createElement('canvas');
  c1.width = c2.width = img.width;
  c1.height = c2.height = img.height;
  display = c1.getContext('2d');
  source = c2.getContext('2d');
  display.drawImage(img, 0, 0);
  c1.addEventListener('click', redraw, false);
  document.body.appendChild(c1);
  c2.style.display = 'none';
  document.body.appendChild(c2);
}

function redraw(event) {
  this.enable = this.enable || true;
  if(!this.enable) return;
  this.enable = false;
  var x = event.clientX + document.body.scrollLeft - event.target.offsetLeft;
  var y = event.clientY + document.body.scrollTop - event.target.offsetTop;
  for(var i = 0; i < points.length; i++) {
    if(points[i].x == x && points[i].y == y) return;
  }
  points.push({x: x, y: y, z: 0});
  points.sort(function(a, b) { return a.x - b.x });
  if(points.length < 3) return;
  var tri = triangulate(points);
  if(tri.n <= 0) return;
  for(var i = 0; i < tri.n; i++) {
    var t = tri.triangles[i];
    var p1x = points[t.p1].x, p1y = points[t.p1].y,
        p2x = points[t.p2].x, p2y = points[t.p2].y,
        p3x = points[t.p3].x, p3y = points[t.p3].y;
    var sign = [p1x, p1y, p2x, p2y, p3x, p3y].join(',');
    if(drew.indexOf(sign) != -1) continue;
    source.save();
    source.beginPath();
    source.moveTo(p1x, p1y);
    source.lineTo(p2x, p2y);
    source.lineTo(p3x, p3y);
    source.clip();
    source.drawImage(img, 0, 0);
    var sx = Math.min(p1x, p2x, p3x), sy = Math.min(p1y, p2y, p3y);
    var lx = Math.max(p1x, p2x, p3x), ly = Math.max(p1y, p2y, p3y);
    if(sx < 0 || sy < 0 || lx >= source.width || ly >= source.height) continue;
    var pixels = source.getImageData(sx, sy, lx - sx, ly - sy);
    var p = pixels.data, count = 0, sum = [0,0,0];
    for(var j = 0; j < p.length; j += 4) {
      if(p[j + 3] == 0) continue;
      sum[0] += p[j];
      sum[1] += p[j + 1];
      sum[2] += p[j + 2];
      count++;
    }
    source.restore();
    source.clearRect(0, 0, img.width, img.height);

    display.beginPath();
    var r = Math.floor(sum[0] / count);
    var g = Math.floor(sum[1] / count);
    var b = Math.floor(sum[2] / count);
    var grad = display.createLinearGradient(sx, 0, lx, 0);
    grad.addColorStop(0, 'rgb(' + [r + 20, g + 20, b + 20].join(',') + ')');
    grad.addColorStop(0.7, 'rgb(' + [r, g, b].join(',') + ')');
    grad.addColorStop(1, 'rgb(' + [r - 20, g - 20, b - 20].join(',') + ')');
    display.fillStyle = grad;
    display.moveTo(p1x, p1y);
    display.lineTo(p2x, p2y);
    display.lineTo(p3x, p3y);
    display.fill();
    drew.push(sign);
  }
  this.enable = true;
}

// http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/
function triangulate(points) {
  var EPSILON = 0.0000000001;
  function Edge() { this.p1 = -1, this.p2 = -1; }

  var pxyz = points.slice();
  var nv = pxyz.length;
  for(var i = 0; i < 3; i++) pxyz[nv + i] = {x: null, y: null, z: null};
  var v = new Array(nv * 3);
  for(var i = 0; i < v.length; i++) v[i] = {p1: null, p2: null, p3: null};

  var complete = [];
  var edges = [];
  var nedge = 0;
  var trimax, emax = 200;

  var inside;
  var xp, yp, x1, y1, x2, y2, x3, y3, xc, yc, r;
  var xmin, xmax, ymin, ymax, xmid, ymid;
  var dx, dy, dmax;

  var ntri = 0;

  trimax = 4 * nv;
  complete = new Array(trimax);
  for(var ic = 0; ic < trimax; ic++) complete[ic] = false;

  edges = new Array(emax);
  for(var ie = 0; ie<emax; ie++) edges[ie] = new Edge();

  xmin = pxyz[0].x;
  ymin = pxyz[0].y;
  xmax = xmin;
  ymax = ymin;
  for(var i = 1; i < nv; i++) {
    if(pxyz[i].x < xmin) xmin = pxyz[i].x;
    if(pxyz[i].x > xmax) xmax = pxyz[i].x;
    if(pxyz[i].y < ymin) ymin = pxyz[i].y;
    if(pxyz[i].y > ymax) ymax = pxyz[i].y;
  }
  dx = xmax - xmin;
  dy = ymax - ymin;
  dmax = (dx > dy) ? dx : dy;
  xmid = (xmax + xmin) / 2.0;
  ymid = (ymax + ymin) / 2.0;

  pxyz[nv+0].x = xmid - 2.0 * dmax;
  pxyz[nv+0].y = ymid - dmax;
  pxyz[nv+0].z = 0.0;
  pxyz[nv+1].x = xmid;
  pxyz[nv+1].y = ymid + 2.0 * dmax;
  pxyz[nv+1].z = 0.0;
  pxyz[nv+2].x = xmid + 2.0 * dmax;
  pxyz[nv+2].y = ymid - dmax;
  pxyz[nv+2].z = 0.0;
  v[0].p1 = nv;
  v[0].p2 = nv + 1;
  v[0].p3 = nv + 2;
  complete[0] = false;
  ntri = 1;

  for(var i = 0; i < nv; i++) {
    xp = pxyz[i].x;
    yp = pxyz[i].y;
    nedge = 0;

    var circle = {x: null, y: null, z:null};
    for(var j = 0; j < ntri; j++) {
      if(complete[j]) continue;
      x1 = pxyz[v[j].p1].x;
      y1 = pxyz[v[j].p1].y;
      x2 = pxyz[v[j].p2].x;
      y2 = pxyz[v[j].p2].y;
      x3 = pxyz[v[j].p3].x;
      y3 = pxyz[v[j].p3].y;
      inside = isCircumCircle(xp, yp, x1, y1, x2, y2, x3, y3, circle );
      xc = circle.x; yc = circle.y; r = circle.z;
      if(xc + r < xp) complete[j] = true;
      if(inside) {
        if(nedge + 3 >= emax) {
          emax += 100;
          var edges_n = new Array(emax);
          for (var ie = 0; ie < emax; ie++) {
            if(edges[ie]) edges_n[ie] = edges[ie];
            else edges_n[ie] = new Edge()
          }
          edges = edges_n;
        }
        edges[nedge].p1 = v[j].p1;
        edges[nedge].p2 = v[j].p2;
        edges[nedge + 1].p1 = v[j].p2;
        edges[nedge + 1].p2 = v[j].p3;
        edges[nedge + 2].p1 = v[j].p3;
        edges[nedge + 2].p2 = v[j].p1;
        nedge += 3;
        v[j].p1 = v[ntri - 1].p1;
        v[j].p2 = v[ntri - 1].p2;
        v[j].p3 = v[ntri - 1].p3;
        complete[j] = complete[ntri - 1];
        ntri--;
        j--;
      }
    }

    for(var j = 0; j < nedge - 1; j++) {
      for(var k = j + 1; k < nedge; k++) {
        if((edges[j].p1 == edges[k].p2) && (edges[j].p2 == edges[k].p1)) {
          edges[j].p1 = -1;
          edges[j].p2 = -1;
          edges[k].p1 = -1;
          edges[k].p2 = -1;
        }
        if((edges[j].p1 == edges[k].p1) && (edges[j].p2 == edges[k].p2)) {
          edges[j].p1 = -1;
          edges[j].p2 = -1;
          edges[k].p1 = -1;
          edges[k].p2 = -1;
        }
      }
    }

    for(var j = 0; j < nedge; j++) {
      if(edges[j].p1 == -1 || edges[j].p2 == -1) continue;
      if(ntri >= trimax) return -1;
      v[ntri].p1 = edges[j].p1;
      v[ntri].p2 = edges[j].p2;
      v[ntri].p3 = i;
      complete[ntri] = false;
      ntri++;
    }
  }

  for(var i = 0; i < ntri; i++) {
    if(v[i].p1 >= nv || v[i].p2 >= nv || v[i].p3 >= nv) {
      v[i] = v[ntri - 1];
      ntri--;
      i--;
    }
  }

  return {n: ntri, triangles: v};


  function isCircumCircle(xp, yp, x1, y1, x2, y2, x3,  y3, circle) {
    var m1,m2,mx1,mx2,my1,my2;
    var dx,dy,rsqr,drsqr;
    var xc, yc, r;
    if(Math.abs(y1 - y2) < EPSILON && Math.abs(y2 - y3) < EPSILON) {
      //print("CircumCircle: Points are coincident.");
      return false;
    }
    if(Math.abs(y2 - y1) < EPSILON) {
      m2 = - (x3 - x2) / (y3 - y2);
      mx2 = (x2 + x3) / 2.0;
      my2 = (y2 + y3) / 2.0;
      xc = (x2 + x1) / 2.0;
      yc = m2 * (xc - mx2) + my2;
    } else if(Math.abs(y3-y2) < EPSILON) {
      m1 = - (x2 - x1) / (y2 - y1);
      mx1 = (x1 + x2) / 2.0;
      my1 = (y1 + y2) / 2.0;
      xc = (x3 + x2) / 2.0;
      yc = m1 * (xc - mx1) + my1;
    } else {
      m1 = - (x2 - x1) / (y2 - y1);
      m2 = - (x3 - x2) / (y3 - y2);
      mx1 = (x1 + x2) / 2.0;
      mx2 = (x2 + x3) / 2.0;
      my1 = (y1 + y2) / 2.0;
      my2 = (y2 + y3) / 2.0;
      xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
      yc = m1 * (xc - mx1) + my1;
    }
    dx = x2 - xc;
    dy = y2 - yc;
    rsqr = dx * dx + dy * dy;
    r = Math.sqrt(rsqr);
    dx = xp - xc;
    dy = yp - yc;
    drsqr = dx * dx + dy * dy;
    circle.x = xc;
    circle.y = yc;
    circle.z = r;
    return (drsqr <= rsqr) ? true : false;
  }
}

</script>
</body>
</html>
	<html>
	<head><title>Canvas Delaunay Triangulation</title></head>
	<body></body>
	<script type="text/javascript">
	var img = new Image();
	img.onload = init;
	img.src = './bg_10.jpg';

	var display, source;
	var points = [], drew = [];

	function init() {
	var c1 = document.createElement('canvas');
	var c2 = document.createElement('canvas');
	c1.width = c2.width = img.width;
	c1.height = c2.height = img.height;
	display = c1.getContext('2d');
	source = c2.getContext('2d');
	display.drawImage(img, 0, 0);
	c1.addEventListener('click', redraw, false);
	document.body.appendChild(c1);
	c2.style.display = 'none';
	document.body.appendChild(c2);
	}

	function redraw(event) {
	this.enable = this.enable \|\| true;
	if(!this.enable) return;
	this.enable = false;
	var x = event.clientX + document.body.scrollLeft - event.target.offsetLeft;
	var y = event.clientY + document.body.scrollTop - event.target.offsetTop;
	for(var i = 0; i < points.length; i++) {
	if(points[i].x == x && points[i].y == y) return;
	}
	points.push({x: x, y: y, z: 0});
	points.sort(function(a, b) { return a.x - b.x });
	if(points.length < 3) return;
	var tri = triangulate(points);
	if(tri.n <= 0) return;
	for(var i = 0; i < tri.n; i++) {
	var t = tri.triangles[i];
	var p1x = points[t.p1].x, p1y = points[t.p1].y,
	p2x = points[t.p2].x, p2y = points[t.p2].y,
	p3x = points[t.p3].x, p3y = points[t.p3].y;
	var sign = [p1x, p1y, p2x, p2y, p3x, p3y].join(',');
	if(drew.indexOf(sign) != -1) continue;
	source.save();
	source.beginPath();
	source.moveTo(p1x, p1y);
	source.lineTo(p2x, p2y);
	source.lineTo(p3x, p3y);
	source.clip();
	source.drawImage(img, 0, 0);
	var sx = Math.min(p1x, p2x, p3x), sy = Math.min(p1y, p2y, p3y);
	var lx = Math.max(p1x, p2x, p3x), ly = Math.max(p1y, p2y, p3y);
	if(sx < 0 \|\| sy < 0 \|\| lx >= source.width \|\| ly >= source.height) continue;
	var pixels = source.getImageData(sx, sy, lx - sx, ly - sy);
	var p = pixels.data, count = 0, sum = [0,0,0];
	for(var j = 0; j < p.length; j += 4) {
	if(p[j + 3] == 0) continue;
	sum[0] += p[j];
	sum[1] += p[j + 1];
	sum[2] += p[j + 2];
	count++;
	}
	source.restore();
	source.clearRect(0, 0, img.width, img.height);

	display.beginPath();
	var r = Math.floor(sum[0] / count);
	var g = Math.floor(sum[1] / count);
	var b = Math.floor(sum[2] / count);
	var grad = display.createLinearGradient(sx, 0, lx, 0);
	grad.addColorStop(0, 'rgb(' + [r + 20, g + 20, b + 20].join(',') + ')');
	grad.addColorStop(0.7, 'rgb(' + [r, g, b].join(',') + ')');
	grad.addColorStop(1, 'rgb(' + [r - 20, g - 20, b - 20].join(',') + ')');
	display.fillStyle = grad;
	display.moveTo(p1x, p1y);
	display.lineTo(p2x, p2y);
	display.lineTo(p3x, p3y);
	display.fill();
	drew.push(sign);
	}
	this.enable = true;
	}

	// http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/
	function triangulate(points) {
	var EPSILON = 0.0000000001;
	function Edge() { this.p1 = -1, this.p2 = -1; }

	var pxyz = points.slice();
	var nv = pxyz.length;
	for(var i = 0; i < 3; i++) pxyz[nv + i] = {x: null, y: null, z: null};
	var v = new Array(nv * 3);
	for(var i = 0; i < v.length; i++) v[i] = {p1: null, p2: null, p3: null};

	var complete = [];
	var edges = [];
	var nedge = 0;
	var trimax, emax = 200;

	var inside;
	var xp, yp, x1, y1, x2, y2, x3, y3, xc, yc, r;
	var xmin, xmax, ymin, ymax, xmid, ymid;
	var dx, dy, dmax;

	var ntri = 0;

	trimax = 4 * nv;
	complete = new Array(trimax);
	for(var ic = 0; ic < trimax; ic++) complete[ic] = false;

	edges = new Array(emax);
	for(var ie = 0; ie<emax; ie++) edges[ie] = new Edge();

	xmin = pxyz[0].x;
	ymin = pxyz[0].y;
	xmax = xmin;
	ymax = ymin;
	for(var i = 1; i < nv; i++) {
	if(pxyz[i].x < xmin) xmin = pxyz[i].x;
	if(pxyz[i].x > xmax) xmax = pxyz[i].x;
	if(pxyz[i].y < ymin) ymin = pxyz[i].y;
	if(pxyz[i].y > ymax) ymax = pxyz[i].y;
	}
	dx = xmax - xmin;
	dy = ymax - ymin;
	dmax = (dx > dy) ? dx : dy;
	xmid = (xmax + xmin) / 2.0;
	ymid = (ymax + ymin) / 2.0;

	pxyz[nv+0].x = xmid - 2.0 * dmax;
	pxyz[nv+0].y = ymid - dmax;
	pxyz[nv+0].z = 0.0;
	pxyz[nv+1].x = xmid;
	pxyz[nv+1].y = ymid + 2.0 * dmax;
	pxyz[nv+1].z = 0.0;
	pxyz[nv+2].x = xmid + 2.0 * dmax;
	pxyz[nv+2].y = ymid - dmax;
	pxyz[nv+2].z = 0.0;
	v[0].p1 = nv;
	v[0].p2 = nv + 1;
	v[0].p3 = nv + 2;
	complete[0] = false;
	ntri = 1;

	for(var i = 0; i < nv; i++) {
	xp = pxyz[i].x;
	yp = pxyz[i].y;
	nedge = 0;

	var circle = {x: null, y: null, z:null};
	for(var j = 0; j < ntri; j++) {
	if(complete[j]) continue;
	x1 = pxyz[v[j].p1].x;
	y1 = pxyz[v[j].p1].y;
	x2 = pxyz[v[j].p2].x;
	y2 = pxyz[v[j].p2].y;
	x3 = pxyz[v[j].p3].x;
	y3 = pxyz[v[j].p3].y;
	inside = isCircumCircle(xp, yp, x1, y1, x2, y2, x3, y3, circle );
	xc = circle.x; yc = circle.y; r = circle.z;
	if(xc + r < xp) complete[j] = true;
	if(inside) {
	if(nedge + 3 >= emax) {
	emax += 100;
	var edges_n = new Array(emax);
	for (var ie = 0; ie < emax; ie++) {
	if(edges[ie]) edges_n[ie] = edges[ie];
	else edges_n[ie] = new Edge()
	}
	edges = edges_n;
	}
	edges[nedge].p1 = v[j].p1;
	edges[nedge].p2 = v[j].p2;
	edges[nedge + 1].p1 = v[j].p2;
	edges[nedge + 1].p2 = v[j].p3;
	edges[nedge + 2].p1 = v[j].p3;
	edges[nedge + 2].p2 = v[j].p1;
	nedge += 3;
	v[j].p1 = v[ntri - 1].p1;
	v[j].p2 = v[ntri - 1].p2;
	v[j].p3 = v[ntri - 1].p3;
	complete[j] = complete[ntri - 1];
	ntri--;
	j--;
	}
	}

	for(var j = 0; j < nedge - 1; j++) {
	for(var k = j + 1; k < nedge; k++) {
	if((edges[j].p1 == edges[k].p2) && (edges[j].p2 == edges[k].p1)) {
	edges[j].p1 = -1;
	edges[j].p2 = -1;
	edges[k].p1 = -1;
	edges[k].p2 = -1;
	}
	if((edges[j].p1 == edges[k].p1) && (edges[j].p2 == edges[k].p2)) {
	edges[j].p1 = -1;
	edges[j].p2 = -1;
	edges[k].p1 = -1;
	edges[k].p2 = -1;
	}
	}
	}

	for(var j = 0; j < nedge; j++) {
	if(edges[j].p1 == -1 \|\| edges[j].p2 == -1) continue;
	if(ntri >= trimax) return -1;
	v[ntri].p1 = edges[j].p1;
	v[ntri].p2 = edges[j].p2;
	v[ntri].p3 = i;
	complete[ntri] = false;
	ntri++;
	}
	}

	for(var i = 0; i < ntri; i++) {
	if(v[i].p1 >= nv \|\| v[i].p2 >= nv \|\| v[i].p3 >= nv) {
	v[i] = v[ntri - 1];
	ntri--;
	i--;
	}
	}

	return {n: ntri, triangles: v};


	function isCircumCircle(xp, yp, x1, y1, x2, y2, x3, y3, circle) {
	var m1,m2,mx1,mx2,my1,my2;
	var dx,dy,rsqr,drsqr;
	var xc, yc, r;
	if(Math.abs(y1 - y2) < EPSILON && Math.abs(y2 - y3) < EPSILON) {
	//print("CircumCircle: Points are coincident.");
	return false;
	}
	if(Math.abs(y2 - y1) < EPSILON) {
	m2 = - (x3 - x2) / (y3 - y2);
	mx2 = (x2 + x3) / 2.0;
	my2 = (y2 + y3) / 2.0;
	xc = (x2 + x1) / 2.0;
	yc = m2 * (xc - mx2) + my2;
	} else if(Math.abs(y3-y2) < EPSILON) {
	m1 = - (x2 - x1) / (y2 - y1);
	mx1 = (x1 + x2) / 2.0;
	my1 = (y1 + y2) / 2.0;
	xc = (x3 + x2) / 2.0;
	yc = m1 * (xc - mx1) + my1;
	} else {
	m1 = - (x2 - x1) / (y2 - y1);
	m2 = - (x3 - x2) / (y3 - y2);
	mx1 = (x1 + x2) / 2.0;
	mx2 = (x2 + x3) / 2.0;
	my1 = (y1 + y2) / 2.0;
	my2 = (y2 + y3) / 2.0;
	xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
	yc = m1 * (xc - mx1) + my1;
	}
	dx = x2 - xc;
	dy = y2 - yc;
	rsqr = dx * dx + dy * dy;
	r = Math.sqrt(rsqr);
	dx = xp - xc;
	dy = yp - yc;
	drsqr = dx * dx + dy * dy;
	circle.x = xc;
	circle.y = yc;
	circle.z = r;
	return (drsqr <= rsqr) ? true : false;
	}
	}

	</script>
	</body>
	</html>