射线法判断点是否在多边形内：算法详解及代码实现

射线法判断点是否在多边形内：算法详解及代码实现

射线法是一种常用的判断点是否在多边形内的算法。其原理是：从待判断点 P 向右引一条水平射线，统计射线与多边形边界的交点数量。如果交点数量为奇数，则点 P 在多边形内；否则点 P 在多边形外。

算法步骤：

1. 选择射线： 选择一条水平的、向点 P 的右侧延伸的、平行于 X 轴的射线。
2. 遍历多边形边： 遍历多边形的所有边，判断射线是否与边相交。
3. 交点计数： 如果射线与边相交，则交点计数加 1。
4. 判断结果： 如果交点计数为奇数，则点 P 在多边形内；否则点 P 在多边形外。

特殊情况处理：

1. 水平边： 水平边不参与交点计数。
2. 边方向： 为了避免重复计数，需要根据边的方向进行判断：
   • 方向向上的边包括其开始点，不包括其终止点。
   • 方向向下的边不包括其开始点，包括其终止点。
3. 交点位置： 交点必须严格在点 P 的右边。

代码示例（Python）：

def is_point_in_polygon(point, polygon):
    '''
    判断点是否在多边形内

    Args:
        point: 待判断点 (x, y)
        polygon: 多边形顶点列表 [(x1, y1), (x2, y2), ...]

    Returns:
        True: 点在多边形内
        False: 点在多边形外
    '''
    count = 0
    for i in range(len(polygon)):
        # 获取当前边和下一条边
        p1 = polygon[i]
        p2 = polygon[(i + 1) % len(polygon)]

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

        # 处理边方向
        if p1[1] < p2[1]:
            if p1[1] <= point[1] < p2[1]:
                # 判断交点是否在点 P 的右边
                if (p2[0] - p1[0]) * (point[1] - p1[1]) / (p2[1] - p1[1]) > point[0]:
                    count += 1
        else:
            if p2[1] <= point[1] < p1[1]:
                # 判断交点是否在点 P 的右边
                if (p2[0] - p1[0]) * (point[1] - p1[1]) / (p2[1] - p1[1]) > point[0]:
                    count += 1

    # 判断交点数量
    return count % 2 == 1

# 示例用法
point = (1, 1)
polygon = [(0, 0), (2, 0), (2, 2), (0, 2)]

if is_point_in_polygon(point, polygon):
    print('点在多边形内')
else:
    print('点在多边形外')

总结：

射线法是一种简单有效的判断点是否在多边形内的算法。通过清晰的步骤和代码示例，可以轻松理解并应用该算法。在实际应用中，可以根据具体需求对算法进行优化，以提高效率。