Skip to content

Instantly share code, notes, and snippets.

@zanarmstrong

zanarmstrong/index.html

Last active September 26, 2018 18:53
Show Gist options
  • Save zanarmstrong/b1c051113be144570881 to your computer and use it in GitHub Desktop.
Save zanarmstrong/b1c051113be144570881 to your computer and use it in GitHub Desktop.
Download ZIP
Exploring Voronoi polygons, Delaunay triangles, and circumcircles
Raw
index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Exploring Voronoi</title>
<link href='http://fonts.googleapis.com/css?family=Raleway' rel='stylesheet' type='text/css'>
<script type="text/javascript" src="datgui-min.js"></script>
<link rel="stylesheet" href="voronoi.css">
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8"></script>
</head>
<body>
<p id="instructions">Explore <a href="http://en.wikipedia.org/wiki/Voronoi_diagram">Voronoi diagrams</a> and <a href="http://en.wikipedia.org/wiki/Delaunay_triangulation">Delaunay triangulation</a>. <strong>Click to add dots.</strong> Drag dots to move them.</p>
<label id="form" for="show-voronoi" class="form">
<input type="checkbox" id="show-voronoi" checked>
Show Voronoi Polygons
</label>
<label id="form2" for="show-triangles" class="form">
<input type="checkbox" id="show-triangles" checked>
Show Delaunay Triangles
</label>
<label id="form3" for="show-circles" class="form">
<input type="checkbox" id="show-circles" checked>
Show Circles
</label>
<label id="form4" for="show-circleCenters" class="form">
<input type="checkbox" id="show-circleCenters">
Show Circle Centers
</label>
<section id="box" class="main">
</section>
<!-- call JS files -->
<script src="voronoi.js"></script>
</body>
</html>
Raw
voronoi.css
body {
font-family: 'Raleway', sans-serif;
}
label {
font-size: 16px;
}
@media(max-width:768px) {
label {
font-size: 12px;
}
}
@media(max-width:558px) {
label {
font-size: 8px;
}
}
.triangles {
stroke: blue;
fill: none;
}
.circles {
stroke: grey;
fill: none;
}
.circleCenters {
stroke: black;
stroke-width: 2px;
fill: white;
}
.voronoi {
stroke: red;
fill: none;
}
#form {
position: absolute;
top: 45px;
left: 82%;
}
#form2 {
position: absolute;
top: 85px;
left: 82%;
}
#form3 {
position: absolute;
top: 125px;
left: 82%;
}
#form4 {
position: absolute;
top: 165px;
left: 82%;
}
.hidden {
display: none;
}
Raw
voronoi.js
/*
to do:
Add css for p, shapes
Add mouseover to triangle/circle to show only triangle & circle & show circle's center?
Add mouseover to polygons to highlight that polygon & its dot?
*/
// so that touchmove is not scrolling
document.body.addEventListener('touchmove', function(event) {
event.preventDefault();
}, false);
var width = window.innerWidth * .8, height = width;
var endOfLastDrag = 0;
var svg = d3.select('body')
.append('svg')
.attr('width', width)
.attr('height', height)
svg.append('rect').attr({width: width, height: height, fill: "none", stroke: 'red'})
svg.on("click", function(){
// ignore click if it just happened
if(Date.now() - endOfLastDrag > 500){
updateDots(d3.mouse(this))
}
})
var myVoronoi = d3.geom.voronoi()
.x(function(d) {
return d[0];
})
.y(function(d) {
return d[1];
})
.clipExtent([[0, 0], [width, height]])
var show = {voronoi: true, triangles: true, circles: true, circleCenters: false}
// for now, easier to debug when element types are grouped
var voronoiG = svg.append("g");
var triangles = svg.append("g");
var circles = svg.append("g");
function updateDots(coord) {
if(coord){
var data = [coord];
} else {
var data = []
}
d3.selectAll(".dots")[0].forEach(function(d){data.push(d.__data__)})
dots = svg.selectAll(".dots").data(data);
dots.attr(dotsAttr);
dots.enter()
.append("circle")
.attr(dotsAttr)
.classed("dots", true)
.call(drag);
dots.exit().remove();
updateVoronoi(data);
}
function updateVoronoi(data) {
// voronoi
currentVoronoi = voronoiG
.selectAll(".voronoi")
.data(myVoronoi(data));
currentVoronoi
.classed("hidden", !show.voronoi)
.attr("d", function(d) {
if(typeof(d) != 'undefined'){
return "M" + d.join("L") + "Z"}
})
.datum(function(d) {
if(typeof(d) != 'undefined'){
return d.point;
}});
currentVoronoi.enter()
.append("path")
.attr("d", function(d) {
if(typeof(d) != 'undefined'){
return "M" + d.join("L") + "Z"}
})
.datum(function(d) {
if(typeof(d) != 'undefined'){
return d.point;
}})
.attr("class", "voronoi")
.classed("hidden", !show.voronoi);
currentVoronoi.exit().remove();
// triangles
var centerCircles = [];
myTriangles = triangles
.selectAll(".triangles")
.data(myVoronoi.triangles(data));
myTriangles
.attr("points", function(d){
centerCircles.push(findCenters(d)); return d.join(" ")
})
.classed("hidden", !show.triangles);
myTriangles
.enter()
.append("polygon")
.attr("points", function(d){
centerCircles.push(findCenters(d)); return d.join(" ")
})
.attr("class", "triangles")
.classed("hidden", !show.triangles);
myTriangles.exit().remove();
// circles
var myCircles = circles.selectAll(".circles")
.data(centerCircles)
myCircles
.enter()
.append("circle")
.attr(circleAttr)
.attr("class", "circles")
.classed("hidden", !show.circles);
myCircles
.attr(circleAttr)
.classed("hidden", !show.circles);
myCircles.exit().remove();
var circleCenters = circles.selectAll(".circleCenters")
.data(centerCircles)
circleCenters
.enter()
.append("circle")
.attr(circleAttrCenter)
.attr("class", "circleCenters")
.classed("hidden", !show.circleCenters);
circleCenters
.attr(circleAttrCenter)
.classed("hidden", !show.circleCenters);
circleCenters.exit().remove();
}
d3.select("#show-voronoi")
.on("change", function() {
show.voronoi = this.checked;
d3.selectAll(".voronoi").classed("hidden", !show.voronoi);
});
d3.select("#show-triangles")
.on("change", function() {
show.triangles = this.checked;
d3.selectAll(".triangles").classed("hidden", !show.triangles);
});
d3.select("#show-circles")
.on("change", function() {
show.circles = this.checked;
d3.selectAll(".circles").classed("hidden", !show.circles);
});
d3.select("#show-circleCenters")
.on("change", function() {
show.circleCenters = this.checked;
d3.selectAll(".circleCenters").classed("hidden", !show.circleCenters);
});
// circle attributes
var circleAttr = {cx: function(d){return d.cx},
cy: function(d){return d.cy},
r: function(d){return d.radius}}
var circleAttrCenter = {cx: function(d){return d.cx},
cy: function(d){return d.cy},
r: function(d){return 3}}
// dot attributes
var dotsAttr = {cx: function(d){return d[0]},
cy:function(d){return d[1]},
r: 5,
fill: "blue"}
// set up drag for circles
var drag = d3.behavior.drag()
.on("drag", dragmove);
function dragmove(d) {
d3.select(this)
.attr("cx", d3.event.x)
.attr("cy", d3.event.y);
this.__data__ = [d3.event.x, d3.event.y]
updateDots();
endOfLastDrag = Date.now();
}
// circumcenter equation from wikipedia: http://en.wikipedia.org/wiki/Circumscribed_circle
function findCenters(d) {
var a = d[0], b = d[1], c = d[2];
var k = 2 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]));
var cx = (smallCalc(a,b[1],c[1]) + smallCalc(b,c[1],a[1]) + smallCalc(c,a[1],b[1])) / k;
var cy = (smallCalc(a,c[0],b[0]) + smallCalc(b,a[0],c[0]) + smallCalc(c,b[0],a[0])) / k;
var radius = Math.sqrt(Math.pow(cx - a[0], 2) + Math.pow(cy - a[1], 2));
return {cx: cx, cy: cy, radius: radius}
}
// little helper so I don't have to write this over and over
function smallCalc(a,b,c){
return (a[0] * a[0] + a[1] * a[1]) * (b - c);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment