python之在 Python 中，如何识别重叠圆圈的簇_编程设计

我所说的集群是指相互连接的重叠圆圈组。这张图片可能让我更好地了解我要查找的内容:

在我的数据中，圆由它们的中心点坐标表示。我已经完成了碰撞检测以生成代表重叠的成对中心点列表:

pts = [(-2,2), (-2,2), (0,0), (2,1), (6,2), (7,1)] 
 
overlaps = [ 
    (pts[0], pts[1]), 
    (pts[0], pts[2]), 
    (pts[1], pts[2]), 
    (pts[2], pts[3]), 
    (pts[4], pts[5]), 
]

这是预期的结果:

expected_clusters = [ 
    ((-2,2), (-2,2), (0,0), (2,1)), 
    ((6,2), (7,1)) 
]

在实践中，我将使用的数据集大约是这个大小，所以我可能永远不需要扩大它。但这并不是说我不赞成更优化的解决方案。

我想出了我自己的幼稚解决方案，我会将其作为答案发布。但我有兴趣查看其他解决方案。

请您参考如下方法:

您所做的并不是真正的聚类分析，而是 connected component分析。聚类分析将采用一大堆单独的点并试图发现圆圈。但是您可能会感兴趣，将点分配到初始邻域和通过重叠邻域基于聚类的可达性的组合是 DBSCAN 的核心。想法及其density-based clustering变体。

在任何情况下，由于您是从圆圈开始的，一旦完成碰撞检测，您所称的重叠列表就是邻接列表，而您所称的簇是连接的组件.该算法相当简单:

创建所有节点的列表L。
创建一个空的连通分量列表Cs
当 L 不为空时:
1. 选取任意节点N
2. 创建连通分量列表C，用N初始化
3. 使用邻接列表进行广度优先或深度优先遍历，将遇到的每个节点添加到 C
4. 将 C 附加到 Cs
5. 从L中移除C中的所有节点