<p>已编辑原始响应以支持<a href="https://stackoverflow.com/a/14607978/1093087">acjohnson55's algorithm</a>:</p>
<pre><code>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)
</code></pre>