2a:null 2b:["$","title",null,{"children":"Voronoi Incircles | Mike Bostock | Observable"}] 30:T56d,canvas = { const context = DOM.context2d(width, height); while (true) { context.fillStyle = "#eee"; context.fillRect(0, 0, width, height); context.beginPath(); for (const cell of voronoi.cellPolygons()) { const [x, y, r] = polygonIncircle(cell); if (r < 1.5) continue; context.moveTo(x + r - 1.5, y); context.arc(x, y, r - 1.5, 0, 2 * Math.PI); } context.fillStyle = "#fff"; context.fill(); context.beginPath(); voronoi.render(context); voronoi.renderBounds(context); context.strokeStyle = "#bbb"; context.stroke(); context.beginPath(); voronoi.delaunay.renderPoints(context); context.fillStyle = "#000"; context.fill(); yield context.canvas; for (let i = 0; i < n; ++i) { const x = i << 1; const y = x + 1; positions[x] += velocities[x]; positions[y] += velocities[y]; if (positions[x] < -margin) positions[x] += width + margin * 2; else if (positions[x] > width + margin) positions[x] -= width + margin * 2; if (positions[y] < -margin) positions[y] += height + margin * 2; else if (positions[y] > height + margin) positions[y] -= height + margin * 2; velocities[x] += 0.2 * (Math.random() - 0.5) - 0.01 * velocities[x]; velocities[y] += 0.2 * (Math.random() - 0.5) - 0.01 * velocities[y]; } voronoi.update(); } }31:[] 2e:{"id":"ba0d23af0509620f","slug":"voronoi-incircles","title":"Voronoi Incircles","thumbnail":"c8306c888d014a8587b876288906665fa6d58a9f3c472a053389e147a952a756","access_level":"public","create_time":"$D2018-05-22T21:38:15.443Z","update_time":"$D2019-11-27T04:32:42.785Z","view_time":null,"first_public_time":"$D2018-05-22T22:44:41.799Z","has_unpublished_edits":null,"fork":false,"stars":38,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":333,"publish_version":333,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":22,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Voronoi Incircles","cells":[{"id":0,"value":"md`# Voronoi Incircles\n\nFor each Voronoi cell, the [largest contained circle](/@mbostock/convex-polygon-incircle) is shown in white.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"positions = Float64Array.from({length: n * 2}, (_, i) => Math.random() * (i & 1 ? height : width))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"velocities = new Float64Array(n * 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":317,"value":"voronoi = new d3.Delaunay(positions).voronoi([0.5, 0.5, width - 0.5, height - 0.5])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"function polygonIncircle(polygon) {\n let circle = [NaN, NaN, 0];\n for (let i = 0, n = polygon.length - 1; i < n; ++i) {\n const pi0 = polygon[i], pi1 = polygon[i + 1];\n for (let j = i + 1; j < n; ++j) {\n const pj0 = polygon[j], pj1 = polygon[j + 1];\n search: for (let k = j + 1; k < n; ++k) {\n const pk0 = polygon[k], pk1 = polygon[k + 1];\n const c = circleTangent(pi0, pi1, pj0, pj1, pk0, pk1);\n if (!(c[2] > circle[2])) continue;\n for (let l = 0; l < n; ++l) {\n if (l === i || l === j || l === k) continue;\n const d = pointLineDistance(c, polygon[l], polygon[l + 1]);\n if (d + 1e-6 < c[2]) continue search;\n }\n circle = c;\n }\n }\n }\n return circle;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"function circleTangent(p0, p1, p2, p3, p4, p5) {\n const b0 = lineLineBisect(p0, p1, p3, p2);\n const b1 = lineLineBisect(p2, p3, p5, p4);\n const i = lineLineIntersect(...b0, ...b1);\n return [...i, pointLineDistance(i, p0, p1)];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"function pointLineDistance([x0, y0], [x2, y2], [x1, y1]) {\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","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":255,"value":"function lineLineBisect([x0, y0], [x1, y1], [x2, y2], [x3, y3]) {\n const x02 = x0 - x2, y02 = y0 - y2;\n const x10 = x1 - x0, y10 = y1 - y0, l10 = Math.sqrt(x10 ** 2 + y10 ** 2);\n const x32 = x3 - x2, y32 = y3 - y2, l32 = Math.sqrt(x32 ** 2 + y32 ** 2);\n const ti = (x32 * y02 - y32 * x02) / (y32 * x10 - x32 * y10);\n const xi = x0 + ti * x10, yi = y0 + ti * y10;\n return [[xi, yi], [xi + x10 / l10 + x32 / l32, yi + y10 / l10 + y32 / l32]];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"function lineLineIntersect([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","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"height = 600","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"margin = 60","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"n = 100","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"d3 = require(\"d3-delaunay@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1"}} 2f:"$2e:body"