python - 如何使用OpenCV查找图像中所有圆的所有接触点

这是图像，我想找到该图像中的所有接触点，我知道每个圆的中心和半径。在我看来，欧几里德距离可能不是一种计算中心到中心距离的有效方法。 ，我的问题是如何以有效的方式找到该图像的所有接触点。谢谢。

最佳答案

圆的接触点将放置在从center1到center2的线上。因此，例如，如果两个圆圈的大小都为samze，则可以选择intersection = center1 + 1/2*(center2-center1)，但由于圆圈的大小不相同，因此您可以选择以下内容:

compute dirVector = center2-center1
compute d = |dirVector|
if d < radius1 + radius2 + threshold: consider circles to intersect so now compute contact point
    gap = d - radius1 - radius2 // remark: here gap might become < 0 which is ok
    contactPoint = center1 + (radius1+gap/2)*(dirVector/d)

我已经用原始的C++代码测试了这种方法，并且得到了以下结果:



绿色圆圈是您的原始图片，红色圆圈是我提取的圆圈(不是很完美，但很简单)，粉红色的点是contact points，表示某些接触距离阈值(20像素)

并且这是较低的接触距离阈值(5)的结果(但是请记住，我提取的圆半径比您的圆半径要小一些):



为了提高效率(因为必须比较每对圆，无论它们多远=> O(n²))，都应该使用某种二进制空间分区，例如:

KD-Tree

Quad-Tree

或类似

或尝试使用空间散列，但这些散列更适合稀疏区域。

通常，您可能希望搜索碰撞检测优化以加快速度(您将找到有关二进制空间分区和空间哈希的更多信息)。

由于您的空间非常满，您也可以考虑使用一个简单的网格(在这种情况下，它类似于空间散列):

//choose size of each grid cell to be the maximum found radius of all your circles.
gridCellSize = max diameter + contact-threshold-distance // radius was wrong I think
for each circle
    indexX = round(center.x/gridCellSize)
    indexY = round(center.y/gridCellSize)
    grid[x,y].push_back(current circle)

for each circle in a grid-cell:
    compare this circle to each other circle in the cell
    compare this circle to each circle in all surrounding cells
    ignore all circles in all other cells

在我的上一个示例中，我提取了最大半径为44像素(您的半径可能约为47像素，具体取决于您绘制圆圈所使用的线大小。

因此，将计算出这样的网格:



例如，在栅格单元格位置(1,1)中，如果栅格为0索引，则定位2个圆。它们中的每个都应与同一单元格中的所有圆圈以及周围单元格中的每个圆圈进行比较。因此，这2个圈子将仅与12个圈子进行比较，而不是n-1圈子。

或以图形方式标记的示例:除了将红色单元格中的其他圆圈(此示例中没有)之外，还必须将红色单元格中的所有圆圈与周围的蓝色单元格中的每个圆圈进行比较: