点的包含性测试

点的包含性测试（Point-in-Polygon Test）是计算几何中的一个基础问题，用于判断一个给定点是否位于多边形内部、外部或边界上。该算法在地理信息系统（GIS）、计算机图形学、碰撞检测等领域有广泛应用。

问题描述[编辑 | 编辑源代码]

给定一个点 $P (x, y)$ 和一个由 $n$ 个顶点组成的多边形 $V = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})}$ ，判断点 $P$ 是否在多边形内部。

常用算法[编辑 | 编辑源代码]

射线投射法（Ray Casting Algorithm）[编辑 | 编辑源代码]

最常用的方法是射线投射法，其核心思想是从点 $P$ 向任意方向（通常向右）发射一条射线，统计该射线与多边形边界的交点数量：

如果交点数量为奇数，则点在多边形内部。
如果交点数量为偶数，则点在多边形外部。

算法步骤[编辑 | 编辑源代码]

1. 从点 $P (x, y)$ 向右发射一条水平射线。 2. 遍历多边形的每一条边 $V_{i} V_{i + 1}$ （假设 $V_{n + 1} = V_{1}$ ），检查射线是否与边相交。 3. 统计交点数量，根据奇偶性判断点的位置。

边界情况处理[编辑 | 编辑源代码]

如果点 $P$ 在多边形的顶点上，直接判定为在边界上。
如果射线与多边形的边重合（水平边），需要特殊处理以避免重复计数。

代码实现[编辑 | 编辑源代码]

以下是 Python 实现示例：

def point_in_polygon(point, polygon):
    x, y = point
    n = len(polygon)
    inside = False
    p1x, p1y = polygon[0]
    for i in range(n + 1):
        p2x, p2y = polygon[i % n]
        if y > min(p1y, p2y):
            if y <= max(p1y, p2y):
                if x <= max(p1x, p2x):
                    if p1y != p2y:
                        xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x, p1y = p2x, p2y
    return inside

# 示例输入
polygon = [(0, 0), (4, 0), (4, 4), (0, 4)]  # 正方形
point1 = (2, 2)  # 内部
point2 = (5, 5)  # 外部

print(point_in_polygon(point1, polygon))  # 输出: True
print(point_in_polygon(point2, polygon))  # 输出: False

绕数法（Winding Number Algorithm）[编辑 | 编辑源代码]

另一种方法是绕数法，通过计算点 $P$ 绕多边形一周的旋转角度总和（绕数）来判断：

如果绕数不为零，则点在多边形内部。
如果绕数为零，则点在多边形外部。

算法步骤[编辑 | 编辑源代码]

1. 遍历多边形的每一条边 $V_{i} V_{i + 1}$ 。 2. 计算向量 $\vec{V_{i} P}$ 和 $\vec{V_{i} V_{i + 1}}$ 的叉积和点积，得到角度变化。 3. 累加角度变化，计算绕数。

代码实现[编辑 | 编辑源代码]

import math

def point_in_polygon_winding(point, polygon):
    x, y = point
    n = len(polygon)
    winding_number = 0
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i + 1) % n]
        if y1 <= y:
            if y2 > y and (x2 - x1) * (y - y1) - (x - x1) * (y2 - y1) > 0:
                winding_number += 1
        else:
            if y2 <= y and (x2 - x1) * (y - y1) - (x - x1) * (y2 - y1) < 0:
                winding_number -= 1
    return winding_number != 0

# 示例输入
polygon = [(0, 0), (4, 0), (4, 4), (0, 4)]  # 正方形
point1 = (2, 2)  # 内部
point2 = (5, 5)  # 外部

print(point_in_polygon_winding(point1, polygon))  # 输出: True
print(point_in_polygon_winding(point2, polygon))  # 输出: False

实际应用案例[编辑 | 编辑源代码]

地理信息系统（GIS）[编辑 | 编辑源代码]

在 GIS 中，点的包含性测试用于：

判断一个地理位置（如建筑物）是否位于某个行政区域内。
筛选特定区域内的数据点（如气象站、人口普查区）。

计算机图形学[编辑 | 编辑源代码]

在图形学中，该算法用于：

多边形填充（判断像素是否在多边形内）。
碰撞检测（判断物体是否进入特定区域）。

可视化示例[编辑 | 编辑源代码]

以下是一个多边形和测试点的示意图：

性能分析[编辑 | 编辑源代码]

时间复杂度：两种算法均为 $O (n)$ ，其中 $n$ 为多边形边数。
空间复杂度： $O (1)$ ，仅需存储多边形顶点。

边界与退化情况[编辑 | 编辑源代码]

点在多边形边上：需额外判断是否满足边方程。
凹多边形：算法仍适用，但需注意射线与多边形的多次相交。
自相交多边形：绕数法更可靠，射线法可能失效。

总结[编辑 | 编辑源代码]

点的包含性测试是计算几何中的基础问题，可通过射线法或绕数法解决。实际应用中需根据场景选择算法，并注意处理边界情况。