Voronoï playground : interactive weighted Voronoï study

This block experiments weighted Voronoï diagram. 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. It helps me to understand the basics (properties, underlying computations, meanings, ...) of such diagram.

From Wikipedia, the additively weighted power diagram is defined when positive weights are subtracted from the squared euclidian distances between points. The distance of a pixel from a site is the additive weighted power distance, further references as awp-distance. For any point of the 2D plan, the closest site is the one with the minimal awp-distance.

I choose this kind of weighted Voronoï diagram because the resulting tessellation is made of concave polygons/cells with straight borders, as the default Voronoï diagram does. Using non-squared distances results in hyperbolic borders.

What are you seeing ?

there is 2 sites (one blue and one green), with their corresponding influence areas (i.e. cells)
circles around sites are their respective unit-circles (awp-distance=1); they give a sense of the weight of each site
the matrix represents pixels and centers of pixels; for each pixel, I added the awp-distance from each site; if the awp-distance from the blue site is lower than the awp-distance from the green site, then the pixel is closer to the blue site and is part of the blue influence area (and vice-versa)

User interactions :

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

Unobvious things I've discovered :

the basic Voronoï diagram is obtained when all sites have the same weight; it could be 0 (default value used in Voronoï diagram algorithm), or anything else (you can experiment this by setting the exact same weight for the two sites; in this case, the border line remains at the center of the two sites)
when a site overweight the other (eg. when the unit-circle of the first site encloses the second site) the cell of the overweighted site still exists but the site is out of its cell (you can experiment this by maximizing the weight of one site, or drag a site inside the unit-circle of the other); if we extend the reasoning with a third site (or more), a site may no longer have any zone of influence !
when the two sites have the exact same position, then all depends on weights: the site with the highiest weight wins!
weights may be negative, but I'm not sure if this has any meaning

Acknowledgments to:

D3.js (v.4)
blockbuilder.org

forked from Kcnarf's block: Voronoï playground : interactive weighted Voronoï study

