Skip to content

Instantly share code, notes, and snippets.

@Azgaar

Azgaar/.block

Last active October 25, 2019 09:32
Show Gist options
  • Save Azgaar/4904e89c12c7347a9e1639edb7655e10 to your computer and use it in GitHub Desktop.
Save Azgaar/4904e89c12c7347a9e1639edb7655e10 to your computer and use it in GitHub Desktop.
Download ZIP
Voronoi Tessellation with Poisson Disc sampling
Raw
.block
license: gpl-3.0
height: 620
border: no
Raw
README.md
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<svg width="960" height="500"></svg>
<div id="sliderR" title="Radius: min distance between samples">
<div id="radius" class="ui-slider-handle"></div>
</div>
<br>
<div id="sliderC" title="Candidates: max candidate samples">
<div id="candidates" class="ui-slider-handle"></div>
</div>
<br>
<div id="sliderL" title="Relax: iterations of Lloyd's relaxation">
<div id="relaxation" class="ui-slider-handle"></div>
</div>
<link rel="stylesheet" type="text/css" href="https://code.jquery.com/ui/1.12.1/themes/base/jquery-ui.css">
<style>
.links {
stroke: black;
stroke-opacity: 0.1;
stroke-width: 1.5;
}
.polygons {
fill: darkgrey;
stroke: white;
stroke-width: 2;
}
.polygons :first-child {
fill: lightgrey;
}
.sites {
fill: white;
stroke: black;
}
.sites :first-child {
stroke: green;
fill: white;
}
.centroids {
fill: grey;
stroke: none;
}
#sliderR, #sliderC, #sliderL {
margin-top: 0.4em;
}
#radius, #candidates, #relaxation {
width: 3em;
height: 1.6em;
top: 50%;
margin-top: -.8em;
text-align: center;
line-height: 1.6em;
}
</style>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://code.jquery.com/jquery-3.2.1.min.js"></script>
<script src="https://code.jquery.com/ui/1.12.1/jquery-ui.min.js"></script>
<script>
var width = 960;
var height = 500;
var radius = 50;
var candidates = 20;
var relax = 1;
var sampler, sites = [], sample;
var polygon, link, site, centroids;
var voronoi = d3.voronoi().extent([[0, 0],[width, height]]);
var svg = d3.select("svg").on("touchmove mousemove", moved);
createSamples(radius,candidates,relax);
draw();
function createSamples(radius,candidates, relax) {
sampler = poissonDiscSampler(radius,candidates), sites = [], sample;
while (sample = sampler()) sites.push(sample);
if (relax) {
for (var r = 0; r < relax; r++) {
sites = voronoi(sites).polygons().map(d3.polygonCentroid);
}
}
centroids = voronoi(sites).triangles().map(d3.polygonCentroid);
}
function draw() {
svg.selectAll("g").remove();
polygon = svg.append("g")
.attr("class", "polygons")
.selectAll("path")
.data(voronoi.polygons(sites))
.enter().append("path")
.call(redrawPolygon);
link = svg.append("g")
.attr("class", "links")
.selectAll("line")
.data(voronoi.links(sites))
.enter().append("line")
.call(redrawLink);
site = svg.append("g")
.attr("class", "sites")
.selectAll("circle")
.data(sites)
.enter().append("circle")
.attr("r", 2.5)
.call(redrawSite);
centroid = svg.append("g")
.attr("class", "centroids")
.selectAll("circle")
.data(centroids)
.enter().append("circle")
.attr("r", 2)
.call(redrawCentroid);
}
function moved() {
sites[0] = d3.mouse(this);
redraw();
}
function redraw() {
var diagram = voronoi(sites);
polygon = polygon.data(diagram.polygons()).call(redrawPolygon);
link = link.data(diagram.links()), link.exit().remove();
link = link.enter().append("line").merge(link).call(redrawLink);
site = site.data(sites).call(redrawSite);
centroid = centroid.data(centroids).call(redrawCentroid);
}
function redrawPolygon(polygon) {
polygon
.attr("d", function(d) { return d ? "M" + d.join("L") + "Z" : null; });
}
function redrawLink(link) {
link
.attr("x1", function(d) { return d.source[0]; })
.attr("y1", function(d) { return d.source[1]; })
.attr("x2", function(d) { return d.target[0]; })
.attr("y2", function(d) { return d.target[1]; });
}
function redrawSite(site) {
site
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
}
function redrawCentroid(centroid) {
centroid
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
}
function poissonDiscSampler(radius,candidates) {
var 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 < candidates; ++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;
}
}
$("#sliderR").slider({
min: 10,
max: 100,
step: 1,
value: radius,
create: function() {
$("#radius").text(radius);
},
slide: function(event, ui) {
$("#radius").text(ui.value);
radius = ui.value;
createSamples(radius,candidates,relax);
draw();
redraw();
}
});
$("#sliderC").slider({
min: 3,
max: 100,
step: 1,
value: candidates,
create: function() {
$("#candidates").text(candidates);
},
slide: function(event, ui) {
$("#candidates").text(ui.value);
candidates = ui.value;
createSamples(radius,candidates,relax);
draw();
redraw();
}
});
$("#sliderL").slider({
min: 0,
max: 20,
step: 1,
value: relax,
create: function() {
$("#relaxation").text(relax);
},
slide: function(event, ui) {
$("#relaxation").text(ui.value);
relax = ui.value;
createSamples(radius,candidates,relax);
draw();
redraw();
}
});
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment