r - 找到所有圆的交点

Question

给定一组 2D 坐标和每个坐标的半径，如何有效地找到该组圆中至少 2 个圆相交的所有点？

我知道两个圆圈最多相交 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])
    }

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

Answer 1

您可能会得到相当多的误报候选对象，但除非圆圈几乎彼此重叠，否则我们可以通过计算圆圈的边界框并运行线扫描来显着减少配对检查的数量。相交的圆圈表示边界框相交，但反之则不然。