Skip to content

Instantly share code, notes, and snippets.

@oliverheilig

oliverheilig/README.md

Last active February 6, 2016 07:34
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 oliverheilig/c9f3c5f7ba8c975b06e4 to your computer and use it in GitHub Desktop.
Save oliverheilig/c9f3c5f7ba8c975b06e4 to your computer and use it in GitHub Desktop.
Download ZIP
Voronoi Territories
Raw
README.md

A visualization for the assignment of points to territories using voronoi cells.

This is done by visually merging the voronoi cells and clipping them with circluar buffers around the point. It's an alternative to the visualization with a convex hull around each particular point set, as it generates a partitioning without overlappings. You can view this sample on a map here.

I'm using Mike Bostock's wonderful D3 library to create the SVG. But rather than calculating the voronois with D3's function, i'm utilizing Raymond Hill's JavaScript implementation, as i couldn't find a way to get the corresponding regions for a cell edge. After finishing, i found that D3 allows the creation of TopoJson fom a vonoroi.topology, which may provide a more elegant way.

Grabbed the initial snippet here, colors by Cynthia Brewer.

Raw
index.html
<html>
<head>
<script type="text/javascript" src="https://d3js.org/d3.v3.min.js"></script>
<script type="text/javascript" src="https://oliverheilig.github.io/Javascript-Voronoi/rhill-voronoi-core.min.js"></script>
</head>
<body>
<div id="chart">
</div>
<script type="text/javascript">
var w = 960,
h = 500,
count = 200,
border = 55,
radius = 50,
strokeWidth = 2;
var types = ["#7fc97f", "#beaed4", "#fdc086", "#ffff99"];
// create some (not completely) random points and assignments
var vertices = d3.range(count).map(function (d, i) {
var a = Math.random();
var type = Math.floor(types.length * a);
var b = Math.pow(Math.random(), 0.75);
var r = Math.random();
var x = Math.cos(a * 2 * Math.PI + r) * b * 0.5;
var y = Math.sin(a * 2 * Math.PI + r) * b * 0.5;
return {
id: i, x: w/2 + x * (w-2*border) , y: h/2 + y*(h-2*border),
type: types[type]
};
});
// setup the SVG stuff
var svg = d3.select("#chart")
.append("svg:svg")
.attr("width", w)
.attr("height", h);
var paths, points, clips, borders, inner1, inner2;
outerBorders = svg.append("svg:g").attr("id", "point-borders");
clips = svg.append("svg:g").attr("id", "point-clips");
paths = svg.append("svg:g").attr("id", "point-paths");
inner1 = svg.append("svg:g").attr("id", "inner-borders1");
inner2 = svg.append("svg:g").attr("id", "inner-borders2");
points = svg.append("svg:g").attr("id", "points");
// create the voronoi diagram
var vorolib = new Voronoi();
var bbox = { xl: 0, xr: w, yt: 0, yb: h };
var voronoi = vorolib.compute(vertices, this.bbox);
// the inner edges are voronoi edges that have differently assigned sites
var innerEdges = [];
for (var i = 0; i < voronoi.edges.length; i++) {
var e = voronoi.edges[i];
if (e.lSite && e.rSite && e.lSite.type !== e.rSite.type)
innerEdges.push(e);
}
// create circles that render the outer border
outerBorders.selectAll("circle")
.data(vertices)
.enter().append("svg:circle")
.attr("transform", function (d) { return "translate(" + d.x + "," + d.y + ")"; })
.attr("r", radius + strokeWidth)
.attr('stroke', 'none')
.style('fill', 'black');
// create the circles as clip paths
clips.selectAll("clipPath")
.data(vertices)
.enter().append("svg:clipPath")
.attr("id", function (d, i) { return "clip-" + d.id; })
.append("svg:circle")
.attr('cx', function (d) { return d.x; })
.attr('cy', function (d) { return d.y; })
.attr('r', radius);
// create the (clipped) cells, don't render the edges
paths.selectAll("path")
.data(voronoi.cells)
.enter().append("svg:path")
.attr("d", function (d) {
var coords = [];
var v = d.halfedges[0].getStartpoint();
coords.push([v.x, v.y]);
for (var i = 0; i < d.halfedges.length; i++) {
v = d.halfedges[i].getEndpoint();
coords.push([v.x, v.y]);
}
return "M" + coords.join(",") + "Z";
})
.attr("id", function (d) { return "path-" + d.site.id; })
.attr("clip-path", function (d) { return "url(#clip-" + d.site.id + ")"; })
.style("fill", function (d) { return d.site.type; })
.style("stroke", function (d) { return d.site.type; });
// some interaction on the cells
paths.selectAll("path")
.on("mouseover", function (d, i) {
d3.select(this)
.style('fill', d3.rgb(164, 164, 164));
})
.on("mouseout", function (d, i) {
d3.select(this)
.style("fill", d.site.type);
});
// create the edges clipped against the circle of the left site
inner1.selectAll("line")
.data(innerEdges)
.enter().append("line")
.attr("x1", function (d) { return d.va.x; })
.attr("y1", function (d) { return d.va.y; })
.attr("x2", function (d) { return d.vb.x; })
.attr("y2", function (d) { return d.vb.y; })
.attr("clip-path", function (d, i) { return "url(#clip-" + d.lSite.id + ")"; })
.style("stroke-width", strokeWidth)
.style("stroke-linecap", "round")
.style("stroke", "black");
// create the edges clipped against the circle of the right site
inner2.selectAll("line")
.data(innerEdges)
.enter().append("line")
.attr("x1", function (d) { return d.va.x; })
.attr("y1", function (d) { return d.va.y; })
.attr("x2", function (d) { return d.vb.x; })
.attr("y2", function (d) { return d.vb.y; })
.attr("clip-path", function (d, i) { return "url(#clip-" + d.rSite.id + ")"; })
.style("stroke-width", strokeWidth)
.style("stroke-linecap", "round")
.style("stroke", "black");
// create the points
points.selectAll("circle")
.data(vertices)
.enter().append("svg:circle")
.attr("transform", function (d) { return "translate(" + d.x + "," + d.y + ")"; })
.attr("r", 3)
.style("fill", function (d) { return d.type; })
.attr('stroke', 'black');
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment