多边形合并异常及点-in-多边形边缘判断Bug排查求助

1. contains_point 边缘判断逻辑缺陷 #

原函数仅处理了点位于非水平且跨越当前y坐标的线段上的情况，遗漏了以下核心场景：

• 点恰好是线段的端点
• 线段为水平线段（此时y1 == y2，原代码会直接跳过该线段的边缘判断）
• 点位于不跨越当前y坐标的线段上（比如线段整体在点的上方/下方，但点在线段的直线范围内）

修复后的contains_point函数 #

def contains_point(self, point: Point) -> bool:
    px = point.x
    py = point.y
    intersections = 0

    for segment in self.segments:
        x1, y1 = segment.start.x, segment.start.y
        x2, y2 = segment.end.x, segment.end.y

        # 判断点是否为线段端点
        if (abs(px - x1) < 1e-9 and abs(py - y1) < 1e-9) or (abs(px - x2) < 1e-9 and abs(py - y2) < 1e-9):
            return True
        
        # 判断点是否在线段所在直线上，且处于线段的 bounding box 范围内
        cross = (x2 - x1) * (py - y1) - (px - x1) * (y2 - y1)
        if abs(cross) < 1e-9:
            if min(x1, x2) - 1e-9 <= px <= max(x1, x2) + 1e-9 and min(y1, y2) - 1e-9 <= py <= max(y1, y2) + 1e-9:
                return True
        
        # 射线法核心逻辑：仅处理跨越水平射线的线段
        if (y1 > py) != (y2 > py):
            x_intersect = ( (py - y1) * (x2 - x1) ) / (y2 - y1) + x1
            if px < x_intersect + 1e-9:
                intersections += 1

    return intersections % 2 == 1

2. break_segments 线段遍历逻辑漏洞 #

原代码使用enumerate遍历线段列表，但插入新线段后列表长度增加，循环仅遍历初始长度的线段，导致新插入的线段未与另一个多边形的线段做相交检测，残留未分割的线段直接导致合并结果错误。

修复后的break_segments方法 #

def break_segments(self, other: Self) -> None:
    segments_1 = self.segments
    segments_2 = other.segments
    i = 0
    # 用while循环确保所有线段（包括新插入的）都被检测
    while i < len(segments_1):
        j = 0
        while j < len(segments_2):
            intersection = find_intersect(
                segments_1[i].start,
                segments_1[i].end,
                segments_2[j].start,
                segments_2[j].end,
            )
            if (
                intersection
                and 1e-9 < intersection["offset"] < 1 - 1e-9  # 用epsilon避免浮点精度误判
            ):
                point = Point(intersection["x"], intersection["y"])
                # 分割当前线段1
                temp_end = segments_1[i].end
                segments_1[i].end = point
                segments_1.insert(i + 1, Segment(point, temp_end))
                # 分割当前线段2
                temp_end_2 = segments_2[j].end
                segments_2[j].end = point
                segments_2.insert(j + 1, Segment(point, temp_end_2))
                # 分割后跳转索引，避免重复处理
                i += 1
                j += 1
            else:
                j += 1
        i += 1

3. 补充优化说明 #

• 虽然你提到排除了浮点精度问题，但实际计算中仍建议引入极小的epsilon（如1e-9）替代精确相等判断，避免浮点运算误差导致逻辑失效。
• 修复后的contains_point全面覆盖了点在边缘、端点、内部、外部的所有场景，射线法逻辑更严谨。
• break_segments的while循环确保所有线段（包括分割后新增的）都能被完整检测和分割。

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