var Delaunay;
(function() {
"use strict";
var EPSILON = 1.0 / 1048576.0;
function supertriangle(vertices) {
var xmin = Number.POSITIVE_INFINITY,
ymin = Number.POSITIVE_INFINITY,
xmax = Number.NEGATIVE_INFINITY,
ymax = Number.NEGATIVE_INFINITY,
i, dx, dy, dmax, xmid, ymid;
for(i = vertices.length; i--; ) {
if(vertices[i][0] < xmin) xmin = vertices[i][0];
if(vertices[i][0] > xmax) xmax = vertices[i][0];
if(vertices[i][1] < ymin) ymin = vertices[i][1];
if(vertices[i][1] > ymax) ymax = vertices[i][1];
}
dx = xmax - xmin;
dy = ymax - ymin;
dmax = Math.max(dx, dy);
xmid = xmin + dx * 0.5;
ymid = ymin + dy * 0.5;
return [
[xmid - 20 * dmax, ymid - dmax],
[xmid , ymid + 20 * dmax],
[xmid + 20 * dmax, ymid - dmax]
];
}
function circumcircle(vertices, i, j, k) {
var x1 = vertices[i][0],
y1 = vertices[i][1],
x2 = vertices[j][0],
y2 = vertices[j][1],
x3 = vertices[k][0],
y3 = vertices[k][1],
fabsy1y2 = Math.abs(y1 - y2),
fabsy2y3 = Math.abs(y2 - y3),
xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;
/* Check for coincident points */
if(fabsy1y2 < EPSILON && fabsy2y3 < EPSILON)
throw new Error("Eek! Coincident points!");
if(fabsy1y2 < 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(fabsy2y3 < 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 = (fabsy1y2 > fabsy2y3) ?
m1 * (xc - mx1) + my1 :
m2 * (xc - mx2) + my2;
}
dx = x2 - xc;
dy = y2 - yc;
return {i: i, j: j, k: k, x: xc, y: yc, r: dx * dx + dy * dy};
}
function dedup(edges) {
var i, j, a, b, m, n;
for(j = edges.length; j; ) {
b = edges[--j];
a = edges[--j];
for(i = j; i; ) {
n = edges[--i];
m = edges[--i];
if((a === m && b === n) || (a === n && b === m)) {
edges.splice(j, 2);
edges.splice(i, 2);
break;
}
}
}
}
Delaunay = {
triangulate: function(vertices, key) {
var n = vertices.length,
i, j, indices, st, open, closed, edges, dx, dy, a, b, c;
/* Bail if there aren't enough vertices to form any triangles. */
if(n < 3)
return [];
/* Slice out the actual vertices from the passed objects. (Duplicate the
* array even if we don't, though, since we need to make a supertriangle
* later on!) */
vertices = vertices.slice(0);
if(key)
for(i = n; i--; )
vertices[i] = vertices[i][key];
/* Make an array of indices into the vertex array, sorted by the
* vertices' x-position. Force stable sorting by comparing indices if
* the x-positions are equal. */
indices = new Array(n);
for(i = n; i--; )
indices[i] = i;
indices.sort(function(i, j) {
var diff = vertices[j][0] - vertices[i][0];
return diff !== 0 ? diff : i - j;
});
/* Next, find the vertices of the supertriangle (which contains all other
* triangles), and append them onto the end of a (copy of) the vertex
* array. */
st = supertriangle(vertices);
vertices.push(st[0], st[1], st[2]);
/* Initialize the open list (containing the supertriangle and nothing
* else) and the closed list (which is empty since we havn't processed
* any triangles yet). */
open = [circumcircle(vertices, n + 0, n + 1, n + 2)];
closed = [];
edges = [];
/* Incrementally add each vertex to the mesh. */
for(i = indices.length; i--; edges.length = 0) {
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--; ) {
/* 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. */
dx = vertices[c][0] - open[j].x;
if(dx > 0.0 && dx * dx > open[j].r) {
closed.push(open[j]);
open.splice(j, 1);
continue;
}
/* If we're outside the circumcircle, skip this triangle. */
dy = vertices[c][1] - open[j].y;
if(dx * dx + dy * dy - open[j].r > EPSILON)
continue;
/* Remove the triangle and add it's edges to the edge list. */
edges.push(
open[j].i, open[j].j,
open[j].j, open[j].k,
open[j].k, open[j].i
);
open.splice(j, 1);
}
/* Remove any doubled edges. */
dedup(edges);
/* Add a new triangle for each edge. */
for(j = edges.length; j; ) {
b = edges[--j];
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 supertriangle,
* building a list of triplets that represent triangles. */
for(i = open.length; i--; )
closed.push(open[i]);
open.length = 0;
for(i = closed.length; i--; )
if(closed[i].i < n && closed[i].j < n && closed[i].k < n)
open.push(closed[i].i, closed[i].j, closed[i].k);
/* Yay, we're done! */
return open;
},
contains: function(tri, p) {
/* Bounding box test first, for quick rejections. */
if((p[0] < tri[0][0] && p[0] < tri[1][0] && p[0] < tri[2][0]) ||
(p[0] > tri[0][0] && p[0] > tri[1][0] && p[0] > tri[2][0]) ||
(p[1] < tri[0][1] && p[1] < tri[1][1] && p[1] < tri[2][1]) ||
(p[1] > tri[0][1] && p[1] > tri[1][1] && p[1] > tri[2][1]))
return null;
var a = tri[1][0] - tri[0][0],
b = tri[2][0] - tri[0][0],
c = tri[1][1] - tri[0][1],
d = tri[2][1] - tri[0][1],
i = a * d - b * c;
/* Degenerate tri. */
if(i === 0.0)
return null;
var u = (d * (p[0] - tri[0][0]) - b * (p[1] - tri[0][1])) / i,
v = (a * (p[1] - tri[0][1]) - c * (p[0] - tri[0][0])) / i;
/* If we're outside the tri, fail. */
if(u < 0.0 || v < 0.0 || (u + v) > 1.0)
return null;
return [u, v];
}
};
if(typeof module !== "undefined")
module.exports = Delaunay;
})();
1.We consider each point one by one inside the larger "super-triangle".
2. For every point, we consider all the triangles whose circumcircles contain the point, and call these the "bad triangles".
3. For every triangle in the "bad triangles", we remove from the main mesh any edges that are shared by at least 2 of the "bad triangles" (i.e. we keep only those "bad-triangle-edges" which are unique to a single "bad triangle"). Now, for every edge belonging to a "bad triangle" that was not removed, form a triangle using the edge and the point.
4. Repeat the above for all points.
5. When done, remove the vertices of the "super triangle" and all edges incident upon them.
Super Triangle
/**
Inspired by
http://www.travellermap.com/tmp/delaunay.htm
License: Public Domain
Original C++ code by Joshua Bell
@modified_by Ikaros Kappler
@date_init 2012-10-17
@date 2017-07-31
@version 2.0.0
/
var EPSILON = 1.0e-6;
window.Delaunay = function( pointList, config ) {
var backgroundTexture;
var polyCanvas;
var context;
//var vertexSet;
/
A box array for storing the tiles in PolyBox objects.
*/
var boxes;
function performPolygonTriangulation() {
return Triangulate( pointList );
}
////////////////////////////////////////////////////////////////////////////////
//
// Delaunay Triangulation Code, by Joshua Bell
//
// Inspired by: http://www.codeguru.com/cpp/data/mfc_database/misc/article.php/c8901/
//
// This work is hereby released into the Public Domain. To view a copy of the public
// domain dedication, visit http://creativecommons.org/licenses/publicdomain/ or send
// a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco,
// California, 94105, USA.
//
////////////////////////////////////////////////////////////////////////////////
//------------------------------------------------------------
// Edge class
//------------------------------------------------------------
function Edge( a, b ) {
this.a = a;
this.b = b;
} // Edge
//------------------------------------------------------------
// Triangulate
//
// Perform the Delaunay Triangulation of a set of vertices.
//
// vertices: Array of Vertex objects
//
// returns: Array of Triangles
//------------------------------------------------------------
function Triangulate( vertices ) {
var triangles = [];
// First, create a "supertriangle" that bounds all vertices
var st = createBoundingTriangle( vertices );
triangles.push( st );
// begin the triangulation one vertex at a time
var i;
for( i in vertices ) {
// NOTE: This is O(n^2) - can be optimized by sorting vertices
// along the x-axis and only considering triangles that have
// potentially overlapping circumcircles
var vertex = vertices[i];
AddVertex( vertex, triangles );
}
// Remove triangles that shared edges with "supertriangle"
for( i in triangles ) {
var triangle = triangles[i];
if( triangle.a == st.a || triangle.a == st.b || triangle.a == st.c ||
triangle.b == st.a || triangle.b == st.b || triangle.b == st.c ||
triangle.c == st.a || triangle.c == st.b || triangle.c == st.c ) {
delete triangles[i];
}
}
return triangles;
} // Triangulate
// Internal: create a triangle that bounds the given vertices, with room to spare
function createBoundingTriangle( vertices ) {
// NOTE: There's a bit of a heuristic here. If the bounding triangle
// is too large and you see overflow/underflow errors. If it is too small
// you end up with a non-convex hull.
var minx, miny, maxx, maxy;
for( var i in vertices )
{
var vertex = vertices[i];
if( minx === undefined || vertex.x < minx ) { minx = vertex.x; }
if( miny === undefined || vertex.y < miny ) { miny = vertex.y; }
if( maxx === undefined || vertex.x > maxx ) { maxx = vertex.x; }
if( maxy === undefined || vertex.y > maxy ) { maxy = vertex.y; }
}
var dx = ( maxx - minx ) 10;
var dy = ( maxy - miny ) 10;
var stv0 = new Vertex( minx - dx, miny - dy*3 );
var stv1 = new Vertex( minx - dx, maxy + dy );
var stv2 = new Vertex( maxx + dx*3, maxy + dy );
return new Triangle( stv0, stv1, stv2 );
} // createBoundingTriangle
// Internal: update triangulation with a vertex
function AddVertex( vertex, triangles ) {
var edges = [];
// Remove triangles with circumcircles containing the vertex
var i;
for( i in triangles ) {
var triangle = triangles[i];
if( triangle.inCircumcircle( vertex ) ) {
edges.push( new Edge( triangle.a, triangle.b ) );
edges.push( new Edge( triangle.b, triangle.c ) );
edges.push( new Edge( triangle.c, triangle.a ) );
delete triangles[i];
}
}
edges = mkUniqueEdges( edges );
// Create new triangles from the unique edges and new vertex
for( i in edges ) {
// console.log( 'adding triangle' );
var edge = edges[i];
triangles.push( new Triangle( edge.a, edge.b, vertex ) );
}
} // AddVertex
// Internal: remove duplicate edges from an array
function mkUniqueEdges( edges ) {
// TODO: This is O(n^2), make it O(n) with a hash or some such
var uniqueEdges = [];
for( var i in edges ) {
var edge1 = edges[i];
var unique = true;
for( var j in edges ) {
if( i != j ) {
var edge2 = edges[j];
if( ( edge1.a == edge2.a && edge1.b == edge2.b ) ||
( edge1.a == edge2.b && edge1.b == edge2.a ) ) {
unique = false;
break;
}
}
}
if( unique )
uniqueEdges.push( edge1 );
}
return uniqueEdges;
} // END mkUniqueEdges
// Do some pseudo exports
this.triangulate = performPolygonTriangulation;
}; // END _constructor
Useful References
Comments