Skip to content

Instantly share code, notes, and snippets.

@NPashaP
Last active November 11, 2016 10:23
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save NPashaP/2ad2fcceadb8a6907098 to your computer and use it in GitHub Desktop.
Save NPashaP/2ad2fcceadb8a6907098 to your computer and use it in GitHub Desktop.
Convex Hull

This program demonstrates an algorithm for finding the smallest convex polygon containing a given set of points (Convex hull).

The algorithm works as follows

  1. Find the highest point A.
  2. Find the second point by searching for a point B such that AB makes the smallest angle with the positive x direction.
  3. Find the remaining points recursively by searcing for a point Z such that YZ makes the smallest angle with XY where X and Y are the last two points found (Y after X). Include the initial point A in the search. When the search ends in A, then the path is complete.

The dot product is used to find the angle between two vectors.

<html>
<head>
<title>Page Title</title>
<style>
.points{
fill:steelblue;
}
polyline, .ray{
fill:none;
stroke-width:3;
stroke:red;
stroke-opacity:0.5;
}
.sweepline{
stroke:blue;
}
</style>
</head>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
var width=900, height=500,points, bnd=[], ang=[];
function getRandomPoints(n){
var mX=50, mY=50;//margin;
return d3.range(0,n).map(function(d){
return {i:d, x:mX+Math.round(Math.random()*(width-2*mX)), y:mY+Math.round(Math.random()*(height-2*mY))};
});
}
function getAngle(p0, p1, p2){
var a1=p1.x-p0.x, b1=p1.y-p0.y;
var a2=p2.x-p1.x, b2=p2.y-p1.y;
var l1 = Math.sqrt(a1*a1+b1*b1);
var l2 = Math.sqrt(a2*a2+b2*b2);
return Math.acos((a1*a2+b1*b2)/(l1*l2));
}
function getBoundary(){
if(bnd.length==0) getInitialPoint();
else if(bnd.length==1) getSecondPoint();
else getNextPoint();
}
function getInitialPoint(){
points.forEach(function(d,i){ if(bnd[0]==undefined || points[bnd[0]].y > d.y) bnd[0]=i; });
d3.select(".ray")
.attr("x1",0).attr("y1",0).attr("x2",width).attr("y2",0).transition().duration(1000)
.attr("y1",points[bnd[0]].y).attr("y2",points[bnd[0]].y);
d3.selectAll(".points").filter(function(d){ return bnd.indexOf(d.i) != -1;})
.transition().delay(500).style("fill","red");
setTimeout(function(){getBoundary()},1000);
}
function getSecondPoint(){
d3.selectAll(".ray").attr("x1",points[bnd[0]].x);
var rp = points.filter(function(d){ return bnd.indexOf(d.i) == -1}); // remaining points.
d3.select(".sweepline").attr("x1",points[bnd[0]].x).attr("y1",points[bnd[0]].y)
.attr("x2",width).attr("y2",points[bnd[0]].y);
var lA; //smallest angle
rp.forEach(function(d,i){
var angle = getAngle({x:0, y:points[bnd[0]].y},points[bnd[0]], d);
setTimeout(function(){
d3.select(".sweepline").transition().duration(3000/rp.length).attr("x2",d.x).attr("y2",d.y);
if(bnd[1]==undefined || angle < lA){
bnd[1]=d.i; lA=angle;
redrawBoundary(3000/rp.length);
}
},3000*i/rp.length);
});
setTimeout(function(){d3.select(".sweepline").style("stroke-opacity",0)},3000);
setTimeout(function(){getBoundary()},3000);
}
function getNextPoint(){
if(bnd[0]==bnd[bnd.length-1]) {
d3.select(".ray").style("stroke-opacity",0);
return false;
}
var p0=points[bnd[bnd.length-2]], p1=points[bnd[bnd.length-1]];
var p = getOuterPoint(p0, p1);
d3.select(".ray").transition().duration(500)
.attr("x2",p.x).attr("y2",p.y).transition().duration(0)
.attr("x1",p1.x).attr("y1",p1.y);
var rp = points.filter(function(d){ return bnd.indexOf(d.i) == -1 || d.i==bnd[0] }); // remaining points.
setTimeout(function(){
d3.select(".sweepline").attr("x1",p1.x).attr("y1",p1.y).attr("x2",p.x).attr("y2",p.y).style("stroke-opacity",1);
},500);
var lA; //smallest angle
var l = bnd.length;
rp.forEach(function(d,i){
var angle = getAngle(p0, p1, d);
setTimeout(function(){
d3.select(".sweepline").transition().duration(3000/rp.length).attr("x2",d.x).attr("y2",d.y);
if(bnd[l]==undefined || angle < lA){
bnd[l]=d.i; lA=angle;
redrawBoundary(3000/rp.length);
}
},1000+3000*i/rp.length);
});
setTimeout(function(){d3.select(".sweepline").style("stroke-opacity",0)},4000);
if(bnd[0] != bnd[l]) setTimeout(function(){getBoundary()},4000);
}
function getOuterPoint(p0, p1){
var dx = p1.x - p0.x, dy=p1.y - p0.y;
if(dy==0) return {x:(dx <0? 0: width), y:p0.y };
if(dx==0) return {x:p0.x, y:(dy < 0? 0 : height)};
if(dy < 0 && 0 <= p0.x-p0.y*dx/dy <= width) return {x:p0.x-p0.y*dx/dy, y:0 };
if(dx < 0 && 0 <= p0.y-p0.x*dy/dx <= height) return {x:0, y:p0.y-p0.x*dy/dx };
if(dx > 0 && 0 <= p0.y+(width-p0.x)*dy/dx <= height) return {x:width, y:p0.y+(width-p0.x)*dy/dx};
if(dy > 0 && 0 <= p0.x+(height-p0.y)*dx/dy <= width) return {x:p0.x+(height-p0.y)*dx/dy, y:height};
}
function redrawBoundary(t){
setTimeout(function(){
d3.select("polyline")
.attr("points",function(){ var r=[]; bnd.forEach( function(d){ r.push(""+points[d].x+','+points[d].y);}); return r.join(" ");});
d3.selectAll(".points")
.filter(function(d){ return bnd.indexOf(d.i) == -1;}).style("fill","steelblue");
d3.selectAll(".points")
.filter(function(d){ return bnd.indexOf(d.i) != -1;}).style("fill","red");
},t);
}
function initialize(){
points=getRandomPoints(15);
d3.select("body").append("svg").attr("width",width).attr("height",height);
d3.select("svg").append("line").attr("class","sweepline");
d3.select("svg").append("polyline");
d3.select("svg").append("line").attr("class","ray")
d3.select("svg").selectAll(".points").data(points).enter().append("circle").attr("class","points")
.attr("cx",function(d){ return d.x}).attr("cy",function(d){ return d.y})
.attr("r",6);
getBoundary();
}
initialize();
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment