2a:null 2b:["$","title",null,{"children":"Voronoi Incircles | Kostya | Observable"}] 30:T79c,canvas = { const context = DOM.context2d(width, height); const margin = 60; const particles = Array.from({length: n}, () => [Math.random() * width, Math.random() * height, 2 * (Math.random() - 0.5), 2*(Math.random() - 0.5)]); const voronoi = d3.voronoi().extent([[0.5, 0.5], [width - 0.5, height - 0.5]]); const color = d3.scaleOrdinal(d3.schemeCategory10); while (true) { const cells = voronoi.polygons(particles); context.clearRect(0, 0, width, height); let circles = cells.map(polygonIncircle); circles.forEach((circle,i) => { const radius = circle[2] - 2.5; if (radius < 0) return; context.beginPath(); context.moveTo(circle[0] + radius, circle[1]); context.arc(circle[0], circle[1], radius, 0, 2 * Math.PI); context.fillStyle = color(i); context.fill(); }); context.beginPath(); cells.forEach(cell => { context.moveTo(cell[0][0], cell[0][1]); for (let i = 1, n = cell.length; i < n; ++i) context.lineTo(cell[i][0], cell[i][1]); context.closePath(); }); context.lineWidth = 1; context.strokeStyle = "#ccc"; context.stroke(); context.beginPath(); particles.forEach(point => { context.moveTo(point[0] + 1.5, point[1]); context.arc(point[0], point[1], 1.5, 0, 2 * Math.PI); }); context.fillStyle = "#000"; context.fill(); yield context.canvas; particles.forEach( (p,i) => { p[0] += p[2]; p[1] += p[3]; if (p[0] < -margin) p[2] = -p[2]; else if (p[0] > width + margin) p[2] = -p[2]; if (p[1] < -margin) p[3] = -p[3]; else if (p[1] > height + margin) p[3] = -p[3]; if (circles[i]){ p[2] += 0.001 * (circles[i][0] - p[0]); p[3] += 0.001 * (circles[i][1] - p[1]); p[3] += 0.001 * Math.random(); p[2] *= 0.999; p[3] *= 0.999; } }); } }31:[] 2e:{"id":"c4aa41895c27dcec","slug":"voronoi-incircles","title":"Voronoi Incircles","thumbnail":"842a69efd9f19a3f5e80d3538ee598605eb33ca8fb675872acbe4fbead9898c7","access_level":"public","create_time":"$D2018-05-23T10:35:22.756Z","update_time":"$D2018-05-23T14:29:20.021Z","view_time":null,"first_public_time":"$D2018-05-23T10:53:15.874Z","fork":{"id":"ba0d23af0509620f","slug":"voronoi-incircles","title":"Voronoi Incircles","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"stars":5,"starred":false,"owner":{"type":"team","id":"10a5086176af0bb0","login":"kkostya","name":"Kostya","avatar_url":"https://avatars-next.observableusercontent.com/f5ff1dfc1cbdafecf8fe126943ef46f7ea62e6d006f5ac9145e91cddb991c06e","tier":"starter_2024"},"version":246,"publish_version":246,"role":null,"authored":false,"authors":[{"type":"individual","id":"f6b1157e2a82619b","login":"kkostya","name":"Kostya","avatar_url":"https://avatars-next.observableusercontent.com/f5ff1dfc1cbdafecf8fe126943ef46f7ea62e6d006f5ac9145e91cddb991c06e","tier":null}],"members":[{"type":"individual","id":"f6b1157e2a82619b","login":"kkostya","name":"Kostya","avatar_url":"https://avatars-next.observableusercontent.com/f5ff1dfc1cbdafecf8fe126943ef46f7ea62e6d006f5ac9145e91cddb991c06e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Voronoi Incircles","cells":[{"id":0,"value":"md`# Voronoi Incircles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":110,"value":"md`The largest circle that fits inside the given closed convex polygon is determined by “brute force”: for each distinct set of three sides of the polygon, extend the sides to form a triangle and compute the triangle’s incircle; then reduce the circle’s radius against the remaining sides.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"function polygonIncircle(points) {\n let circle = [NaN, NaN, 0];\n for (var i = 0, n = points.length; i < n; ++i) {\n const pi0 = points[i], pi1 = points[(i + 1) % n];\n for (let j = i + 1; j < n; ++j) {\n const pj0 = points[j], pj1 = points[(j + 1) % n];\n const pij = j === i + 1 ? pj0 : lineLineIntersection(pi0, pi1, pj0, pj1);\n search: for (let k = j + 1; k < n; ++k) {\n const pk0 = points[k], pk1 = points[(k + 1) % n];\n const pik = lineLineIntersection(pi0, pi1, pk0, pk1);\n const pjk = k === j + 1 ? pk0 : lineLineIntersection(pj0, pj1, pk0, pk1);\n const c = triangleIncircle(pij, pik, pjk);\n for (let l = 0; l < n; ++l) {\n const pl0 = points[l];\n const pl1 = points[(l + 1) % n];\n const r = pointLineDistance(c, pl0, pl1);\n if (r < circle[2]) continue search;\n if (r < c[2]) c[2] = r;\n }\n circle = c;\n }\n }\n }\n return circle;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":120,"value":"md`A triangle’s incircle is the largest circle that fits inside the given triangle; it is tangent to all three sides.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":27,"value":"function triangleIncircle(p0, p1, p2) {\n const [x0, y0] = p0, [x1, y1] = p1, [x2, y2] = p2;\n const x01 = x0 - x1, y01 = y0 - y1;\n const x02 = x0 - x2, y02 = y0 - y2;\n const x12 = x1 - x2, y12 = y1 - y2;\n const l01 = Math.sqrt(x01 * x01 + y01 * y01);\n const l02 = Math.sqrt(x02 * x02 + y02 * y02);\n const l12 = Math.sqrt(x12 * x12 + y12 * y12);\n const k0 = l01 / (l01 + l02);\n const k1 = l12 / (l12 + l01);\n const c = lineLineIntersection(p0, [x1 - k0 * x12, y1 - k0 * y12], p1, [x2 + k1 * x02, y2 + k1 * y02]);\n c[2] = Math.sqrt((l02 + l12 - l01) * (l12 + l01 - l02) * (l01 + l02 - l12) / (l01 + l02 + l12)) / 2;\n return c;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":123,"value":"md`The signed distance from point ${tex`\\langle x_0,y_0 \\rangle`} to the infinite line intersecting ${tex`\\langle x_1,y_1 \\rangle`} and ${tex`\\langle x_2,y_2 \\rangle`} is positive if the the given point might be inside the given convex polygon, and negative if it is outside. This value is used to compute the incircle radius.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":62,"value":"function pointLineDistance([x0, y0], [x1, y1], [x2, y2]) {\n const x21 = x2 - x1, y21 = y2 - y1;\n return (y21 * x0 - x21 * y0 + x2 * y1 - y2 * x1) / Math.sqrt(y21 * y21 + x21 * x21);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":134,"value":"md`To compute the intersection of two infinite lines, one intersecting ${tex`\\langle x_0,y_0 \\rangle`} and ${tex`\\langle x_1,y_1 \\rangle`}, and the other intersecting ${tex`\\langle x_2,y_2 \\rangle`} and ${tex`\\langle x_3,y_3 \\rangle`}, we use a parametric representation.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":29,"value":"function lineLineIntersection([x0, y0], [x1, y1], [x2, y2], [x3, y3]) {\n const x02 = x0 - x2, y02 = y0 - y2;\n const x10 = x1 - x0, y10 = y1 - y0;\n const x32 = x3 - x2, y32 = y3 - y2;\n const t = (x32 * y02 - y32 * x02) / (y32 * x10 - x32 * y10);\n return [x0 + t * x10, y0 + t * y10];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":13,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":150,"value":"n = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2f:"$2e:body"