## [算法] 大草原装路灯算法 求解

CuiRong 发布于 2012/08/08 11:13

0

0
<!DOCTYPE HTML>
<html>
<meta charset="utf-8">
<title>house & light</title>
<style type="text/css">
body{font:normal 12px/2 Arial, Helvetica, sans-serif; color:#181416; padding: 0; margin: 0; overflow: hidden;}
#top{ position: absolute; top:0; left: 0; right: 0; border-bottom: solid 1px #ccc; background: rgba(255,255,255,.5); padding: 0 10px}
.info{ color: #aaa; padding: 5px; float: right}
</style>

<body>
<div id="top">
<div class="info">按键 Backspace 撤销操作</div>
一片大草原上有若干人家，

<canvas id="canvas" width="800" height="500">Fallback content, in case the browser does not support Canvas.</canvas>
<script type="text/javascript">
//momofiona 大草原算法解1
;(function(){
var canvas=document.getElementById("canvas"),
resultText=document.getElementById("result");
var cxt=canvas.getContext("2d"),
houses=[[487,269],[600,308]],
r=80,result=[],
draw=function(o,i){
cxt.fillStyle="#000";
//cxt.fillRect(o[0]-2,o[1]-2,4,4);
cxt.fillText(i+1+" ["+o+"]", o[0]+10 ,o[1]);
cxt.beginPath();
cxt.arc(o[0],o[1],4,0,Math.PI*2,true);
cxt.closePath();
cxt.fill();
cxt.beginPath();
cxt.arc(o[0],o[1],r,0,Math.PI*2,true);
cxt.closePath();
cxt.fillStyle="rgba(51,153,255,0.1)";
cxt.fill();
},
//避免发生线段交叉
nocross=function(arr){
arr.sort(function(a,b){return a[1]<b[1]});
var v=arr[0];
arr.map(function(x){
x.ac=Math.atan2(x[1]-v[1],x[0]-v[0]);
return x;
});
arr.sort(function(a,b){
return a.ac<b.ac
});
return arr;
},
//为所有队伍确立队伍关系网，
drawline=function(arr){
cxt.strokeStyle="rgba(51,153,255,0.5)";
cxt.lineWidth=1;
for(var i=0,l;l=arr[i];i++){
if(l.length==1) continue;
if(l.length>3) l=nocross(l);
cxt.beginPath();
cxt.moveTo(l[0][0],l[0][1])
for(var j=0,k;k=l[j];j++){
cxt.lineTo(k[0],k[1]);
}
cxt.lineTo(l[0][0],l[0][1]);
cxt.stroke();
}
},
drawall=function(){
clear();
for(var i=0,l=houses.length;i<l;i++) draw(houses[i],i);
arrange([],houses.slice());
resultText.innerHTML=result.length;
drawline(result);
},
clear=function(){cxt.clearRect(0,0,canvas.width,canvas.height);};
canvas.onclick=function(e){
houses.push([e.pageX-this.offsetLeft,e.pageY-this.offsetTop]);
drawall();
};
document.onkeydown=function(e){
if(e.keyCode==8){
houses.pop();
drawall();
return false;
};
};
window.onresize=function(){
canvas.width=document.documentElement.clientWidth;
canvas.height=document.documentElement.clientHeight;
drawall();
};
var getDistance=function(a,b){
return Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
};
//house是否和hk有公共的相交区域，已知hk相交
var circle=function(h,k,house){
var l=getDistance(h,k);//两圆心距离
var d=Math.sqrt(r*r-l*l/4)// 圆交点到l的距离
var x=[(k[0]+h[0])/2,(k[1]+h[1])/2] //l中心点
var _x=(k[1]-h[1])/l*d;//圆交点相对X x偏移量
var _y=(k[0]-h[0])/l*d;
return getDistance([x[0]-_x,x[1]+_y],house)<r||getDistance([x[0]+_x,x[1]-_y],house)<r
};
//house是否符合group招募条件
//符合的返回true，否则false
var recruit=function(group,house){
for(var i=0,h;h=group[i];i++){
//如果出现不想交的house则立刻判定失败
if(getDistance(h,house)>r*2) return false;
for(var j=0,k;k=group[j];j++){
if(i>=j) continue;
if(!circle(h,k,house)) return false;
}
}
return true;
};
//返回抢夺到的队员，默认为完全抢夺,去掉部分抢夺分支
var grab =function(group,house){
for(var i=0,h;h=group[i];i++){
//如果出现不相交的house则立刻判定失败
if(getDistance(h,house)>r*2) return false;
for(var j=0,k;k=group[j];j++){
if(i>=j) continue;
if(!circle(h,k,house)) return false;
}
}
return true;
};
//对返回结果进行递归，
//抢夺分支：（新增独立分支，与自助、招募分支互不影响）对于不符合某队伍招募条件的house，有权利把该队伍中和自己可组队的house抢夺过来成立新队伍
//自助分支：当没有被任何队伍招募时自己建队伍的分支
//招募分支: 当被某个队伍招募成功时产生的分支
//assembly  这里是所有最终集合的可能组合[[house,house],[house]]
//houses   	[house,house,...]
//house  	一间房屋
function arrange(assembly,houses){
var house=houses.shift();
//组队完成
if(!house){
console.log("result ==> ",assembly.length,JSON.stringify(assembly));
//把队伍最少的分组方案复制给result
if(result.length==0||assembly.length<result.length){
result=assembly;
}
return false;
}
//第一次assembly=[]
if(assembly.length==0){
result.length=0;
arrange([[house]],houses);
return false;
}
//招募分支
for(var i=0,k=0,l=assembly.length;i<l;i++){
if(recruit(assembly[i],house)){
k=1;
var _assembly=assembly.slice();
_assembly[i].push(house);
arrange(_assembly,houses);
return false;
}else{
k
}
}
//自助分支
if(k==0){
assembly.push([house]);
arrange(assembly,houses);
}
}
//首次draw
window.onresize();
})();
</script>
</body>
</html>

0

0