圆内检测算法中的圆优化低于O(n²)

Question

我正在尝试执行一个带圆圈列表的函数,并仅返回完全重叠的圆形列表(一个在另一个内部).问题是该算法至少为O(n²),这是由于getConcentricCircles函数中的嵌套for,以及大数据集的年龄.有没有办法优化它？

编辑:我不知道这是否有帮助,但我使用该算法来检测虹膜和瞳孔检测中的假阳性.如果圆圈完全位于另一个圆圈内,则可能是瞳孔,外部是虹膜.它们应该是同心的,简化了很多,但是人眼中的瞳孔并不完全位于虹膜的中心,这就是我这样做的原因.

编辑2:我已经用Peter Lawrey的解决方案替换了isCircleInCircle,对于某些情况我的不正确

用于检查圆圈是否在圆圈内的功能:

private static boolean isCircleInCircle(Circle a, Circle b) {
    // the circle is inside if the distance between the centre is less than the difference in the radius
    double dx = a.getX() - b.getX();
    double dy = a.getY() - b.getY();
    double radiusDifference = a.getRadius() - b.getRadius();
    double centreDistanceSquared = dx*dx + dy*dy; // edited
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

然后我互相检查列表中的每个元素,并只保存重叠的圆圈(和重叠的圆圈):

public HashSet<Circle> getConcentricCircles(List<Circle> circleList) {
    HashSet<Circle> toReturn = new HashSet<Circle>();

    for (Circle circle : circleList) {
        for (Circle toCheck : circleList) {
            // if the circles are not the same and one is inside another,
            if (!toCheck.equals(circle) && isCircleInCircle(circle, toCheck)) {
                // add both to the hashset
                toReturn.add(circle);
                toReturn.add(toCheck);
            }
        }
    }
    return toReturn;
}

Answer 1

该算法的复杂度不能降低到以下O(n^2)。想象一个规则网格，其点是圆心，圆半径是1，相邻网格点之间的距离是2。任何圆都不包含在任何其他圆中。为了证明这一点，你必须将每个圆圈与其他圆圈进行检查。如果你不证明每个组合，那么就存在圆圈a和b，它们没有相互测试。现在让矩阵看起来有点不同：圆a比圆小一点，b并且它们共享相同的中心。所以你没有发现它a包含在中b，因此你的算法是不正确的。关于复杂性的证明就这么多了。

为了帮助加快程序速度，您必须关注平均情况：这意味着小圆圈包含在大圆圈中。构建一个有向图，其节点代表圆，其边表示源圆包含目标圆。从半径最大的圆开始。使用深度优先搜索构建图。如果你知道这个圆a包含在另一个圆中。b然后尝试找到包含在 中的圆a。如果b存在，首先继续b。当其中不再包含任何内容时，b请后退一步，继续处理尚未包含在另一个找到的圈子中的所有圈子。O(nlog(n))在最好的情况下，这会给你带来复杂性。这是由于在搜索包含的节点时对剩余节点的管理以及按半径排序。这里最好的情况是所有圆都具有相同的圆心和不同的半径。

编辑：阿基的回答
让我想起了另一种加快速度的方法。在一般情况下，这些圆会形成簇，其中一个圆与其他一些圆部分重叠。因此，您可以首先计算依赖集的分区（不，我不是指独立集，因为这会很困难）。这减少了上述算法必须使用的数据大小。NP

当谈到寻找可能完全重叠的候选者时，还有另一个可能的改进。由于圆包含在一个平面中，因此可以使用 R 树或四叉树等空间数据结构来查找候选对象，这些数据结构可以完全重叠，更有效。

然而，我不认为这会降低最坏情况的复杂性，即使这些建议也会提高上述最坏情况下的性能。新的最坏情况可能是圆形，其中心是规则网格的点，但与规则网格中的点之间的距离相比，其半径非常大。