编辑“︁多边形表示”︁

= 多边形表示 =

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

== 基本概念 ==

多边形可以定义为平面内由'''有限条线段'''首尾顺次连接组成的'''闭合图形'''。根据边的性质，多边形可分为：
* '''简单多边形'''：边不相交（除相邻边在顶点处相交）。
* '''复杂多边形'''：边存在自相交。

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

== 表示方法 ==

=== 1. 顶点列表（Point List） ===
最直接的表示方式是按顺序存储多边形的所有顶点坐标。例如：
<syntaxhighlight lang="python">
polygon = [(0, 0), (2, 0), (2, 2), (1, 3), (0, 2)]  # 五边形
</syntaxhighlight>

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

=== 2. 边列表（Edge List） ===
显式存储多边形的所有边。例如：
<syntaxhighlight lang="python">
edges = [((0, 0), (2, 0)), ((2, 0), (2, 2)), ((2, 2), (1, 3)), 
         ((1, 3), (0, 2)), ((0, 2), (0, 0))]
</syntaxhighlight>

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

=== 3. 翼边结构（Winged-Edge） ===
高级表示法，记录每条边的起点、终点、左右相邻边及左右多边形（适用于网格）。数据结构示例：
<syntaxhighlight lang="cpp">
struct WingedEdge {
    Vertex* start, *end;
    WingedEdge* leftPrev, *leftNext;
    WingedEdge* rightPrev, *rightNext;
};
</syntaxhighlight>

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

== 方向性与 winding number ==

多边形的顶点顺序决定其“方向”：
* '''顺时针（CW）'''：顶点按顺时针排列。
* '''逆时针（CCW）'''：顶点按逆时针排列。

方向性影响面积计算、点包含测试等算法。面积公式（鞋带公式）：
<math>
\text{Area} = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i) \right|
</math>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 实际应用案例 ==

=== 案例1：游戏中的碰撞检测 ===
在2D游戏中，多边形的表示用于检测角色（点）是否位于障碍物（多边形）内。例如：
* 使用'''射线法'''（Ray Casting）判断点是否在多边形内部。

=== 案例2：地理信息系统（GIS） ===
地图中的行政区划常表示为多边形，需支持：
* '''多边形合并'''（如合并相邻省份）。
* '''裁剪'''（如计算两个区域的交集）。

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

== 常见问题与注意事项 ==

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

== 进阶话题 ==

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

{{Stub}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:计算几何算法]]