在XYZ值网格中查找符合Z值范围要求的两点连续路径的实现方案

核心优化思路 #

你最初构想的遍历搜索属于盲目搜索类的DFS/BFS逻辑，在栅格尺寸较大时搜索效率极低，更适合的方案是带可通行约束的A*寻路算法，适配你的需求逻辑如下：

• 先做预处理批量生成可通行掩码：直接过滤出所有Z值落在指定区间的XY节点，标记为可通行，剩余节点直接判定为障碍，避免搜索过程中重复判断Z值
• A*算法的启发函数可以直接用曼哈顿距离或者切比雪夫距离，不需要依赖欧氏距离做路径计算，支持8邻域移动，生成的路径自然可以满足曲线形态要求
• 搜索结束后直接输出路径对应的掩码数组即可，也可以对路径点做样条插值得到更平滑的连续曲线

可直接运行的示例代码 #

import numpy as np
import heapq

def a_star_search(z_arr, start_xy, end_xy, z_min, z_max):
    # z_arr: 二维数组，对应XY坐标下的Z值，shape为(行数, 列数)，行对应Y坐标，列对应X坐标
    # start_xy: 起点坐标 (x, y)
    # end_xy: 终点坐标 (x, y)
    # z_min, z_max: Z值允许的范围
    
    rows, cols = z_arr.shape
    # 预处理生成可通行掩码
    valid_mask = (z_arr >= z_min) & (z_arr <= z_max)
    # 8邻域移动方向
    directions = [(-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,-1), (1,1)]
    
    # 初始化代价矩阵：g_cost是起点到当前点的实际代价，f_cost = g_cost + 启发代价
    g_cost = np.full((rows, cols), np.inf)
    g_cost[start_xy[1], start_xy[0]] = 0
    f_cost = np.full((rows, cols), np.inf)
    # 启发函数用切比雪夫距离，适配8邻域移动
    heuristic = lambda x1,y1,x2,y2: max(abs(x1-x2), abs(y1-y2))
    f_cost[start_xy[1], start_xy[0]] = heuristic(start_xy[0], start_xy[1], end_xy[0], end_xy[1])
    
    # 优先级队列：(f_cost, x, y)
    heap = []
    heapq.heappush(heap, (f_cost[start_xy[1], start_xy[0]], start_xy[0], start_xy[1]))
    # 记录父节点，用于回溯路径
    came_from = {}
    
    while heap:
        current_f, x, y = heapq.heappop(heap)
        # 到达终点，回溯路径
        if (x, y) == end_xy:
            path = []
            while (x, y) in came_from:
                path.append((x, y))
                x, y = came_from[(x, y)]
            path.append(start_xy)
            path.reverse()
            # 生成路径掩码数组
            path_mask = np.zeros_like(z_arr, dtype=bool)
            for (px, py) in path:
                path_mask[py, px] = True
            return path, path_mask
        
        # 遍历8邻域
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            # 判断是否在栅格范围内，且属于可通行区域
            if 0 <= nx < cols and 0 <= ny < rows and valid_mask[ny, nx]:
                # 计算移动代价，斜向移动代价为√2，横向/纵向为1
                move_cost = np.sqrt(2) if dx !=0 and dy !=0 else 1
                temp_g = g_cost[y, x] + move_cost
                # 如果当前路径到该点的代价更低，更新信息
                if temp_g < g_cost[ny, nx]:
                    came_from[(nx, ny)] = (x, y)
                    g_cost[ny, nx] = temp_g
                    f_cost[ny, nx] = temp_g + heuristic(nx, ny, end_xy[0], end_xy[1])
                    heapq.heappush(heap, (f_cost[ny, nx], nx, ny))
    
    # 没有找到合法路径
    return None, None

# 测试示例
if __name__ == "__main__":
    # 生成测试用的100x100的Z数组，模拟高程或者其他指标
    x = np.linspace(0, 10, 100)
    y = np.linspace(0, 10, 100)
    X, Y = np.meshgrid(x, y)
    Z = np.sin(X) * np.cos(Y) * 5
    # 起点(10,10)，终点(80,80)，Z值允许范围是[-2, 2]
    path, path_mask = a_star_search(Z, (10,10), (80,80), z_min=-2, z_max=2)
    if path:
        print(f"找到路径，共{len(path)}个节点")
        # 路径掩码path_mask可以直接输出使用
    else:
        print("没有找到符合Z值约束的路径")

补充优化点 #

如果需要更平滑的曲线路径，可以对输出的路径点序列做B样条插值，得到连续的曲线坐标。如果你的栅格数据量超过1000×1000，可以进一步对可通行区域做稀疏化处理，降低搜索的节点数量。

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