Skip to content

Instantly share code, notes, and snippets.

@Kcnarf

Kcnarf/.block

Last active January 29, 2017 20:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kcnarf/e062012f6f08d6e987302aa5a5919bf0 to your computer and use it in GitHub Desktop.
Save Kcnarf/e062012f6f08d6e987302aa5a5919bf0 to your computer and use it in GitHub Desktop.
Download ZIP
D3-voronoi.clipCircle() - 2nd experiment
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. It is a is a continuation of a previous one, and follows the work done by Philippe Riviere in its Circular Bounded Voronoi Tessellation.

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;
}
.sites {
fill: grey;
stroke: none;
}
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/4
}
var color = d3.scaleOrdinal(d3.schemePastel1),
line = d3.line().curve(d3.curveCatmullRomClosed);
var sites = d3.range(100)
.map(function(d, i) {
return [
sitesMargin + (width-2*sitesMargin)*Math.random(),
sitesMargin + (height-2*sitesMargin)*Math.random()
];
});
var polygons = voronoi(sites).polygons();
redraw();
function moved() {
coord = d3.mouse(this);
clippingCircle.cx = coord[0]-margin.left;
clippingCircle.cy = coord[1]-margin.right;
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 p = d3sPolygons.selectAll("path")
.data(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