关于Delaunay三角网的构建，我自己也写了一个算法，但是效率很低，于是参考网上的相关算法，这里特别感谢“纸异兽”，他的文章讲的最为详细， http://www.cnblogs.com/zhiyishou/p/4430017.html 但是这个算法，不是一个完整的算法，最后删除辅助三角形的三个顶点，过于简单粗暴。
纸异兽实现的算法完美适配的情况是“点集中的每个点恰好是凸多边形的顶点”。 有两点做得不好， 1）当点集只有4到10个点，算法的缺陷被放大，经常找不完全，甚至出现孤点，每个点都应该是三角形的顶点，不应该出现孤立的点； 当点集有很多时，比如50个点以上，经常出现，边界三角形被漏掉，最终三角网不是凸包, 而是凹包。
2）当有3个以上邻接点共线时，会出现点在三角形的边上，而不是顶点。
第二个问题很好解决，只需要加个判断即可，
for (j = buffer.length; j;) { var obj = circumcircle(vertices, buffer[--j], buffer[--j], current); if (obj.r != Infinity) { open.push(obj); } }第一个问题，比较麻烦，我的思路是，一个点一个点地删除，每删除一个点，就要局部更新三角网。
<html><head><title>Delaunay update</title> </head><body><div> <canvas id="canvas" width="1000" height="350" style="border: solid black 1px; cursor: default;"></canvas> </div> <div> <input type="button" value="clear" onclick="demo.clear();"> <input type="button" value="load from string" onclick="demo.load();"> <input type="button" value="save to string" onclick="demo.save();"> <input type="button" value="generate" onclick="demo.generate(true);"> <input type="button" value="smaller" onclick="demo.smaller();"> <input type="button" value="delete" id="deleteBtn" disabled="true"> </div> <br/> <textarea id="txtArea" style="margin: 0px; width: 1200px; height: 33px;"></textarea> <br/> <script type="text/javascript" src="MathUtil.js"></script> <script type="text/javascript"> var demo = new Demo(); var config = new Config(); function Config() { this.MIN_DISTANCE = 40; this.TOTAL_VERTICES = 80; this.OBSTACLE_PERCENT = 25; } var canvas = document.getElementById('canvas'); var context = canvas.getContext('2d'); function Demo() { var vertices = []; var obstacleFlags = []; var allTriangles; function initRandomVertices() { if (vertices.length == 0) { var first = createRandomPoint(); first.id = 0; vertices.push(first); } for (var i = 1; i < config.TOTAL_VERTICES; i++) { var p = createProperRandomPoint(); if (p != null) { p.id = i; vertices.push(p); } else { break; } } console.log("expected: " + config.TOTAL_VERTICES + ", actually: " + vertices.length); } function createProperRandomPoint() { for (var i = 0; i < 255; i++) { var v = createRandomPoint(); var closestDistance = getClosestPoint(v, vertices, []).distance; if (closestDistance >= config.MIN_DISTANCE) { return v; } } return null; } function createRandomPoint() { return new Vertex(getRandom(50, canvas.width-50), getRandom(50, canvas.height-50)); } function getTriangleByPoint(p) { if (allTriangles != null && allTriangles.length > 0) { for (var i = 0; i < allTriangles.length; i++) { if (allTriangles[i].contains(p)) { return allTriangles[i]; } } } return null; } var mouseOnTri = null; var priTris = []; var pd = null; this.onMouseMove = function(x, y) { if (allTriangles == null || allTriangles.length == 0) { return; } priTris = []; pd = null; mouseOnTri = null; document.getElementById("deleteBtn").disabled = true; var p = new Vertex(x, y); for (var i = 0; i < vertices.length; i++) { var v = vertices[i]; var dx = v.x - p.x; var dy = v.y - p.y; if (dx*dx + dy*dy < 225) { pd = v; priTris = []; this.render(); return; } } for (var i = 0; i < allTriangles.length; i++) { var tri = allTriangles[i]; if (tri.circumcircleContains(p)) { priTris.push(tri); if (tri.contains(p)) { mouseOnTri = tri; } } } this.render(); } this.clickAt = function(x, y) { var p = new Vertex(x, y); var newTris = []; if (pd != null) { var trisDelete = point_triangles[pd.toString()]; var isUpdatingBorder = false; var edges = point_edges[pd.toString()]; for (var i = 0; i < edges.length; i++) { var edge = edges[i]; var str1 = edge[0].toString() + "," + edge[1].toString(); var str2 = edge[1].toString() + "," + edge[0].toString(); var tris = edge_triangles[str1]; if (tris == null) { tris = edge_triangles[str2]; } if (tris != null && tris.length == 1) { isUpdatingBorder = true; break; } } this.deleteTriangles(trisDelete); if (isUpdatingBorder) { //update border, delet point on border newTris = deletePointFromBorder(trisDelete, vertices, pd); } else { newTris = updateTriangles(trisDelete, vertices, null, pd); } vertices.splice(pd.id, 1); for (var i = pd.id; i < vertices.length; i++) { vertices[i].id = i; } } else if (priTris != null && priTris.length > 0) { p.id = vertices.length; vertices.push(p); this.deleteTriangles(priTris); if (mouseOnTri == null) { newTris = addPointOutOfBorder(p, vertices, priTris); priTris = []; } else { newTris = updateTriangles(priTris, vertices, p, null); priTris = []; } } else { //update border, add point out of border p.id = vertices.length; vertices.push(p); newTris = addPointOutOfCircles(p, vertices); } allTriangles = allTriangles.concat(newTris); //rebuild neighborhood clearNeighborhood(); for (var i = 0; i < allTriangles.length; i++) { var t = allTriangles[i]; t.index = i; saveToPointAndEdgeMap(t); } initNeighborhood(allTriangles); //draw new triangles this.render(); } this.deleteTriangles = function(needDelete) { for (var i = 0; i < needDelete.length; i++) { for (var j = 0; j < allTriangles.length; j++) { if (allTriangles[j].index == needDelete[i].index) { allTriangles.splice(j, 1); break; } } } } this.save = function() { document.getElementById("txtArea").value = vertices.toString(); } var isLoading = false; this.load = function() { this.clearVertices(); isLoading = true; var txt = document.getElementById("txtArea").value; if (txt == null || txt.length < 12) { return; } var arr = txt.split("<>"); var points = arr[0].split(","); for (var i=0; i<points.length; i++) { var p = new Vertex(0, 0); p.init(points[i]); p.id = i; vertices.push(p); } if (arr.length > 1) { var obstaclesStr = arr[1]; obstacleFlags = obstaclesStr.split(","); } if (obstacleFlags.length > 0) { this.generateObstacles(); } else if (vertices.length > 0) { this.generate(true); } isLoading = false; } this.generate = function(needDraw) { if (!isLoading) { this.clear(); initRandomVertices(); document.getElementById("txtArea").value = vertices.toString(); } allTriangles = getAllDelaunayTriangles(vertices, true); for (var i = 0; i < allTriangles.length; i++) { allTriangles[i].index = i; saveToPointAndEdgeMap(allTriangles[i]); } initNeighborhood(allTriangles); if (needDraw) { this.render(); } } this.generateObstacles = function() { } this.smaller = function() { if (vertices.length > 0) { var ret = []; for (var i= 0; i < vertices.length; i++) { var p = vertices[i]; p.x = p.x / 2; p.y = p.y / 2; ret.push(p); } document.getElementById("txtArea").value = ret.toString(); } } this.clear = function() { this.clearVertices(); document.getElementById("txtArea").value = ""; } this.clearVertices = function() { clearNeighborhood(); vertices = []; obstacleFlags = []; context.clearRect(0, 0, Number(canvas.width), Number(canvas.height)); } this.render = function() { context.clearRect(0, 0, Number(canvas.width), Number(canvas.height)); if (!canvas.getContext) return; if (vertices.length <= 0) { return; } var validCount = 0; for (var i = 0; i < allTriangles.length; i++) { allTriangles[i].draw(context); if (allTriangles[i].isValid) { validCount++; } } console.log("delaunay triangle total: " + allTriangles.length + ", validCount:" + validCount); vertices.forEach(function(vertex) { vertex.draw(context); context.font = "23px Courier New"; context.fillStyle = "orange"; context.fillText(vertex.id, vertex.x, vertex.y); }); if (pd != null) { pd.drawWith(context, "#00aa00"); } for (var i = 0; i < priTris.length; i++) { var t = priTris[i]; t.drawWith(context, "#22bb22"); } if (mouseOnTri != null) { mouseOnTri.drawCircumcircleWith(context, "#33aa33"); } } }; var EPSILON = Number.EPSILON || Math.pow(2,-52); function getAllDelaunayTriangles(vertices, needScanBorder) { var n, i, j, indices, buffer, open, closed, current, dx, dy; if ((n = vertices.length) < 3) return []; vertices = vertices.concat(); //create a array base vertices's key for (i = n, indices = new Array(n); i--;) indices[i] = i; //sort the indices base on the x coordinate of vertices //from bigger to smaller indices.sort(function (a, b) { return vertices[b].x - vertices[a].x; }); //create a supertriangle to buffer and push the vertex to vertices Array buffer = supertriangle(vertices); buffer[0].id = n; buffer[1].id = n+1; buffer[2].id = n+2; vertices.push(buffer[0], buffer[1], buffer[2]); //attach supertriangle to open for a start triangle open = [circumcircle(vertices, n + 0, n + 1, n + 2)]; closed = []; buffer = []; //starting loop from smallest x of vertex for (i = indices.length; i--; buffer.length = 0) { current = indices[i]; for (j = open.length; j--;) { dx = vertices[current].x - open[j].x; if (dx > 0 && dx * dx > open[j].r) { closed.push(open[j]); open.splice(j, 1); continue; } //skip this point if it is outside this circumcircle dy = vertices[current].y - open[j].y; if (dx * dx + dy * dy - open[j].r > EPSILON) continue; //add edges of this triangle to buffer buffer.push(open[j].i, open[j].j, open[j].j, open[j].k, open[j].k, open[j].i); open.splice(j, 1); } dedup(buffer); for (j = buffer.length; j;) { var obj = circumcircle(vertices, buffer[--j], buffer[--j], current); if (obj.r != Infinity) { open.push(obj); } } } for (i = open.length; i--;) closed.push(open[i]); var ret = []; // for (var i = 0; i < closed.length; i++) { // var obj = closed[i]; // var t = new Triangle(vertices[obj.i], vertices[obj.j], vertices[obj.k]); // t.circumcircle = circumcircle(vertices, obj.i, obj.j, obj.k); // ret.push(t); // } var deletingTris; var closed2; var removed = []; for (var j = 0; j < 3; j++) { deletingTris = []; closed2 = []; var lastIndex = vertices.length - 1; for (var i = 0; i < closed.length; i++) { var circumcircleObj = closed[i]; var t = new Triangle(vertices[circumcircleObj.i], vertices[circumcircleObj.j], vertices[circumcircleObj.k]); if (circumcircleObj.i == lastIndex || circumcircleObj.j == lastIndex || circumcircleObj.k == lastIndex) { deletingTris.push(t); } else { closed2.push(closed[i]); } } var deletingPoint = vertices[lastIndex]; for (var k = 0; k < ret.length; k++) { if (ret[k].isAnglePoint(deletingPoint)) { removed.push(ret[k]); deletingTris.push(ret[k]); } } var tris = deletePointFromBorder(deletingTris, vertices, deletingPoint); ret = ret.concat(tris); closed = closed2; vertices.pop(); } ret = subtract(ret, removed); for (var i = 0; i < closed.length; i++) { var obj = closed[i]; var t = new Triangle(vertices[obj.i], vertices[obj.j], vertices[obj.k]); t.circumcircle = obj; ret.push(t); } return ret; } function supertriangle(v) { var xmin = Number.POSITIVE_INFINITY, ymin = xmin, ymax = 0, xmax = 0, i, xl, yl, xlh; for (i = v.length; i--;) v[i].x < xmin && (xmin = v[i].x), v[i].x > xmax && (xmax = v[i].x), v[i].y < ymin && (ymin = v[i].y), v[i].y > ymax && (ymax = v[i].y); xl = xmax - xmin; yl = ymax - ymin; xlh = xl / 2; return [ new Vertex(xmin - xlh, ymax), //the left vertex's coordinate new Vertex(xmin + xlh, ymin - yl ), //the top vertex's coordinate new Vertex(xmax + xlh, ymax) //teh right vertex's coordinate ]; } //multiplex the circumcircle algorithm function circumcircle(v, i, j, k) { var x1 = v[i].x, y1 = v[i].y, x2 = v[j].x, y2 = v[j].y, x3 = v[k].x, y3 = v[k].y, fabsy1y2 = Math.abs(y1 - y2), fabsy2y3 = Math.abs(y2 - y3), xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy; 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, r2: Math.sqrt(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; } } } } function saveTriangleToPointMap(triangle, key) { if (point_triangles[key] == null) { point_triangles[key] = [triangle]; } else { point_triangles[key].push(triangle); } } function saveTriangleToEdgeMap(triangle, str1, str2) { if (edge_triangles[str1 + "," + str2] != null) { edge_triangles[str1 + "," + str2].push(triangle); } else if (edge_triangles[str2 + "," + str1] != null) { edge_triangles[str2 + "," + str1].push(triangle); } else { edge_triangles[str1 + "," + str2] = [triangle]; } } function saveToPointEdgesMap(tri, p1, p2, p3) { if (point_edges[p1] == null) { point_edges[p1] = []; } if (point_edges[p2] == null) { point_edges[p2] = []; } if (point_edges[p3] == null) { point_edges[p3] = []; } addToPointEdges(p1, [tri.v1, tri.v3]); addToPointEdges(p1, [tri.v1, tri.v2]); addToPointEdges(p2, [tri.v2, tri.v3]); addToPointEdges(p2, [tri.v2, tri.v1]); addToPointEdges(p3, [tri.v3, tri.v1]); addToPointEdges(p3, [tri.v3, tri.v2]); } function addToPointEdges(pStr, edge) { if (!containEdge(point_edges[pStr], edge)) { point_edges[pStr].push(edge); } } function containEdge(arr, edge) { for (var i = 0; i < arr.length; i++) { var e = arr[i]; if ((e[0].toString() == edge[0].toString() && e[1].toString() == edge[1].toString()) || (e[0].toString() == edge[1].toString() && e[1].toString() == edge[0].toString())) { return true; } } return false; } // return arr1 - arr2 elements function getSubtract(arr1, arr2) { if (arr2 == null || arr2.length == 0) { return arr1; } var arr = []; for (var i=0; i<arr1.length; i++) { if (contains(arr1[i], arr2)) { continue; } arr.push(arr1[i]); } return arr; } function contains(p, arr) { for (var i=0; i<arr.length; i++) { if (arr[i].x == p.x && arr[i].y == p.y) { return true; } } return false; } function getClosestPoint(p, array, uncheckArr) { var arr = getSubtract(array, uncheckArr); var min = -1; var v; for (var i=0; i<arr.length; i++) { var distance = getDistanceSquare(p, arr[i]); if (min < 0) { min = distance; v = arr[i]; } else if (min > distance) { min = distance; v = arr[i]; } } v.distance = Math.sqrt(min); return v; } var point_triangles = []; var edge_triangles = []; var point_edges = []; var triangle_neighbor = []; function clearNeighborhood() { point_triangles = []; edge_triangles = []; point_edges = []; triangle_neighbor = []; } function saveToPointAndEdgeMap(triangle) { var str1 = triangle.v1.toString(); var str2 = triangle.v2.toString(); var str3 = triangle.v3.toString(); saveTriangleToPointMap(triangle, str1); saveTriangleToPointMap(triangle, str2); saveTriangleToPointMap(triangle, str3); saveTriangleToEdgeMap(triangle, str1, str2); saveTriangleToEdgeMap(triangle, str2, str3); saveTriangleToEdgeMap(triangle, str3, str1); saveToPointEdgesMap(triangle, str1, str2, str3); } function initNeighborhood(allTriangles) { for (var i = 0; i < allTriangles.length; i++) { var triangle = allTriangles[i]; var neighbor = new Neighbor(triangle); triangle_neighbor[triangle.toString()] = neighbor; var edge12_triangles = subtract(getTrianglesByEdge(triangle.v1, triangle.v2), [triangle]); var edge23_triangles = subtract(getTrianglesByEdge(triangle.v2, triangle.v3), [triangle]); var edge31_triangles = subtract(getTrianglesByEdge(triangle.v3, triangle.v1), [triangle]); var v1_triangles = subtract(point_triangles[triangle.v1.toString()], [triangle].concat(edge12_triangles).concat(edge31_triangles)); var v2_triangles = subtract(point_triangles[triangle.v2.toString()], [triangle].concat(edge12_triangles).concat(edge23_triangles)); var v3_triangles = subtract(point_triangles[triangle.v3.toString()], [triangle].concat(edge23_triangles).concat(edge31_triangles)); neighbor.edgeNeighbors = edge12_triangles.concat(edge23_triangles).concat(edge31_triangles); neighbor.pointNeighbors = v1_triangles.concat(v2_triangles).concat(v3_triangles); if (edge12_triangles.length > 0) neighbor.triangle_edge[edge12_triangles[0].toString()] = [triangle.v1, triangle.v2]; if (edge23_triangles.length > 0) neighbor.triangle_edge[edge23_triangles[0].toString()] = [triangle.v2, triangle.v3]; if (edge31_triangles.length > 0) neighbor.triangle_edge[edge31_triangles[0].toString()] = [triangle.v3, triangle.v1]; } } function getPathOfTriangles(srcTriangle, dstTriangle) { var start = triangle_neighbor[srcTriangle.toString()]; start.parentNeighbor = "none"; if (start.me.equals(dstTriangle)) { return start; } var openedItems = start.getPassableNeighbors(); var closedNeighbors = [start]; for (var i = 0; i < openedItems.length; i++) { openedItems[i].parentNeighbor = start; } while (openedItems.length > 0) { var neighbor = openedItems.shift(); if (neighbor.me.equals(dstTriangle)) { return neighbor; } var newComingItems = neighbor.getPassableNeighbors(); for (var i = 0; i < newComingItems.length; i++) { // if (newComingItems[i].parentNeighbor == null) { // newComingItems[i].parentNeighbor = neighbor; // openedItems.push(newComingItems[i]); // } var newItem = newComingItems[i]; if (!hasNeighbor(openedItems, newItem) && !hasNeighbor(closedNeighbors, newItem)) { newItem.parentNeighbor = neighbor; openedItems.push(newItem); } } closedNeighbors.push(neighbor); } return null; } function hasNeighbor(arr, neighbor) { for (var i = 0; i < arr.length; i++) { if (arr[i].equals(neighbor)) { return true; } } return false; } function Neighbor(triangle) { this.id = triangle.id; this.me = triangle; this.triangle_edge = []; this.pointNeighbors = []; this.edgeNeighbors = []; this.getAllNeighbors = function() { return this.edgeNeighbors.concat(this.pointNeighbors); } this.getPassableNeighbors = function () { var ret = []; for (var i = 0; i < this.edgeNeighbors.length; i++) { if (this.edgeNeighbors[i].isValid && !this.edgeNeighbors[i].isObstacle) { ret.push(triangle_neighbor[this.edgeNeighbors[i].toString()]); } } return ret; } this.equals = function(other) { if (other == null) return false; if (other.id == this.id) { return true; } else { return false; } } } function getTrianglesByEdge(v1, v2) { var str1 = v1.toString(); var str2 = v2.toString(); if (edge_triangles[str1 + "," + str2] != null) { return edge_triangles[str1 + "," + str2]; } else if (edge_triangles[str2 + "," + str1] != null) { return edge_triangles[str2 + "," + str1]; } return []; } function addPointEdgeMap(edges, edge) { var flag = false; for (var i = 0; i < edges.length; i++) { var e = edges[i]; if ((e[0] == edge[0] && e[1] == edge[1]) || (e[0] == edge[1] && e[1] == edge[0])) { flag = true; break; } } if (!flag) { edges.push(edge); } } //for debug function pointsToStr(arr) { var ret = []; for (var i = 0; i < arr.length; i++) { ret.push(arr[i].id); } return ret.toString(); } function changeIndices(arr) { var ret = []; for (var i = 0; i < arr.length; i++) { ret.push(arr[i].id); arr[i].id = i; } return ret; } function loadIndices(arr, indexArr) { for (var i = 0; i < arr.length; i++) { arr[i].id = indexArr[i]; } } function updateTriangles(deleteLst, vertices, newPoint, deletingPoint) { var ret = []; if (newPoint != null) { var borderPoints = getBorderByNearTriangles(deleteLst, vertices); for (var i = 0; i < borderPoints.length; i++) { var p1 = borderPoints[i]; var p2 = borderPoints[getValidIndex(i+1, borderPoints.length)]; var t = new Triangle(p1, p2, newPoint); t.circumcircle = circumcircle(vertices, p1.id, p2.id, newPoint.id); ret.push(t); } return ret; } else { processDeleteLst(deleteLst, null, deletingPoint, ret); return ret; } } function deletePointFromBorder(deleteLst, vertices, deletingPoint) { var points = getBorderByNearTriangles(deleteLst, vertices); var index; for (var i = 0; i < points.length; i++) { var p = points[i]; var preIndex = getValidIndex(i-1, points.length); var nxtIndex = getValidIndex(i+1, points.length); if (deletingPoint != null && p.id == deletingPoint.id) { index = i; break; } } var arr = points.splice(index, points.length - index); points = arr.concat(points); var tris = scanForEdgeTris(points, deletingPoint, true); return tris; } function addPointOutOfBorder(outerPoint, vertices, deleteLst) { var ret = []; var points = processDeleteLst(deleteLst, outerPoint, null, ret); //scan border var triLst = addPointOutOfCircles(outerPoint, vertices); for (var i = 0; i < triLst.length; i++) { var t = triLst[i]; var arr = [t.v1, t.v2, t.v3]; var arr2 = subtract(arr, points); if (arr2.length > 0) { ret.push(t); } } return ret; } //retrieve triangles from delete triangle lst, return points of the return triangles function processDeleteLst(deleteLst, outerPoint, erasingPoint, outputTris) { var remains = []; var points = []; for (var i = 0; i < deleteLst.length; i++) { var tri = deleteLst[i]; var neighbor = triangle_neighbor[tri.toString()]; var lst = neighbor.getAllNeighbors(); var arr = subtract(lst, deleteLst); var arr2 = subtract(arr, remains); remains = remains.concat(arr2); var pts = [tri.v1, tri.v2, tri.v3]; var pts2 = subtract(pts, points); points = points.concat(pts2); } if (outerPoint != null) { points.push(outerPoint); } if (erasingPoint != null) { points = subtract(points, [erasingPoint]); } var indexBac = changeIndices(points); var tris = getAllDelaunayTriangles(points, true); loadIndices(points, indexBac); for (var i = 0; i < tris.length; i++) { var has = false; var crossWith = false; var t = tris[i]; for (var j = 0; j < remains.length; j++) { var tri = remains[j]; if (tri.isSame(t)) { has = true; break; } if (tri.crossWith(t)) { crossWith = true; break; } } if (!has && !crossWith) { outputTris.push(t); } } return points; } function addPointOutOfCircles(outerPoint, vertices) { //retrieve max border var edgeLst = []; var pEdgesMap = []; for (var key in edge_triangles) { var tris = edge_triangles[key]; if (tris.length == 1) { var arr = key.split(","); var p1 = new Vertex(), p2 = new Vertex(); p1.init(arr[0]); p2.init(arr[1]); p1 = getVertex(vertices, p1); p2 = getVertex(vertices, p2); var edge = [p1.id, p2.id]; edgeLst.push(edge); if (pEdgesMap[p1.id] == null) { pEdgesMap[p1.id] = [edge]; } else { pEdgesMap[p1.id].push(edge); } if (pEdgesMap[p2.id] == null) { pEdgesMap[p2.id] = [edge]; } else { pEdgesMap[p2.id].push(edge); } } } var points = getBorderSqence(pEdgesMap, edgeLst[0][0], edgeLst[0][1], vertices); var ret = []; for (var i = 0; i < points.length; i++) { var next = getValidIndex(i + 1, points.length); if (!isCrossWithBorder(points, i, outerPoint)) { if (!isCrossWithBorder(points, next, outerPoint)) { var t = new Triangle(outerPoint, points[i], points[next]); t.circumcircle = circumcircle(vertices, outerPoint.id, points[i].id, points[next].id); ret.push(t); } } } return ret; } function getVertex(vertices, p) { for (var i = 0; i < vertices.length; i++) { var current = vertices[i]; current.x = parseInt(current.x); current.y = parseInt(current.y); if (current.x == p.x && current.y == p.y) { return current; } } return null; } function getBorderByNearTriangles(triangles, vertices) { var edges = []; var eArr = []; for (var i = 0; i < triangles.length; i++) { var t = triangles[i]; eArr.push([t.v1, t.v2]); eArr.push([t.v2, t.v3]); eArr.push([t.v3, t.v1]); } for (var i = 0; i < eArr.length; i++) { var edge = eArr[i]; var index = getEdgeIndex(edges, edge); if (index < 0) { edges.push(edge); } else { edges.splice(index, 1); } } var pEdgesMap = []; for (var i = 0; i < edges.length; i++) { var edge = edges[i]; if (pEdgesMap[edge[0].id] == null) { pEdgesMap[edge[0].id] = [[edge[0].id, edge[1].id]]; } else { addPointEdgeMap(pEdgesMap[edge[0].id], [edge[0].id, edge[1].id]); } if (pEdgesMap[edge[1].id] == null) { pEdgesMap[edge[1].id] = [[edge[0].id, edge[1].id]]; } else { addPointEdgeMap(pEdgesMap[edge[1].id], [edge[0].id, edge[1].id]); } } return getBorderSqence(pEdgesMap, edges[0][0].id, edges[0][1].id, vertices); } function getEdgeIndex(edges, edge) { for (var i = 0; i < edges.length; i++) { if ((edges[i][0].id == edge[0].id && edges[i][1].id == edge[1].id) || (edges[i][1].id == edge[0].id && edges[i][0].id == edge[1].id)) { return i; } } return -1; } function isCrossWithBorder(borderPoints, index, outerPoint) { var p1 = getValidIndex(index - 1, borderPoints.length); var p2 = getValidIndex(index + 1, borderPoints.length); var needSkip = [p1, p2]; for (var i = 0; i < borderPoints.length; i++) { var edgeIndex = (i+1) % borderPoints.length; if ((index == i && needSkip.indexOf(edgeIndex) >= 0) || (index == edgeIndex && needSkip.indexOf(i) >= 0)) { continue; } if (lineSegmentCross(borderPoints[i], borderPoints[edgeIndex], borderPoints[index], outerPoint)) { return true; } } return false; } function getBorderSqence(pEdgeMap, e0, e1, vertices) { var squence = [e0]; var next = pEdgeMap[e0]; var p0 = e0, p1 = e1; if (next == null) { return; } if (next.length == 1) { squence.push(e1); next = pEdgeMap[e1]; } while (next != null) { var e = findNextEdge(next, p0, p1); squence.push(e[0]); next = pEdgeMap[e[0]]; p0 = e[0]; p1 = e[1]; if (p0 == e0) { squence.pop(); next = null; } if (p0 == e1) { next == null; } } var points = []; for (var i = 0; i < squence.length; i++) { var p = vertices[squence[i]]; p.location = squence[i]; points.push(p); } return points; } function copyArr(arr) { var ret = []; for (var i in arr) { ret.push(arr[i]); } return ret; } function scanForEdgeTris(points, deletingPoint, needReverse) { if (points.length < 4) { return []; } var ret = []; var count=0; while(true) { count++; if (count > 10) break; var len = ret.length; var isClockwise = isClockwiseSquence(points); if (needReverse) { isClockwise = !isClockwise; } var concavMark = isClockwise ? "left" : "right"; var removed = []; points[1].mark = points[points.length-1].mark = "end"; var curSize = points.length; for (var i = 2; i < curSize - 1; i++) { var p = points[i]; if (p.mark != concavMark) { continue; } var preIndex = getValidIndex(i-1, points.length); var nxtIndex = getValidIndex(i+1, points.length); var pre = points[preIndex]; var nxt = points[nxtIndex]; if (pre.mark != concavMark && nxt.mark != concavMark) { var t = new Triangle(pre, p, nxt); t.circumcircle = circumcircle(points, preIndex, i, nxtIndex); ret.push(t); removed.push(p); } else if (nxt.mark == concavMark) { removed.push(p, nxt); var arr = [pre, p, nxt]; var j = i + 2; for (; j < curSize - 1; j++) { if (points[j].mark == concavMark) { arr.push(points[j]); removed.push(points[j]); } else { break; } } arr.push(points[j]); getTrisFromConvexPolygon(arr, ret); i = j + 1; } } if (len == ret.length) { break; } for (var i = 0; i < removed.length; i++) { for (var j = 0; j < points.length; j++) { if (points[j].id == removed[i].id) { points.splice(j, 1); break; } } } if (points.length < 4) { break; } } return ret; } function getTrisFromConvexPolygon(points, output) { if (points.length < 3) { return; } else if (points.length == 3) { var t = new Triangle(points[0], points[1], points[2]); t.circumcircle = circumcircle(points, 0, 1, 2); return output.push(t); } var i = 2; for (;i < points.length; i++) { var tri = new Triangle(points[0], points[1], points[i]); tri.circumcircle = circumcircle(points, 0, 1, i); var isValid = true; for (var j = 2; j < points.length; j++) { if (j == i) continue; var p = points[j]; if (tri.circumcircleContains(p)) { isValid = false; break; } } if (isValid) { output.push(tri); break; } } if (i == points.length-1) { points.splice(0, 1); getTrisFromConvexPolygon(points, output); } else if (i == 2) { points.splice(1, 1); getTrisFromConvexPolygon(points, output); } else { var item = points[i]; var arr = points.splice(1, i); var item0 = points.shift(); points.push(item0), points.unshift(item); getTrisFromConvexPolygon(arr, output); getTrisFromConvexPolygon(points, output); } } function findNextEdge(edges, e0, e1) { if (edges[0][0] != e0 && edges[0][0] != e1) return [edges[0][0], edges[0][1]]; if (edges[0][1] != e0 && edges[0][1] != e1) return [edges[0][1], edges[0][0]]; if (edges[1][0] != e0 && edges[1][0] != e1) return [edges[1][0], edges[1][1]]; if (edges[1][1] != e0 && edges[1][1] != e1) return [edges[1][1], edges[1][0]]; } function isClockwiseSquence(vertices) { var leftAngleSum = 0; var rightAngleSum = 0; for (var i = 0; i < vertices.length; i++) { var v2Index = getValidIndex(i + 1, vertices.length); var pIndex = getValidIndex(i + 2, vertices.length); var curSide = getPointOnVectorSide(vertices[i], vertices[v2Index], vertices[pIndex]); var angle = Math.PI - getAngle(vertices[i], vertices[v2Index], vertices[pIndex]); if (curSide == ON_LEFT_SIDE) { vertices[v2Index].mark = "left"; leftAngleSum += angle; } else if (curSide == ON_RIGHT_SIDE) { vertices[v2Index].mark = "right"; rightAngleSum += angle; } } //Math.abs(rightAngleSum - leftAngleSum)/2 equal with Math.PI if (rightAngleSum > leftAngleSum) { return true; } return false; } window.onload = function() { document.getElementById("canvas").onclick = function(e) { e = e ? e : window.event; var rect = this.getBoundingClientRect(); demo.clickAt(e.clientX - rect.left, e.clientY - rect.top); } document.getElementById("canvas").onmousemove = function(e) { e = e ? e : window.event; var rect = this.getBoundingClientRect(); demo.onMouseMove(e.clientX - rect.left, e.clientY - rect.top); } }; </script> </body></html>