求可判定正负多边形间包含关系的通用算法

问题定义 #

给定两个多边形顶点列表polyA和polyB，需判定区域A是否完全包含于区域B：

• 若顶点逆时针排列（有向面积area>0），区域为多边形闭内部（紫色）
• 若顶点顺时针排列（有向面积area<0），区域为多边形闭外部（粉色，即整个平面减去多边形内部）
  区域为闭集，边仅接触不交叉时视为包含。

现有方案缺陷 #

常规仅处理正多边形的方案无法覆盖所有场景，当前算法仅检查顶点是否在区域内、多边形是否相交，会出现以下误判：

1. 中心重合的小负多边形与大正多边形

polyA = [(1, 1), (1, 2), (2, 2), (2, 1)]  # 顺时针（负区域）
polyB = [(0, 0), (3, 0), (3, 3), (0, 3)]  # 逆时针（正区域）
polygon_in_polygon(polyA, polyB)  # 预期返回False，实际返回True

2. 互为逆序的同大小多边形

polyA = [(0, 0), (1, 0), (1, 1), (0, 1)]  # 逆时针（正区域）
polyB = [(0, 0), (0, 1), (1, 1), (1, 0)]  # 顺时针（负区域）
polygon_in_polygon(polyA, polyB)  # 预期返回False，实际返回True

完整解决方案 #

核心思路是根据多边形的区域类型（正/负），分四种组合场景处理包含逻辑，同时补充边界点判断、边交叉检测、内部点验证等关键步骤。

基础工具函数 #

def compute_area(poly: tuple[tuple[int, int]]) -> float:
    """计算多边形的有向面积：逆时针为正，顺时针为负"""
    n = len(poly)
    area = 0.0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%n]
        area += (x1 * y2) - (x2 * y1)
    return area / 2.0

def point_on_segment(p: tuple[int, int], a: tuple[int, int], b: tuple[int, int]) -> bool:
    """判断点p是否在闭线段ab上"""
    min_x = min(a[0], b[0])
    max_x = max(a[0], b[0])
    min_y = min(a[1], b[1])
    max_y = max(a[1], b[1])
    if not (min_x <= p[0] <= max_x and min_y <= p[1] <= max_y):
        return False
    cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
    return cross == 0

def point_on_polygon_edge(point: tuple[int, int], polygon: tuple[tuple[int, int]]) -> bool:
    """判断点是否在多边形的闭边上"""
    n = len(polygon)
    for i in range(n):
        a = polygon[i]
        b = polygon[(i+1)%n]
        if point_on_segment(point, a, b):
            return True
    return False

def winding_number(point: tuple[float, int], polygon: tuple[tuple[int, int]]) -> int:
    """计算点相对于多边形的绕数"""
    wn = 0
    n = len(polygon)
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1)%n]
        if y1 <= point[1]:
            if y2 > point[1]:
                cross = (x2 - x1) * (point[1] - y1) - (y2 - y1) * (point[0] - x1)
                if cross > 0:
                    wn += 1
        else:
            if y2 <= point[1]:
                cross = (x2 - x1) * (point[1] - y1) - (y2 - y1) * (point[0] - x1)
                if cross < 0:
                    wn -= 1
    return wn

def segments_intersect(a1: tuple[int, int], a2: tuple[int, int], b1: tuple[int, int], b2: tuple[int, int]) -> bool:
    """判断两条线段是否相交于内部点（非端点）"""
    def ccw(p, q, r):
        return (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])
    
    ccw1 = ccw(a1, a2, b1)
    ccw2 = ccw(a1, a2, b2)
    ccw3 = ccw(b1, b2, a1)
    ccw4 = ccw(b1, b2, a2)
    
    # 跨立相交
    if (ccw1 * ccw2 < 0) and (ccw3 * ccw4 < 0):
        return True
    
    # 端点在对方线段内部
    if point_on_segment(b1, a1, a2) and b1 != a1 and b1 != a2:
        return True
    if point_on_segment(b2, a1, a2) and b2 != a1 and b2 != a2:
        return True
    if point_on_segment(a1, b1, b2) and a1 != b1 and a1 != b2:
        return True
    if point_on_segment(a2, b1, b2) and a2 != b1 and a2 != b2:
        return True
    
    return False

