圆集的最小覆盖圆

Question

我正在尝试用Java实现以下内容。

给定一组不同大小（可能是）和位置的圆，确定一个大圆（位置和大小），它正好包含所有圆。

public class Circle {
    public int x, y, radius;
}

有什么想法吗？

- CodeGuy

---

除非这是作业，否则这与Java没有任何关系。 - Karl

我会循环遍历这些圆，并查看它们的最大顶部、左侧、右侧和底部坐标。这将给你一个要覆盖的矩形。在矩形重心处画一个半径与其中一个角落的距离相匹配的圆应该就可以解决问题了。不过这种推理可能存在缺陷。 - James P.

这是一个有趣的问题，但它与Java没有任何关系。 - Perception

可能是重复问题：重叠圆的组合面积。 - trashgod

这绝对不是特定于Java的...除非你想让别人为你编写代码。- 这不是重复的@trashgod，只是密切相关的。 - Kheldar

Answer 1

小球套球问题已经在《"最小的球形包围盒：组合结构和算法"》中进行过研究。例如，这项研究的一个结果是，至少对于一些小球-点问题的算法（如Welzl算法），不能很容易地从点推广到球。

上述论文提出了一种O(n)算法来计算一组球（n为输入球数量，即二维圆）的最小球。C++实现可在计算几何算法库（CGAL）中找到。（您不需要使用CGAL的所有内容；只需提取所需的头文件和源文件即可。）

注意：我是上述论文的合著者，也是CGAL Min_sphere_of_spheres包的作者。

- Hbf

Answer 2

我有一个大致为O(n⁴)的真正解决方案，我正在使用JavaScript实现它作为一个产品：

您需要一个函数来确定解决方案是否有效：确切地说，需要一个函数来检查所有圆是否都在提议的超级圆内。这相当简单：对于每个圆C_i，要求从超级圆的中心到C_i的中心的距离加上C_i的半径小于或等于超级圆的半径。

然后，使用每对和每组三个圆构建一个超级圆。

• 对于一对圆，从C_i的中心到C_j的中心绘制一条线。在每个端点上延伸线段的长度为各自圆的半径。线段的中点是超级圆的中心，其半径是线段长度的一半。

• 对于3个圆，这是阿波罗尼斯问题：http://mathworld.wolfram.com/ApolloniusProblem.html；请注意，您需要获得正确的符号以获得包含所有三个圆的圆。

正确的解决方案是具有最小半径的有效超级圆。

这是我的代码：

'use strict';

/**
 * Epsilon value for floating point equality.
 * @const
 */
var EPSILON = 1E-6;

/**
 * Calculates the minimum bounding circle for a set of circles.
 * O(n^4)
 *
 * @param {Array.<Object.<string, number>>} circles A list of 2+ circles.
 * @return {Object.<string, number>} {cx, cy, radius} of the circle.
 */
function minimumBoundingCircleForCircles(circles) {

    var areAllCirclesInOrOnCircle = function(circle) {
        for (var i = 0; i < circles.length; i++) {
            if (!isCircleInOrOnCircle(circles[i], circle)) return false;
        }
        return true;
    };

    // try every pair and triple
    var best = {radius: 9E9};

    for (var i = 0; i < circles.length; i++) {
        for (var j = i + 1; j < circles.length; j++) {
            var circle = circleFrom2Circles(circles[i], circles[j]);
            if (areAllCirclesInOrOnCircle(circle) &&
                circle.radius < best.radius) {
                best.cx = circle.cx; best.cy = circle.cy;
                best.radius = circle.radius;
            }

            for (var k = j + 1; k < circles.length; k++) {
                var signs = [-1, 1, 1, 1];
                circle = apollonius(circles[i], circles[j], circles[k],
                                    signs);
                if (areAllCirclesInOrOnCircle(circle) &&
                    circle.radius < best.radius) {
                    best.cx = circle.cx; best.cy = circle.cy;
                    best.radius = circle.radius;
                }
            }
        }
    }

    return best;
}


