Voronoï playground : interactive weighted Voronoï study II

This block experiments weighted Voronoï diagram, and is a continuation of a previous block. Weighted Voronoï diagram comes in severall flavours (additive/multiplicative, powered/not-powered, 2D/3D and highier dimensions, ...), but this block focuses on the 2D additive weighted power diagram, which provides a tessellation made of concave polygons/cells with straight borders, as the default Voronoï diagram does.

What are you seeing ?

there is 2 sites (one blue and one green), with their corresponding influence areas (i.e. cells)
if weights are big enough, circles around sites give a sense of the weight of each site

User interactions :

you can change the weight of each site with the corresponding slider
you can drag and drop each site

Code details :

Code essentially comes from mkedwards's block: Treemap, which is an implementation of the technique describe in Computing Voronoi Treemaps : Faster, Simpler, and Resolution-independent. I extracted the code which produces the power diagram, and updated it for D3v4:

reuse ConvexHull.js,
reuse PowerDiagram.js,
remove VoronoiTreemap.js,
remove VoronoiTreemapD3.js,
remove Vertex's percentage,
dummy bounding sites related to clipping polygon (ie. available area), instead of depending on extremes sites
in linearDependant function, bug fix p1.x==0 || p2.x==0 (insteaf of p1.x==0 || p1.x==0)
add epsilonesque function
rename GraphEdge as ConflictListNode

Furthermore, as d3 v4 no longer provides polygon clipping, code for polygon clipping comes from mbostock's block: Polygon Clipping III, which he introduces as 'a trivial port of Sutherland–Hodgman clipping from v3'.

For a more up-to-date version of the code, please refer to the [Weighted Voronoi Treemap in D3v4] (https://bl.ocks.org/kcnarf/15d54f4ccae6a3710cd3029546664eec) block.

Acknowledgments to:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>Voronoï playground : interactive weighted Voronoï study II</title>
    <meta name="description" content="Weighted Voronoï in D3.js">
    <script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
    <script language="javascript" type="text/javascript" src="ConvexHull.js"></script>
    <script language="javascript" type="text/javascript" src="PowerDiagram.js"></script>
    <script language="javascript" type="text/javascript" src="d3-polygon-clip.js"></script>
    <style>
      #wip {
        display: none;
        position: absolute;
        top: 200px;
        left: 330px;
        font-size: 40px;
        text-align: center;
      }

.control {
        position: absolute;
        top: 5px;
      }
      .control#control-0 {
        left: 5px;
      }
      .control#control-1 {
        right: 5px;
      }
      .control input {
        width: 400px;
      }

#drawing-area.dragging {
        cursor: move;
      }

#site-container {
        clip-path: url("#clipper");
      }
      .seed {
        fill: steelBlue;
      }
      .seed.dragging, .seed:hover {
        fill: pink;
        cursor: move;
      }
      .seed#seed-1 {
        fill: green;
      }
      .seed#seed-1.dragging, .seed#seed-1:hover {
        fill: pink;
        cursor: move;
      }
      .unit-circle {
        fill: none;
        stroke: lightsteelBlue;
      }
      .unit-circle#unit-circle-1 {
        stroke: lightgreen;
      }

.cell {
        fill-opacity: 0.1;
        fill: lightsteelBlue;
        stroke: lightsteelBlue;
      }
      .cell#cell-1 {
        fill: lightgreen;
        stroke: lightgreen;
      }
    </style>
  </head>
  <body>
    <div id="control-0" class="control">
      Blue site's weight :
      <form>
        <input id="weight" type="range" name="points" min="-10000" max="100000" value="0" oninput="weightUpdated()">
      </form>
    </div>
    <div id="control-1" class="control">
      Green site's weight :
      <form>
        <input id="weight" type="range" name="points" min="-10000" max="100000" value="0" oninput="weightUpdated()">
      </form>
    </div>

<div id="wip">
      Work in progress ...
    </div>
  </body>

//begin: layout conf.
    var svgWidth = 960,
        svgHeight = 500,
        margin = {top: 40, right: 10, bottom: 10, left: 10},
        width = svgWidth - margin.left - margin.right,
        height = svgHeight - margin.top - margin.bottom,
        halfWidth = width/2,
        halfHeight = height/2,
        quarterWidth = width/4,
        quarterHeight = height/4;
    //end: layout conf.

//begin: voronoi stuff definitions
    var sites = [{index: 0, x: halfWidth-100, y: halfHeight, weight: 0},
                 {index: 1, x: halfWidth+100, y: halfHeight, weight: 0}];
    var clippingPolygon = [[0,0], [0,height], [width,height], [width,0]];
    var cells = [[], []];					// stores, for each site, each cell's verteces
    //end: voronoi stuff definitions

//begin: utilities
    function uc(w) { return (w<=0)? 0 : Math.sqrt(w); }	//scale for unit-circles
    var cellLiner = d3.line()
    .x(function(d){ return d[0]; })
    .y(function(d){ return d[1]; });
    //end: utilities

//begin: reusable d3-selections
    var svg = d3.select("svg"),
        clipper = d3.select("#clipper>rect"),
        drawingArea = d3.select("#drawing-area"),
        cellContainer = d3.select("#cell-container"),
        siteContainer = d3.select("#site-container");
    //end: reusable d3-selections

