Old school D3 from simpler times

All examples By author By category About

NPashaP

Full window Github gist

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

Find the highest point A.
Find the second point by searching for a point B such that AB makes the smallest angle with the positive x direction.
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="https://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>

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

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