Closest Pair Problem

Closest pair of points problem is a classic problem. A brute-force will takes N*(N-1)(N-2)... comparisons, which yields an exponential complexity. By using a divide and conquer approach, we fall back to a linearithmic complexity.

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>Closest Pair</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;
    stroke-linecap: round
}

.enter {
  fill: green;
}
.active {
  fill: #FFEEEE;
}

circle {
    fill: #FFEEFE;
    stroke: black;
    stroke-width: 2;
}
</style>
<body>
</body>

// arrays is assumed to be sorted, to compute median efficiently
var points = [[12,12],[14,130],[30,90],[34,180],[51,42],[80,120],[120,200],[200,400],[250,20],[300,120],[310,50],[340,150],[420,240],[700,300]];
//points = [[679,79],[863,287],[410,433],[549,217],[59,82],[370,154],[548,239],[115,475],[481,304],[616,58],[291,37],[296,330],[637,245],[616,202]];
var pxAccessor = function(d) { return d[0];};
console.log(median(points,pxAccessor));
var bestMatch = {};
var end = closestPair(points);
console.log(end);
var width = "960px";
var height = "500px";
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .style("position","absolute")
    .style("top","0px");
var d3points = svg.selectAll(".point").data(points,function(d,i){return i});

var line = d3.select("svg").append("line")
.attr("x1",end.minPoints[0][0])
.attr("y1",end.minPoints[0][1])
.attr("x2",end.minPoints[1][0])
.attr("y2",end.minPoints[1][1])
.classed("sweepLine",true)

d3points.enter().append("circle")
  .attr("cx",function(d){ return d[0];})
  .attr("cy",function(d){ return d[1];})
  .attr("r",8)
  .classed("simple",true)
  .classed("point",true)

d3points.filter(function(d){ return (d==end.minPoints[0] || d==end.minPoints[1]);}).transition()
    .duration(200)
    .attr("r",10)
    .style("stroke-width",3);

setTimeout(resetSimulation,1000);
function resetSimulation() {

newPoints = points.map(function(item) {
    return [ ((30+Math.random()*900) >> 0), ((30+Math.random()*450) >> 0)]
 })
 newPoints = newPoints.sort(function(a,b){ return a[0]-b[0]})
 var update = d3points.data(newPoints);
 end = closestPair(newPoints);
 update.transition().duration(700)
  .attr("cx",function(d){ return d[0];})
  .attr("cy",function(d){ return d[1];})
  .attr("r",8)
  .style("stroke-width",2).each("end",function(d){
     if (d == end.minPoints[0] || d == end.minPoints[1]) {
        d3.select(this).attr("r",10).style("stroke-width",3);
     }
  });
 /*update.filter(function(d){ return (d==end.minPoints[0] || d==end.minPoints[1]);}).transition()
    .duration(200)
    .attr("r",10)
    .style("stroke-width",3); // THIS FAILS, WHY ?
 */

line.transition().duration(300).style("stroke-width",0).attr("x1",end.minPoints[0][0])
    .attr("y1",end.minPoints[0][1])
    .attr("x2",end.minPoints[0][0])
    .attr("y2",end.minPoints[0][1]).transition().delay(350).duration(1000)
    .attr("x1",end.minPoints[0][0])
    .attr("y1",end.minPoints[0][1])
    .attr("x2",end.minPoints[1][0])
    .attr("y2",end.minPoints[1][1])
    .style("stroke-width",3);
 // put line at start
 setTimeout(resetSimulation,1400);
}

function closestPair(arr) {
  console.log(arr.length);
  if (arr.length<= 3) {
    return closestBruteForce(arr);
  }
  var medianElement = median(arr,pxAccessor);
  var xL = arr[medianElement];
  var a = arr.slice (medianElement,arr.length);
  var b = arr.slice (0,medianElement);
  var p1 = closestPair(a);
  var p2 = closestPair(b);

if (p1.minDist > p2.minDist) p = p2;
    else p = p1;
  var lp = [];

//WE HAVE THE SMALLEST BETWEEN TWO LR-MOST PARTS

for (var i=0;i<arr.length;i++) {
    if ( Math.abs(xL[0]-arr[i][0]) < p.minDist )  {
      lp.push(arr[i]);
    }
  }
  lp.sort(function(a,b){
      return b[1]-a[1];
  });
  //console.log("SORTED BY Y",lp,lp.length,p);

// WE CHECK IF THERE IS ANOTHER SHORTER POINT, AND ELECT IT, IF NEEDED
  for (i=0;i<lp.length;i++){
    // compare with 11 next neighbor
    var nextEleven = i+12;  // closed bound
    if (nextEleven>lp.length) nextEleven = lp.length;
    for (j=i+1;j<nextEleven;j++) {
      if (euclidean(lp[i],lp[j])<p.minDist) {
        p.minPoints = [lp[i],lp[j]];
        p.minDist = euclidean(lp[i],lp[j]);
      }
    }
  }
  // WE NOW CAN RETURN

return p;
}

function euclidean(p1, p2) {
    //console.log(p1,p2);
    var deltaX = Math.pow(p1[0] - p2[0], 2),
        deltaY = Math.pow(p1[1] - p2[1], 2);
    //console.log("DELTA",deltaX,deltaY,p1,p2);
    return Math.floor(Math.sqrt(deltaX + deltaY));
}

// median for sorted array, use binary search
function median(arr,accessor) {
    var n = arr.length;

if (n%2 === 0)
        return (n/2 >> 0) ;
    else
        return (n/2 >> 0) +1;
}

function closestBruteForce(points) {
  if (points.length<2) return null;
  if (points.length==2) return {minPoints:points,minDist:euclidean(points[0],points[1])};

</script>

Modified http://d3js.org/d3.v3.min.js to a secure url

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