path for Distance-limited Voronoi cell

This block is a continuation on my reflexions on Distance-Limited Vornoi Interaction (see 2, and 1).

This block experiments how to compute the path of a distance limited vironoï cell, which is the intersection area of a d3 Voronoï cell and a circle.

Acknowledgments to:

D3.js (v3.5.5)
blockbuilder.org

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }
  
  .seed {
    fill: grey;
    stroke: black;
  }
  
  .seed.draggable:hover, .seed.dragging {
    cursor: all-scroll;
  }
  
  .radius {
    fill: pink;
    stroke: red;
  }
  
  .radius.draggable:hover, .radius.dragging {
    cursor: ew-resize;
  }
  
  .max-cell-distance {
    fill: none;
    stroke: pink;
  }

.cell {
    fill: none;
    stroke: lightBlue;
  }
  
  .limited-cell {
    fill: lightBlue;
    stroke: lightBlue
  }

</style>
<body>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
	<script src="https://d3js.org/d3.v3.min.js"></script>
  
  <script>
    var margin = {left: 20, top: 20, right: 20, bottom: 20},
        legendHeight = 20,
				width = 960 - margin.left - margin.right,
        height = 500 - margin.top - legendHeight - margin.bottom;
    var seedCount = 5;
    var seeds = d3.range(seedCount).map(function(d,i) {
      return [width/2+150*Math.cos(d*2*Math.PI/seedCount),
              height/2+150*Math.sin(d*2*Math.PI/seedCount)];
    });
    seeds[0] = [width/2, height/2];
    var xAccessor = function(d) { return d[0]; };
    var yAccessor = function(d) { return d[1]; };
    var maxCellDistance = 100;
    
    //begin: drag behaviors
    var dragSeed = d3.behavior.drag()
      .origin(function(d) { return d; })
      .on("dragstart", dragStarted)
      .on("drag", seedDragged)
      .on("dragend", dragEnded);
    
    var dragRadius = d3.behavior.drag()
      .origin(function(d) { return d; })
      .on("dragstart", dragStarted)
      .on("drag", radiusDragged)
      .on("dragend", dragEnded);
    //end: drag behaviors
    
    //begin: define and compute voronoi layout
    var voronoi = d3.geom.voronoi()
      .x(xAccessor)
      .y(yAccessor)
      .clipExtent([[0, 0], [width, height]]);
    
    var voronoiLayout, cellOfConcern;
    (updateVoronoiLayout = function() {
      voronoiLayout = voronoi(seeds);
      cellOfConcern = voronoiLayout[0];
    })()
    //end: define and compute voronoi layout
    
    var svg = d3.select("body").append("svg")
      .attr("width", width + margin.left + margin.right)
      .attr("height", height + margin.top + legendHeight + margin.bottom);
    
    var drawingArea = svg.append("g").attr("transform", "translate("+[margin.left,margin.top]+")");
    
    //begin: redraw()
    (redraw = function () {
      // draw cells of the voronoi layout in lightblue dashed
      var drawnCells = drawingArea.selectAll(".cell")
        .data(voronoiLayout);
      drawnCells.enter()
        .append("path")
          .classed("cell", true);
      drawnCells.attr("d", function(d) { return d3.svg.line()(d)+"z" });
      
      // draw distance limited vornoi cell in lightgrey
      var drawnLimitedCell = drawingArea.selectAll(".limited-cell")
        .data([cellOfConcern]);
      drawnLimitedCell.enter()
        .append("path")
          .classed("limited-cell", true);
      drawnLimitedCell.attr("d", function(d) { return distanceLimitedCell(d, maxCellDistance) });
      
			// draw circle representing max distance
      var drawnMaxCellDistance = drawingArea.selectAll(".max-cell-distance")
        .data([cellOfConcern]);
      drawnMaxCellDistance.enter()
        .append("circle")
          .classed("max-cell-distance", true);
      drawnMaxCellDistance.attr({
        cx: function(d) { return xAccessor(d.point); },
        cy: function(d) { return yAccessor(d.point); },
        r: maxCellDistance
      });
      
      // draw seeds
      var drawnSeeds = drawingArea.selectAll(".seed")
        .data(seeds);
      drawnSeeds.enter()
        .append("circle")
          .classed("seed draggable", true)
          .attr("r", 4)
          .call(dragSeed);
      drawnSeeds.attr({
        cx: function(d) { return xAccessor(d); },
        cy: function(d) { return yAccessor(d); }
      });
			
      // draw max distance anchor
      var drawnRadius = drawingArea.selectAll(".radius")
        .data([cellOfConcern]);
      drawnRadius.enter()
        .append("circle")
          .classed("radius draggable", true)
          .attr("r", 4)
          .call(dragRadius);
      drawnRadius.attr({
        cx: function(d) { return xAccessor(d.point)+maxCellDistance; },
        cy: function(d) { return yAccessor(d.point); }
      });
    })()
    //end: redraw()
    
    insertLegend();
    
    ////////////////////////
    // bl.ocks' utilities //
    ////////////////////////
    
    function dragStarted(d) {
      d3.select(this).classed("dragging", true);
    }

function dragEnded(d) {
      d3.select(this).classed("dragging", false);
    }

function seedDragged(d) {
      d[0] += d3.event.dx;
      d[1] += d3.event.dy;
      updateVoronoiLayout();
      redraw();
    }

return path;
      }
      
      function allVertecesInsideMaxDistanceCircle (cell, seed, r) {
        var result = true;
        var p;
        for (var ip=0; ip<cell.length; ip++) {
          result &= !pointTooFarFromSeed(cell[ip], seed, r);
        }
        return result;
      }
      
      function pointTooFarFromSeed(p, seed, r) {
        return (Math.pow(p[0]-seed[0],2)+Math.pow(p[1]-seed[1],2)>Math.pow(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
        
        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>
</body>

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