29:null 2a:["$","title",null,{"children":"Delaunay triangulation : hand-made | Pierre Ripoll | Observable"}] 2f:T44e,{ await visibility(); const ctx = DOM.context2d(width, height); yield ctx.canvas; function render() { ctx.clearRect(0, 0, width, height); drawPoints(ctx, example_points, 5); drawTriangle(ctx, example_points); ctx.save(); ctx.strokeStyle = "red"; ctx.fillStyle = "red"; let bisections = getBisections(example_points); let { center, radius } = getCircumcircle(bisections); let bisectionLength = 2.3 * getMinimalLengthBisections(bisections.map(b => b.vertex), center); drawBisections(ctx, bisections, bisectionLength); ctx.beginPath(); ctx.fillStyle = `rgb(255,0,0,0.03)`; ctx.arc(center.x, center.y, radius, 0, 2 * Math.PI); ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.beginPath(); ctx.fillStyle = `black`; ctx.arc(center.x, center.y, 5, 0, 2 * Math.PI); ctx.fill(); ctx.restore(); } render(); // Bind the drag behavior for interaction. d3.select(ctx.canvas).call( drag( example_points, render, () => (mutable example_points = mutable example_points) ) ); }30:T44e,{ await visibility(); const ctx = DOM.context2d(width, height); yield ctx.canvas; function render() { ctx.clearRect(0, 0, width, height); drawPoints(ctx, example_points, 5); drawTriangle(ctx, example_points); ctx.save(); ctx.strokeStyle = "red"; ctx.fillStyle = "red"; let bisections = getBisections(example_points); let { center, radius } = getCircumcircle(bisections); let bisectionLength = 2.3 * getMinimalLengthBisections(bisections.map(b => b.vertex), center); drawBisections(ctx, bisections, bisectionLength); ctx.beginPath(); ctx.fillStyle = `rgb(255,0,0,0.03)`; ctx.arc(center.x, center.y, radius, 0, 2 * Math.PI); ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.beginPath(); ctx.fillStyle = `black`; ctx.arc(center.x, center.y, 5, 0, 2 * Math.PI); ctx.fill(); ctx.restore(); } render(); // Bind the drag behavior for interaction. d3.select(ctx.canvas).call( drag( example_points, render, () => (mutable example_points = mutable example_points) ) ); }31:T522,{ await visibility(); const ctx = DOM.context2d(width, height); yield ctx.canvas; function render() { let sample_points = points.slice(0, 5); let bisections = getBisections(example_points); let { center, radius } = getCircumcircle(bisections); let bisectionLength = 2.3 * getMinimalLengthBisections(bisections.map(b => b.vertex), center); let point_included = sample_points.find( pt => distance(center, pt) < radius ); ctx.clearRect(0, 0, width, height); drawPoints(ctx, sample_points, 4); drawPoints(ctx, example_points, 5); if (!point_included) drawTriangle(ctx, example_points); ctx.strokeStyle = `${point_included ? "red" : "blue"}`; ctx.fillStyle = `${point_included ? "red" : "blue"}`; ctx.beginPath(); ctx.fillStyle = `rgb(${point_included ? "255,0,0" : "0,0,255"},0.03)`; ctx.arc(center.x, center.y, radius, 0, 2 * Math.PI); ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.beginPath(); ctx.fillStyle = `black`; // ctx.arc(center.x, center.y, 5, 0, 2 * Math.PI); ctx.fill(); } render(); // Bind the drag behavior for interaction. d3.select(ctx.canvas).call( drag( example_points, render, () => (mutable example_points = mutable example_points) ) ); }32:Tb05,{ replay; await visibility(); const ctx = DOM.context2d(width, height); yield ctx.canvas; mutable random_points = createPoints(200, height, width, 50).sort( (a, b) => a.x - b.x + (a.y - b.y) ); const pts = mutable random_points; var edges = []; var circles = []; var bisections = []; var tested_circle = { center: { x: 0, y: 0 }, radius: 0 }; var pts_included = []; var coor = []; var trxPt = []; var delaunay = d3.Delaunay.from( pts, (p) => p.x, (p) => p.y ); function draw() { let incorrectTriangulation = pts_included.length !== 0; ctx.clearRect(0, 0, width, height); ctx.strokeStyle = `black`; drawEdges(ctx, edges); drawPoints(ctx, pts, 2); drawPoints(ctx, trxPt, 6, "green"); if (incorrectTriangulation) drawPoints(ctx, pts_included, 3, "red"); ctx.beginPath(); ctx.strokeStyle = "rgb(0,0,255,0.1)"; circles.forEach((c) => drawCircle(ctx, c.center, c.radius)); ctx.closePath(); ctx.stroke(); ctx.beginPath(); ctx.strokeStyle = `${incorrectTriangulation ? "red" : "blue"}`; ctx.fillStyle = `rgb(${ incorrectTriangulation ? "255,0,0" : "0,0,255" },0.03)`; if (tested_circle && tested_circle.center) drawCircle(ctx, tested_circle.center, tested_circle.radius); ctx.closePath(); ctx.fill(); ctx.stroke(); ctx.fillStyle = `black`; pts_included = []; trxPt = []; tested_circle = { center: null, radius: null }; return ctx.canvas; } for (let i = 0; i < pts.length - 2; i++) { for (let u = i + 1; u < pts.length - 1; u++) { for (let v = u + 1; v < pts.length; v++) { trxPt = [pts[i], pts[u], pts[v]]; // var bisec = getBisections(trxPt); // var { center, radius } = getCircumcircle(bisec, trxPt); var { center, radius } = getCircumcircle2(trxPt); if (center === null) break; coor = coor.concat([center.x, center.y, radius]); tested_circle.center = center; tested_circle.radius = radius; // bisections = bisec; pts_included = pts .slice() .filter( (vt) => distance(vt, center) < radius && trxPt.findIndex((p) => p.x === vt.x && p.y === vt.y) === -1 ); if (pts_included.length === 0) { circles.push({ center, radius }); edges = edges.concat([ [trxPt[0], trxPt[1]], [trxPt[1], trxPt[2]], [trxPt[2], trxPt[0]] ]); } if (mutable delay >= 100) yield Promises.delay(mutable delay, draw()); } if (mutable delay < 100 && mutable delay > 0) yield Promises.delay(mutable delay, draw()); else yield draw(); } if (mutable delay === 0) yield draw(); } yield draw(); }33:T6db,// adapted from https://observablehq.com/@d3/hello-d3-drag dragTriangle = (triangle, draw, end) => { // When starting a drag gesture, move the subject to the top and mark it as active. function dragstarted() { d3.select(this).style("cursor", "grabbing"); } // When dragging, update the subject’s position. async function dragged() { const agent = d3.event.subject; let dx = triangle.circumcenter.x - Math.max(0, Math.min(width, d3.event.x)), dy = triangle.circumcenter.y - Math.max(0, Math.min(height, d3.event.y)); triangle.vertices.forEach(vt => { (vt.x += dx), (vt.y += dy); }); await draw(); } // When ending a drag gesture, mark the subject as inactive again. function dragended() { d3.event.subject.active = false; d3.select(this).style("cursor", "grab"); if (end) end(); draw(); } function dragsubject(event) { const radius = radius_interaction; if (!event) event = d3.event; let subject = null; let maxDistance = radius * 1.5; let d = Math.hypot( event.x - triangle.circumcenter.x, event.y - triangle.circumcenter.y ); console.log(d, maxDistance); if (d < maxDistance) { maxDistance = d; subject = triangle.circumcenter; } return subject; } return function(sel) { sel .style("cursor", "pointer") .call( d3 .drag() .subject(dragsubject) .on("start", dragstarted) .on("drag", dragged) .on("end", dragended) ) .on("mousemove", function() { const m = d3.mouse(this), subject = dragsubject({ x: m[0], y: m[1] }); d3.select(this).style("cursor", subject ? "grab" : "pointer"); }); }; }34:T60e,// adapted from https://observablehq.com/@d3/hello-d3-drag drag = (agents, draw, end) => { // When starting a drag gesture, move the subject to the top and mark it as active. function dragstarted() { d3.select(this).style("cursor", "grabbing"); } // When dragging, update the subject’s position. async function dragged() { const agent = d3.event.subject; agent.x = Math.max(0, Math.min(width, d3.event.x)); agent.y = Math.max(0, Math.min(height, d3.event.y)); await draw(); } // When ending a drag gesture, mark the subject as inactive again. function dragended() { d3.event.subject.active = false; d3.select(this).style("cursor", "grab"); if (end) end(); draw(); } function dragsubject(event) { const radius = radius_interaction; if (!event) event = d3.event; let subject = null; let maxDistance = radius * 1.5; for (const c of agents) { let d = Math.hypot(event.x - c.x, event.y - c.y); if (d < maxDistance) { maxDistance = d; subject = c; } } return subject; } return function(sel) { sel .style("cursor", "pointer") .call( d3 .drag() .subject(dragsubject) .on("start", dragstarted) .on("drag", dragged) .on("end", dragended) ) .on("mousemove", function() { const m = d3.mouse(this), subject = dragsubject({ x: m[0], y: m[1] }); d3.select(this).style("cursor", subject ? "grab" : "pointer"); }); }; }35:[] 2d:{"id":"21749c5c98038319","slug":"delaunay-triangulation-hand-made","title":"Delaunay triangulation : hand-made","thumbnail":"5d4ea2aa8223dd297156e66277b51f069375049a5fd55473b1eeb4a81d22b54f","access_level":"public","create_time":"$D2020-02-20T14:28:31.592Z","update_time":"$D2022-06-01T01:04:01.400Z","view_time":null,"first_public_time":"$D2020-02-24T15:33:32.528Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"4b6918df760e73ca","login":"pierreleripoll","name":"Pierre Ripoll","avatar_url":"https://avatars-next.observableusercontent.com/a228ad56cf675f22f000d821fcc5eff96cb60bbff4135f603575a1ceaad2712a","tier":"starter_2024"},"version":937,"publish_version":937,"role":null,"authored":false,"authors":[{"type":"individual","id":"5aed0c8feb597b86","login":"pierreleripoll","name":"Pierre Ripoll","avatar_url":"https://avatars-next.observableusercontent.com/a228ad56cf675f22f000d821fcc5eff96cb60bbff4135f603575a1ceaad2712a","tier":null}],"members":[{"type":"individual","id":"5aed0c8feb597b86","login":"pierreleripoll","name":"Pierre Ripoll","avatar_url":"https://avatars-next.observableusercontent.com/a228ad56cf675f22f000d821fcc5eff96cb60bbff4135f603575a1ceaad2712a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"97c9a11f8bdff74a","slug":"epfl-3-juin","title":"EPFL 3 JUIN","owner":{"id":"4b6918df760e73ca","login":"pierreleripoll","name":"Pierre Ripoll"}},"type":"notebook","body":{"title":"Delaunay triangulation : hand-made","cells":[{"id":0,"value":"md`# Delaunay triangulation : hand-made`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"md`Delaunay triangulation starts by finding circumcircle of triangle ! [This will be my guide.](https://thesoftwaresimpleton.com/blog/2015/10/31/perpendicular)\n\\nSo that's our points:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"{\n await visibility();\n const ctx = DOM.context2d(width, height);\n yield ctx.canvas;\n\n function render() {\n ctx.clearRect(0, 0, width, height);\n drawPoints(ctx, example_points, 30);\n }\n\n render();\n\n // Bind the drag behavior for interaction.\n d3.select(ctx.canvas).call(\n drag(\n example_points,\n render,\n () => (mutable example_points = mutable example_points)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md` We would like to calculate the circumference of the triangle ! `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"{\n await visibility();\n const ctx = DOM.context2d(width, height);\n yield ctx.canvas;\n\n function render() {\n ctx.clearRect(0, 0, width, height);\n drawPoints(ctx, example_points, 10);\n\n drawTriangle(ctx, example_points);\n }\n\n render();\n\n // Bind the drag behavior for interaction.\n d3.select(ctx.canvas).call(\n drag(\n example_points,\n render,\n () => (mutable example_points = mutable example_points)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"md`To do so, first we draw bisections of each edge, the crossing point will be the center of our circumcircle.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"{\n await visibility();\n const ctx = DOM.context2d(width, height);\n yield ctx.canvas;\n\n function render() {\n ctx.clearRect(0, 0, width, height);\n drawPoints(ctx, example_points, 5);\n\n drawTriangle(ctx, example_points);\n\n ctx.save();\n ctx.strokeStyle = \"red\";\n ctx.fillStyle = \"red\";\n\n for (let i = 0; i < example_points.length; i++) {\n let { vertex, slope } = perpendicularBisector(\n example_points[i % example_points.length],\n example_points[(i + 1) % example_points.length]\n );\n let dx = getDx(slope, 500) / 2;\n let dy = slope * dx;\n drawPoints(ctx, [vertex], 3);\n ctx.beginPath();\n ctx.moveTo(vertex.x + dx, vertex.y + dy);\n ctx.lineTo(vertex.x - dx, vertex.y - dy);\n ctx.stroke();\n }\n ctx.restore();\n }\n\n render();\n\n // Bind the drag behavior for interaction.\n d3.select(ctx.canvas).call(\n drag(\n example_points,\n render,\n () => (mutable example_points = mutable example_points)\n )\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"md` Now all we need to do is to draw the circle with this center that connect all edges !`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"md`If a graph point is inside the circle then the triangle will not be shown !`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"md`Now let's watch an animation of the process on multiple random points (it will lead to the starting point of [Mike Bostock excellent notebook](https://observablehq.com/@mbostock/the-delaunays-dual)).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":504,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"viewof replay = html`