将圆包装在圆内

Question

给定单位圆，以及一组 M 个半径为 r 的小圆。找到较小圆的最大半径，使它们全部适合在单位圆内而不重叠。

我有以下圆形包装在多边形示例中链接

我想改变所有圆都在多边形内部的方程

theta = 2*pi/N;       % Angle covered by each side of the polygon

phi = theta*(0:N-1)'; % Direction of the normal to the side of the polygon

polyEq = ( [cos(phi) sin(phi)]*x <= cdist-r );

方程表明所有圆都在圆内，但我不知道如何。有人可以帮助我吗？

亲切的问候。

Answer 1

在您的情况下，没有“多边形的边”，因此没有与

theta

类似的东西，您需要更改引用

theta

的每个位置，以及引用

theta

的所有变量（例如

phi 

）。

像下面这样的东西应该可以工作。 我刚刚从您的链接中复制粘贴了代码，删除了

theta

和

phi

，重新定义了

cdist

和

polyEq

，并使其在答案中绘制单位圆而不是多边形。 如果这些选择中有任何不清楚，请询问。

M = 19; % number of circles to fit

toms r              % radius of circles
x = tom('x', 2, M); % coordinates of circle centers

clear pi % 3.1415...

cdist = 1;          % radius of unit circle

%%%%%% equations saying all circles are inside of unit circle
polyEq = (sqrt(x(1,:).^2 + x(2,:).^2) + r <= cdist);

% create a set of equations that say that no circles overlap
circEq = cell(M-1,1);
for i=1:M-1
    circEq{i} = ( sqrt(sum((x(:,i+1:end)-repmat(x(:,i),1,M-i)).^2)) >= 2*r );
end

% starting guess
x0 = { r == 0.5*sqrt(1/M), x == 0.3*randn(size(x)) };

% solve the problem, maximizing r
options = struct;
% try multiple starting guesses and choose best result
options.solver = 'multimin';
options.xInit = 30; % number of different starting guesses
solution = ezsolve(-r,{polyEq,circEq},x0,options);

% plot result
x_vals = (0:100)./100;
plot(sqrt(1 - x_vals.^2),'-') % top of unit circle
plot(-1.*sqrt(1 - x_vals.^2),'-') % bottom of unit circle
axis image
hold on
alpha = linspace(0,2*pi,100);
cx = solution.r*cos(alpha);
cy = solution.r*sin(alpha);
for i=1:M
    plot(solution.x(1,i)+cx,solution.x(2,i)+cy) % circle number i
end
hold off
title(['Maximum radius = ' num2str(solution.r)]);

Answer 2

这可以表述为一个显式优化问题：

 parameter radius(i)

 positive variable r
 variable p(i,c)  (here c is {x,y}) 

 min r
 subject to
     sum(c, sqr(p(i,c)-p(j,c))) >= sqr(radius(i)+radius(j))
     sum(c, sqr(p(i,c))) <= sqr(r-radius(i))  

这是一个非凸优化问题，但通过全局求解器或多启动方法，我们看到：