平面点群最小包络圆模型与计算
1 问题描述
很多材料与口头表述中出现了这样一个句子：“求多边形最小外接圆”。事实上这样的描述是不准确的，多边形的外接圆指与多边形各顶点都相交的圆，若多边形存在外接圆，则外接圆唯一。这句话想表明的意思切确的来说，应该解释为求一个最小的圆，能够覆盖整个多边形。在探讨任意多边形的覆盖问题时，用平面点群来取代多边形，则更具备普适性。因此可将原问题转化为：“求平面点群最小包络圆”。
2 数学模型
文字被编辑器吃掉了，我直接上图好了
3 模型求解
3.1 简单算法
在不考虑计算的量的情况下，提出一种简单算法。其基本理论基础是①任意点群，相互距离最大的两点必在该点群的最小包络圆上②最小包络圆与点群至少有两个交点③当交点只有两个时，最小包络圆以距离最大两点的连线为直径④若包络圆与点群中三个及三个以上的点相交，则包络圆为点群中某三点构成的三角形的外接圆。
基于上述基础，算法思想为：先求点群距离最大两点，再与其余点组合形成三角形，迭代判别三角形外接圆是否满足条件。
算法步骤如下所示：
STEP 1: 计算点群P的距离矩阵，选取距离最近两点，设为A、B；
STEP 2: 求以AB为直径的圆O，判断O是否能覆盖所有点，是则输出该圆，否则继续；
STEP 3: 计算所有点到AB的距离，并以距离降序排列点，得到新点群P’；
STEP 4: 从P’中取出当前桟顶的点，与A、B构成三角形T，求T的外接圆O，判断O能否覆盖点群P’中的所有点，是则输出当前圆，否则继续迭代，直到桟为空。
3.2 算法优化
上述算法复杂度高，大批量点群无法高效处理。作为一个最优化问题，可以考虑将上述迭代算法变更为遗传算法、牛顿迭代算法或者共轭梯度算法。
另外，由于点群凸包的最小包络圆与点群包络圆一致，因此可以先求点群的凸包，再基于凸包点进行求解，这样可以大大简化计算量。
4 算例与结果
Matlab环境下，通过P=100*rand(100,2)产生100个
参考文献
[1]用遗传算法求平面点列的最小包容圆[EB/OL]20170306:http://wenku.baidu.com/view/51e154284b73f242336c5f99.html
[2]知乎：用MATLAB画包络圆[EB/OL]20170306:https://www.zhihu.com/question/27569214、
[3]Matlab求三角形外接圆[EB/OL]20170306:http://www.cnblogs.com/tiandsp/p/3995876.html
[4]多边形最小外接圆算法[EB/OL]20170306:
http://wenku.baidu.com/link?url=n-YNirK3qMweJGum3bbvBbBcV9hpnxww0oyyW0TIRqNEjLlodBDWV5PXR1lKkRCCxXe1h9OOHjKilTju89wje1-6shUmr85NcDrsVWA62Xi
[5]Matlab求矩阵最大元素的行列号[EB/OL]20170307:http://blog.csdn.net/llw01/article/details/9263545
附录（Matlab源代码）
function [O,r]= main_calcu(P)
%by 武汉大学孙一璠20170307
%本函数是算法主程序用于体现逻辑
%计算距离矩阵,找到点群长轴两端点
[A,B]=findLongAxis(P);
%判断以长轴为直径的圆是否能够覆盖所有的点
O(1)=(A(1)+B(1))/2;
O(2)=(A(2)+B(2))/2;
r=sqrt((O(1)-A(1))^2+(O(2)-A(2))^2);
if isContain(P,O,r)
T=[A;B];
displayResult(P,O,r,T);
return;
end
%遍历所有其他点，求与AB构成的三角形的外接圆，判断是否能够包含，如果能够包含
d=calcDistance(A,B,P);
P2=[P d];
sortrows(P2,-3);
[m,~]=size(P2);
for i=1:m
tP=P2(i,1:2);
T=[A;B;tP];
[O,r]= triangleCircumcircle(T);
if isContain(P,O,r)
displayResult(P,O,r,T);
return;
end
end
end
function [A,B]=findLongAxis(P)
[m,~]=size(P);
d=ones(m);
for i=1:m
for j=1:m
d(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
%这里没有考虑多个距离一样的情况，一般情况也能用了
[lie_max,hanghao]=max(d);
[~,liehao]=max(lie_max);
hanghao=hanghao(liehao);
A=P(hanghao,:);
B=P(liehao,:);
end
function flag=isContain(P,O,r)
%用于判断输入圆是否完整地包含了整个点群
[m,~]=size(P);
flag=true;
for i=1:m
if sqrt((O(1)-P(i,1))^2+(O(2)-P(i,2))^2)>r
flag=false;
break;
end
end
end
function d=calcDistance(A,B,P)
%用于求某点与指定线段AB所在直线的距离
a=B(2)-A(2);
b=A(1)-B(1);
c=B(1)*A(2)-B(2)*A(1);
d=abs(a.*P(:,1)+b.*P(:,2)+c)./sqrt(a*a+b*b);
end
function displayResult(P,O,r,T)
%本函数用于绘制点群及其最小包络圆
figure;hold on;
rectangle('Position',[O(1)-r,O(2)-r,2*r,2*r],'Curvature',[1,1]);
plot(P(:,1),P(:,2),'markeredgecolor','k','marker','.','linestyle','none');
plot(O(:,1),O(:,2),'markeredgecolor','r','marker','*','linestyle','none');
plot(T(:,1),T(:,2),'markeredgecolor','b','marker','O','linestyle','none');
axis equal;
end
function[O,r]= triangleCircumcircle(T)
%本函数用于求解任意三角形的外接圆
%O为圆心，r为半径，T为传入三角形，如[1 2;3 4;5 6]
%三角形赋值
xa=T(1,1);ya=T(1,2);
xb=T(2,1);yb=T(2,2);
xc=T(3,1);yc=T(3,2);
%矩阵赋值
A=[xa-xb ya-yb;xa-xc ya-yc];
W=[(xa*xa-xb*xb+ya*ya-yb*yb)/2;(xa*xa-xc*xc+ya*ya-yc*yc)/2];
%求解
O=(A^(-1)*W)';
r=sqrt((O(1,1)-xa)^2+(O(1,2)-ya)^2);
end
