找到包含其他圆圈的最小圆圈？

Question

如果圆圈由其中心的X,Y和半径定义,那么如何找到包含给定圈数的圆？单个圆圈,是可能的最小圆圈,完全包含任意大小和位置的2个或更多圆圈.

起初我尝试通过找到中心的中点并且是新圆的中点来尝试仅包含2个圆,而半径等于2个初始圆的半径的一半和它们的中心之间的距离的一半,但不知何故它总是变得有点偏.找到半径似乎问题似乎总是存在问题,但我对此感到头疼,我无法使其工作.

我不一定需要一种方法来查找包含3个或更多圆圈的圆.我可以找到一个包含2的圆圈,取圆圈并用另一个圆圈包围它,另一个圆圈,最后一个圆圈应包含整个步骤中给出的所有圆圈.

Answer 1

给定两个圆,中心为[x1,y1],[x2,y2],半径为R1和R2.封闭圆的中心是什么？

假设R1不大于R2.如果第二个圆圈较小,则只需交换它们即可.

在后一种情况下,封闭圆的中心必须位于连接两个中心的线上.所以我们可以把新中心写成

center = (1-theta)*[x1,y1] + theta*[x2,y2]

其中theta由.给出

theta = 1/2 + (R2 - R1)/(2*D)

请注意,theta将始终为正数,因为我们已确保(D + R1)> R2.同样,我们应该能够确保theta永远不会大于1.这两个条件确保封闭中心严格位于两个原始圆心之间.

Answer 2

它被称为最小封闭圆("MEC"),或有时称为"最小封闭圆".

MEC算法通过采用大的边界圆并缩小它来工作.您可以将圆圈表示为不是代表其中心的点,而是围绕其周长的点; 你可以简单地使用距离足够小的点,或者你可以做数学运算,将点放在距离边界圆的中心最远的点上等. (3认同)
我认为这并不是他正在寻找的东西:MEC寻找包含(有限)点集的最小圆.他寻找一个包含其他圆圈的圆圈.不过,这可能是一个很好的起点. (2认同)
我很好奇:通过3个点找到一个圆是非常简单的,但是找到一个接触其他3个圆的圆形会产生一个由3个二次方程组成的系统,而我的计算机代数系统无法找到它的解.是什么让你如此确定MEC可以简单地转化为这个问题？此外,只需查看凸壳上的点即可简化IIRC MEC.这不适用于圈子. (2认同)

Answer 3

您手头的问题称为球的最小封闭球。我已经写了关于它的论文，请参见苏黎世联邦理工学院的“最小的球”。

您可以在Bounding Volumes包的Computational Geometry Algorithms Library（CGAL）中找到非常有效的C ++实现。（无需使用所有CGAL；只需提取所需的源文件和头文件，即可启动并运行。）

注意：如果您正在寻找一种仅计算点的最小封闭球体的算法，那么还有其他实现方法，请参阅本文。

Answer 4

只需理解圆的方程并推导出一个方程（或一系列）即可找到答案，然后开始实施。鉴于您已经做了一些事情，也许我们能够帮助您。