D3 Examples - Rectangle Intersection Problem

Rectangle Intersection Problem

The rectangle intesection problem tries to find all intersection between N different rectangles.

One naive approach would be to check every rectangle against every rectangle; this would take O(N^2) time for N rectangles. A better approach would be the use a sweep line; this sweep line would stop when we cross the left boundary of a rectangle, and this rectangle is added to the set of active rectangles. When we cross the right boundary of a rectangle, we remove the rectangle from the set of active rectangles.

We must then report all intersections between a newly activated rectangle that lie on the scan line, and the set of active rectangles. To do this, we just have to check if the vertical segment of the rectangle overlap. The key to a good solution is to organize the active rectangles so that intersection,deletion, and detection are executed efficiently.

I have choosed to use a Min-Priority Queue to manage the insertion and deletion. A pass thru a sorted array of x values of rectangles would work too.

I am simply testing the current segment against active segments, but a data structure like an interval tree could be used. This would yiels an execution time of O(Nlg(N)+F) where F is the number of rectangle intersections and N the number of line segments inserted in the interval tree

Notice how the sets of active rectangle evolves as the sweep line advances.

xxxxxxxxxx
 
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>Basic Axes</title>
    <script src="https://d3js.org/d3.v3.min.js"></script>
​
</head>
<style>
​
.rectangle {
    fill: none;
    stroke: steelblue;
    stroke-width: 2;
    fill-opacity: 0.6;
}
text {
  font: bold 48px monospace;
}
​
.sweepLine {
    fill:none;
    stroke: red;
    stroke-width: 3;
}
​
.enter {
  fill: green;
}
.active {
  fill: #FFEEEE;
}
​
circle {
    fill: none;
    stroke: black;
    stroke-width: 1;
}
</style>
<body>
</body>
​
<script>
function indexMinPQ(maxN) {
  var _ = {};
  _.N = 0;  //ELEMENTS OF ELEMENTS IN KEYS
  _.pq = new Array(maxN+1);// binary heap used 1-array indexing (=indices)
  _.qp = new Array(maxN+1);// inverse qp[pq[i]] = pq[qp[i]] = i
  _.keys = new Array(maxN+1);// items with priorities
  for (var i=0;i<=maxN;i++) _.qp[i] = -1;
  _.isEmpty = function () { return _.N === 0;};
  _.contains = function (i) { return _.qp[i] != -1;}; //by definition qp returns -1 for empty index
  _.insert = function (i,key) {  //insert key, associate it with index i
    _.N++;
    _.qp[i] = _.N;    // _qp is a helper to have the index in heap for index i
    _.pq[_.N] = i;    // _pq notes reference to index in heap
    _.keys[i] = key;  // _update key indexes
    _.swim(_.N);
  };
  _.minKey = function() { return _.keys[_.pq[1]];}; // find the index of the smallest element, return its associated keys
  _.delMin = function() {
    var minIndex = _.pq[1];
    var minKey = _.keys[minIndex];
    _.exch(1, _.N--); // last elements on the root
    _.sink(1);  // sink it;
    _.keys[_.pq[_.N+1]] = null; // avoid loitering
    _.qp[_.pq[_.N+1]] = -1; // update inverse
    return {index:minIndex,key:minKey};
  };
  _.minIndex = function() {
    return _.pq[1];
  };
  _.changeKey = function(i, key) {
    _.keys[i] = key;
    _.swim(_.qp[i]);  // peut-être que la clef est trop petite par rapport aux parents, il faut la monter d'un+ niveua
    _.sink(_.qp[i]);  // peut-être que la clef est trop grande par rapport aux enfants, il faut la descendre d'un+ niveau
  };
  _.deleteIndex = function(i) {
    var index =  _.qp[i];
    exch(index, _.N--);
    _.swim(index);
    _.sink(index);
    _.keys[i] = null;  //la clef est null
    _.qp[i] = -1;   // tableau des index correspondants dans l'arbre
  };
  _.swim = function(k) {
    while (k > 1 && _.greater((k/2 >> 0), k)) {
        _.exch(k, (k/2)>>0 ) ;
        k = ((k/2)>>0);
    }
  };
  _.sink = function(k) {
    while (2*k <= _.N) {
        var j = 2*k;
        if (j < _.N && _.greater(j, j+1)) j++;
        if (!_.greater(k, j)) break;
        _.exch(k, j);
        k = j;
    }
  };
  _.greater = function(i,j) {
        return  (_.keys[_.pq[i]] > _.keys[_.pq[j]]);
  };
​
  _.exch = function(i, j) {
        var  swap = _.pq[i]; _.pq[i] = _.pq[j]; _.pq[j] = swap;
        _.qp[_.pq[i]] = i; _.qp[_.pq[j]] = j;
    };
  return _;
}
​
​
var width = "960px";
var height = "500px";
var sl = {x:0,height:500};
​
​
​
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .style("position","absolute")
var rects = [[20,20,60,60],[30,60,137,120],[70,90,315,120], [40,130,200,150],[140,20,90,40],[120,40,20,120],[300,50,100,40],
[700,50,90,20]];
var helperRects = [];
var d3Rects = [];
​
​
var active = [];
var PQ = indexMinPQ(rects.length);
for (var i=0;i<rects.length;i++) {
  var d = rects[i];
​
  helperRects[i*2] = rects[i];
  helperRects[i*2+1] = rects[i];
  d3Rects.push( {x:d[0],y:d[1],w:d[2],h:d[3],id:i});
​
  PQ.insert(i*2,rects[i][0]);
  PQ.insert(i*2+1,rects[i][0]+rects[i][2]);
}
​
var active = [];
var intersections = [];
​
​
var _rects = svg.selectAll(".rectangle").data(d3Rects,function(d){return d.id}).enter().append("rect").
    attr("x",function(d){ return d.x}).
    attr("y",function(d){ return d.y}).
    attr("width",function(d){ return d.w}).
    attr("height",function(d) { return d.h}).
    classed("rectangle",true);
