Python实现按连续区域分组点坐标（修复错误低效代码）

给定平面网格步长step，网格节点上分布若干点，这些点构成多个连续区域。连续区域定义：区域内每个点都存在另一个点与其距离≤step*√2。需基于坐标字典/列表与步长，将点按所属连续区域分组到新数组中。

当前Python 2代码逻辑错误，输出不符合预期，且实现低效。错误代码如下：

from itertools import groupby

step = 1
regions = [] # list of lists with points from particular regions
while all_equal(list(points.values())) == False: # while not all points have been explored ("points" is a single dict with coordinates, where keys are numbers of points and values are tuples with coordinates)
    region = [] # create a list for new region
    region.append(points[list(points.keys())[0]]) # add to the new list the first value from "points"
    points[list(points.keys())[0]] = None # "None" means that this point has already been explored
    for point in points:
        for region_point in region:
            if points[point] != None: # if this point has not already been explored
                if distance(points[point], region_point) <= step*2**0.5: # if these points form a continuous segment
                    region.append(points[point])
                    points[point] = None
                    break
    regions.append(region)
    points = {k:v for k,v in points.items() if v != None} # remove all explored points from a single dict

for element in regions:
    print element


def all_equal(array):
    g = groupby(array)
    return next(g, True) and not next(g, False)

原代码核心问题 #

1. 遍历逻辑缺陷：仅在初始加入第一个点后，遍历一轮剩余点与当前region中的点匹配，但新加入region的点没有被用来再次检查剩余点，导致遗漏连通点（比如示例中的(1,8)、(2,6)未被纳入第一个区域）。
2. 状态判断错误：all_equal函数无法正确判断所有点是否已被处理，且直接修改原字典的方式易引发遍历异常。
3. 效率低下：嵌套循环的遍历方式时间复杂度高，未利用集合快速查找的特性。

输入数据 #

points = {
    1: (1, 10),
    2: (1, 8),
    3: (2, 9),
    4: (2, 6),
    5: (3, 8),
    6: (3, 7),
    7: (3, 6),
    8: (6, 7),
    9: (7, 8),
    10: (7, 7),
    11: (8, 7),
    12: (8, 6),
    13: (10, 5),
    14: (11, 6),
    15: (12, 6),
    16: (12, 5),
    17: (13, 6),
    18: (13, 5)
}

预期输出 #

[(1, 10), (1, 8), (2, 9), (2, 6), (3, 8), (3, 7), (3, 6)]
[(6, 7), (7, 8), (7, 7), (8, 7), (8, 6)]
[(10, 5), (11, 6), (12, 6), (12, 5), (13, 6), (13, 5)]

当前错误输出 #

[(1, 10), (2, 9), (3, 8), (3, 7), (3, 6)]
[(1, 8)]
[(2, 6)]
[(6, 7), (7, 8), (7, 7), (8, 7), (8, 6)]
[(10, 5), (11, 6), (12, 6), (12, 5), (13, 6), (13, 5)]

采用广度优先搜索(BFS) 处理连通分量问题，逻辑清晰且效率更高，兼容Python 2和Python 3：

import math

def distance(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def group_regions(points_dict, step):
    # 提取所有未访问的点集合
    unvisited = set(points_dict.values())
    regions = []
    
    while unvisited:
        # 取一个未访问的点作为起始点
        start_point = unvisited.pop()
        current_region = [start_point]
        # BFS队列，初始放入起始点
        queue = [start_point]
        
        while queue:
            current_point = queue.pop(0)
            # 遍历所有未访问的点，检查是否连通
            # 用list避免遍历过程中修改集合引发的异常
            for neighbor in list(unvisited):
                if distance(current_point, neighbor) <= step * math.sqrt(2):
                    current_region.append(neighbor)
                    queue.append(neighbor)
                    unvisited.remove(neighbor)
        
        regions.append(current_region)
    
    return regions

# 测试示例
points = {
    1: (1, 10),
    2: (1, 8),
    3: (2, 9),
    4: (2, 6),
    5: (3, 8),
    6: (3, 7),
    7: (3, 6),
    8: (6, 7),
    9: (7, 8),
    10: (7, 7),
    11: (8, 7),
    12: (8, 6),
    13: (10, 5),
    14: (11, 6),
    15: (12, 6),
    16: (12, 5),
    17: (13, 6),
    18: (13, 5)
}

step = 1
result = group_regions(points, step)
for region in result:
    print(region)

修复说明 #

1. BFS遍历逻辑：从每个未访问点出发，递归查找所有连通点，确保不会遗漏任何属于同一区域的点。
2. 状态管理：用unvisited集合跟踪未处理的点，避免修改原字典，逻辑更安全。
3. 效率优化：利用集合的O(1)查找/删除特性，结合BFS的线性遍历，时间复杂度远低于原代码的嵌套循环。

内容的提问来源于stack exchange，提问作者Alexander Fedorov