2. 多边形搜索区域顶点顺序规范化与自相交检测

为什么顶点顺序必须先规范化

覆盖规划算法（栅格化、平行航线裁剪、多边形求交）几乎都隐含两个前提：多边形顶点按同一绕向排列，且首尾闭合。若输入来自人工点选、GIS 导出或多次拼接，常见问题是绕向混杂、首尾未闭合、存在重复点或三点共线，甚至出现"8"字形自相交。这些缺陷在后续栅格化时不会报错，而是悄悄产生负面积、错误的内外判断或漏覆盖区。因此本步的任务是：把任意顺序的顶点序列整理成闭合、绕向一致、无自相交的合法几何。

规范化处理链

处理顺序有讲究：先去重与去共线，再判绕向并统一，最后做闭合与自相交检测。若先判绕向再删点，删点可能改变绕向；若先闭合再检测自相交，重复的首尾点会被误判为相交。下面这张图给出各步骤的输入输出与判定分支。

关键实现：绕向判定与自相交检测

绕向用鞋带公式（有向面积）判定，自相交用跨立实验逐对检查非相邻边。下面给出可直接运行的 Python 实现，输入为经纬度顶点列表，输出规范化后的闭合多边形或抛出异常。

import math

def signed_area(pts):
    """鞋带公式，pts 为 [(lon, lat), ...]，不要求闭合"""
    s = 0.0
    n = len(pts)
    for i in range(n):
        x1, y1 = pts[i]
        x2, y2 = pts[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return s / 2.0

def dedup_and_collinear(pts, eps=1e-9):
    """删除相邻重复点与共线中间点"""
    # 去重
    out = []
    for p in pts:
        if not out or (abs(p[0]-out[-1][0]) > eps or abs(p[1]-out[-1][1]) > eps):
            out.append(p)
    # 去共线（循环处理，直到稳定）
    changed = True
    while changed and len(out) > 3:
        changed = False
        res = []
        n = len(out)
        for i in range(n):
            a, b, c = out[(i-1) % n], out[i], out[(i+1) % n]
            cross = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
            if abs(cross) < eps:
                changed = True
                continue
            res.append(b)
        out = res
    return out

def orient(a, b, c):
    """叉积符号：>0 逆时针，<0 顺时针，=0 共线"""
    v = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
    if abs(v) < 1e-12:
        return 0
    return 1 if v > 0 else -1

def on_segment(a, b, c):
    """c 在 ab 线段上（含端点）"""
    return (min(a[0], b[0]) - 1e-12 <= c[0] <= max(a[0], b[0]) + 1e-12 and
            min(a[1], b[1]) - 1e-12 <= c[1] <= max(a[1], b[1]) + 1e-12)

def segments_intersect(p1, p2, p3, p4):
    """跨立实验 + 共线重叠判断"""
    d1 = orient(p3, p4, p1)
    d2 = orient(p3, p4, p2)
    d3 = orient(p1, p2, p3)
    d4 = orient(p1, p2, p4)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True
    # 共线情况
    if d1 == 0 and on_segment(p3, p4, p1): return True
    if d2 == 0 and on_segment(p3, p4, p2): return True
    if d3 == 0 and on_segment(p1, p2, p3): return True
    if d4 == 0 and on_segment(p1, p2, p4): return True
    return False

def normalize_polygon(pts, want_ccw=True):
    """完整规范化流程"""
    if len(pts) < 3:
        raise ValueError("顶点数不足 3")
    # 1. 去重去共线
    pts = dedup_and_collinear(pts)
    if len(pts) < 3:
        raise ValueError("去重后顶点数不足 3")
    # 2. 绕向统一
    a = signed_area(pts)
    if abs(a) < 1e-12:
        raise ValueError("面积为 0，退化多边形")
    if (a > 0) != want_ccw:
        pts = pts[::-1]
    # 3. 闭合
    if pts[0] != pts[-1]:
        pts = pts + [pts[0]]
    # 4. 自相交检测（闭合后边数 = len(pts)-1）
    n = len(pts) - 1
    for i in range(n):
        for j in range(i + 1, n):
            # 跳过相邻边
            if j == i + 1 or (i == 0 and j == n - 1):
                continue
            if segments_intersect(pts[i], pts[i+1], pts[j], pts[j+1]):
                raise ValueError(f"自相交：边 {i} 与边 {j}")
    return pts

# 示例：乱序 + 未闭合 + 含重复点
raw = [(120.0, 30.0), (120.5, 30.0), (120.5, 30.5),
       (120.0, 30.5), (120.0, 30.0), (120.5, 30.0)]
result = normalize_polygon(raw, want_ccw=True)
print("规范化结果:", result)
print("有向面积:", signed_area(result[:-1]))

示例中 raw 首尾重复且中间夹了一个重复点，经去重后得到 4 个角点，鞋带公式给出正面积（逆时针），闭合后输出 5 个点（首尾相同）。若把 raw 改成"8"字形（如 [(0,0),(1,1),(1,0),(0,1)]），normalize_polygon 会抛出 ValueError: 自相交：边 0 与边 2，提示需要人工修正或拆分为两个子区域。

结果判读与修正策略

规范化完成后，输出应满足：顶点数 ≥ 4（含闭合点）、首尾相同、有向面积符号与约定一致、任意两条非相邻边不相交。这份结果可直接作为例 3 栅格化和例 4 航线间距计算的输入。