|
<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> |