如何高效移除2D二进制数组多边形冗余线段以执行点-in-polygon检测

针对你提出的从二进制网格多边形中移除冗余线段的效率优化问题，我有一个更高效的实现思路，核心是用队列（或栈）跟踪待处理的点，避免原算法中多次全量遍历网格的低效操作。

原算法的问题分析 #

你提到的“循环检测并移除相邻填充数不足2的点”方法，最大的问题是每次循环都要遍历整个网格，而冗余点往往是链式的（移除一个点会导致它的邻居变成新的冗余点），这会导致大量重复扫描，尤其是在大型网格场景下，时间成本很高。

高效算法的核心思路 #

我们可以利用**广度优先搜索（BFS）**的思想，只处理受影响的点，而非每次全量扫描：

1. 初始扫描：遍历一次网格，找出所有初始符合“相邻填充单元格数<2”的填充点，将它们加入队列。
2. 链式处理：从队列中取出点，标记为空白（移除），然后检查它的四个相邻点。对于每个相邻的填充点，重新计算它的相邻填充数，如果此时该数<2且未被加入队列，就把它加入队列等待处理。
3. 终止条件：直到队列为空，所有冗余点都被处理完毕。

这种方法的时间复杂度是O(N)（N为网格总单元格数），因为每个点最多被扫描两次（初始扫描+后续检查），远优于原算法的O(N*K)（K为循环次数）。

伪代码实现 #

这里用Python风格的伪代码展示具体实现：

from collections import deque

def remove_redundant_segments(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    if rows == 0 or cols == 0:
        return grid
    
    # 定义四个方向（北、东、南、西）
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque()

    # 第一步：初始扫描，收集所有待移除的点
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                neighbor_count = 0
                # 统计当前点的相邻填充数
                for dx, dy in directions:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                        neighbor_count += 1
                if neighbor_count < 2:
                    queue.append((i, j))

    # 第二步：链式处理队列中的点
    while queue:
        x, y = queue.popleft()
        # 跳过已经被移除的点（可能被其他点的处理触发过）
        if grid[x][y] == 0:
            continue
        # 标记为空白，完成移除
        grid[x][y] = 0
        # 检查相邻点是否变成新的冗余点
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                # 重新计算相邻填充数
                new_neighbor_count = 0
                for ddx, ddy in directions:
                    nnx, nny = nx + ddx, ny + ddy
                    if 0 <= nnx < rows and 0 <= nny < cols and grid[nnx][nny] == 1:
                        new_neighbor_count += 1
                if new_neighbor_count < 2:
                    queue.append((nx, ny))
    
    return grid

关键细节说明 #

• 2x2及以上区域保留：这类区域中的每个填充点，相邻填充数至少为2（比如2x2网格里的每个点，上下左右至少有2个填充单元格），所以不会被加入队列，自然不会被移除，符合你的设定。
• 射线投射算法兼容性：该方法只移除“端点式”的冗余线段（即那些一端或两端没有足够连接的线段），保留了构成多边形轮廓的必要水平/垂直线段，完全适配后续的射线投射算法需求。

内容的提问来源于stack exchange，提问作者Philip Eagles