block by NPashaP 2ad2fcceadb8a6907098

Convex Hull

Full Screen

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.

index.html

<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="//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>