The underlying Delaunay algorithm of this experiment was ported and adapted from Paul Bourke.
Delaunay = function()
{
var EPSILON = 1.0 / 1048576.0;
function superTriangle( vertices )
{
var minX = Number.POSITIVE_INFINITY;
var minY = Number.POSITIVE_INFINITY;
var maxX = Number.NEGATIVE_INFINITY;
var maxY = Number.NEGATIVE_INFINITY;
for( var i = vertices.length; i--; )
{
if( vertices[ i ].x < minX )
{
minX = vertices[ i ].x;
}
if( vertices[ i ].x > maxX )
{
maxX = vertices[ i ].x;
}
if( vertices[ i ].y < minY )
{
minY = vertices[ i ].y;
}
if( vertices[ i ].y > maxY )
{
maxY = vertices[ i ].y;
}
}
var dx = maxX - minX;
var dy = maxY - minY;
var dMax = Math.max( dx, dy );
var midX = minX + dx * 0.5;
var midY = minY + dy * 0.5;
return new DTriangle(
{ x: ( midX - 20 * dMax ), y: ( midY - dMax ) },
{ x: midX, y: ( midY + 20 * dMax ) },
{ x: ( midX + 20 * dMax ), y: ( midY - dMax ) }
);
}
function circumCircle( vertices, i, j, k )
{
var x1 = vertices[ i ].x;
var y1 = vertices[ i ].y;
var x2 = vertices[ j ].x;
var y2 = vertices[ j ].y;
var x3 = vertices[ k ].x;
var y3 = vertices[ k ].y;
var fabSy1y2 = Math.abs( y1 - y2 );
var fabSy2y3 = Math.abs( y2 - y3 );
var xc;
var yc;
/* Check for coincident points */
if( fabSy1y2 < EPSILON && fabSy2y3 < EPSILON )
{
throw new Error( "Coincident points!" );
}
if( fabSy1y2 < EPSILON )
{
var m2 = -((x3 - x2) / (y3 - y2));
var mx2 = (x2 + x3) / 2.0;
var my2 = (y2 + y3) / 2.0;
xc = (x2 + x1) / 2.0;
yc = m2 * (xc - mx2) + my2;
}
else if( fabSy2y3 < EPSILON )
{
var m1 = -((x2 - x1) / (y2 - y1));
var mx1 = (x1 + x2) / 2.0;
var my1 = (y1 + y2) / 2.0;
xc = (x3 + x2) / 2.0;
yc = m1 * (xc - mx1) + my1;
}
else
{
var m1 = -((x2 - x1) / (y2 - y1));
var m2 = -((x3 - x2) / (y3 - y2));
var mx1 = (x1 + x2) / 2.0;
var mx2 = (x2 + x3) / 2.0;
var my1 = (y1 + y2) / 2.0;
var my2 = (y2 + y3) / 2.0;
xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
yc = (fabSy1y2 > fabSy2y3) ? m1 * (xc - mx1) + my1 : m2 * (xc - mx2) + my2;
}
var dx = x2 - xc;
var dy = y2 - yc;
return { i: i, j: j, k: k, x: xc, y: yc, r: dx * dx + dy * dy };
}
function dedup( edges )
{
for( var j = edges.length; j > 0; )
{
var b = edges[ --j ];
var a = edges[ --j ];
for( var i = j; i > 0; )
{
var n = edges[ --i ];
var m = edges[ --i ];
if( (a === m && b === n) || (a === n && b === m) )
{
edges.splice( j, 2 );
edges.splice( i, 2 );
break;
}
}
}
}
this.compute = function( points )
{
var n = points.length;
if( n < 3 )
{
return [];
}
var i;
var j;
// make a copy of points
var vertices = points.slice( 0 );
// make an array of indices into the vertex array, sorted by the vertices' x-position.
var indices = new Array( n );
for( i = 0; i < n; ++i )
{
indices[ i ] = i;
}
indices.sort( function( i, j )
{
return vertices[ j ].x - vertices[ i ].x;
} );
// find the vertices of the super-triangle ( which contains all other
// triangles), and append them onto the end of a the vertex array.
var t = superTriangle( vertices );
vertices.push( t.p1, t.p2, t.p3 );
// Initialize the open list (containing the super-triangle and nothing
// else) and the closed list (which is empty since we haven't processed any triangles yet).
var open = [ circumCircle( vertices, n + 0, n + 1, n + 2 ) ];
var closed = [];
var edges = [];
// incrementally add each vertex to the mesh.
for( i = indices.length; i--; edges.length = 0 )
{
var c = indices[ i ];
/* For each open triangle, check to see if the current point is
* inside it's circumcircle. If it is, remove the triangle and add
* it's edges to an edge list. */
for( j = open.length; j--; )
{
var oj = open[ j ];
// If this point is to the right of this triangle's circumcircle,
// then this triangle should never get checked again. Remove it
// from the open list, add it to the closed list, and skip.
var dx = vertices[ c ].x - oj.x;
if( dx > 0.0 && dx * dx > oj.r )
{
closed.push( oj );
open.splice( j, 1 );
continue;
}
// If we're outside the circumcircle, skip this triangle.
var dy = vertices[ c ].y - oj.y;
if( dx * dx + dy * dy - oj.r > EPSILON )
{
continue;
}
// remove the triangle and add it's edges to the edge list.
edges.push( oj.i, oj.j, oj.j, oj.k, oj.k, oj.i );
open.splice( j, 1 );
}
// remove any doubled edges.
dedup( edges );
// add a new triangle for each edge.
for( j = edges.length; j; )
{
var b = edges[ --j ];
var a = edges[ --j ];
open.push( circumCircle( vertices, a, b, c ) );
}
}
// Copy any remaining open triangles to the closed list, and then
// remove any triangles that share a vertex with the super-triangle,
// building a list of triplets that represent triangles.
for( i = open.length; i--; )
{
closed.push( open[ i ] );
}
var triangles = [];
for( i = closed.length; i--; )
{
var c = closed[ i ];
if( c.i < n && c.j < n && c.k < n )
{
triangles.push( new DTriangle( points[ c.i ], points[ c.j ], points[ c.k ] ) );
}
}
return triangles;
}
};
DTriangle = function( point1, point2, point3 )
{
this.p1 = point1;
this.p2 = point2;
this.p3 = point3;
this.getCenter = function()
{
return {
x: ( this.p1.x + this.p2.x + this.p3.x ) / 3,
y: ( this.p1.y + this.p2.y + this.p3.y ) / 3
}
};
};