/**
 * Calculates a circle from 2 circles.
 *
 * @param {Object.<string, number>} circle1 The first circle.
 * @param {Object.<string, number>} circle2 The second circle.
 * @return {Object.<string, number>} cx, cy, radius of the circle.
 */
function circleFrom2Circles(circle1, circle2) {

    var angle = Math.atan2(circle1.cy - circle2.cy,
                           circle1.cx - circle2.cx);

    var lineBetweenExtrema = [[circle1.cx + circle1.radius * Math.cos(angle),
                               circle1.cy + circle1.radius * Math.sin(angle)],
                              [circle2.cx - circle2.radius * Math.cos(angle),
                               circle2.cy - circle2.radius * Math.sin(angle)]];

    var center = lineMidpoint(lineBetweenExtrema[0], lineBetweenExtrema[1]);
    return { cx: center[0],
             cy: center[1],
             radius: lineLength(lineBetweenExtrema[0], 
                                lineBetweenExtrema[1]) / 2
           };
}

/**
 * Solve the Problem of Apollonius: a circle tangent to all 3 circles.
 * http://mathworld.wolfram.com/ApolloniusProblem.html
 *
 * @param {Object.<string, number>} circle1 The first circle.
 * @param {Object.<string, number>} circle2 The second circle.
 * @param {Object.<string, number>} circle3 The third circle.
 * @param {Array.<number>} signs The array of signs to use.
 *                               [-1, 1, 1, 1] gives max circle.
 * @return {Object.<string, number>} The tangent circle.
 */
function apollonius(circle1, circle2, circle3, signs) {

    var sqr = function(x) { return x * x };

    var a1 = 2 * (circle1.cx - circle2.cx);
    var a2 = 2 * (circle1.cx - circle3.cx);
    var b1 = 2 * (circle1.cy - circle2.cy);
    var b2 = 2 * (circle1.cy - circle3.cy);
    var c1 = 2 * (signs[0] * circle1.radius + signs[1] * circle2.radius);
    var c2 = 2 * (signs[0] * circle1.radius + signs[2] * circle3.radius);
    var d1 = (sqr(circle1.cx) + sqr(circle1.cy) - sqr(circle1.radius)) -
        (sqr(circle2.cx) + sqr(circle2.cy) - sqr(circle2.radius));
    var d2 = (sqr(circle1.cx) + sqr(circle1.cy) - sqr(circle1.radius)) -
        (sqr(circle3.cx) + sqr(circle3.cy) - sqr(circle3.radius));

    // x = (p+q*r)/s; y = (t+u*r)/s

    var p = b2 * d1 - b1 * d2;
    var q = (- b2 * c1) + (b1 * c2);
    var s = a1 * b2 - b1 * a2;
    var t = - a2 * d1 + a1 * d2;
    var u = a2 * c1 - a1 * c2;

    // you are not expected to understand this.
    // It was generated using Mathematica's Solve function.
    var det = (2 * (-sqr(q) + sqr(s) - sqr(u)));
    var r = (1 / det) * 
        (2 * p * q + 2 * circle1.radius * sqr(s) + 2 * t * u -
         2 * q * s * circle1.cx - 2 * s * u * circle1.cy + signs[3] *
         Math.sqrt(sqr(-2 * p * q - 2 * circle1.radius * sqr(s) - 2 * t * u +
                       2 * q * s * circle1.cx + 2 * s * u * circle1.cy) - 
                   4 * (-sqr(q) + sqr(s) - sqr(u)) * 
                   (-sqr(p) + sqr(circle1.radius) * sqr(s) - sqr(t) +
                    2 * p * s * circle1.cx - sqr(s) * sqr(circle1.cx) + 
                    2 * s * t * circle1.cy - sqr(s) * sqr(circle1.cy))))

    //console.log(r);
    r = Math.abs(r);

    var x = (p + q * r) / s;

    var y = (t + u * r) / s;

    //console.log(x); console.log(y);
    return {cx: x, cy: y, radius: r};
}

