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

这是预期结果：

^{pr2}$

实际上，我将要处理的数据集大约是这个大小，所以我可能永远不需要扩大它。但这并不是说我不喜欢更优的解决方案。在

我已经想出了我自己天真的解决方案，我会把它作为答案贴出来。但我想看看其他的解决方案。在

Answer 1

已编辑原始响应以支持acjohnson55's algorithm：

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

你所做的不是真正的聚类分析，而是connected component分析。聚类分析就是从一大堆单独的点中找出圆圈。但您可能感兴趣的是，将点分配到初始邻域和通过重叠邻域进行基于聚类的可达性的组合是DBSCAN思想及其density-based clustering变体的核心。在

在任何情况下，因为你是从圆开始的，一旦你完成了碰撞检测，你所说的重叠列表就是邻接列表，而你所称的集群就是连接的组件。算法相当简单：

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