3. 搜索区域栅格化分辨率选择与覆盖单元生成

为什么分辨率不能“拍脑袋”定

栅格分辨率 r 是覆盖单元（cell）的边长，它同时决定三件事：单元数量（内存与规划规模）、边界逼近误差（几何保真度）、以及单元与探测幅宽 W 的匹配关系。分辨率过粗，多边形边界被“锯齿化”，实际搜索会漏掉边缘条带；分辨率过细，单元数按 1/r² 增长，规划与存储开销迅速膨胀，而对覆盖精度几乎没有额外收益。

本例采用两条可量化的选型准则：

• 探测匹配准则：单元边长应能整除或近似整除有效幅宽，使一条航线覆盖的单元列数与幅宽一致，避免半列浪费。取 r ≤ W / n，n 为期望的每幅宽单元列数（通常 2~4）。
• 边界误差准则：栅格化后边界相对真实多边形的最大偏差约为 r·√2/2（半个对角线）。要求该偏差不超过任务允许的边界逼近误差 ε，即 r ≤ ε·√2。

两条准则取更严格者，再向上归整到“整齐”的候选值（如 5 m、10 m、20 m、25 m），得到最终分辨率。

栅格化与覆盖单元生成

给定多边形顶点（经纬度或局部平面坐标），先建立外包矩形，按 r 划分行列，对每个单元取中心点做点在多边形内判定（射线法），保留中心落在区域内的单元作为覆盖单元。这样得到的单元集合天然是“中心覆盖”语义，与后续航线按行/列扫描的生成方式一致。

下面给出可直接运行的 Python 实现，包含分辨率选型、栅格化、单元统计与边界误差验证。

import math

def point_in_polygon(x, y, poly):
    """射线法：判断点是否在多边形内（poly 为 [(x,y),...]，首尾不闭合也可）"""
    inside = False
    n = len(poly)
    j = n - 1
    for i in range(n):
        xi, yi = poly[i]
        xj, yj = poly[j]
        if ((yi > y) != (yj > y)) and \
           (x < (xj - xi) * (y - yi) / (yj - yi) + xi):
            inside = not inside
        j = i
    return inside

def choose_resolution(width, eps, n_cols=3, candidates=(5,10,20,25,50)):
    """按探测匹配与边界误差双准则选分辨率，返回 (r, 依据)"""
    r_detect = width / n_cols          # 探测匹配上限
    r_error  = eps * math.sqrt(2)      # 边界误差上限
    r_limit  = min(r_detect, r_error)
    ok = [c for c in candidates if c <= r_limit]
    r = max(ok) if ok else min(candidates)
    basis = "探测匹配" if r_detect <= r_error else "边界误差"
    return r, basis, r_detect, r_error

def rasterize(poly, r):
    """中心点判定栅格化，返回单元列表 [(row,col,cx,cy)] 与网格信息"""
    xs = [p[0] for p in poly]; ys = [p[1] for p in poly]
    x0, x1 = min(xs), max(xs)
    y0, y1 = min(ys), max(ys)
    ncol = math.ceil((x1 - x0) / r)
    nrow = math.ceil((y1 - y0) / r)
    cells = []
    for i in range(nrow):
        for j in range(ncol):
            cx = x0 + (j + 0.5) * r
            cy = y0 + (i + 0.5) * r
            if point_in_polygon(cx, cy, poly):
                cells.append((i, j, cx, cy))
    return cells, (x0, y0, nrow, ncol)

def boundary_ratio(cells, nrow, ncol):
    """边界单元：四邻域中至少一个邻居不在集合内"""
    s = {(i,j) for i,j,_,_ in cells}
    b = 0
    for (i,j) in s:
        for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
            if (i+di, j+dj) not in s:
                b += 1
                break
    return b, b / len(s)

def boundary_error(poly, r):
    """用单元边界到真实多边形的最大距离近似逼近误差（采样估计）"""
    # 对每个单元的四条边中点，计算到多边形各边的最近距离
    def seg_dist(px,py,ax,ay,bx,by):
        dx,dy = bx-ax, by-ay
        L2 = dx*dx+dy*dy
        t = 0 if L2==0 else max(0,min(1,((px-ax)*dx+(py-ay)*dy)/L2))
        qx,qy = ax+t*dx, ay+t*dy
        return math.hypot(px-qx, py-qy)
    xs=[p[0] for p in poly]; ys=[p[1] for p in poly]
    x0,y0=min(xs),min(ys)
    ncol=math.ceil((max(xs)-x0)/r); nrow=math.ceil((max(ys)-y0)/r)
    cells,_,_ = rasterize(poly,r)
    worst=0.0
    for i,j,_,_ in cells:
        for fx,fy in ((0.5,0),(0.5,1),(0,0.5),(1,0.5)):
            px=x0+(j+fx)*r; py=y0+(i+fy)*r
            d=min(seg_dist(px,py,poly[k][0],poly[k][1],
                           poly[(k+1)%len(poly)][0],poly[(k+1)%len(poly)][1])
                  for k in range(len(poly)))
            worst=max(worst,d)
    return worst

# ---- 教学示例：局部平面坐标下的五边形搜索区（单位 m）----
poly = [(0,0),(800,0),(900,500),(400,700),(0,500)]
W, eps = 60.0, 8.0
r, basis, rd, re = choose_resolution(W, eps)
print(f"探测匹配上限={rd:.1f} m, 边界误差上限={re:.1f} m, 选型依据={basis}, r={r} m")

cells, (x0,y0,nrow,ncol) = rasterize(poly, r)
b, ratio = boundary_ratio(cells, nrow, ncol)
err = boundary_error(poly, r)
print(f"网格 {nrow}×{ncol}, 覆盖单元={len(cells)}, 边界单元={b}, 占比={ratio:.1%}")
print(f"边界逼近误差估计={err:.2f} m, 允许={eps} m, 判定={'通过' if err<=eps else '不通过'}")

示例参数下（幅宽 60 m、允许误差 8 m），探测匹配上限为 20 m，边界误差上限约 11.3 m，故选型依据为探测匹配，取候选值 r = 20 m。此时网格约 35×45，覆盖单元数量在千级，边界单元占比通常在 20%~35% 之间——占比过高说明区域狭长或分辨率偏粗，可据此回头调整 r 或 n_cols。

结果判读与常见调整