/**
 * Is the circle inside/on another circle?
 *
 * @param {Object.<string, number>} innerCircle the inner circle.
 * @param {Object.<string, number>} outerCircle the outer circle.
 * @return {boolean} is the circle inside/on the circle?
 */
function isCircleInOrOnCircle(innerCircle, outerCircle) {
    return ((lineLength([innerCircle.cx, innerCircle.cy],
                        [outerCircle.cx, outerCircle.cy]) +
             innerCircle.radius - EPSILON) < outerCircle.radius);
}


/**
 * Calculates the length of a line.
 * @param {Array.<number>} pt1 The first pt, [x, y].
 * @param {Array.<number>} pt2 The second pt, [x, y].
 * @return {number} The length of the line.
 */
function lineLength(pt1, pt2) {
    return Math.sqrt(Math.pow(pt1[0] - pt2[0], 2) +
                     Math.pow(pt1[1] - pt2[1], 2));
}

/**
 * Calculates the midpoint of a line.
 * @param {Array.<number>} pt1 The first pt, [x, y].
 * @param {Array.<number>} pt2 The second pt, [x, y].
 * @return {Array.<number>} The midpoint of the line, [x, y].
 */
function lineMidpoint(pt1, pt2) {
    return [(pt1[0] + pt2[0]) / 2,
            (pt1[1] + pt2[1]) / 2];
}

- dja

Answer 3

维基百科文章最小圆问题描述了一个针对初始圆的大小相等的情况下的线性平均时间算法。尽管我不确定复杂度分析会发生什么变化，但将其推广到初始圆的大小不同的情况似乎很简单。

- hmakholm left over Monica

---

我不确定是否可以简单地将这些包围点的算法推广为包围不同半径的圆盘的算法... - Joseph O'Rourke

我同意@JosephO'Rourke的观点，对于如何将这些算法推广到不同半径的情况并不完全明显 - 至少对我来说不是 :) 然而，在[计算几何算法库（CGAL）]（http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Bounding_volumes/Chapter_main.html）中有一个算法和C ++实现。（您不需要使用CGAL的所有内容; 只需提取所需的头文件和源文件即可。） - Hbf

Answer 4

你可以找到最大边界（xmin，xmax，ymin，ymax），然后在两个轴上取最大值，然后要求Java在该正方形中绘制椭圆或以其中心和边作为直径。

不行吗？

敬礼， 斯蒂芬

- Snicolas

---

（xmin - 对应半径，xmax + c半径）（ymin / max +- c半径）可能是一个好的开始，但不足够。想象一个8x8矩阵，在（0，-4），（0，4），（-4，0），（4，0）处半径为1的圆。一个以（0,0）为中心，半径为5的大圆可以覆盖它们所有，但是另一个在（4,4）处半径为1的圆不会改变最小/最大（x/y），但是大圆将无法覆盖它。 - user unknown

Answer 5

哎呀，如评论中所述，以下内容无法正常工作：

首先解决三个圆的问题。在这种情况下，外接圆将接触到每个内部的三个圆，并且您可以将其中心找到为两个双曲线的交点。（给定两个固定点距离的差异的点的轨迹是双曲线）。经过一些代数运算，这归结为一个二次方程。

现在通过归纳添加更多内部圆。在每个步骤开始时，您都知道包围所有旧圆的最小圆;它将接触到三个特定的旧“角落”圆。如果新圆在其中一个圆内，则无需进行任何操作。如果不是，则将新圆与选择两个旧角落圆的三种方式相结合，并为每个三元组计算外接圆。其中之一应该包括第四个圆，它现在不再是角落圆了。

继续添加所有圆。

这提供了具有有限舍入误差的线性时间算法（因为每个外接圆都是从原始输入坐标重新计算的）。

- hmakholm left over Monica

---

