| license: gpl-3.0 | |
| height: 510 | |
| border: no |
Voronoi Sampling methods comparison (using D3)
Methods:
Pure Random
Random Relaxed (Lloyd's ralaxation, 1 iteration)
Random Relaxed (Lloyd's ralaxation, 5 iterations)
Random Relaxed (Lloyd's ralaxation, 10 iterations)
Poisson Disc Voronoi
Poisson Disc Voronoi (aligned to regular xy grid)
Voronoi Tessellation code is based on D3 implementation by Mike Bostock. Poisson Disc sampling code is also created by Mike. It's based on of Bridson’s algorithm coded by Jason Davies
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <svg id="rand" width="300" height="250"></svg> | |
| <svg id="relax1" width="300" height="250"></svg> | |
| <svg id="relax5" width="300" height="250"></svg> | |
| <svg id="relax10" width="300" height="250"></svg> | |
| <svg id="pois" width="300" height="250"></svg> | |
| <svg id="poisAl" width="300" height="250"></svg> | |
| <style> | |
| svg { | |
| background-color: grey; | |
| fill: darkgrey; | |
| stroke: white; | |
| stroke-width: 2; | |
| } | |
| </style> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| <script> | |
| // Common variables | |
| var width = 300; | |
| var height = 250; | |
| var voronoi = d3.voronoi().extent([[5, 5],[width-5, height-5]]); | |
| // Pure Random Voronoi | |
| var svgRand = d3.select("#rand"); | |
| var sites = d3.range(100).map(function(d) { | |
| return [Math.random() * width, Math.random() * height]; | |
| }); | |
| var polygonsRand = voronoi(sites).polygons(); | |
| polygonsRand.map(function(i) { | |
| svgRand.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Random Relaxed (1 iteration) Voronoi | |
| var svgRelax1 = d3.select("#relax1"); | |
| var sites = relax(1); | |
| var polygonsRelax1 = voronoi(sites).polygons(); | |
| polygonsRelax1.map(function(i) { | |
| svgRelax1.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Random Relaxed (5 iterations) Voronoi | |
| var svgRelax5 = d3.select("#relax5"); | |
| var sites = relax(4); | |
| var polygonsRelax5 = voronoi(sites).polygons(); | |
| polygonsRelax5.map(function(i) { | |
| svgRelax5.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Random Relaxed (10 iterations) Voronoi | |
| var svgRelax10 = d3.select("#relax10"); | |
| var sites = relax(5); | |
| var polygonsRelax10 = voronoi(sites).polygons(); | |
| polygonsRelax10.map(function(i) { | |
| svgRelax10.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Poisson Disc Voronoi | |
| var svgPois = d3.select("#pois"); | |
| var sampler = poissonDiscSampler(23), samples = [], sample; | |
| while (sample = sampler()) samples.push(sample); | |
| var polygonsPois = voronoi(samples).polygons(); | |
| polygonsPois.map(function(i) { | |
| svgPois.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Poisson Disc Voronoi - aligned | |
| var svgPoisAl = d3.select("#poisAl"); | |
| samples.map(function(i, d) { | |
| i[0] = Math.floor(i[0]); | |
| i[1] = Math.floor(i[1]); | |
| }); | |
| var polygonsPoisAl = voronoi(samples).polygons(); | |
| polygonsPoisAl.map(function(i) { | |
| i.map(function(d) { | |
| d[0] = Math.floor(d[0]); | |
| d[1] = Math.floor(d[1]); | |
| }); | |
| svgPoisAl.append("path").attr("d", "M" + i.join("L") + "Z"); | |
| }); | |
| // Based on https://www.jasondavies.com/poisson-disc/ | |
| function poissonDiscSampler(radius) { | |
| var k = 30, // 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; | |
| } | |
| } | |
| function relax(iterations) { | |
| for (var i = 0; i < iterations; i++) { | |
| sites = voronoi(sites).polygons().map(d3.polygonCentroid); | |
| } | |
| return sites; | |
| } | |
| </script> |