射线法判断点在多边形内外的算法与实现

射线法判断点在多边形内外

射线法是一种常用的判断点与多边形关系的算法。其原理是从目标点引出一条射线，统计该射线与多边形边界的交点个数。

算法步骤：

选择射线： 从目标点出发，水平向右引出一条射线。
遍历多边形边： 对于多边形的每一条边，进行以下判断：
- 是否与射线相交： 若相交，则继续下一步；否则，跳过该边。
- 交点是否有效：
  - 方向向上的边：包括起点，不包括终点。
  - 方向向下的边：不包括起点，包括终点。
  - 水平边：不参与计算。
  - 交点必须在目标点的右侧。
统计交点个数： 遍历完所有边后，得到射线与多边形有效交点的个数。
判断点的位置：
- 若交点个数为奇数，则点在多边形内部。
- 若交点个数为偶数，则点在多边形外部。

特殊情况处理：

射线穿过多边形顶点： 需要特殊处理，避免重复计数。
射线与多边形边重合： 这种情况需要根据具体情况判断是否算作相交。

代码示例 (Python):

def is_point_in_polygon(point, polygon):
    """
    使用射线法判断点是否在多边形内

    参数:
        point: 目标点坐标 (x, y)
        polygon: 多边形顶点坐标列表 [(x1, y1), (x2, y2), ...]

    返回值:
        True: 点在多边形内
        False: 点在多边形外
    """

    cross_count = 0
    polygon_length = len(polygon)

    for i in range(polygon_length):
        p1 = polygon[i]
        p2 = polygon[(i + 1) % polygon_length] # 取下一条边，最后一条边连接第一条边

        # 处理水平边
        if p1[1] == p2[1]:
            continue

        # 判断射线是否穿过边
        if (point[1] < p1[1] and point[1] >= p2[1]) or (point[1] >= p1[1] and point[1] < p2[1]):
            # 计算交点横坐标
            x = p1[0] + (point[1] - p1[1]) * (p2[0] - p1[0]) / (p2[1] - p1[1])

            # 判断交点是否有效
            if x > point[0]:
                cross_count += 1

    return cross_count % 2 == 1  # 奇数个交点，点在多边形内

总结：

射线法是一种简单高效的点与多边形关系判断方法，但需要注意处理特殊情况。以上代码示例仅供参考，实际应用中需要根据具体情况进行调整。