Skip to content

Instantly share code, notes, and snippets.

Last active July 28, 2016 22:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alexmacy/611e234e0132dfc5789a3a66cf4c2073 to your computer and use it in GitHub Desktop.
Save alexmacy/611e234e0132dfc5789a3a66cf4c2073 to your computer and use it in GitHub Desktop.
Voronoi Sorting
license: gpl-3.0

This is an experiment with sorting the polygons of a voronoi diagram. They sort on a logarithmic scale because a linear scale was causing them to cluster all to one side in a progressively more compact way. The sorting is by the area of the shape - which is also represented by color. After moving to the new location, the sort is re-calculated based on the new shapes and the shapes move again. This was the result of reading Mike Bostock's article on Visualizing Algorithms.

The previous versions are here: Voronoi Shuffling v1, Voronoi Shuffling v2, & Voronoi Shuffling v3

<!DOCTYPE html>
<meta charset="utf-8">
body {
margin: 0;
path {
fill-opacity: .75;
stroke: black;
<script src="//"></script>
var width = window.innerWidth,
height = window.innerHeight,
samples = [];
var voronoi = d3.voronoi()
.size([width, height])
//the size of the polygon will determine it's fill color - and later, it's placement along the x axis
var color = d3.scaleSequential(d3.interpolateCubehelixDefault),
x = d3.scaleLog().range([0,width]);
var svg ="body").append("svg")
.attr("width", width)
.attr("height", height)
var paths = svg.selectAll("path")
paths.attr("transform", "translate(0,0)")
.style("fill", function(d, i) {return color(samples[i].area); })
.attr("d", function(d, i) {return getPath(samples[i].sample); })
function getData() {
//if loading data for the first time, generate an array of random coordinates
if (!samples.length) {
for (i=0; i<500; i++) {samples[i] = [Math.random() * width, Math.random() * height];}
//otherwise, update the x coordinate based on the polygon's size
} else {
for (i in samples) {samples[i] = [x(samples[i].area), samples[i].point[1]];}
//create new polygons and bind them and their calculated area to the main data array
var voronoiData = voronoi(samples).polygons();
for (i in voronoiData) {
samples[i] = {
point: samples[i],
sample: voronoiData[i],
area: d3.polygonArea(voronoiData[i]),
//set the domain of the scales by finding the min and max area values
var minMax = d3.extent(samples, function(d) {return d.area;});
//create the paths for the polygons
function getPath(points) {
//redrawing the polygons was causing some unwanted effects when transitioning a polygon to a new shape that has more sides. this was because the new points would be drawn off screen before transitioning into place.
//my solution was to default each polygon to having more points than (hopefully) necessary, with the extra points placed on top of each other. this is potentially not performant as it creates multiple points in the same location.
var thisPath = "M" + points[0];
for (n=1; n<15; n++) {
thisPath += "L" + (n < points.length ? points[n] : points[0])
return thisPath;
var sortShapes = function() {
//slide the polygons into order of size along the x-axis according to the log scale
.attr("transform", function(d, i) { return "translate(" + (-samples[i].point[0] + x(samples[i].area)) + ",0)"})
//re-calculate the voronoi polygons and their sizes based on the new positions
//transition to the new sizes and shapes
.attr("transform", "translate(0,0)")
.attr("d", function(d, i) {return getPath(samples[i].sample);})
.style("fill", function(d, i) {return color(samples[i].area);})
//loop the sorting process
d3.timeout(sortShapes, 6000);
d3.timeout(sortShapes, 2000);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment