2a:null 2b:["$","title",null,{"children":"Random Convex Polygons | Zihou Ng | Observable"}] 30:Tb9a,{ const root = d3.select(DOM.svg(300, 300)); const scale = d3.scaleLinear([0,1],[0,150]); const dx = d => scale(d[0]), dy = d => scale(d[1]); const state = makeAlgorithmState(numPoints); const g = root.append("g").attr("transform", "translate(150,150)"); const px = g.selectAll(".px").data(state.vec) .join("circle").classed("px", true) .attr("r", 3) .attr("fill", palette.orange); const py = g.selectAll(".py").data(state.vec) .join("circle").classed("py", true) .attr("r", 3) .attr("fill", palette.blue); const p = g.selectAll(".p").data(state.vec) .join("circle").classed("point-xy", true) .attr("cx", dx).attr("cy", dy) .attr("fill", palette.red) .style("opacity", 0); const lines = g.selectAll(".vec").data(state.segments) .join("line").classed("vec", true) .attr("x2", d => scale(d[0][0])).attr("y2", d => scale(d[0][1])) .attr("stroke", palette.dark) .style("opacity", 0); const n = state.points.length; const [cx, cy] = d3.polygonCentroid(state.points); const polygon = g.append('polygon') .attr("points", state.points.map(x => `${scale(x[0])},${scale(x[1])}`).join(" ")) .style("stroke", `hsl(${n / 100 * 360},50%,50%)`) .style("fill", `hsl(${n / 100 * 360},45%,50%)`) .style("opacity", 0); function showCoord() { const dur = d3.randomInt(500, 750); const tx = px.transition().duration(dur).ease(d3.easeCubic) .attr("cx", dx) .end(); const ty = py.transition().duration(dur).ease(d3.easeCubic) .attr("cy", dy) .end(); return Promise.all([tx, ty]); } function showVecs() { px.transition().duration(700).ease(d3.easeCubic) .attr("cx", dx) .attr("cy", dy) .remove(); py.transition().duration(700).ease(d3.easeCubic) .attr("cx", dx) .attr("cy", dy) .remove(); p.transition().delay(300) .attr("r", 4) .style("opacity", .8) .end(); return lines.transition().delay(500) .style("opacity", 1).end(); } function combine() { p.transition().duration(1000) .delay((_, i) => i * 2000/state.vec.length) .ease(d3.easeCubic) .attr("r", 0) .style("opacity", 0); return lines.transition() .delay((_, i) => i * 2000/state.vec.length) .ease(d3.easeCubic) .duration(1000) .attr("x1", d => scale(d[1][0])) .attr("y1", d => scale(d[1][1])) .attr("x2", d => scale(d[2][0])) .attr("y2", d => scale(d[2][1])) .end(); } function showPoly() { lines.transition().ease(d3.easeCubic).style("opacity", 0); return polygon.transition().ease(d3.easeCubic).style("opacity", 1).end(); } function shiftPoly() { polygon.transition().duration(700).ease(d3.easeCubic) .attr("transform", `translate(${scale(-cx)},${scale(-cy)})`); } showCoord() .then(showVecs) .then(combine) .then(showPoly) .then(shiftPoly); return root.node(); }31:T57e,makeConvexPolygon = n => { const xs = [], ys = []; for (let i = 0; i < n; i++) { xs.push(Math.random()); ys.push(Math.random()); } xs.sort(); ys.sort(); const minX = xs[0], maxX = xs[n-1]; const minY = ys[0], maxY = ys[n-1]; let lastTop = minX, lastBot = minX; let lastLeft = minY, lastRight = minY; const vx = [], vy = []; for (let i = 1; i < n - 1;i++) { if (Math.random() < 0.5) { vx.push(xs[i] - lastTop); lastTop = xs[i]; } else { vx.push(lastBot - xs[i]); lastBot = xs[i]; } if (Math.random() < 0.5) { vy.push(ys[i] - lastLeft); lastLeft = ys[i]; } else { vy.push(lastRight - ys[i]); lastRight = ys[i]; } } vx.push(maxX - lastTop); vx.push(lastBot - maxX); vy.push(maxY - lastLeft); vy.push(lastRight - maxY); d3.shuffle(vy); const vec = []; for (let i = 0; i < n; i++) { vec.push([vx[i], vy[i]]); } vec.sort((a, b) => Math.atan2(a[1],a[0]) - Math.atan2(b[1],b[0])); const points = []; let x = 0, y = 0, mpx = 0, mpy = 0; for (let i = 0; i < n; i++) { points.push([x, y]) x += vec[i][0]; y += vec[i][1]; mpx = Math.min(mpx, x); mpy = Math.min(mpy, y); } const xShift = minX - mpx, yShift = minY - mpy; for (let i = 0; i < n; i++) { points[i][0] += xShift; points[i][1] += yShift; } return points; }32:T528,makeAlgorithmState = n => { const xs = [], ys = []; for (let i = 0; i < n; i++) { xs.push(Math.random()); ys.push(Math.random()); } xs.sort(); ys.sort(); const minX = xs[0], maxX = xs[n-1]; const minY = ys[0], maxY = ys[n-1]; let lastTop = minX, lastBot = minX; let lastLeft = minY, lastRight = minY; const vx = [], vy = []; for (let i = 1; i < n - 1;i++) { if (Math.random() < 0.5) { vx.push(xs[i] - lastTop); lastTop = xs[i]; } else { vx.push(lastBot - xs[i]); lastBot = xs[i]; } if (Math.random() < 0.5) { vy.push(ys[i] - lastLeft); lastLeft = ys[i]; } else { vy.push(lastRight - ys[i]); lastRight = ys[i]; } } vx.push(maxX - lastTop); vx.push(lastBot - maxX); vy.push(maxY - lastLeft); vy.push(lastRight - maxY); d3.shuffle(vy); const vec = []; for (let i = 0; i < n; i++) vec.push([vx[i], vy[i]]); vec.sort((a, b) => Math.atan2(a[1],a[0]) - Math.atan2(b[1],b[0])); const points = []; let x = 0, y = 0; for (let i = 0; i < n; i++) { points.push([x, y]) x += vec[i][0]; y += vec[i][1]; } const segments = []; for (let i = 0; i < n; i++) { segments.push([vec[i], points[i], points[(i+1)%n]]); } return { vec, points, segments }; }33:[] 2e:{"id":"3306aa7fd29277e6","slug":"random-convex-polygons","title":"Random Convex Polygons","thumbnail":"a23fd2bd5be2584d3f1c65c49a32f12fd042abe8ecc3b64563c14641629e9595","access_level":"public","create_time":"$D2020-12-30T12:13:48.996Z","update_time":"$D2022-01-07T11:44:35.728Z","view_time":null,"first_public_time":"$D2020-12-31T05:45:48.482Z","fork":false,"stars":24,"starred":false,"owner":{"type":"team","id":"7fad80bf128915e9","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":"starter_2024"},"version":609,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null}],"members":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":7,"collection":null,"type":"notebook","body":{"title":"Random Convex Polygons","cells":[{"id":0,"value":"md`# Random Convex Polygons`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":137,"value":"md`An efficient ${tex`O(n \\log n)`} algorithm by [Sander Verdonschot](https://cglab.ca/~sander/misc/ConvexGeneration/convex.html) to generate random convex polygons with specific number of vertices. The idea is quite simple, here is how it works for a convex ${numPoints}-gon:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":124,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":472,"value":"viewof numPoints = slider({\n min: 3, \n max: 100, \n step: 1, \n value: 8, \n title: \"Number of Vertices\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":491,"value":"md`---\nNow let's make some polygons!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":512,"value":"{\n btnMore;\n const rand = d3.randomInt(...numPointsRange);\n const polygons = d3.range(90).map(() => makeConvexPolygon(rand()));\n \n const ncol = 15, cell = width / ncol;\n const root = d3.select(DOM.svg(width, cell * polygons.length / ncol));\n const scale = d3.scaleLinear([0,1],[0, cell]);\n \n root.selectAll(\".polygon\").data(polygons)\n .join(\"polygon\").classed(\"polygon\", true)\n .attr(\"transform\", (_, i) => `translate(${(i % ncol) * cell},${Math.floor(i / ncol) * cell})`)\n .attr(\"points\", d => d.map(x => `${scale(x[0])},${scale(x[1])}`).join(\" \"))\n .attr(\"fill\", palette.dark);\n\n return root.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":501,"value":"viewof numPointsRange = rangeSlider({\n min: 3,\n max: 100,\n precision: 0,\n title: 'Number of Vertices',\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":560,"value":"viewof btnMore = button({\"value\": \"generate\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":553,"value":"md`---\n## Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":455,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":462,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":428,"value":"palette = ({\n \"red\": d3.schemeCategory10[3],\n \"blue\": d3.schemeCategory10[0],\n \"orange\": d3.schemeCategory10[1],\n \"green\": d3.schemeCategory10[2],\n \"dark\": \"hsl(0,0%,30%)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":15,"value":"md`### Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":469,"value":"import {slider,button} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":497,"value":"import {rangeSlider} from \"@mootari/range-slider\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 2f:"$2e:body"