多边形表示

多边形表示

多边形表示是计算几何中的基础概念，指在计算机中描述和存储多边形几何形状的方法。多边形由一系列有序的顶点（或称为节点）组成，这些顶点通过边连接形成闭合的平面图形。在多边形表示中，顶点的顺序、存储结构以及坐标系的定义直接影响算法的正确性和效率。

基本概念

多边形可以定义为平面内由有限条线段首尾顺次连接组成的闭合图形。根据边的性质，多边形可分为：

• 简单多边形：边不相交（除相邻边在顶点处相交）。
• 复杂多边形：边存在自相交。

数学定义

设多边形由$n$个顶点组成，记为$P=\{v_0,v_1,\dots ,v_{n-1}\}$，其中$v_i=(x_i,y_i)$表示第$i$个顶点的坐标。多边形的边为$e_i=\overline{v_i{v}_{i+1}}$（约定$v_n=v_0$）。

表示方法

1. 顶点列表（Point List）

最直接的表示方式是按顺序存储多边形的所有顶点坐标。例如：

polygon = [(0, 0), (2, 0), (2, 2), (1, 3), (0, 2)]  # 五边形

优点：存储简单，适合大多数计算几何算法。 缺点：未显式存储边关系，需动态计算。

2. 边列表（Edge List）

显式存储多边形的所有边。例如：

edges = [((0, 0), (2, 0)), ((2, 0), (2, 2)), ((2, 2), (1, 3)), 
         ((1, 3), (0, 2)), ((0, 2), (0, 0))]

优点：明确边的连接关系。 缺点：存储冗余（相邻边共享顶点）。

3. 翼边结构（Winged-Edge）

高级表示法，记录每条边的起点、终点、左右相邻边及左右多边形（适用于网格）。数据结构示例：

struct WingedEdge {
    Vertex* start, *end;
    WingedEdge* leftPrev, *leftNext;
    WingedEdge* rightPrev, *rightNext;
};

优点：高效支持拓扑查询（如邻边遍历）。 缺点：实现复杂，内存开销大。

方向性与 winding number

多边形的顶点顺序决定其“方向”：

• 顺时针（CW）：顶点按顺时针排列。
• 逆时针（CCW）：顶点按逆时针排列。

方向性影响面积计算、点包含测试等算法。面积公式（鞋带公式）： $\text{Area}=\frac{1}{2}|\sum _{i=0}^{n-1}(x_i{y}_{i+1}-x_{i+1}{y}_i)|$

代码示例：判断多边形方向

def is_clockwise(polygon):
    area = 0
    n = len(polygon)
    for i in range(n):
        x_i, y_i = polygon[i]
        x_j, y_j = polygon[(i + 1) % n]
        area += (x_j - x_i) * (y_j + y_i)
    return area > 0

# 测试
polygon = [(0, 0), (2, 0), (2, 2), (0, 2)]  # 逆时针
print(is_clockwise(polygon))  # 输出: False

实际应用案例

案例1：游戏中的碰撞检测

在2D游戏中，多边形的表示用于检测角色（点）是否位于障碍物（多边形）内。例如：

• 使用射线法（Ray Casting）判断点是否在多边形内部。

案例2：地理信息系统（GIS）

地图中的行政区划常表示为多边形，需支持：

• 多边形合并（如合并相邻省份）。
• 裁剪（如计算两个区域的交集）。

graph TD A[多边形A] -->|合并| C[新多边形] B[多边形B] -->|合并| C D[点P] -->|射线法| E[在内部?]

常见问题与注意事项

1. 顶点顺序一致性：确保所有顶点按统一方向排列。 2. 闭合性检查：首尾顶点必须相同（除非使用隐式闭合）。 3. 浮点精度：坐标计算时注意浮点误差累积。

进阶话题

• 带洞多边形：通过外环+内环表示（如岛屿中的湖泊）。
• 三维多边形（多边形网格）：需扩展至三维空间（如STL文件格式）。