5

我正在尝试做一个函数，它需要一个圆圈列表，并且只返回一个完全重叠的圆圈列表（一个在另一个里面）。问题在于该算法至少为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;
}
4

6 回答 6

2

我看到一个圆圈是否在另一个圆圈内的第一印象是知道

  1. 两个圆的中心点。
  2. 圆的两个半径。
  3. 如果 C1 到 C2 + R2 > R1 则为外部，否则为内部。

这应该会大大简化您的逻辑。

编辑：为了提高复杂性，

  1. 按半径排序（从大到小）
  2. 第一个 for 循环从大到小
  3. 第二个for循环从大到小
  4. 一旦你在外圈内找到一个内圈，你就可以从外圈中删除这个圈子
  5. 原因是因为第一个外圈封装了这个内圈，你不在乎是否有其他东西落在这个圈子里，只要它随后在更大的那个之外。

这将得到你的圆圈列表，这些圆圈被一个更大的圆圈包围。

于 2012-10-18T09:44:55.890 回答
1

你的数据集是什么样的？检查每个圆圈与其他圆圈本质上是 O(n^2)，为了降低复杂性，您需要一些度量来防止必须检查每个圆圈。

根据圆的分布，有各种可能有用的宽相位算法。例如，如果圆所占据的空间远大于典型半径，并且圆在该空间中分布相对均匀，则使用四叉树进行空间划分有助于最大限度地减少检查彼此相距较远的对象之间的包容性。

于 2012-10-18T10:06:20.190 回答
1

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

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

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

然后，在寻找可能完全重叠的候选人时，还有另一个可能的改进。由于圆包含在一个平面中，因此可以使用 R 树或四叉树之类的空间数据结构来查找可以完全重叠的候选者，效率更高。

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

于 2012-10-18T11:13:54.543 回答
0

虽然不是您问题的答案，但您可以使用以下方法更快地进行检查。

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 centreDistance = Math.sqrt(dx*dx + dy+dy);
    // return radiusDifference > centreDistance;
    double centreDistanceSquared = dx*dx + dy+dy;
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

private static boolean isPointInCircle(Point center, int outsideRadius, Point toCheck) {
    // distance between two points is sqrt((x1-x2)²+(y1-y2)²)
    double dx = center.getX() - toCheck.getX();
    double dy = center.getX() - toCheck.getY();
    double distSquared = dx * dx + dy * dy;
    // if the distance is less than the radius, then the point is inside
    return distSquared < outsideRadius * outsideRadius;
}

注意：第一种方法不再需要第二种方法。

于 2012-10-18T09:54:44.130 回答
0

如果圆圈的分布允许，可以根据它们的位置将圆圈分成几个或多个槽——然后将测试限制在相同或附近的槽中。

事实证明，问题在于眼睛数量足够少的实时眼睛检测，复杂性不会成为问题。可以轻松地在 RT 中每帧花费 10M 次浮点运算，这表明数据集小于 1000 个圆（具有优化的内循环）。

优化的内循环将计算：

(x0-x1)^2 + (y0-y1)^2 < (r0-r1)^2

对于每一对圆圈，检查其中一个是否完全包含另一个。该公式非常适合并行性，并且可以通过为通过上述测试的每个圆圈增加一个计数器来排除奇怪的情况。最后应该是1。

于 2012-10-18T10:21:03.313 回答
0

两点：

  1. 您的算法不正确。考虑下图中的圆圈：

    小圆圈重叠但不被大圆圈包含

    小圆的四个罗盘点在大圆内，但不包含在大圆内。这个问题可以通过 Alan 和 Peter 描述的更好的圆环测试来解决。

  2. 您的问题描述并不完全清楚。输出应该是：

    1. 第一个包含在第二个中的每对圆的列表。
    2. 至少一个完全重叠的每个圆圈的列表。
    3. 与其他圆圈的某种组合完全重叠的每个圆圈的列表。

    其中第一个显然没有比 O(N^2) 更好的最坏情况运行时间，因为所有圆圈可能同心排列，所以第一个圆圈包含彼此，第二个圆圈包含除第一个之外的所有其他圆圈，依此类推. 并且由于输出为 (N^2)，因此运行时间再好不过了。

    第二个可能有更好的最坏情况运行时间，但我对此不太有信心。

    第三个听起来像是要解决的噩梦。

如果您可以保证重叠量很低，那么您可以通过创建每个圆的最小（最左边）和最大（最右边）x 位置的列表并对其进行排序来获得更好的运行时间。遍历列表，在遇到左边缘时将圆圈添加到工作集中，并在遇到右边缘时将其删除。当每个圆圈都添加到集合中时，仅将其与当前在集合中的其他圆圈进行比较。

这仍然是最坏情况的 O(n^2)，除非你可以对圆的分布和大小做出足够的保证，但这应该是一个很大的进步。

于 2012-10-18T10:23:47.757 回答