<html>
<head>
<meta charset="utf-8">
<title>Voronoï playground : interactive weighted Voronoï study</title>
<meta content="Studying Weigthed Voronoï Diagram with D3" name="description">
<style>
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 250px;
    font-size: 40px;
  }
  
  .control {
    position: absolute;
    top: 5px;
  }
  .control#control-0 {
    left: 5px;
  }
  .control#control-1 {
    right: 5px;
  }
  .control input {
    width: 400px;
  }
  
  text {
    font-size: 12px;
    fill: grey;
  }
  
  #drawing-area.dragging {
    cursor: move;
  }
  
  #pixel-matrix>circle {
    fill: lightGrey;
    stroke: none;
  }
  .legend.site-0 text {
    fill: lightsteelblue;
  }
  .legend.site-1 text {
    fill: lightgreen;
  }
  
  .legend path {
    fill: none;
    stroke: grey;
  }
  
  #legend-pixel-container circle {
    fill: url("#radial-transparent");
  }
  
  .legend #legend-unit-circle-1 {
    stroke: lightgreen
  }
  
  #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;
  }
  
  .distance {
    font-size: 10px;
    fill: lightsteelBlue;
  }
  #site-distances-container-1>.distance {
    fill: lightseagreen;
  }
  
  .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="-10" max="100" 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="-10" max="100" value="0" oninput="weightUpdated()">
    </form>
  </div>
  <svg>
    <defs>
      <clipPath id="clipper">
        <rect x="0" y="0" width="960" height="500" />
      </clipPath>
      <radialGradient id="radial-transparent">
        <stop offset="0%" stop-color="white" stop-opacity="0"/>
        <stop offset="60%" stop-color="white" stop-opacity="1"/>
      </radialGradient>
    </defs>
    <g id="drawing-area">
      <g id="legend-container">
        <g id="legend-pixel-container"></g>
        <g id="legend-pixel-center-container"></g>
        <g id="legend-unit-circle-container"></g>
      </g>
      <g id="pixel-matrix"></g>
      <g id="cell-container"></g>
      <g id="distances-container"></g>
      <g id="site-container"></g>
    </g>
  </svg>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script>
    var WITH_TRANSITION = true;
    var WITHOUT_TRANSITION = false;
    var duration = 250;
    var sqrt = Math.sqrt;
  	function sqr(i) { return Math.pow(i, 2); };
    
		//begin: layout conf.
    var svgWidth = 960,
        svgHeight = 500,
        squareSize = 60,	//distance between each point in the background
    		hSquareCount = Math.floor(svgWidth/squareSize),
        vSquareCount = Math.floor(svgHeight/squareSize);
    if ((hSquareCount%2)===0) { hSquareCount--; }	//must be odd
    if ((vSquareCount%2)===0) { vSquareCount--; } //must be odd
    var hMargin = (svgWidth-hSquareCount*squareSize)/2,	//2 for centering purpose
        vMargin = (svgHeight-vSquareCount*squareSize)/2,	//2 for centering purpose
        margin = {top: vMargin, right: hMargin, bottom: vMargin, left: hMargin},
        width = svgWidth - margin.left - margin.right,
        height = svgHeight - margin.top - margin.bottom;
    //end: layout conf.
    
    //begin: voronoi stuff definitions
    var sites = [{index: 0, x: 3, y: (vSquareCount-1)/2, weight: 0},
             			{index: 1, x: hSquareCount-4, y: (vSquareCount-1)/2, weight:0}];
    var sitesDistances = [[],[]];	// stores, for each site, each pixel's distances
    var cells = [[], []];					// stores, for each site, each cell's verteces
    //end: voronoi stuff definitions
    
    //begin: scales
    function x(i) { return squareSize*i+squareSize/2; };
    function y(j) { return x(j); }
    function invX(x) { return (x-squareSize/2)/squareSize; };
    function invY(y) { return invX(y); }
    function uc(i) { return x(i)-squareSize/2; }	//scale for unit-circles
    var cellLiner = d3.line()
    									.x(function(d){ return x(d[0]); })
    									.y(function(d){ return y(d[1]); });
    //end: scales
    
    //begin: reusable d3-selections
    var svg = d3.select("svg"),
        clipper = d3.select("#clipper>rect"),
        drawingArea = d3.select("#drawing-area"),
    		pixelMatrix = d3.select("#pixel-matrix"),
        legendPixelCenterContainer = d3.select("#legend-pixel-center-container"),
        legendPixelContainer = d3.select("#legend-pixel-container"),
        legendUnitCircleContainer = d3.select("#legend-unit-circle-container"),
        cellContainer = d3.select("#cell-container"),
    		distancesContainer = d3.select("#distances-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];
      computeSiteDistances(index);
      computeAllCells();

redrawAllCells(WITHOUT_TRANSITION);
      redrawSiteDistances(index);
      redrawUnitCircle(index, WITHOUT_TRANSITION);
      redrawWeights(index);
    }
    var startX, startY;
    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);
      
      startX = x(d.x);
      startY = y(d.y);
    }

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

