D3-voronoi.clipCircle()

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:

D3.js (v4)
blockbuilder.org

<!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 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 https://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 https://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

</script>

https://d3js.org/d3.v4.min.js

https://d3js.org/d3-scale-chromatic.v1.min.js