理论来自论文：https://www.doc88.com/p-7189543163840.html 如果看不了就搜一下我的这篇博客的标题吧，至少写博客的时候是能看的
用js实现了这篇论文，命名也是用ABCD比较容易对应上。红色是点，蓝色是包含所有点的最小圆
初始有5个点，和对应的圆，包含这5个点。
鼠标点击一个空位置可以生成一个新点，点击已有的点会删除这个点，每次点击都会重新渲染
下面是完整代码，复制到一个html文件里双击打开就可以用
<!DOCTYPE html>
<html>
<head>
<style>
canvas{
background-color: lightgrey;
}
</style>
</head>
<body>
<canvas width="1600" height="1000"></canvas>
</body>
<script>
var points=[
{x: 500, y: 500},
{x: 530, y: 500},
{x: 570, y: 530},
{x: 530, y: 560},
{x: 500, y: 560}
];
//两点距离
function getD(A,B){
return Math.sqrt((A.x-B.x)**2 + (A.y-B.y)**2);
}
//三角形外接圆
function circleCenter(A, B, C) {
let yDelta_a = B.y - A.y;
let xDelta_a = B.x - A.x;
let yDelta_b = C.y - B.y;
let xDelta_b = C.x - B.x;
if(xDelta_a==0||xDelta_b==0||yDelta_a==0)//边界情况，把点换个位置
return circleCenter(B,C,A);
let center = {};
let aSlope = yDelta_a/xDelta_a;
let bSlope = yDelta_b/xDelta_b;
center.x = (aSlope*bSlope*(A.y - C.y) + bSlope*(A.x + B.x)
- aSlope*(B.x+C.x) )/(2* (bSlope-aSlope) );
center.y = -1*(center.x - (A.x+B.x)/2)/aSlope + (A.y+B.y)/2;
center.r=getD(center,A);//求出圆心之后随便跟一个点算距离就是半径
return center;
}
//包含三点的最小圆
function minCircleOf3(A,B,C){
let edges=new Array(3);
let points=[A,B,C];
for(let i=0;i<3;i++){
let cur=points[i],next=points[(i+1)%3];
edges[i]=(cur.x-next.x)**2 + (cur.y-next.y)**2;
}
let sum=edges.reduce((a,b)=>a+b);
let max=Math.max(...edges);
if(max<sum/2)
return circleCenter(A,B,C);
let index=edges.indexOf(max);
let p1=points[index],p2=points[(index+1)%3];
let x=(p1.x+p2.x)/2;
let y=(p1.y+p2.y)/2;
let r=Math.sqrt(max)/2;
return {x,y,r};
}
//距离target的最远点
function getfarthest(target){
let d=points.map(p=>getD(p,target));
let res=0;
for(let i=1;i<d.length;i++){
if(d[i]>d[res])
res=i;
}
return {index:res, d:d[res]};
}
function minCircle(){
let ABC=[points[0],points[parseInt(points.length/3)],points[parseInt(points.length*2/3)]];
let circle=minCircleOf3(...ABC);
let D=getfarthest(circle);
let t=0;
while(D.d-circle.r>0.1&&t++<10){//兼容误差
let next=new Array(3);
for(let i=0;i<3;i++){
let cp=ABC.slice();
cp[i]=points[D.index];
next[i]=minCircleOf3(...cp);
}
let max=0;
for(let i=1;i<3;i++)
if(next[i].r>next[max].r)
max=i;
circle=next[max];
ABC[max]=points[D.index];
D=getfarthest(circle);
}
return circle;
}
function render(){
let canvas=document.getElementsByTagName('canvas')[0];
let ctx=canvas.getContext('2d');
canvas.width=canvas.width;//to clear
ctx.fillStyle = 'red';
for(let point of points){
ctx.beginPath();
ctx.arc(point.x, point.y, 3, 0, 2*Math.PI);
ctx.closePath();
ctx.fill();
}
if(points.length<3)
return;
let circle=minCircle();
ctx.strokeStyle='#0000ff50';
ctx.lineWidth=6;
ctx.beginPath();
ctx.arc(circle.x,circle.y,circle.r,0,2*Math.PI);
ctx.stroke();
}
render();
document.getElementsByTagName('canvas')[0].addEventListener('click',e=>{
let x=e.offsetX,y=e.offsetY;
let newPoints=points.filter(u=>getD(u,{x,y})>6);
if(newPoints.length==points.length){
points.push({x,y});
}
else{
points=newPoints;
}
render();
});
</script>
</html>
标签：canvas,center,包含,ctx,最小,点集,points,let,circle From： https://www.cnblogs.com/nsyglpc/p/17375095.html