Skip to content

Instantly share code, notes, and snippets.

@alexmacy alexmacy/.block
Last active Jun 26, 2018

Embed
What would you like to do?
K-Means Voronoi Relaxation
license: mit
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
body {margin:0;}
polygon {stroke: black; fill-opacity: .5;}
circle {stroke: none; fill-opacity: .5;}
text {stroke: black;}
</style>
<script src="https://d3js.org/d3.v4.min.js"></script>
</head>
<body>
<svg></svg>
<div>
<button onclick="stop = false; start()">start</button>
<button onclick="stop = true">stop</button>
<button onclick="stop = true; redraw()">redraw</button>
<b id="specs"></b><b id="average"></b><b id="deviation"></b><b id="steps"> - Steps: 0</b>
</div>
</body>
<script>
var width = 960,
height = 470;
var stop = false;
var pointCount = 20000,
polygonCount = 100,
steps = 0;
var voronoi = d3.voronoi().extent([[0, 0],[width, height]]);
var colorScale = d3.scaleLinear().range(["white", "green", "black"])
var pointCoords = randomPoints(pointCount),
voronoiPoints = randomPoints(polygonCount),
populations = [];
d3.select("#specs").html(" " + d3.format(",")(pointCount) + " points, " + polygonCount + " polygons")
d3.select("#average").html(" - Average: " + pointCount/polygonCount)
var svg = d3.select("svg")
.attr("width", width)
.attr("height", height)
var points = svg.selectAll("circle")
.data(pointCoords)
.enter().append("circle")
.attr("r", 1)
.attr("cx", function(d) {return d[0]})
.attr("cy", function(d) {return d[1]})
var polygons = svg.selectAll("polygon")
.data(voronoi(voronoiPoints).polygons())
.enter().append("polygon")
.attr("points", function(d) {return d})
var centroids = svg.selectAll("text")
.data(voronoiPoints)
.enter().append("text")
.attr("x", function(d) {return d[0]})
.attr("y", function(d) {return d[1]})
.attr("text-anchor", "middle")
voronoiPoints.forEach(function(d, i) {return populations[i] = [];})
pointCoords.forEach(function(d) {populations[findClosest(d)].push(d);})
d3.select("#deviation").html(" - Deviation: " + d3.deviation(populations, function(d) {return d.length}).toFixed(2))
var extent = d3.extent(populations, function(d) {return d.length});
colorScale.domain([extent[0],pointCount/polygonCount,extent[1]])
centroids.html(function(d, i) {return populations[i].length})
polygons.attr("fill", function(d, i) {return colorScale(populations[i].length)})
function start(){
if (stop) {
console.log("stopping")
return stop = false;
}
groupPoints();
var stopVal = 0;
for (i=0; i<voronoiPoints.length; i++) {
var newPoint = getNewCenter(i)
stopVal += (voronoiPoints[i][0] == newPoint[0] && voronoiPoints[i][1] == newPoint[1]) ? 1 : 0;
voronoiPoints[i] = newPoint;
if (stopVal == voronoiPoints.length) {stop = true};
}
if (stop) {
console.log("stopping")
return stop = false;
}
d3.select("#steps").html(" - Steps: " + ++steps)
centroids.data(voronoiPoints)
.attr("x", function(d) {return d[0]})
.attr("y", function(d) {return d[1]})
polygons.data(voronoi(voronoiPoints).polygons())
.attr("points", function(d) {return d})
d3.timeout(start, 50);
}
function groupPoints() {
voronoiPoints.forEach(function(d, i) {return populations[i] = [];})
pointCoords.forEach(function(d) {populations[findClosest(d)].push(d);})
d3.select("#deviation").html(" - Deviation: " + d3.deviation(populations, function(d) {return d.length}).toFixed(2))
centroids.html(function(d, i) {return populations[i].length})
polygons.attr("fill", function(d, i) {return colorScale(populations[i].length)})
}
function getNewCenter(n) {
var centerX = d3.sum(populations[n], function(d) {return d[0]})/populations[n].length;
var centerY = d3.sum(populations[n], function(d) {return d[1]})/populations[n].length;
return [centerX, centerY];
}
function randomPoints(count) {
return d3.range(count)
.map(function() {return [Math.random() * width, Math.random() * height];})
}
function findClosest(coords) {
var closestDist = Infinity,
closestPoint;
for (i=0; i<voronoiPoints.length; i++) {
var thisDist = calcDistance(coords, voronoiPoints[i]);
if (thisDist < closestDist) {
closestDist = thisDist;
closestPoint = i;
}
}
function calcDistance(coord1, coord2) {
var distX = coord2[0] - coord1[0];
var distY = coord2[1] - coord1[1];
return Math.sqrt(distX * distX + distY * distY);
}
return closestPoint
}
function redraw() {
voronoiPoints = randomPoints(polygonCount);
steps = 0;
polygons.data(voronoi(voronoiPoints).polygons())
.attr("points", function(d) {return d})
centroids.data(voronoiPoints)
.attr("x", function(d) {return d[0]})
.attr("y", function(d) {return d[1]})
d3.select("#steps").html(" - Iteration: " + steps)
groupPoints();
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.