我非常喜欢这个。不过，在一些（很多？）情况下，最佳的圆只会与两个内部圆相接触。例如三个连续或几乎连续的圆。 - david van brink

嗯，你说得对。实际上这破坏了整个方案，因为可能会出现这样的情况：当你添加一个新的圆非常远时，新的外接圆会同时接触到新的内部圆和之前甚至不在任何角落的内圆。回到起点... - hmakholm left over Monica

我在想你是否可以保留“最好的3个”...但最后可能减少到2个。这只是一次瞎猜。 :) - david van brink

很抱歉，“最佳3个”这件事是无法挽救的。例如，假设我们有四个半径为0的圆，分别以A（0,1）、B（1,0）、C（10,0）、D（0,10）和E（10,10）为中心。那么外接圆会接触到C、D和E。但是如果我们添加F（1000，1000），那么我们的角点就变成了A、B和F，与之前的角点没有一个相同。 - hmakholm left over Monica

Answer 6

我认为这可以分为三个步骤完成：

• 第一个边界圆c1:

  • 中心点由 x_c1 = (x_max + x_min) / 2 和 y_c1 = (y_max + y_min) / 2 确定。
  • 对于每个圆，计算其中心到 c1 中心加上其半径的距离（我称之为超出距离）。这些值中的最大值是 c1 的半径。相应的圆是 a。

• 第二个边界圆c2: (在此步骤中，您将c1的中心向a方向尽可能移动。)

  • 对于除了a以外的每个圆，确定您需要将c1的中心向a方向移动多少，以便从那里到该圆的超出距离与到a的超出距离相同。其中最小值确定了c2的中心。相应的圆是b。到a和b的超出距离（两者相同）是c2的半径。

• 第三个边界圆c3: (在此步骤中，您将c2的中心向a和b之间的方向尽可能移动。)

  • 确定您可以将c2移动到的方向v，使得到a和b的超出距离保持不变。
  • 对于除了a和b以外的每个圆，确定您需要将c2的中心向v方向移动多少，以便从那里到该圆的超出距离与到a和b的超出距离相同。其中最小值确定了c3的中心。半径是找到的三个圆的超出距离。

我相信c3是一个很好的第一次尝试，你可以通过迭代地删除第一个圆并重复第三步来得到更好的解决方案。如果你到达了一组已经看过的三个圆，这可能是最终的解决方案。

- Svante

---

好吧，“你相信” :) 问题出在选择圆a上，它基于一些“矩形逻辑”，而不是正确的优化算法...然而，你的算法可能是一个微不足道的近似（不是解决方案），值得一试。 - Tomas

不行！你的修改是错误的！这样你仍然不能期望更多，只能得到一个近似值。这是一个复杂的问题（请看我的回答）。有一个二维的可能解集，但你只是在一些相当好的锯齿线上寻找最优解。在设计算法时，你应该证明你的解决方案是唯一的。 - Tomas

@Tomas Telensky：你不明白“可能会”的哪个部分吗？ - Svante

我并没有任何困惑，我只是说你的算法只是一个近似值，根本不可能通过这种方式达到最优解。"可能会"……只是在非常特殊的情况下偶然发生。 - Tomas

Answer 7

我的建议算法与Svante的算法类似，但有一些不同之处。

首先创建一个圆，该圆可以轻松地包含所有子圆，然后像气泡一样缩小它，直到被1、2或3个圆固定。

第一次近似：

一个以0,0为中心，半径为max（子圆距离0,0的距离+子圆半径）的圆

如果确定圆的半径的子圆包围了所有其他子圆，则它显然是正确的结果，并且可以返回

第二次近似：

在保持圆与其“固定”到的子圆相切的同时减小第一次近似中找到的圆的半径，将圆心移向固定的子圆，直到它与另一个子圆相切。

最终结果：

