2d:null 2e:["$","title",null,{"children":"Delaunay Triangulation | John C | Observable"}] 33:T1161,# Delaunay Triangulation One of the most used triangulation in computational geometry, also the base of 3D mesh, named after mathematician Boris Delaunay. By the mathematical definition, Delaunay Triangulation (DT) is the triangulation of a set of points (a triangulation means a way to connect a set of points into triangles) such that no point is inside the circumcircle of any triangle formed. Below we will implement an algorithm that do DT based on its math mathematical definition. This incremental approach is not the most efficient one, but it is very straightforward and easy to understand. Here is the basic step of the algorithm: 1. Create a large enough triangle that contains all the points 2. Add one point from the set into the triangulation, this point will divide the large triangle into three. 3. Add another point, check the existing triangles, if the new point is inside the circumcircle of it, erase the triangle, connect its vertices and the new point to form new triangles. repeat until all the points are added. This algorithm is known as the Bowyer–Watson algorithm. To implement this, one key function we need to write is a function to decide if a point is inside the circumcircle of a triangle or not. It is easy to check if a point is inside a circle by comparing the distance between it and the center of the circle to the radius of the circle, to make it more efficient, we compare the square of the radius to the square of the distance, like this: ```js function isInCircle(x,y,cx,cy,r){ let dx = x - cx, dy = y - cy; if (dx * dx + dy * dy < r * r) return true; return false; } ``` To get the circumcircle of a triangle from three vertices, we only need to locate the circumcenter, and the radius will be given by the distance of a vertex to the circumcenter. The circumcenter can be located by the following formula: ``` P(X, Y) = [(x1 * sin(2A) + x2 * sin(2B) + x3 * sin(2C)) / (sin(2A) + sin(2B) + sin(2C)), (y1 * sin(2A) + y2 * sin(2B) + y3 * sin(2C)) / (sin(2A) + sin(2B) + sin(2C))] ``` Where A(x1,y1), B(x2,y2), C(x3,y3) are the vertices and A, B, C are their respective angles. Replacing the angle with trigonometric formula we can get a function like this: ```js function circumcenter(x1, y1, x2, y2, x3, y3) { // (sin(2A) + sin(2B) + sin(2C)) let va = 2 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)); let x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; let y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; return [x, y]; } ``` Now let's put these functions into a triangle class for us to use in the DT. ```js class Triangle{ constructor(x1, y1, x2, y2, x3, y3){ this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; this.x3 = x3; this.y3 = y3; let c = this.circumcenter(x1, y1, x2, y2, x3, y3); this.cx = c[0]; this.cy = c[1]; this.crSq = (this.x1 - this.cx) * (this.x1 - this.cx) + (this.y1 - this.cy) * (this.y1 - this.cy); } circumcenter(x1, y1, x2, y2, x3, y3) { // (sin(2A) + sin(2B) + sin(2C)) let va = 2 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)); let x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; let y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; return [x, y]; } isInCircumcircle(x, y) { let dx = x - this.cx, dy = y - this.cy; if (dx * dx + dy * dy < this.crSq) return true; return false; } } ``` Another thing we need to do to the triangle in the steps is to divide them when a new point is added, we can put the function for that into the triangle class too. ```js divide(x, y){ let newTris = []; newTris.push(new Triangle(x, y, this.x1, this.y1, this.x2, this.y2)); newTris.push(new Triangle(x, y, this.x2, this.y2, this.x3, this.y3)); newTris.push(new Triangle(x, y, this.x1, this.y1, this.x3, this.y3)); return newTris; } ``` One last thing for the triangle class we would need is a simple function to check if a point is one of the vertex of the triangle, this will help deal with the super triangle we create in step 1 in the later steps. The final class looks like this (expand the cell to see the code):34:T5a6,class Triangle{ constructor(x1, y1, x2, y2, x3, y3){ this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; this.x3 = x3; this.y3 = y3; let c = this.circumcenter(x1, y1, x2, y2, x3, y3); this.cx = c[0]; this.cy = c[1]; this.crSq = (this.x1 - this.cx) * (this.x1 - this.cx) + (this.y1 - this.cy) * (this.y1 - this.cy); } circumcenter(x1, y1, x2, y2, x3, y3) { // (sin(2A) + sin(2B) + sin(2C)) let va = 2 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)); let x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; let y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)) / va; return [x, y]; } isInCircumcircle(x, y) { let dx = x - this.cx, dy = y - this.cy; if (dx * dx + dy * dy < this.crSq) return true; return false; } divide(x, y){ let newTris = []; newTris.push(new Triangle(x, y, this.x1, this.y1, this.x2, this.y2)); newTris.push(new Triangle(x, y, this.x2, this.y2, this.x3, this.y3)); newTris.push(new Triangle(x, y, this.x1, this.y1, this.x3, this.y3)); return newTris; } isVertex(x, y) { if (x === this.x1 && y === this.y1) return true; if (x === this.x2 && y === this.y2) return true; if (x === this.x3 && y === this.y3) return true; return false; } }35:Tc73,For step 1, we need to first create a large super triangle, it can be a bit tricky with a random set of points. But for our example, we know that the points we generate are inside a square, so we just need to create a triangle that contain the square. ```js let superTriangle = new Triangle(-10, 810, 810, -10, -10, -10); ``` For a input with unknownies, we would need to loop over the point to find them. We will have two arrays to store the triangles and all the points that have been added, and we initialise them with the super triangle: ```js let vertices = [-10, 810, 810, -10, -10, -10], triangles = [superTriangle]; ``` Then we loop over all the points to perform step 2 and step 3. For each of the points, we check it against all existing triangles. We create two arrays, one to store the newly created triangles by division (`newTriangles`), one to store the triangles that are going to next iteration (`nextTriangles`). ```js let newTriangles = [], nextTriangles = []; // check the new point against all existing triangles for(let ti = 0; ti < triangles.length; ti ++) { const currentTri = triangles[ti]; if (currentTri.isInCircumcircle(x, y)) { // new point inside the circumcircle of this triangle, this triangle need to be divided newTriangles = newTriangles.concat(currentTri.divide(x, y)); } else { // this triangle should be keep nextTriangles.push(currentTri); } } ``` After we got the new triangles, we check them against all the points that have been added. To do this we have a little helper function to decide if the triangle is bad and need to be removed: ```js function isBadTriangle = (x, y, tri) => { if (tri.isVertex(x,y)){ return false; } return tri.isInCircumcircle(x,y); } // perform a check on the newly formed triangles against exising point for (let ti = 0; ti < newTriangles.length; ti ++) { const currentTri = newTriangles[ti]; let badTriangle = false; for(let j = 0; j < vertices.length; j += 2){ const vx = vertices[j]; const vy = vertices[j + 1]; if (isBadTriangle(vx, vy, currentTri)) { badTriangle = true; break; } } if (!badTriangle) nextTriangles.push(currentTri); } ``` Then we add the point to `vertices` and use the `nextTriangles` as the `triangles` for next iteration. ```js vertices.push(x); vertices.push(y); triangles = nextTriangles; ``` After looping through all the points, we now have a Delaunay triangulation of the set. But remember, at the very beginning we created a huge super triangle and used it to initialise `vertices` and `triangles`, thus, the result also includes the three vertices of the super triangles that we want to get rid of. ```js //final process to delete the super triangle for (let i = 0; i < triangles.length; i++){ let t = triangles[i]; let shouldDelete = false; if (t.isVertex(superTriangle.x1, superTriangle.y1)) shouldDelete = true; if (t.isVertex(superTriangle.x2, superTriangle.y2)) shouldDelete = true; if (t.isVertex(superTriangle.x3, superTriangle.y3)) shouldDelete = true; if (shouldDelete){ triangles.splice(i, 1); i --; } } ``` Finally we have a function like this (expand the cell to see the code):36:T7b4,function dt(points) { const isBadTriangle = (x, y, tri) => { if (tri.isVertex(x,y)){ return false; } return tri.isInCircumcircle(x,y); } let superTriangle = new Triangle(-10, 810, 810, -10, -10, -10); let vertices = [-10, 810, 810, -10, -10, -10], triangles = [superTriangle]; for(let i = 0; i < points.length; i += 2) { let x = points[i], y = points[i + 1]; let newTriangles = [], nextTriangles = []; // check the new point against all existing triangles for(let ti = 0; ti < triangles.length; ti ++) { const currentTri = triangles[ti]; if (currentTri.isInCircumcircle(x, y)) { // new point inside the circumcircle of this triangle, this triangle need to be divided newTriangles = newTriangles.concat(currentTri.divide(x, y)); } else { // this triangle should be keep nextTriangles.push(currentTri); } } // perform a check on the newly formed triangles against exising point for (let ti = 0; ti < newTriangles.length; ti ++) { const currentTri = newTriangles[ti]; let badTriangle = false; for(let j = 0; j < vertices.length; j += 2){ const vx = vertices[j]; const vy = vertices[j + 1]; if (isBadTriangle(vx, vy, currentTri)) { badTriangle = true; break; } } if (!badTriangle) nextTriangles.push(currentTri); } vertices.push(x); vertices.push(y); triangles = nextTriangles; } //final process to delete the super triangle for (let i = 0; i < triangles.length; i++){ let t = triangles[i]; let shouldDelete = false; if (t.isVertex(superTriangle.x1, superTriangle.y1)) shouldDelete = true; if (t.isVertex(superTriangle.x2, superTriangle.y2)) shouldDelete = true; if (t.isVertex(superTriangle.x3, superTriangle.y3)) shouldDelete = true; if (shouldDelete){ triangles.splice(i, 1); i --; } } return triangles; }37:T1a4b,## Voronoi Diagram Voronoi diagram is another important tool for computational geometry, named after Georgy Feodosievych Voronoy. In mathematic, Voronoi diagram is a partition of plane into regions close to each of a given set of objects. In the simplest case, it divides a 2D plane into cells according to a set of point, every points within each cells are closest to the corresponding point in the set. And, in this simplest case, it is a dual diagram of the Delaunay triangulation of the set of points. Thus, we can easily translate the Delaunay Triangulation into Voronoi diagram and create some new visuals. To convert the triangles we have into Voronoi diagram, we need to perform the following steps: 1. Compute the perpendicular bisectors of the edges of the triangles; 2. Find the intersections of adjacent bisector from step 1; 3. Subset of the lines from step 1 with the intersection points from step 2. To complete the above steps, we will need a few functions. Firstly, a function to compute the perpendicular bisectors of the edges. It is actually very easy, in most cases, because we already get the circumcenters of the triangles. For any edge, its perpendicular bisector must go through the circumcenter. Further more, as you can observe from the Delaunay triangulation, most of the edges are shared by two triangles, which means the line going through the circumcenters of the two triangle is the perpendicular bisector of the shared edge. We can further find out the intersections in step 2 are exactly the circumcenters because all three perpendicular bisectors of the triangle must go through it. Thus, for those triangles that are surrounded by other triangles, we can compute the corresponding Voronoi edge easily: ```js // for each triangle tri let adjoinTriangles = []; let sharedEdges = []; let otherEdges = []; for(let i = 0; i < triangles.length; i ++) { if (i === id) continue; const currentTri = triangles[i]; let commonVertexCount = 0; let v1Count = 0, v2Count = 0, v3Count = 0; //check if the triangles share vertex if (currentTri.x1 === tri.x1 && currentTri.y1 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x1 && currentTri.y2 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x1 && currentTri.y3 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x1 === tri.x2 && currentTri.y1 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x2 && currentTri.y2 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x2 && currentTri.y3 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x1 === tri.x3 && currentTri.y1 === tri.y3) { v3Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x3 && currentTri.y2 === tri.y3) { v3Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x3 && currentTri.y3 === tri.y3) { v3Count ++; commonVertexCount ++; } if (commonVertexCount === 2) { adjoinTriangles.push(currentTri); let p1 = [tri.cx, tri.cy], p2 = [currentTri.cx, currentTri.cy]; if (!res.includes([p1, p2]) && !res.includes([p2, p1])) res.push([p1, p2]); if (v1Count === 0) { if (!sharedEdges.includes("23")) sharedEdges.push("23"); } else if (v2Count === 0) { if (!sharedEdges.includes("13")) sharedEdges.push("13"); } else if (v3Count === 0) { if (!sharedEdges.includes("12")) sharedEdges.push("12"); } } } ``` For those triangles that lie on the outside of the Delaunay triangulation, there are 1 or 2 edges that are not shared with any other triangles, for those we can connect the center of the edge and the circumcenter of the triangle to find the perpendicular bisector. In those cases the subset of the bisectors are actually a ray that go out to infinity from the circumcenter(we can use line clipping to clip it to a window, this topic is cover in [this post](../@real-john-cheung/line-clipping)). We can use the simple code below to compute the perpendicular bisector for those edges: ```js // triangles that are not surrounded by other triangles if (sharedEdges.length < 3){ if (!sharedEdges.includes("23")) otherEdges.push("23"); if (!sharedEdges.includes("13")) otherEdges.push("13"); if (!sharedEdges.includes("12")) otherEdges.push("12"); } // deal with the edge that are not shared otherEdges.forEach(e => { let x0, y0, x1, y1; if (e === "23") { x0 = tri.x2, y0 = tri.y2, x1 = tri.x3, y0 = tri.y3; } else if (e === "13") { x0 = tri.x1, y0 = tri.y1, x1 = tri.x3, y0 = tri.y3; } else if (e === "12") { x0 = tri.x1, y0 = tri.y1, x1 = tri.x2, y0 = tri.y2; } let mid = [x0 + x1 / 2, y0 + y1 / 2]; let start = [tri.cx, tri.cy]; // ray from circumcenter to the middle point of the edge let d = [start[0] - mid[0], start[1] - mid[1]]; // the lines here are rays actually, we just make it long enough to draw instead of clipping it here to make it simpler d[0] *= 10; d[1] *= 10; let end = [start[0] - d[0], start[1] - d[1]]; if (!res.includes([start, end]) && !res.includes([end, start])) res.push([start, end]); }); ``` There is one small problem in the above code: sometimes, the circumcenter can fall outside the triangle, if the edge happens to be the longest of the triangle, it makes the ray go alone the opposite direction from circumcenter to the middle point of the edge. Thus we need to check if this is the case. So we need a helper function to check if the circumcenter is inside the triangle: ```js function pointInTriangle(x, y, tri) { let dx = x - tri.x1, dy = y - tri.y1; let side12 = (tri.x2 - tri.x1) * dy > (tri.y2 - tri.y1) * dx; // side13 === side12? if ((tri.x3 - tri.x1) * dy > (tri.y3 - tri.y1) * dx === side12) return false; // side23 if ((tri.x3 - tri.x2) * (y - tri.y2) > (tri.y3 - tri.y2)*(x - tri.x2) !== side12) return false; return true; } ``` The idea of this helper function is simple: if a point is on the same side of two of the edges AB and AC of a triangle, it must be outside the triangle; otherwise if it is to the same side of AB as BC (and also CA), it is inside the triangle. With this method we can check if a point is inside the triangle with only multiplication and addition operations. The refined code looks like this: ```js let d; // special case when the edge is the longest and the circumcenter is outside the triangle if (!pointInTriangle(start[0], start[1], tri) && isLongest(e, tri)) { d = [mid[0] - start[0], mid[1] - start[1]]; } else { d = [start[0] - mid[0], start[1] - mid[1]]; } ``` You can check the complete function below (expand the cell to see the code): 38:T12ce,function voronoiFromDelaunay(triangles){ const pointInTriangle = (x, y, tri) => { let dx = x - tri.x1, dy = y - tri.y1; let side12 = (tri.x2 - tri.x1) * dy > (tri.y2 - tri.y1) * dx; // side13 === side12? if ((tri.x3 - tri.x1) * dy > (tri.y3 - tri.y1) * dx === side12) return false; // side23 if ((tri.x3 - tri.x2) * (y - tri.y2) > (tri.y3 - tri.y2)*(x - tri.x2) !== side12) return false; return true; } const cross = (a, b) =>{ return a[0] * b[1] - a[1] * b[0]; } const isLongest = (e, tri) =>{ if (e === "12") { let dxA = tri.x1 - tri.x2, dyA = tri.y1 - tri.y2, dxB = tri.x1 - tri.x3, dyB = tri.y1 - tri.y3, dxC = tri.x3 - tri.x2, dyC = tri.y3 - tri.y2; return (dxA*dxA+dyA*dyA >= dxB*dxB+dyB*dyB && dxA*dxA+dyA*dyA > dxC*dxC+dyC*dyC); } else if (e === "23") { let dxA = tri.x2 - tri.x3, dyA = tri.y2 - tri.y3, dxB = tri.x1 - tri.x3, dyB = tri.y1 - tri.y3, dxC = tri.x1 - tri.x2, dyC = tri.y1 - tri.y2; return (dxA*dxA+dyA*dyA >= dxB*dxB+dyB*dyB && dxA*dxA+dyA*dyA > dxC*dxC+dyC*dyC); } else if (e === "13") { let dxA = tri.x1 - tri.x3, dyA = tri.y1 - tri.y3, dxB = tri.x2 - tri.x3, dyB = tri.y2 - tri.y3, dxC = tri.x1 - tri.x2, dyC = tri.y1 - tri.y2; return (dxA*dxA+dyA*dyA >= dxB*dxB+dyB*dyB && dxA*dxA+dyA*dyA > dxC*dxC+dyC*dyC); } throw Error(); } let res = []; triangles.forEach((tri, id) => { let adjoinTriangles = []; let sharedEdges = []; let otherEdges = []; for(let i = 0; i < triangles.length; i ++) { if (i === id) continue; const currentTri = triangles[i]; let commonVertexCount = 0; let v1Count = 0, v2Count = 0, v3Count = 0; //check if the triangles share vertex if (currentTri.x1 === tri.x1 && currentTri.y1 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x1 && currentTri.y2 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x1 && currentTri.y3 === tri.y1) { v1Count ++; commonVertexCount ++; } if (currentTri.x1 === tri.x2 && currentTri.y1 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x2 && currentTri.y2 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x2 && currentTri.y3 === tri.y2) { v2Count ++; commonVertexCount ++; } if (currentTri.x1 === tri.x3 && currentTri.y1 === tri.y3) { v3Count ++; commonVertexCount ++; } if (currentTri.x2 === tri.x3 && currentTri.y2 === tri.y3) { v3Count ++; commonVertexCount ++; } if (currentTri.x3 === tri.x3 && currentTri.y3 === tri.y3) { v3Count ++; commonVertexCount ++; } if (commonVertexCount === 2) { adjoinTriangles.push(currentTri); let p1 = [tri.cx, tri.cy], p2 = [currentTri.cx, currentTri.cy]; if (!res.includes([p1, p2]) && !res.includes([p2, p1])) res.push([p1, p2]); if (v1Count === 0) { if (!sharedEdges.includes("23")) sharedEdges.push("23"); } else if (v2Count === 0) { if (!sharedEdges.includes("13")) sharedEdges.push("13"); } else if (v3Count === 0) { if (!sharedEdges.includes("12")) sharedEdges.push("12"); } } } // triangles that are not surrounded by other triangles if (sharedEdges.length < 3){ if (!sharedEdges.includes("23")) otherEdges.push("23"); if (!sharedEdges.includes("13")) otherEdges.push("13"); if (!sharedEdges.includes("12")) otherEdges.push("12"); } // deal with the edge that are not shared otherEdges.forEach(e => { let x0, y0, x1, y1; if (e === "23") { x0 = tri.x2, y0 = tri.y2, x1 = tri.x3, y0 = tri.y3; } else if (e === "13") { x0 = tri.x1, y0 = tri.y1, x1 = tri.x3, y0 = tri.y3; } else if (e === "12") { x0 = tri.x1, y0 = tri.y1, x1 = tri.x2, y0 = tri.y2; } let mid = [x0 + x1 / 2, y0 + y1 / 2]; let start = [tri.cx, tri.cy]; let d; // special case when the edge is the longest and the circumcenter is outside the triangle if (!pointInTriangle(start[0], start[1], tri) && isLongest(e, tri)) { d = [mid[0] - start[0], mid[1] - start[1]]; } else { d = [start[0] - mid[0], start[1] - mid[1]]; } // the lines here are rays actually, we just make it long enough to draw d[0] *= 10; d[1] *= 10; let end = [start[0] - d[0], start[1] - d[1]]; if (!res.includes([start, end]) && !res.includes([end, start])) res.push([start, end]); }); }); return res; }39:T6c8,p5(s => { s.setup = function () { s.createCanvas(400,400); s.background(255); s.stroke(0); s.noFill(); s.strokeWeight(5); for (let i = 0; i < points.length; i += 2) { s.point(points[i], points[i+1]); } s.strokeWeight(1); s.stroke("red"); let ps = delaunayD3.points, halfedges = delaunayD3.halfedges, triangles = delaunayD3.triangles; let hull = delaunayD3.hull; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = triangles[i]; const tj = triangles[j]; s.line(ps[ti * 2], ps[ti * 2 + 1], ps[tj * 2], ps[tj * 2 + 1]); } for (let i = 1; i < hull.length; ++i) { s.line(ps[hull[i-1] * 2], ps[hull[i-1] * 2 + 1], ps[hull[i] * 2], ps[hull[i] * 2 + 1]); } s.stroke("blue"); let voi = voronoiD3; let inedges = delaunayD3.inedges; let circumcenters = voronoiD3.circumcenters, vectors = voronoiD3.vectors; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = Math.floor(i / 3) * 2; const tj = Math.floor(j / 3) * 2; const xi = circumcenters[ti]; const yi = circumcenters[ti + 1]; const xj = circumcenters[tj]; const yj = circumcenters[tj + 1]; s.line(xi, yi, xj, yj); } let h0, h1 = hull[hull.length - 1]; for (let i = 0; i < hull.length; ++i) { h0 = h1, h1 = hull[i]; const t = Math.floor(inedges[h1] / 3) * 2; const x = circumcenters[t]; const y = circumcenters[t + 1]; const v = h0 * 4; const p = voronoiD3._project(x, y, vectors[v + 2], vectors[v + 3]); if (p) s.line(x, y, p[0], p[1]); } } })3a:[] 31:{"id":"83fc04ee322b25a8","slug":"delaunay","title":"Delaunay Triangulation","thumbnail":"add73de20f2b42ca88fa22e9f0018f5e73376c226752e18ae9b2428d9eebe750","access_level":"public","create_time":"$D2024-03-05T09:47:16.888Z","update_time":"$D2024-03-05T15:55:41.259Z","view_time":null,"first_public_time":"$D2024-03-05T09:48:53.691Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024"},"version":153,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null}],"members":[{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024","role":"editor"},{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"8a91769c6d3b75ab","slug":"algorithms","title":"Algorithms","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"title":"Delaunay Triangulation","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"Now we can start, first, let's generate some random points.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":37,"value":"points = {\n let res = [];\n for (let i = 0; i < 50; i ++) {\n res.push(Math.random() * 400); // x\n res.push(Math.random() * 400); // y\n }\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":46,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"And let's test it out:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":93,"value":"dtTriangles = dt(points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"p5(s => {\n s.setup = function () {\n s.createCanvas(400,400);\n s.background(255);\n s.stroke(0);\n s.noFill();\n s.strokeWeight(5);\n for (let i = 0; i < points.length; i += 2) {\n s.point(points[i], points[i+1]);\n }\n s.strokeWeight(1);\n let triangles = dtTriangles;\n triangles.forEach(tri => {\n s.line(tri.x1, tri.y1, tri.x2, tri.y2);\n s.line(tri.x1, tri.y1, tri.x3, tri.y3);\n s.line(tri.x3, tri.y3, tri.x2, tri.y2);\n });\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"$37","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":98,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"Let's put it into test...","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":104,"value":"voronoi = voronoiFromDelaunay(dtTriangles);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"p5(s => {\n s.setup = function () {\n s.createCanvas(400,400);\n s.background(255);\n s.stroke(0);\n s.noFill();\n s.strokeWeight(5);\n for (let i = 0; i < points.length; i += 2) {\n s.point(points[i], points[i+1]);\n }\n s.strokeWeight(1);\n s.stroke(\"red\");\n let triangles = dtTriangles;\n triangles.forEach(tri => {\n s.line(tri.x1, tri.y1, tri.x2, tri.y2);\n s.line(tri.x1, tri.y1, tri.x3, tri.y3);\n s.line(tri.x3, tri.y3, tri.x2, tri.y2);\n });\n s.stroke(\"blue\");\n let voi = voronoi;\n voi.forEach(vo => {\n s.line(vo[0][0], vo[0][1], vo[1][0], vo[1][1]);\n });\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"## d3.Delaunay\n\nAs mentioned, the above described algorithms are straightforward, but not the fastest. There are many library for computing Delaunay triangulation and Voronoi diagram available. [d3.Delaunay](https://d3js.org/d3-delaunay) is one of them. d3.Delaunay implement a very fast sweep algorithm for Delaunay triangulation, below is an example of how you can use this library to get the same result as above, but much faster.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":135,"value":"Delaunay = d3.Delaunay","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"delaunayD3 = new Delaunay(points)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"voronoiD3 = delaunayD3.voronoi([0,0,400,400])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"$39","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"import {p5} from \"@real-john-cheung/p5js\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 32:"$31:body"