Forked from ucnv/canvas-delaunay-triangulation.html
Created
January 19, 2019 17:17
-
-
Save wisniewski94/a4151dc4bfb60189965f2497024662b6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<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> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment