D3-voronoi.clipCircle() - 2nd experiment

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:

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;
    }

.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 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