在Python中，如何识别重叠的圆团？

Question

簇是指一组相互连接的重叠圆。该图像可能会更好地说明我要查找的内容：

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

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))
]

在实践中，我将使用的数据集约为这个大小，因此我可能永远都不需要扩大规模。但这并不是说我不会支持更理想的解决方案。

我提出了自己的幼稚解决方案，我将其发布为答案。但是我会对看到其他解决方案感兴趣。

Answer 1

您要做的实际上不是集群分析，而是连接的组件分析。聚类分析将采取一大堆单个点并试图发现圈子。但您可能会感兴趣的是，将点分配到初始邻域和通过重叠邻域进行基于聚类的可达性的组合是DBSCAN想法及其基于密度的聚类变体的核心。

无论如何，由于您是从圆开始的，所以一旦完成碰撞检测，您所说的重叠列表就是邻接列表，而您所说的簇就是连接的组件。该算法非常简单：

1. 创建L所有节点的列表。
2. 创建一个空的已连接组件列表 Cs
3. 虽然L不为空：
   1. 选择一个任意节点 N
   2. 创建一个连接的组件列表C，用初始化N
   3. 使用邻接表将遇到的每个节点添加到广度优先或深度优先遍历 C
   4. 附加C到Cs
   5. 删除所有节点C从L