​
var sweepLine = svg.append("line");
sweepLine.datum(sl)
    .attr("x1",function(d){ return d.x })
    .attr("x2",function(d){ return d.x })
    .attr("y1",function(d){ return 0})  // a bit of overkill
    .attr("y2",function(d){ return d.height})
    .classed("sweepLine",true);
​
var transition = null;
​
// we keep a stack of events for our animations
var activeRect = [];
var stop =0;
var currentStep = 0;
​
main();
​
function main() {
while(!PQ.isEmpty()) {
  var currentPoint = PQ.delMin();
  var currentRect = helperRects[currentPoint.index];
  var d3Rect = d3Rects[currentPoint.index/2  >> 0];
​
​
  currentPoint = currentPoint.key;
  sl.x = currentPoint;
  var segment =  [currentRect[1],currentRect[1]+currentRect[3]];
​
​
​
  // if x is start of rectangle
  if (currentPoint == currentRect[0])
  {
​
​
    checkSegments(segment,currentPoint);
    active.push(segment);
    activeRect.push(d3Rect);
​
  } else
  {
    removeSegments(segment);
    removeRectangle(d3Rect);
    checkSegments(segment,currentPoint);
  }
​
  (function(a,current){
      var _active = [];
      // if we dont copy array, it will have changed in the closure of the transition
      for (var i=0;i<a.length;i++) {
        _active.push(a[i]);
      }
      var xbound = current;
​
      // first transition is not chained
      if(!transition) {
        transition = sweepLine.transition().duration(500)
         .attr("x1",function(d){ return d.x; })
         .attr("x2",function(d){ return d.x; })
         .each("end",function(d,e){
            _rects.data(_active,function(d){return d.id;}).classed("active",true);
         });
      } else {
        transition = transition.transition().duration(500)
         .attr("x1",function(d){ return d.x })
         .attr("x2",function(d){ return d.x })
         .each("end",function(d,e){
            _rects.data(_active,function(d){return d.id}).classed("active",true).exit().classed("active",false);
            updateIntersections(xbound)
            currentStep++;
            if (currentStep == stop-1) {
​
                resetSimulation();
            }
         })
      }
   })(activeRect,currentPoint);
}
}
​
function resetSimulation() {
    var rectsLength = rects.length;
    activeRect = [];
    active = [];
    rects = [];
    stop =0;
    currentStep = 0;
    d3Rects=[];
    helperRects = [];
    intersections = [];
    transition = null;
​
    for(var i=0;i<rectsLength;i++) {
        var x = Math.random()*700;
        var y = Math.random()*250;
        var w = 10+Math.random()*200;
        var h = 10+Math.random()*200;
        rects.push([x,y,w,h]);
    }
    for (i=0;i<rects.length;i++) {
     var d = rects[i];
​
     helperRects[i*2] = rects[i];
     helperRects[i*2+1] = rects[i];
     d3Rects.push( {x:d[0],y:d[1],w:d[2],h:d[3],id:i});
​
     PQ.insert(i*2,rects[i][0]);
     PQ.insert(i*2+1,rects[i][0]+rects[i][2]);
    }
​
    _rects.data(d3Rects,function(d){return d.id}).transition(500).
    attr("x",function(d){ return d.x}).
    attr("y",function(d){ return d.y}).
    attr("width",function(d){ return d.w}).
    attr("height",function(d) { return d.h});
    updateIntersections();
    sl = {x:0,height:500};
    sweepLine.datum(sl).transition().duration(500)
         .attr("x1",function(d){ return d.x })
         .attr("x2",function(d){ return d.x })
         .each("end",function(d,e){
​
            main();
    });
}
​
​
​
​
​
​
function checkSegments(segment,x) {
  var min,max;
  var contained;
  stop++;
​
​
  for (var i=0;i<active.length;i++) {
​
    if (segment[0]>active[i][0])
    {
       min = active[i];
       max = segment;
       contained = true;
    } else
    {
      min =segment;
      max =active[i];
      contained = false;
    }
    if (min[1]< max[0]) {
      // no overlap
    } else if (min[1]<max[1])
    {
      // which intersections are we interested in
      /*if (segment[0]<active[0])
        intersections.push({x:x,y:active[i][1]});
      else
        intersections.push({x:x,y:active[i][0]});
​
     */
​
     if (min == segment)
        intersections.push({x:x,y:active[i][0]});
     else
        intersections.push({x:x,y:active[i][1]});
​
    } else if (!contained) {
      // overlap at both
      intersections.push({x:x,y:max[1]});
      intersections.push({x:x,y:max[0]});
​
​
    }
  }
​
}
​
​
function updateIntersections(x_bound) {
​
    var filtered = [];
    for (var i=0;i<intersections.length;i++) {
        if (intersections[i].x<= x_bound) filtered.push(intersections[i]);
    }
​
    var circles= svg.selectAll("circle").data(filtered);
    circles.enter().append("circle")
        .attr("cx",function(d) { return d.x})
        .attr("cy",function(d) { return d.y})
        .attr("r",0)
        .transition(1000).attr("r",5)
    //typical d3 trap, this transitions should last before we restart the sim, or we'll end with
    // circles messing up the data join
    circles.exit().transition(300).attr("r",0).remove();
​
}
​
​
​
// DO IT BETTER
function removeRectangle(rect) {
    var  id = rect.id;
    var current = [];
    for (var i=0;i<activeRect.length;i++) {
​
        if (activeRect[i].id != id) {
            current.push(activeRect[i]);
        }
    }
    activeRect = current;
}
function removeSegments(segment) {
  var current =[];
​
  for (var i=0;i<active.length;i++) {
    if (active[i][0]==segment[0] && active[i][1]==segment[1]) {
​
    } else {
      current.push(active[i]);
    }
  }
  active = current;
}
​
​
</script>
​
​
​
​
    