在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

编辑了原来的回答，支持acjohnson55的算法：

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

overlapping_circle_pts = [
    (center_pts[0], center_pts[1]),
    (center_pts[0], center_pts[2]),
    (center_pts[1], center_pts[2]),
    (center_pts[2], center_pts[3]),
    (center_pts[4], center_pts[5]),
]

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


def cluster_overlaps(nodes, adjacency_list):
    clusters = []
    nodes = list(nodes)  # make sure we're mutating a copy

    while len(nodes):
        node = nodes[0]
        path = dfs(node, adjacency_list, nodes)

        # append path to connected_nodes
        clusters.append(path)

        # remove all nodes from
        for pt in path:
            nodes.remove(pt)

    return clusters


def dfs(start, adjacency_list, nodes):
    """ref: http://code.activestate.com/recipes/576723/"""
    path = []
    q = [start]

    while q:
        node = q.pop(0)

        # cycle detection
        if path.count(node) >= nodes.count(node):
            continue

        path = path + [node]

        # get next nodes
        next_nodes = [p2 for p1,p2 in adjacency_list if p1 == node]
        q = next_nodes + q

    return path

print cluster_overlaps(center_pts, overlapping_circle_pts)

Answer 2

你现在做的其实不是聚类分析，而是连通分量分析。聚类分析是指把很多单独的点放在一起，试图找出它们的圈子。不过，你可能会对这样一个事实感兴趣：把点分配到初始邻域，再通过重叠的邻域进行聚类，这正是DBSCAN算法及其基于密度的聚类变体的核心思想。

无论如何，既然你是从圈子开始的，一旦完成了碰撞检测，你所称的重叠列表其实就是邻接列表，而你称之为聚类的部分就是连通分量。这个算法其实很简单：

1. 创建一个包含所有节点的列表L。
2. 创建一个空的连通分量列表Cs。
3. 当L不为空时：
   1. 随机选择一个节点N。
   2. 创建一个连通分量列表C，并用N初始化。
   3. 使用你的邻接列表进行广度优先或深度优先遍历，把遇到的每个节点都添加到C中。
   4. 把C添加到Cs中。
   5. 从L中移除C中的所有节点。