//begin: user interaction handlers
    function weightUpdated() {
      var newWeights = [],
          index;
      newWeights[0] = +d3.select("#control-0 input").node().value;
      newWeights[1] = +d3.select("#control-1 input").node().value;
      if (newWeights[0] !== sites[0].weight) {
        index = 0;
      } else {
        index = 1;
      }

sites[index].weight = newWeights[index];
      computeAllCells();

redrawAllCells(WITHOUT_TRANSITION);
      redrawUnitCircle(index, WITHOUT_TRANSITION);
      redrawWeights(index);
    }

var dragSite = d3.drag()
    .subject(function(d) { return d; })
    .container(drawingArea.node())
    .on("start", dragStarted)
    .on("drag", draggingSite)
    .on("end", dragEnded);

function dragStarted(d) {
      d3.select(this).classed("dragging", true);
      drawingArea.classed("dragging", true);
    }

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

function draggingSite(d) {
      var newX = Math.round(d3.event.x),
          newY = Math.round(d3.event.y);

if (newX!==d.x || newY!==d.y) {
        d.x = newX;
        d.y = newY;

computeAllCells();

redrawAllCells(WITHOUT_TRANSITION);
        redrawSite(d.index,WITHOUT_TRANSITION);
      }
    }
    //end: user interaction handlers

computeAllCells();
		initLayout();
    
    redrawAllCells(WITHOUT_TRANSITION);
    redrawAllUnitCircles(WITHOUT_TRANSITION);
    redrawAllWeights();
    redrawAllSites(WITHOUT_TRANSITION);

/***************/
    /* Computation */
    /***************/

function computeAllCells() {
      //begin: map sites to the expected format of PowerDiagram
      var formatedSites = sites.map(function(s) {
        return new Vertex(s.x, s.y, null, s.weight, s, false);
      })
      var boundingSites  = getBoundingSites();
      //end: map sites to the expected format of PowerDiagram

cells = computePowerDiagramIntegrated(formatedSites, boundingSites, clippingPolygon);
    }

function getBoundingSites() {
      var siteBasedBounding = false;	// when activated (as done in original code), resulting clipping is weird: diamond-shaped clipping

var boundingSites = [],
          xExtent, yExtent,
          minX, maxX, minY, maxY,
          x0, x1, y0, y1;

if (siteBasedBounding) {
        xExtent = extent(sites.map(function(s) {return s.x;}));
        yExtent = extent(sites.map(function(s) {return s.y;}));
      } else {
        xExtent = [0,width];
        yExtent = [0,height];
      }

minX = xExtent[0];
      maxX = xExtent[1];
      minY = yExtent[0];
      maxY = yExtent[1];
      x0 = minX - maxX;
      x1 = 2 * maxX;
      y0 = minY - maxY;
      y1 = 2 * maxY;

var result = [];
      result[0] = [x0, y0];
      result[1] = [x0, y1];
      result[2] = [x1, y1];
      result[3] = [x1, y0];

for (var i = 0; i < result.length; i++){
        boundingSites.push( new Vertex(result[i][0], result[i][1], null, epsilon, new Vertex(result[i][0], result[i][1], null, epsilon, null, true), true));
      }

return boundingSites;
    }

/***********/
    /* Drawing */
    /***********/

function redrawAllSites(withTransition) {
      redrawSite(0, withTransition);
      redrawSite(1, withTransition);
    }

//redraw site = place site at adequate position
    function redrawSite(index, withTransition) {
      d3.select("#site-"+index).transition()
        .duration(withTransition? duration : 0)
        .attr("transform", function(d){ return "translate("+[d.x,d.y]+")"; });
    }

function redrawAllWeights() {
      redrawWeights(0);
      redrawWeights(1);
    }

// redraw site's weight = update text
    function redrawWeights(index) {
      d3.select("#weight-"+index)
        .text(function(d){  return "weight: " +d.weight; })
    }

function redrawAllUnitCircles() {
      redrawUnitCircle(0);
      redrawUnitCircle(1);
    }

// redraw site's unit circle = update radius
    function redrawUnitCircle(index, withTransition) {
      d3.select("#unit-circle-"+index).transition()
        .duration(withTransition? duration : 0)
        .attr("r", function(d){  return uc(d.weight); })
    }

function initLayout () {
      svg.attr("width", svgWidth)
        .attr("height", svgHeight);

clipper.attr("x", 0)
        .attr("y", 0)
        .attr("width", width)
        .attr("height", height);

drawingArea.attr("width", width)
        .attr("height", height)
        .attr("transform", "translate("+[margin.left, margin.top]+")");

//begin: draw sites
      var drawnSites = siteContainer.selectAll(".site")
      .data(sites)
      .enter()
      .append("g")
      .attr("id", function(d){ return "site-"+d.index})
      .classed("site", true);
      drawnSites.append("circle")
        .attr("id", function(d,i){ return "unit-circle-"+i; })
        .classed("unit-circle", true)
      drawnSites.append("text")
        .attr("id", function(d,i){ return "weight-"+i; })
        .attr("transform", "translate("+[0,15]+")")
        .attr("text-anchor", "middle");
      drawnSites.append("circle")
        .attr("id", function(d,i){ return "seed-"+i; })
        .classed("seed", true)
        .attr("r", 4)
        .call(dragSite);
      //end: draw sites

//begin: draw cells
      cellContainer.selectAll(".cell")
        .data(cells)
        .enter()
        .append("path")
        .classed("cell", true)
        .attr("id", function(d){ return "cell-"+d.site.originalObject.index; });
      //end: draw cells
    }
  </script>
</html>

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