找到所有圆的交点

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

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