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.
xxxxxxxxxx
<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>
<script>
// 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])};
var minDist = euclidean(points[0], points[1]);
var minPoints = points.slice(0, 2);
for (var i=0; i<points.length-1; i++) {
for (var j=i+1; j<points.length; j++) {
if (euclidean(points[i], points[j]) < minDist) {
minDist = euclidean(points[i], points[j]);
minPoints = [ points[i], points[j] ];
}
}
}
//console.log('BRUTE FORCE',minPoints,"FROM",points);
return {minPoints:minPoints,minDist:minDist};
}
</script>
Modified http://d3js.org/d3.v3.min.js to a secure url
https://d3js.org/d3.v3.min.js