function draggingSite(d) {
      var newX = Math.round(invX(d3.event.x+startX)),
          newY = Math.round(invY(d3.event.y+startY));
      
      if (newX!==d.x || newY!==d.y) {
        d.x = newX;
        d.y = newY;

computeSiteDistances(d.index);
        computeAllCells();

redrawAllCells(WITH_TRANSITION);
        redrawSiteDistances(d.index);
        redrawSite(d.index,WITH_TRANSITION);
      }
    }
    //end: user interaction handlers
    
    computeAllSitesDistances();
    computeAllCells();
    
    initLayout();
    redrawAllCells(WITHOUT_TRANSITION);
    redrawAllSitesDistances();
    redrawAllUnitCircles(WITHOUT_TRANSITION);
    redrawAllWeights();
    redrawAllSites(WITHOUT_TRANSITION);
    
    
    /***************/
    /* Computation */
    /***************/
    function computeAllSitesDistances() {
      computeSiteDistances(0);
      computeSiteDistances(1);
    }
    
    // compute the Additive Weighted Power Distance (awpd) of each pixel
    // awpd allows to have straight lines as cells border
    function computeSiteDistances (index) {
      var site = sites[index],
      		distances = [];
      
      d3.range(0,hSquareCount)
        .forEach(function(x){
        	d3.range(0,vSquareCount)
            .forEach(function(y){
            	distances.push({x: x, y: y, distance: awpd(x, y, site)});
          })
      });
      sitesDistances[index] = distances;
    }
    
    // compute the Additive Weighted Power Distance (awpd)
    // considering pixel P, site S with weight Ws,
    //   awpd(P,S,Ws) = ||P->S||^2 - Ws,
    //   where ||P->S|| is the Euclidian distance
    function awpd(x, y, site) {
      return sqr(x-site.x)+sqr(y-site.y)-site.weight;
    }
    
    //compute all cells = compute each vertex of each cell's polygon
    function computeAllCells() {
      var s0 = sites[0],
          s1 = sites[1],
          intersections = {};
      
      //begin: handle same site's position
      if (s0.x === s1.x && s0.y === s1.y) {
        computeEmptyAndFullCells();
        return true;
      }
      //end: handle same site's position
      
      // below formula comes from ||P->S0||^2 - Ws0 = ||P->S1||^2 - Ws1
      // where -> are vectors,
      // and applying p->S0 = alpha*S0->S1, and p->S1 = (1-alpha)*S0->S1
      var dx = s1.x-s0.x,
          dy = s1.y-s0.y,
          sqr_d = sqr(dx)+sqr(dy),
          alpha = .5+(s0.weight-s1.weight)/(2*sqr_d),
          border = {x: s0.x+alpha*dx, y: s0.y+alpha*dy, dx: -dy, dy: dx};

//begin: compute plan's bounding segments intersection with border
      intersections["left"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, -.5, -.5, -.5, vSquareCount-.5);
      intersections["bottom"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, -.5, vSquareCount-.5, hSquareCount-.5, vSquareCount-.5);
      intersections["right"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, hSquareCount-.5, vSquareCount-.5, hSquareCount-.5, -.5);
      intersections["top"] = checkLineIntersection(border.x, border.y, border.x+border.dx, border.y+border.dy, hSquareCount-.5, -.5, -.5, -.5);
      //end: compute plan's bounding segments intersection with border
      
      computeCell(0, intersections);
      computeCell(1, intersections);
    }
    
    // compute cell = compute each vertex of the cell's polygon
    function computeCell (index, intersections) {
      var s = sites[index],
          sOther = sites[(index+1)%2],
          defaultOrderedFullCellEdges = [
            [[-.5,-.5], [-.5,vSquareCount-.5]],
            [[-.5,vSquareCount-.5], [hSquareCount-.5, vSquareCount-.5]],
            [[hSquareCount-.5, vSquareCount-.5], [hSquareCount-.5,-.5]],
            [[hSquareCount-.5,-.5], [-.5,-.5]]
          ],
          defaultOrderedEdgeTypes = ["left", "bottom", "right", "top"],
          orderOffset = -1,
          orderedEdgeTypes = [],
          orderedFullCellEdges = [],
          borderStarted = false,
          borderAtCorner = false,
      		intersectionCount = Object.values(intersections).reduce(function (acc, intersect) { return (intersect.onSegment2)? ++acc : acc }, 0);
			var cell, intersect;
      
      //begin: handle case where cells' border is out of plan's bounding rect
      if (intersectionCount===0) {
        computeEmptyAndFullCells();
        return true;
      }
      //end: handle case when cells' border is out of plan's bounding rect
      
      if (intersectionCount===2) {
        borderAtCorner = true;
      }
      
      //begin: find first vertex in cell
      defaultOrderedFullCellEdges.forEach( function(edge, i) {
        if (orderOffset === -1 && (awpd(edge[0][0], edge[0][1], s) < awpd(edge[0][0], edge[0][1], sOther))) {
          orderOffset = i;
        };
      })
      //end: find first vertex in cell
      
      //begin: handle case when cell's boder is a corner or a plans's bounding segment
      if (orderOffset===-1) {
        computeEmptyAndFullCells();
        return true;
      }
      //end: handle case when cell's boder is a corner or a plan's bounding segment
      
      //begin: order D2 plan's bounding segments from first vertex in cell
      defaultOrderedEdgeTypes.forEach(function(edgeType, i) {
        orderedEdgeTypes.push(defaultOrderedEdgeTypes[(i+orderOffset)%4]);
        orderedFullCellEdges.push(defaultOrderedFullCellEdges[(i+orderOffset)%4]);
      })
      //end: order D2 plan's bounding segments from first vertex in cell
      
      //begin: walk through plan's bounding segments to compute cell's verteces
      cell = [orderedFullCellEdges[0][0]];
      orderedEdgeTypes.forEach( function(edgeType, i) {
        intersect = intersections[edgeType];
        if (intersect.onSegment2) {
          if (!borderStarted) {
            if (borderAtCorner || cell[cell.length-1][0]!==intersect.x || cell[cell.length-1][1]!==intersect.y) {
              if (cell.length !== 1) {
                cell.push(orderedFullCellEdges[i][0])
              }
              cell.push([intersect.x, intersect.y]);
              borderStarted = !borderStarted;
            }
          } else {
          	if (borderAtCorner || cell[cell.length-1][0]!==intersect.x || cell[cell.length-1][1]!==intersect.y) {
              cell.push([intersect.x, intersect.y]);
              cell.push(orderedFullCellEdges[i][1]);
              borderStarted = !borderStarted;
            };
          }
        } else {
          if (!borderStarted) {
            cell.push(orderedFullCellEdges[i][1]);
          }
        }
      })
      cells[index] = cell;
      //end: walk through plan's bounding segments to compute cell's verteces
    }
    
    function computeEmptyAndFullCells () {
      computeEmptyCell(0);
      computeEmptyCell(1);
      if (sitesDistances[0][0].distance < sitesDistances[1][0].distance) {
        computeFullCell(0);
      } else {
        computeFullCell(1);
      }
    }
    
    // compute full cell = cell verteces are the plan's bounding verteces
    function computeFullCell (index) {
      cells[index] = [[-.5,-.5], [-.5,vSquareCount-.5], [hSquareCount-.5, vSquareCount-.5], [hSquareCount-.5,-.5]];
    }
    
    // compute empty cell = cell verteces becomes empty
    function computeEmptyCell (index) {
      var s = sites[index];
      
      cells[index] = [[s.x, s.y], [s.x, s.y], [s.x, s.y], [s.x, s.y]];
    }
    
    /***********/
    /* Drawing */
    /***********/
    function initLayout () {
      svg.attr("width", svgWidth)
      	.attr("height", svgHeight);
      
      clipper.attr("x", x(-.5))
      	.attr("y", y(-.5))
      	.attr("width", (hSquareCount)*squareSize)
      	.attr("height", (vSquareCount)*squareSize);
      
      drawingArea.attr("width", width)
      	.attr("height", height)
      	.attr("transform", "translate("+[margin.left, margin.top]+")");
      
      //begin: draw pixel centers matrix
      var pixelData = [];
      d3.range(0,hSquareCount)
        .forEach(function(x){
        	d3.range(0,vSquareCount)
            .forEach(function(y){
            	pixelData.push({x: x, y: y});
          })
      });
      
      pixelMatrix.selectAll("circle")
      	.data(pixelData)
      	.enter()
      		.append("circle")
      			.attr("r", 2)
      			.attr("cx", function(d){ return x(d.x); })
      			.attr("cy", function(d){ return y(d.y); });
      //end: draw pixel centers matrix
      
      //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 distances
      distancesContainer.selectAll(".site-distances-container")
        .data(sitesDistances)
      	.enter()
          .append("g")
            .classed("site-distances-container", true)
            .attr("id", function(d,i){ return "site-distances-container-"+i;});
      
      d3.range(0,2).forEach(function(i){
        var textAnchor = (i===0)? "end" : "start";
        var dx = (i===0)? -6 : 6;
        d3.select("#site-distances-container-"+i).selectAll("distance")
          .data(sitesDistances[i])
          .enter()
            .append("text")
              .classed("distance", true)
        			.attr("dx", dx)
        			.attr("dy", 3)
              .attr("text-anchor", textAnchor);
      })
      //end: draw distances
      
      //begin: draw cells
      cellContainer.selectAll(".cell")
      	.data(cells)
      	.enter()
      		.append("path")
      			.classed("cell", true)
      			.attr("id", function(d,i){ return "cell-"+i; });
      //end: draw cells
      
      //begin: draw legends
      legendPixelCenterContainer.attr("transform", "translate("+[x(4),y(vSquareCount-1)]+")");
      var legend = legendPixelCenterContainer.append("g")
      	.classed("legend", true);
      legend.append("path")
      	.attr("d", "M0,5v23");
      legend.append("text")
      	.attr("y", 40)
      	.attr("text-anchor", "middle")
      	.text("center of a pixel");
      legend = legendPixelCenterContainer.append("g")
      	.classed("legend site-0", true);
      legend.append("path")
      	.attr("d", "M-10,7v45h-5");
      legend.append("text")
      	.attr("y", 53)
      	.attr("x", -20)
      	.attr("text-anchor", "end")
      	.text("awp-distance from blue site");
      legend = legendPixelCenterContainer.append("g")
      	.classed("legend site-1", true);
      legend.append("path")
      	.attr("d", "M10,7v45h5");
      legend.append("text")
      	.attr("y", 53)
      	.attr("x", 20)
      	.attr("text-anchor", "start")
      	.text("awp-distance from green site");
      
      legendPixelContainer.classed("legend", true);
      d3.range(0,4).forEach(function(i){
        legendPixelContainer.append("path")
          .attr("d", function(d) {
            return "M"+[x(i-.5), y(vSquareCount-.5)]+"v-"+3*squareSize;
          });
        legendPixelContainer.append("path")
          .attr("d", function(d) {
            return "M"+[x(-.5), y(vSquareCount-i-.5)]+"h"+3*squareSize;
          });
      })
      legendPixelContainer.append("circle")
      	.attr("cx", x(-.5))
      	.attr("cy", y(vSquareCount-.5))
      	.attr("r", 5*squareSize);
      legendPixelContainer.append("path")
      	.attr("d", "M"+[x(0),y(vSquareCount-.5)]+"v5");
      legendPixelContainer.append("text")
      	.attr("x", x(0))
        .attr("y", y(vSquareCount-.5)+15)
      	.attr("text-anchor", "middle")
      	.text("pixel matrix");
      
      legendUnitCircleContainer.classed("legend", true)
      	.attr("transform", "translate("+[x(8),y(vSquareCount-.25)]+")");
      legendUnitCircleContainer.selectAll("circle")
      	.data(d3.range(0,2))
      	.enter()
      		.append("circle")
      			.attr("cx", function(d) { return d*25; })
      			.attr("r", 10)
      			.classed("unit-circle", true)
      			.attr("id", function(d){ return "legend-unit-circle-"+d; });
      legendUnitCircleContainer.append("text")
      	.attr("transform", "translate("+[40,3]+")")
      	.text(": unit-circles, give a sense of the weight of each site")
      //end: draw legends
    }
    
    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("+[x(d.x),y(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 (d.weight>=-1)? uc(sqrt(d.weight+1)):0; })
    }
    
    function redrawAllSitesDistances() {
      redrawSiteDistances(0);
      redrawSiteDistances(1);
    }
    
    // redraw site's distances = redraw the distances to the site of each pixel
    function redrawSiteDistances(index) {
      d3.select("#site-distances-container-"+index).selectAll(".distance")
      	.data(sitesDistances[index])
          .attr("x", function(d){ return x(d.x); })
          .attr("y", function(d){ return x(d.y); })
          .text(function(d){ return Math.round(d.distance); })
    }
    
    function redrawAllCells(withTransition) {
      // redraw cells = redraw each polygon
      d3.select("#cell-container").selectAll(".cell")
      	.data(cells).transition()
	      	.duration(withTransition? duration : 0)
          .attr("d", function(d){ return cellLiner(d)+"z"; });
    }
    
    /*********************************************************/
    /*          line-line intersection coordinates           */
    /* from https://jsfiddle.net/justin_c_rounds/Gd2S2/light/ */
    /*********************************************************/
    
    function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
      // if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
      var denominator, a, b, numerator1, numerator2, result = {
          x: null,
          y: null,
          onSegment1: false,
          onSegment2: false
      };
      denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
      if (denominator == 0) {
          return result;
      }
      a = line1StartY - line2StartY;
      b = line1StartX - line2StartX;
      numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
      numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
      a = numerator1 / denominator;
      b = numerator2 / denominator;

// if we cast these lines infinitely in both directions, they intersect here:
      result.x = line1StartX + (a * (line1EndX - line1StartX));
      result.y = line1StartY + (a * (line1EndY - line1StartY));
      /*
      // it is worth noting that this should be the same as:
      x = line2StartX + (b * (line2EndX - line2StartX));
      y = line2StartY + (b * (line2EndY - line2StartY));
      */
      // if line1 is a segment and line2 is infinite, they intersect if:
      if (a >= 0 && a <= 1) {
          result.onSegment1 = true;
      }
      // if line2 is a segment and line1 is infinite, they intersect if:
      if (b >= 0 && b <= 1) {
          result.onSegment2 = true;
      }
      // if line1 and line2 are segments, they intersect if both of the above are true
      return result;
  };
    
	</script>
</body>
</html>

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