找到所有圆的交点

Question

给定一组二维坐标和每个坐标的半径，如何高效地找到所有至少有两个圆相交的点？

我知道两个圆最多相交2个点，因此可以通过对两个圆进行成对比较并循环整个数据集来完成，但是当真实数据集具有10000个圆时，执行所有成对比较将计算量过大。

以下是生成测试数据的示例代码。

    library("plotrix")
    set.seed(1995)
    XCoordinate = sample(x = 1:100,size = 20)
    set.seed(2000)
    YCoordinate = sample(x = 1:100,size = 20)
    set.seed(1997)
    Radius = sample(x = 1:50,size = 20)
    ## Create DataFrame
    TestData = data.frame(XCoordinate = XCoordinate,YCoordinate = YCoordinate, 
    Radius = Radius )

    ## Plot Circle
    plot(TestData$XCoordinate, TestData$YCoordinate, 
         type="n", xlab="", ylab="" , main="Test draw.circle")

    for(Row in 1:nrow(TestData)){
      PlotCircle(TestData$XCoordinate[Row], 
                 TestData$YCoordinate[Row], 
                 TestData$Radius[Row])
    }

我正在尝试找到附件中标记为黑色的所有点。

- user2063055

---

你的问题不是很清楚。你可以构建前两个圆的2个交点，然后对于每个交点检查该点是否在所有圆上。然后你会得到0、1或2个答案。 - SergGr

可能我提出的问题方式有些混淆。我想要获取所有至少两个圆相交的点。我将通过一张图片重新表述这个问题。 - user2063055

编写一个函数，将两个圆作为输入，并输出它们的交点。然后编写一个for循环，遍历你所有的圆对。 - Gregor Thomas

我有10000个圆，不太确定交点的数量。可能我需要再写一个函数来获取计数，即使这需要进行1000C2次比较。 - user2063055

如果您想要所有的交点，那么避免成对比较是不可能的。如果您不比较两个圆，就无法知道它们是否相交。话虽如此，“choose(10000, 2)”接近5000万次比较，所以您的担忧是正确的。您可以从{x,y}坐标上使用“dist”函数开始，其中的核心部分是用C编写的。生成的距离矩阵至少是您需要完成的一半工作，并且将让您快速判断两个圆是否相交。 - Gregor Thomas

Answer 1

你可能会得到很多误判的候选项，但除非圆圈基本上重叠在一起，否则我们可以通过计算圆圈的边界框并运行线性扫描来显著减少成对检查的数量。相交的圆圈意味着边界框相交，但反之则不一定。

- גלעד ברקן

Answer 2

可能比גלעד ברקן的解决方案更加复杂，但也许更具选择性：

1. 构建一个 R-Tree，组织圆心并添加一个额外的属性maxRadius到每个节点中，该属性保存任何圆形的最大半径，其圆心包含在该节点中

2. 对于每个圆c，在R-Tree上执行范围搜索，找到候选圆。当minDist(c, p) > c.radius + p.maxRadius时，丢弃节点p

3. 计算每个候选圆的交点

在2D中构建R-Tree通常是O(n log n)，对于适度范围（半径），范围搜索被认为是O(log n)。在平均情况下总共是O(n log n)。

- SaiBot

---

当圆包含在其他圆中时，这不会导致误报吗？（使用退化数据可能是O(n^2)吗？例如：(((()))))） - גלעד ברקן

由于所有候选人都必须通过第三步进行验证，因此不应该出现误报，或者我错过了什么情况吗？前两个步骤仅用于候选人生成，就像您提出的算法一样。关于圆中的圆的好点子，这种情况处理效率不高。 - SaiBot

我指的是假阳性候选项。 - גלעד ברקן

当一个圆落在r-Tree节点内时，minDist(c, p) = 0，因此该节点不会被丢弃。当你处于叶子级别时，你需要计算与叶子节点中所有圆的交集（可能我的回答中这部分不太清楚）。 - SaiBot

Answer 3

我已经在C++中实现了圆相交的扫描线算法，代码在这里：github.com/malyasova/intersect_circles。

它的工作原理类似于线段相交算法，只是每个圆的上弧和下弧被插入到状态中，而不是线段。它的时间复杂度为O((n+k)log n)，其中n是圆的数量，k是相交点的数量。

- Viktoriya Malyasova