def polygon_centroid(poly: tuple[tuple[int, int]]) -> tuple[float, float]:
    """计算多边形重心（用于内部点验证）"""
    n = len(poly)
    area = compute_area(poly)
    if area == 0:
        return poly[0]
    cx = 0.0
    cy = 0.0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%n]
        factor = (x1*y2 - x2*y1)
        cx += (x1 + x2) * factor
        cy += (y1 + y2) * factor
    cx /= (6 * area)
    cy /= (6 * area)
    return (cx, cy)

核心判断函数 #

def point_in_polygon(point: tuple[int, int], polygon: tuple[tuple[int, int]]) -> bool:
    """检查点是否在多边形定义的闭区域内"""
    if point_on_polygon_edge(point, polygon):
        return True
    area = compute_area(polygon)
    wind = winding_number(point, polygon)
    return wind == 1 if area > 0 else wind == 0

def polygon_and_polygon(polyA: tuple[tuple[int, int]], polyB: tuple[tuple[int, int]]) -> bool:
    """检查两个多边形是否有交叉边（相交于内部点）"""
    n = len(polyA)
    m = len(polyB)
    for i in range(n):
        a1 = polyA[i]
        a2 = polyA[(i+1)%n]
        for j in range(m):
            b1 = polyB[j]
            b2 = polyB[(j+1)%m]
            if segments_intersect(a1, a2, b1, b2):
                return True
    return False

def polygon_in_polygon(polyA: tuple[tuple[int, int]], polyB: tuple[tuple[int, int]]) -> bool:
    """检查区域A是否完全包含于区域B（闭集）"""
    is_A_positive = compute_area(polyA) > 0
    is_B_positive = compute_area(polyB) > 0

    # 场景3：A是外部区域，B是内部区域 → 无限区域无法包含于有限内部
    if not is_A_positive and is_B_positive:
        return False

    # 场景4：A和B都是外部区域 → 等价于B的内部包含于A的内部
    if not is_A_positive and not is_B_positive:
        # 验证B的所有顶点在A的正区域内
        for point in polyB:
            if point_on_polygon_edge(point, polyA):
                continue
            if winding_number(point, polyA) != 1:
                return False
        # 验证无交叉边
        if polygon_and_polygon(polyA, polyB):
            return False
        # 验证B的重心在A的正区域内
        b_centroid = polygon_centroid(polyB)
        if not point_on_polygon_edge(b_centroid, polyA):
            if winding_number(b_centroid, polyA) != 1:
                return False
        return True

    # 场景1：A和B都是内部区域 → A的内部包含于B的内部
    if is_A_positive and is_B_positive:
        for point in polyA:
            if not point_in_polygon(point, polyB):
                return False
        if polygon_and_polygon(polyA, polyB):
            return False
        a_centroid = polygon_centroid(polyA)
        if not point_in_polygon(a_centroid, polyB):
            return False
        return True

    # 场景2：A是内部区域，B是外部区域 → A的内部包含于B的外部
    if is_A_positive and not is_B_positive:
        for point in polyA:
            if not point_in_polygon(point, polyB):
                return False
        if polygon_and_polygon(polyA, polyB):
            return False
        # 验证A的重心在B的外部
        a_centroid = polygon_centroid(polyA)
        if not point_in_polygon(a_centroid, polyB):
            return False
        # 验证B的重心不在A的内部（避免A包含B的内部）
        b_centroid = polygon_centroid(polyB)
        if not point_on_polygon_edge(b_centroid, polyA):
            if winding_number(b_centroid, polyA) == 1:
                return False
        return True

测试验证 #

• 场景1：返回False，符合预期
• 场景2：返回False，符合预期
• 正三角形在正正方形内：返回True
• 负正方形在负三角形内：返回True

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