2b:null 2c:["$","title",null,{"children":"Voronoi Polygon Smoothing | Kemper Smith | Observable"}] 31:T92f,// Based on https://www.jasondavies.com/poisson-disc/ function poissonDiscSampler(width, height, radius) { var k = 40, // maximum number of samples before rejection radius2 = radius * radius, R = 3 * radius2, cellSize = radius * Math.SQRT1_2, gridWidth = Math.ceil(width / cellSize), gridHeight = Math.ceil(height / cellSize), grid = new Array(gridWidth * gridHeight), queue = [], queueSize = 0, sampleSize = 0; return function() { if (!sampleSize) return sample(Math.random() * width, Math.random() * height); // Pick a random existing sample and remove it from the queue. while (queueSize) { var i = Math.random() * queueSize | 0, s = queue[i]; // Make a new candidate between [radius, 2 * radius] from the existing sample. for (var j = 0; j < k; ++j) { var a = 2 * Math.PI * Math.random(), r = Math.sqrt(Math.random() * R + radius2), x = s[0] + r * Math.cos(a), y = s[1] + r * Math.sin(a); // Reject candidates that are outside the allowed extent, // or closer than 2 * radius to any existing sample. if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) return sample(x, y); } queue[i] = queue[--queueSize]; queue.length = queueSize; } }; function far(x, y) { var i = x / cellSize | 0, j = y / cellSize | 0, i0 = Math.max(i - 2, 0), j0 = Math.max(j - 2, 0), i1 = Math.min(i + 3, gridWidth), j1 = Math.min(j + 3, gridHeight); for (j = j0; j < j1; ++j) { var o = j * gridWidth; for (i = i0; i < i1; ++i) { if (s = grid[o + i]) { var s, dx = s[0] - x, dy = s[1] - y; if (dx * dx + dy * dy < radius2) return false; } } } return true; } function sample(x, y) { var s = [x, y]; queue.push(s); grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = s; ++sampleSize; ++queueSize; return s; } }32:[] 2f:{"id":"1255cc389d59ddad","slug":"voronoi-polygon-smoothing","title":"Voronoi Polygon Smoothing","thumbnail":"b6094f47880195ffb831a60cfc01f269f441efa63680f0db0f472126222a1ccd","access_level":"public","create_time":"$D2019-03-10T20:36:45.246Z","update_time":"$D2019-08-07T17:11:02.646Z","view_time":null,"first_public_time":"$D2019-03-10T20:37:03.461Z","fork":true,"stars":20,"starred":false,"owner":{"type":"team","id":"167a7adedc130581","login":"kemper","name":"Kemper Smith","avatar_url":"https://avatars-next.observableusercontent.com/62a102a58152b7c85d17d4ea9f040c01bd0cb0ae2ebc8b040d43e51a729deee3","tier":"starter_2024"},"version":752,"publish_version":752,"role":null,"authored":false,"authors":[{"type":"individual","id":"d015eb85d8c25b2e","login":"kemper","name":"Kemper Smith","avatar_url":"https://avatars-next.observableusercontent.com/62a102a58152b7c85d17d4ea9f040c01bd0cb0ae2ebc8b040d43e51a729deee3","tier":null}],"members":[{"type":"individual","id":"d015eb85d8c25b2e","login":"kemper","name":"Kemper Smith","avatar_url":"https://avatars-next.observableusercontent.com/62a102a58152b7c85d17d4ea9f040c01bd0cb0ae2ebc8b040d43e51a729deee3","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":7,"collection":null,"type":"notebook","body":{"title":"Voronoi Polygon Smoothing","cells":[{"id":0,"value":"md`# Voronoi Polygon Smoothing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"voronoiDiagram = {\n\tconst svg = d3.select(DOM.svg(width, height));\n \n \tsvg.style(\"background-color\", \"grey\");\n \n let cell = svg.selectAll(\"g\")\n .data(sites)\n .enter().append(\"g\");\n\n cell.append(\"path\")\n .data(voronoiPolygons.map(d => cleanPoints(d)))\n \t.attr(\"d\", d => line(resample(d)))\n .style(\"stroke\", \"grey\")\n \t.style(\"fill\", \"white\")\n \t.style(\"stroke-width\", cellStrokeWidth);\n \n \tsvg.append(\"g\")\n .selectAll(\".site\")\n .data(sites)\n .enter().append(\"circle\")\n .attr(\"class\", \"site\")\n .attr(\"cx\", d => d[0])\n .attr(\"cy\", d => d[1])\n .attr(\"r\", 1.5)\n .style(\"fill\", \"grey\")\n \t\t.style(\"display\", () => showSites ? \"block\" : \"none\");\n\t\n \treturn svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"viewof separationRadius = makeSliderWithValue(\"separationRadius\", 20, 100, 1, 55, \"pixels\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":496,"value":"viewof cellStrokeWidth = makeSliderWithValue(\"cellStrokeWidth\", 0, 30, 1, 6, \"pixels\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":477,"value":"viewof isCornerRadiusAbsolute = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":479,"value":"viewof cornerRadius = isCornerRadiusAbsolute ? makeSliderWithValue(\"cornerRadius\", 0, 100, 1, 10, \"pixels\") : makeSliderWithValue(\"cornerRadius\", 0, 0.5, 0.01, 0.4, \"\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":436,"value":"viewof cleanCornerRadius = makeSliderWithValue(\"cleanCornerRadius\", 0, 30, 1, 10, \"pixels\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"viewof showSites = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":468,"value":"voronoiPolygons = voronoi.polygons(sites)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"voronoi = d3.voronoi()\n .extent([[1, 1], [width - 2, height - 2]])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":471,"value":"sites = runSample()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"line = d3.line()\n .curve(d3.curveBasisClosed)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"function runSample() {\n let sampleSites = poissonDiscSampler(width, height, separationRadius)\n\n function sites() {\n let points = [];\n\n for (var i = 0; i < 10000; ++i) {\n let s = sampleSites();\n if (s) points.push(s);\n }\n return points;\n }\n \n \treturn sites();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":621,"value":"md`Resampling generates additional vertices along polygon's segements to allow for more precise rounding of corners using *d3.curveBasisClosed*. This is from Mike Bostock's [Rotating Voronoi example](https://bl.ocks.org/mbostock/4636377) but modified to allow for dividing segements into unequeal lengths`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"function resample(points) {\n \tlet i = -1;\n \tlet n = points.length;\n \tlet p0 = points[n - 1];\n let x0 = p0[0];\n let y0 = p0[1];\n let p1, x1, y1;\n let points2 = [];\n \n while (++i < n) {\n \tp1 = points[i];\n x1 = p1[0];\n y1 = p1[1];\n \n \tlet finalRadius = 0;\n \n \tif (isCornerRadiusAbsolute) {\n let distance = Math.sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2);\n let distFromPoint = cornerRadius / distance;\n finalRadius = distFromPoint >= 0.5 ? 0.5 : distFromPoint;\n }\n else {\n \tfinalRadius = cornerRadius;\n }\n \t\n points2.push(\n [x0 + (x1 - x0) * finalRadius,\n y0 + (y1 - y0) * finalRadius],\n [x0 + (x1 - x0) * (1 - finalRadius),\n y0 + (y1 - y0) * (1 - finalRadius)],\n \tp1\n );\n \n p0 = p1;\n x0 = x1;\n y0 = y1;\n }\n return points2;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"md`Layout of voronoi sites uses the Poisson-Disc sampling technique from Mike Bostock's [Visualizing Algorithms](https://bost.ocks.org/mike/algorithms/) which is based on Jason Davies's [Poisson-Disc Sampling](https://www.jasondavies.com/poisson-disc/)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"// Cleaning polygon vertices using js-clipper requires converting points in {X:0,Y:0} format\nfunction cleanPoints(points) {\n return cleanPoly(points.map(d => {\n return {X:d[0],Y:d[1]};\n })).map(d => [d.X,d.Y]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"function cleanPoly(path) {\n \tlet cleanedPath = clipper.JS.Clean(path, cleanCornerRadius)\n \tif (cleanedPath.length > 0) return cleanedPath;\n else return path;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":731,"value":"import {makeSliderWithValue} from \"@kemper/code-snippets\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":698,"value":"import {viewof polygonDrawing as resamplingDemo} from \"@kemper/polygon-smoothing-test\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":723,"value":"md`Demo of how polygon segments get divided with additional vertices and then smoothed using *d3.curveBasisClosed*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":716,"value":"viewof resamplingDemo","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":615,"value":"md`[JavaScript Clipper](https://sourceforge.net/projects/jsclipper) is a library for doing various things with polygons including boolean operations, cleaning, simplification, etc.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"clipper = require(\"https://bundle.run/js-clipper@1.0.1\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"