Python高效移除大量2D边缘点中冗余点的方案求助

你好！你的问题很典型——处理大规模点集时，最容易踩的坑就是用了低效的查找和遍历逻辑，你的原代码里确实有几个关键性能瓶颈，我来帮你梳理优化方案：

原代码的核心问题 #

• 查找效率极低：用列表的(x+i,y+j) in edges_points判断点是否存在，每次都是O(n)的时间复杂度，15万点的话每次检查都要遍历十几万次，这直接导致整个程序慢到不可用。
• 错误的邻居判断：你检查了8个方向的点，但题目要求的是距离为1的邻居，只有上下左右四个方向（比如(x+1,y)、(x-1,y)、(x,y+1)、(x,y-1)），对角线的点距离是√2，不符合要求，这会导致你误判邻居数量。
• 反复从头遍历：每次删除点后就从头开始循环，这会带来大量重复计算，进一步拖慢速度。

高效优化方案 #

我们可以用集合加速查找+队列迭代处理的思路，把时间复杂度从O(n²)降到接近O(n)，具体步骤如下：

1. 将点集转为集合：集合的成员查找是O(1)时间，这是性能提升的关键。
2. 只检查4个有效邻域：严格按照“距离为1”的要求，只判断上下左右四个方向的点。
3. 用队列维护待处理点：每次修改点集后，只把受影响的点（被删除点的邻居）加入队列重新检查，避免全量遍历。

优化后的代码 #

from collections import deque

def clean_redundant_points(edges_points):
    # 转成集合，实现O(1)时间的点存在性查找
    points_set = set(edges_points)
    # 初始化队列，先将所有点加入待处理队列
    queue = deque(points_set)
    
    # 定义4个符合"距离为1"要求的邻域方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        current_point = queue.popleft()
        # 如果当前点已经被移除，直接跳过
        if current_point not in points_set:
            continue
        
        # 统计当前点的有效邻居数量，并记录邻居列表
        neighbor_count = 0
        neighbors = []
        dx, dy = current_point
        for d in directions:
            neighbor = (dx + d[0], dy + d[1])
            if neighbor in points_set:
                neighbor_count += 1
                neighbors.append(neighbor)
        
        # 若邻居数超过2，移除当前点，并将其邻居加入队列重新检查（因为邻居的邻接关系已变化）
        if neighbor_count > 2:
            points_set.remove(current_point)
            for n in neighbors:
                queue.append(n)
    
    # 将处理后的集合转回列表返回
    return list(points_set)

# 使用示例
cleaned_points = clean_redundant_points(edges_points)
print(f"处理后剩余点数量：{len(cleaned_points)}")

代码说明 #

• 集合查找：points_set让我们可以瞬间判断一个点是否存在，这比原代码的列表查找快了几个数量级。
• 队列处理：每次删除一个点后，只需要把它的邻居加入队列，因为只有这些点的邻居数量可能发生变化，不需要从头遍历所有点。
• 邻域修正：只检查4个方向，完全符合你“距离为1的邻居”的要求，避免了误判。

进一步优化建议 #

如果初始点集特别大，你可以先遍历一次，只把邻居数>2的点加入队列，这样可以减少初始队列的大小，进一步提升速度：

# 优化后的队列初始化逻辑
queue = deque()
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for point in points_set:
    dx, dy = point
    count = 0
    for d in directions:
        if (dx + d[0], dy + d[1]) in points_set:
            count +=1
            if count >2: # 提前终止判断，不用遍历完4个方向
                queue.append(point)
                break

关于后续问题 #

你提到的点排序、断开点处理，后续可以考虑：

• 排序：从一个端点（邻居数=1的点）开始，沿着邻居依次遍历，就能得到有序的边缘点序列。
• 断开点：可以通过连通性分析（比如并查集）把不同的连通分量分开处理。

备注：内容来源于stack exchange，提问作者Fel