Я недавно закончил реализацию алгоритма Бойера-Ватсона для вычисления триангуляции Делоне на плоскости в Javascript. В статье Википедии (https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) говорится, что это от O (n log n) до O (n ^ 2) в особенно вырожденных случаях. Почему моя реализация всегда делает это больше, чем O (n ^ 2)? в моей реализации или в самом алгоритме? я запускаю функцию после события onclick и в Google Chrome, если это помогает.
Я заметил это при проверке того, сколько времени понадобилось для расчета по разным количествам узлов. Это займет около 4 мс для 100 узлов, затем 150 мс для 1000 узлов, а затем до 60 000 мс для 10 000 узлов. Еще одна любопытная вещь - первые два запуска функции после обновления вкладки всегда занимают больше всего времени. Для 100 узлов, например, 30 мс -> 16 мс -> 4 мс -> 4 мс -> ...
А вот и соответствующий код. Если вы не можете прочитать чужой неаккуратный код (я бы вас не осудил), перейдите к статье в Википедии выше и посмотрите, сможете ли вы найти проблему в псевдокоде. Я очень внимательно следил за этим, поэтому любые проблемы, которые вы можете найти в моей программе, могут быть связаны с тем, как построен этот алгоритм. Удачи и заранее спасибо.
// This is the function where the problem lies
function get_delaunay_triangulation(nodeList){
var triangulation = []; // The list of triangles the function will output
var badTriangles = []; // List of triangles no longer valid due to the insertion
var nextNode; // Node inserted in each iteration
var polygonHole = [];
// The supertriangle has to contain all other nodes inside it
/* Node is a class defined by its coords, and are accessed with node.x and node.y */
var sTVertex1 = new Node(0, 0);
// c.width and c.height are just the width and height of the screen
var sTVertex2 = new Node(2 * c.width + 1, 0);
var sTVertex3 = new Node(0, 2 * c.height + 1);
/* Edge is a class defined by its vertices, and are accessed with
edge.vertex1 and edge.vertex2 */
var sTEdge1 = new Edge(sTVertex1, sTVertex2);
var sTEdge2 = new Edge(sTVertex2, sTVertex3);
var sTEdge3 = new Edge(sTVertex3, sTVertex1);
/* Triangle is a class defined by its edges which you can access with triangle.edges,
but you can also access its vertices with triangle.vertices */
var superTriangle = new Triangle([sTEdge1, sTEdge2, sTEdge3]);
triangulation.push(superTriangle);
for (var i = 0; i < nodeList.length; i++){
nextNode = nodeList[i]; // The next point to be inserted
badTriangles = []; // Resets badTriangles for every new point
/* This loops through every triangle in the triangulation added so far. This
might be the cause of the slowdown, but I don't see why it would do that, and
why the wikipedia article wouldn't say anything about that. */
for (var j = 0; j < triangulation.length; j++){
var maybeBadTriangle = triangulation[j];
var verticesInST = maybeBadTriangle.get_vertices_in(
superTriangle.vertices);
/* This checks every triangle in triangulation and adds the ones that
are no longer valid due to the insertion. This part works well and is not
likely to be the cause of the slowdown. */
if (verticesInST.length == 0){
if (maybeBadTriangle.circumcircle_contains(nextNode)){
badTriangles.push(maybeBadTriangle);
}
} else if (verticesInST.length == 1) {
var otherVertices = [...maybeBadTriangle.vertices];
otherVertices.splice(
otherVertices.indexOf(verticesInST[0]), 1);
var tempEdge = new Edge(otherVertices[0], otherVertices[1]);
if (verticesInST[0].isRightOfEdge(tempEdge) ==
nextNode.isRightOfEdge(tempEdge)){
badTriangles.push(maybeBadTriangle);
}
} else if (verticesInST.length == 2) {
var otherVertices = [...maybeBadTriangle.vertices];
var otherVertex;
for (var k = 0; k < 3; k++){
if (!superTriangle.vertices.includes(otherVertices[k])){
otherVertex = otherVertices[k];
break;
}
}
var tempEdge = new Edge(otherVertex, new Node(
otherVertex.x + verticesInST[1].x - verticesInST[0].x,
otherVertex.y + verticesInST[1].y - verticesInST[0].y)
);
if (nextNode.isRightOfEdge(tempEdge) ==
verticesInST[0].isRightOfEdge(tempEdge)){
badTriangles.push(maybeBadTriangle);
}
} else {
badTriangles.push(maybeBadTriangle);
}
}
/* This part gathers the edges in badTriangles that are not shared by any other
triangle in badTriangles, so that polygonHole will contain the boundary of
the hole left behind when the bad triangles are removed. */
polygonHole = [];
for (var j = 0; j < badTriangles.length; j++){
// Kollar varje kant i triangeln
for (var k = 0; k < 3; k++){
var testEdge = badTriangles[j].edges[k];
var testEdgeIsUnique = true;
for (var l = 0; l < badTriangles.length; l++){
for (var m = 0; m < 3; m++){
if (testEdge.is_equal_to(badTriangles[l].edges[m]) &&
l != j){
testEdgeIsUnique = false;
break;
}
}
if (!testEdgeIsUnique){ break; }
}
if (testEdgeIsUnique){
polygonHole.push(testEdge);
}
}
}
// Removes the triangles in badTriangles from triangulation
for (var j = 0; j < badTriangles.length; j++){
var index = triangulation.indexOf(badTriangles[j]);
if (index != -1){
triangulation.splice(index, 1);
}
}
// Makes a new triangle from every edge of polygonHole to nextNode
var polygonEdge;
for (var j = 0; j < polygonHole.length; j++){
polygonEdge = polygonHole[j];
triangulation.push(
new Triangle([
polygonEdge,
new Edge(polygonEdge.vertex1, nextNode),
new Edge(polygonEdge.vertex2, nextNode)
])
);
}
}
/* When every point is inserted, the triangles which have a vertex in the original
superTriangle are removed from triangulation */
var i = 0;
while (i < triangulation.length){
testVertices = triangulation[i].vertices;
if (testVertices.includes(sTVertex1) ||
testVertices.includes(sTVertex2) ||
testVertices.includes(sTVertex3)){
triangulation.splice(i, 1);
} else {
i++;
}
}
return new Triangle_Mesh(triangulation);
}