Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active January 27, 2017 16:56
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 Kcnarf/04eed6cd1dab08f2738d0787931f4a22 to your computer and use it in GitHub Desktop.
Save Kcnarf/04eed6cd1dab08f2738d0787931f4a22 to your computer and use it in GitHub Desktop.
Download ZIP
D3-voronoi.clipCircle()
Raw
.block
license: lgpl-3.0
Raw
README.md

This block experiments how to programmatically circle-clip a Voronoï tessellation, and does not rely on the browser to do the clipping in the screen space. This block follows the work done by Philippe Riviere in its Circular Bounded Voronoi Tessellation. Another experimentation is available in this block.

By default, d3.voronoi comes with a rectangular clipping, through the d3-voronoi.extent() API. This block shows another way to clip the initial tesselation.

The algorithm used in this block is basically a copy/paste of the algorithm used in the d3.distanceLimitedVoronoi d3 plugin I made. The two algorithms have distinct purposes: the plugin leverages UX by defining [interactive and not-too-far] areas around each site, whereas this block define a global clipping.

Acknowledgments to:

Raw
index.html
<!DOCTYPE html>
<title>d3-voronoi.clipCircle</title>
<meta content="Circle-clipping a Voronoï tesselation" name="description">
<meta charset="utf-8">
<style>
.polygons {
stroke-width: 1;
}
.polygons path {
fill-opacity: 0.4;
stroke-opacity: 0.8;
}
.polygons :first-child {
fill: red;
fill-opacity: 1;
}
.sites {
fill: grey;
stroke: none;
}
.sites :first-child {
fill: white;
}
p {
position: absolute;
bottom: 10px;
right: 10px;
color: lightgrey;
text-align: end;
}
</style>
<svg width="960" height="500"></svg>
<p>
Drag your mouse to see the clipping in action.
</p>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
<script>
//begin: layout conf.
var svg = d3.select("svg"),
margin = {top: 10, right: 10, bottom: 10, left: 10},
svgWidth = +svg.attr("width"),
svgHeight = +svg.attr("height"),
width = svgWidth - margin.left - margin.right,
height = svgHeight - margin.top - margin.bottom,
size = Math.min(width, height),
sitesMargin = 10;
//end: layout conf.
var drawingArea, d3sPolygons, d3sSites; // d3s... means 'd3 selection'
initLayout();
//Voronoï layout definition
var voronoi = d3.voronoi()
.extent([[-1, -1], [width + 1, height + 1]]);
//definition of the clipping circle
var clippingCircle = {
cx: width/2,
cy: height/2,
r: size/2
}
var color = d3.scaleOrdinal(d3.schemePastel1),
line = d3.line().curve(d3.curveCatmullRomClosed);
var sites = d3.range(100)
.map(function(d, i) {
var len = (clippingCircle.r - sitesMargin) * Math.sqrt(Math.random()),
angle = Math.random() * 2 * Math.PI;
return [
clippingCircle.cx + len * Math.cos(angle),
clippingCircle.cy + len * Math.sin(angle)
];
});
redraw();
function moved() {
coord = d3.mouse(this);
sites[0] = [coord[0]-margin.top, coord[1]-margin.left];
redraw();
}
function initLayout() {
svg.on("touchmove mousemove", moved)
drawingArea = svg.append("g")
.attr("transform", "translate("+[margin.left, margin.top]+")");
d3sPolygons = drawingArea.append("g")
.attr("class", "polygons");
d3sSites = drawingArea.append("g")
.attr("class", "sites");
}
function redraw() {
var diagram = voronoi(sites);
var p = d3sPolygons.selectAll("path")
.data(diagram.polygons());
p.enter().append("path")
.attr("fill", function(d,i) { return color(i); })
.merge(p)
.call(redrawPolygon)
p.exit().remove();
var s = d3sSites.selectAll("circle")
.data(sites);
s.enter().append("circle")
.attr("r", 2.5)
.merge(s)
.call(redrawSite);
}
function redrawPolygon(polygon) {
polygon
.attr("fill", function(d, i) { return color(i); })
.attr("stroke", function(d, i) { return color(i); })
.attr("d", function(d) { return clipCell(d, clippingCircle) });
}
function redrawSite(site) {
site
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
}
/////////////////////
// Clipping of the //
// Voronoi layout //
/////////////////////
function clipCell (cell, clippingCircle) {
var clippingCenter = [clippingCircle.cx, clippingCircle.cy];
var r = clippingCircle.r;
if (allVertecesInsideClippingCircle(cell, clippingCircle)) {
return "M"+cell.join("L")+"Z";
} else {
var path = "";
var p0TooFar = firstPointTooFar = pointTooFarFromClippingCircle(cell[0], clippingCircle);
var p0, p1, intersections;
var openingArcPoint, lastClosingArcPoint;
//begin: loop through all segments to compute path
for (var iseg=0; iseg<cell.length; iseg++) {
p0 = cell[iseg];
p1 = cell[(iseg+1)%cell.length];
// compute intersections between segment and maxDistance circle
intersections = segmentCircleIntersections (p0, p1, clippingCenter ,r);
// complete the path (with lines or arc) depending on:
// intersection count (0, 1, or 2)
// if the segment is the first to start the path
// if the first point of the segment is inside or outside of the maxDistance circle
if (intersections.length===2) {
if (p0TooFar) {
if (path==="") {
// entire path will finish with an arc
// store first intersection to close last arc
lastClosingArcPoint = intersections[0];
// init path at 1st intersection
path += "M"+intersections[0];
} else {
//close arc at first intersection
path += largeArc(openingArcPoint, intersections[0], clippingCenter)+" 0 "+intersections[0];
}
// then line to 2nd intersection, then initiliaze an arc
path += "L"+intersections[1];
path += "A "+r+" "+r+" 0 ";
openingArcPoint = intersections[1];
} else {
// THIS CASE IS IMPOSSIBLE AND SHOULD NOT ARISE
console.error("What's the f**k");
}
} else if (intersections.length===1) {
if (p0TooFar) {
if (path==="") {
// entire path will finish with an arc
// store first intersection to close last arc
lastClosingArcPoint = intersections[0];
// init path at first intersection
path += "M"+intersections[0];
} else {
// close the arc at intersection
path += largeArc(openingArcPoint, intersections[0], clippingCenter)+" 0 "+intersections[0];
}
// then line to next point (1st out, 2nd in)
path += "L"+p1;
} else {
if (path==="") {
// init path at p0
path += "M"+p0;
}
// line to intersection, then initiliaze arc (1st in, 2nd out)
path += "L"+intersections[0];
path += "A "+r+" "+r+" 0 ";
openingArcPoint = intersections[0];
}
p0TooFar = !p0TooFar;
} else {
if (p0TooFar) {
// entire segment too far, nothing to do
} else {
// entire segment in maxDistance
if (path==="") {
// init path at p0
path += "M"+p0;
}
// line to next point
path += "L"+p1;
}
}
}//end: loop through all segments
if (path === '') {
// special case: no segment intersects the clipping circle
// cell perimeter is entirely outside the clipping circle
// path is empty
path = "M"+[clippingCenter[0]+r,clippingCenter[1]];
} else {
// if final segment ends with an opened arc, close it
if (firstPointTooFar) {
path += largeArc(openingArcPoint, lastClosingArcPoint, clippingCenter)+" 0 "+lastClosingArcPoint;
}
path+="Z";
}
return path;
}
function allVertecesInsideClippingCircle (cell, clippingCircle) {
var result = true;
var p;
for (var ip=0; ip<cell.length; ip++) {
result &= !pointTooFarFromClippingCircle(cell[ip], clippingCircle);
}
return result;
}
function pointTooFarFromClippingCircle(p, clippingCircle) {
return (Math.pow(p[0]-clippingCircle.cx,2)+Math.pow(p[1]-clippingCircle.cy,2)>Math.pow(clippingCircle.r, 2));
}
function largeArc(p0, p1, seed) {
var v1 = [p0[0] - seed[0], p0[1] - seed[1]],
v2 = [p1[0] - seed[0], p1[1] - seed[1]];
// from http://stackoverflow.com/questions/2150050/finding-signed-angle-between-vectors
var angle = Math.atan2( v1[0]*v2[1] - v1[1]*v2[0], v1[0]*v2[0] + v1[1]*v2[1] );
return (angle<0)? 0 : 1;
}
};
function segmentCircleIntersections (A, B, C, r) {
/*
from http://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm
*/
var Ax = A[0], Ay = A[1],
Bx = B[0], By = B[1],
Cx = C[0], Cy = C[1];
// compute the euclidean distance between A and B
LAB = Math.sqrt(Math.pow(Bx-Ax, 2)+Math.pow(By-Ay, 2));
// compute the direction vector D from A to B
var Dx = (Bx-Ax)/LAB;
var Dy = (By-Ay)/LAB;
// Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1.
// compute the value t of the closest point to the circle center (Cx, Cy)
var t = Dx*(Cx-Ax) + Dy*(Cy-Ay);
// This is the projection of C on the line from A to B.
// compute the coordinates of the point E on line and closest to C
var Ex = t*Dx+Ax;
var Ey = t*Dy+Ay;
// compute the euclidean distance from E to C
var LEC = Math.sqrt(Math.pow(Ex-Cx, 2)+Math.pow(Ey-Cy, 2));
// test if the line intersects the circle
if( LEC < r )
{
// compute distance from t to circle intersection point
var dt = Math.sqrt(Math.pow(r, 2)-Math.pow(LEC, 2));
var tF = (t-dt); // t of first intersection point
var tG = (t+dt); // t of second intersection point
var result = [];
if ((tF>0)&&(tF<LAB)) { // test if first intersection point in segment
// compute first intersection point
var Fx = (t-dt)*Dx + Ax;
var Fy = (t-dt)*Dy + Ay;
result.push([Fx, Fy])
}
if ((tG>0)&&(tG<LAB)) { // test if second intersection point in segment
// compute second intersection point
var Gx = (t+dt)*Dx + Ax;
var Gy = (t+dt)*Dy + Ay;
result.push([Gx, Gy])
}
return result;
} else {
// either (LEC === r), tangent point to circle is E
// or (LEC < r), line doesn't touch circle
// in both cases, returning nothing is OK
return [];
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment