2D Polygon Boolean Operations with D3.js SVG

Question

I have 2 simple area graphs I've created using D3.js with the data & code below - Let's call them Graph A & Graph B. I would like to use them to create 3 new paths/polygons based on how they intersect.

Path 1 = Graph A - Graph B
Path 2 = Graph B - Graph A
Path 3 = Graph B - Path 2 or Graph A and Graph B intersection

Most visual editors allow you to perform these boolean operations, see: https://en.wikipedia.org/wiki/Boolean_operations_on_polygons

Is it possible to do this in D3.js?

jsfiddle: https://jsfiddle.net/jvf1utmx/

Graph Definitions:

// data
var dataA = [
    { x: 0, y: 100, },
    { x: 100, y: 150, },
    { x: 200, y: 350, },
    { x: 300, y: 200, },
];

var dataB = [
    { x: 0, y: 200, },
    { x: 100, y: 100, },
    { x: 200, y: 250, },
    { x: 300, y: 150, },
];

// Graph shapes
    var graphA = svg.append("path")
    .datum(dataA)
    .attr("class", "area")
    .attr("d", area)
    .style({fill: '#bbbb00', opacity: 0.8});

    var graphB = svg.append("path")
    .datum(dataB)
    .attr("class", "area")
    .attr("d", area)
    .style({fill: '#666666', opacity: 0.8});

My attempt at clip paths:

// Clipping attempts
    var graphBClip = svg.append("clipPath")
        .attr('id','graphBClip')

    graphBClip.append(graphB);

    graphA.attr("clip-path","url(#graphBClip)");

From your wiki article there's a few accepted algorithms for this: [Vatti clipping](https://en.wikipedia.org/wiki/Vatti_clipping_algorithm) and [Greiner-Horrman](https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm). If you search a bit there's a [few](http://stackoverflow.com/a/16248147/16363) [implementations](https://github.com/w8r/GreinerHormann) [in javascript](http://sourceforge.net/projects/jsclipper/) [floating around](http://www.kevlindev.com/geometry/2D/intersections/index.htm). — Mark, Nov 10 '15 at 14:07

score 3 · Accepted Answer · answered Nov 10 '15 at 21:24

As a follow-up to my comment; I just tried out the GreinerHormann library I linked. It plays very nice with d3 (It takes input in the same manner, arrays of objects).

Here's a quick example of your A - B and B - A:

<!DOCTYPE html>
<html>

<head>
  <script data-require="d3@3.5.3" data-semver="3.5.3" src="//cdnjs.cloudflare.com/ajax/libs/d3/3.5.3/d3.js"></script>
  <script src="https://rawgit.com/w8r/GreinerHormann/master/dist/greiner-hormann.min.js"></script>
</head>

<body>
  <script>
    // data
    var dataA = [{
      x: 0,
      y: 100,
    }, {
      x: 100,
      y: 150,
    }, {
      x: 200,
      y: 350,
    }, {
      x: 300,
      y: 200,
    }, ];

    var dataB = [{
      x: 0,
      y: 200,
    }, {
      x: 100,
      y: 100,
    }, {
      x: 200,
      y: 250,
    }];
    
    var area = d3.svg.line()
      .x(function(d){
        return d.x;
      })
      .y(function(d){
        return d.y;
      });
      
    var svg = d3.select('body')
      .append('svg')
      .attr('width', 500)
      .attr('height', 500);

    // Graph shapes
    var graphA = svg.append("path")
      .datum(dataA)
      .attr("class", "area")
      .attr("d", area)
      .style({
        fill: 'none'
      });

    var graphB = svg.append("path")
      .datum(dataB)
      .attr("class", "area")
      .attr("d", area)
      .style({
        fill: 'none'
      });
      
    var AminusB = greinerHormann.diff(dataA, dataB);
    var BminusA = greinerHormann.diff(dataB, dataA);
    
    // Graph shapes
    AminusB.forEach(function(d){
      svg.append("path")
      .datum(d)
      .attr("class", "area")
      .attr("d", area)
      .style({
        fill: 'steelblue',
        opacity: 0.8
      });
    });
    
    // Graph shapes
    BminusA.forEach(function(d){
      svg.append("path")
      .datum(d)
      .attr("class", "area")
      .attr("d", area)
      .style({
        fill: 'orange',
        opacity: 0.8
      });
    });
      
  </script>

</body>

</html>

Hmm it doesn't look like this library works in all scenarios. If I give it dataset `var dataA = [{ x: 0, y: 0, }, { x: 0, y: 100, }, { x: 100, y: 150, }, { x: 200, y: 350, }, { x: 300, y: 200, }, { x: 300, y: 0, }];` `var dataB = [{ x: 0, y: 0, }, { x: 0, y: 200, }, { x: 100, y: 100, }, { x: 200, y: 250, }, { x: 300, y: 200, }, { x: 300, y: 0, }];` it seems to fail... — Ryan King, Nov 12 '15 at 07:17
Maybe it's how the paths are drawn in d3 that makes the above dataset fail? — Ryan King, Nov 12 '15 at 13:58

score 1 · Answer 2 · answered Nov 12 '15 at 13:52

jsclipper (sourceforge.net/projects/jsclipper) solution

// Accepts array or coordinate arrays [[{X:,Y:}]] - note X & Y must be upper case, d3.js requires lowercase
function boolean2D(subj_paths, clip_paths, clip_type) {

  var ct;

  switch (clip_type) {
    case "union":
      ct = ClipperLib.ClipType.ctUnion;
      break;
    case "difference":
      ct = ClipperLib.ClipType.ctDifference;
      break;
    case "intersection":
      ct = ClipperLib.ClipType.ctIntersection;
      break;
    case "exclusion":
      ct = ClipperLib.ClipType.ctXor;
      break;
  }

  var cpr = new ClipperLib.Clipper();

  cpr.AddPaths(subj_paths, ClipperLib.PolyType.ptSubject, true);  // true means closed path
  cpr.AddPaths(clip_paths, ClipperLib.PolyType.ptClip, true);

  var solution_paths = new ClipperLib.Paths();
  var succeeded = cpr.Execute(ct, solution_paths, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero);

  return solution_paths //produces array of paths to plug into d3.js
}


aXY = boolean2D(x,y,"difference");


// convert XY to lowercase

axy = [];

aXY.forEach(function(d) {
    b = []
    d.forEach(function(c) {
      b.push({x:c.X, y:c.Y});
    });
    axy.push(b);
  });



//d3 output

var svg = d3.select('#chart').append('svg')
    .attr('width', 500)
    .attr('height', 500)
    .style('background', '#C9D7D6');

axy.forEach(function(d){
      svg.append("path")
      .attr("d", lineFunction(d))
      .style({
        fill: 'orange',
        opacity: 0.8
      });
    });

2D Polygon Boolean Operations with D3.js SVG

2 Answers2

Linked