再次减小圆的半径，使其与上述两个子圆相切，直到另一个子圆与圆相切，或者圆的中心位于其固定的两个子圆的中心之间的线上。这应该是最小的，因为从这里没有办法减小圆的半径而不让其中一个子圆“突破”

我不确定算法的哪个部分是“减小半径直到另一个子圆变得相切”的部分。显然，二分搜索可以在合理的时间内给出足够好的近似值，但我怀疑你可以将其简化为一个方程式。

- Rcxdude

---

再次强调，这只是一个近似值，请参考我在Svante算法中的评论。在你宣称结果是“最终”的之前，你应该先进行一些证明。你只是选择了一些解决方案，忽略了无限（2D集合）的其他可能解决方案。 - Tomas

Answer 8

这是一个非常困难的问题，我只能概述可能的解决方法，你需要自己完成它。我假设你想要找到最小外接圆。

形式化你的问题 - 对于i = 1..N，已知xi，yi和ri，你正在寻找点[x，y]，使得：

max(distance([x, y], [xi, yi]) + ri)

很简单。这是一个非平凡的极小极大问题。首先看一下这个问题的简化版本最小圆问题，它只涉及点：

max(distance([x, y], [xi, yi]))

首先尝试改进上面链接中提出的算法以解决更复杂的情况。如果这种方法行不通，你可能需要考虑二次规划。祝好运...

- Tomas

Answer 9

我会尝试找到最西端的点，然后是最南端的点，接着以这些点为直径画一个圆。

为了找到这些点，我会通过圆心和半径进行循环。

最终结果如下：

 initiate max object and min object to average center of circle and zero radius
 For every circle object
     calculate topmost western point of the circle
     check if further away than current point
     if further, calculate position of topmost western point required to pass over this new point and set as new min object
     calculate down most eastern point of the circle
     do the same as previous step, only for max object
 make a circle with center equals to middle of min-max line and radius equals to half min-max line length

如果你是那种书虫类型的人，可以在大学图书馆里找到这本书：E.Welzl, Smallest Enclosing Disks (Balls and Ellipsoids), in H. Maurer (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Vol. 555, Springer-Verlag, 359–37 (1991)

而如果你想要阅读C++代码并将其适应于Java，可以参考此链接：http://miniball.sourceforge.net/。当然，这里只涉及到d=2的圆形情况。

- Kheldar

---

请使用更新的CGAL版本，而不是http://miniball.sourceforge.net/（我是http://miniball.sourceforge.net/的作者）。 - Hbf

Answer 10

对于两个圆来说很容易。通过两个圆心的一条直线将击中周长，这是一个外接圆会与它们接触的地方。

对于更多的圆，您需要在每个周长点上应用FEM（有限元分析-http://en.wikipedia.org/wiki/Finite_element_method），这些点可能成为与外部圆接触的点。例如，排除那些面对其他圆的段。当您开始将不同的半径应用于您的点，直到找到最小的交叉所有其他点的公共点-即您的外接圆的中心时，计算仍然相当大。

- John

---

正如JRL所说，这是一个装箱问题，你需要一些数值分析（NA）的方法，因为我不相信存在可以减少复杂性的公式。有限元法可能是最好的选择，但它只是数值分析技术的一个例子。 - John

我在纸上涂鸦了一下，我认为需要NA。更糟糕的是，在最小化问题上还存在局部极小值，因此您需要一些算法来首先找出一些起始点，使您达到全局最小值。祝你好运。（我想看看有更好解决方案的人。） - toto2

我认为有限元方法不能胜任这项工作。它们用于解决微分方程，而这不是这种情况。 - Tomas

@Tomas 这是一个带有约束条件的优化问题，你需要找到最佳圆的位置和半径。当你写下这个优化问题时，你会得到一些微分方程。 - toto2

@Tomas 我希望看到你的解决方案中没有微分方程。最佳圆的中心位置和半径将需要从某些连续优化方法中找到。我会从非常大的半径开始缩小它；当包围圆开始接触其他圆时，包围圆的中心将不得不移动。 - toto2