简单多边形

形式陈述 ​

给定按循环顺序排列的平面顶点 $v_0,\dots ,v_{n-1}$，令边 $e_i=[v_i,v_{(i+1)modn}]$。在本页约定中，$n\ge 3$、相邻顶点不同，非相邻边不相交，相邻边只在共同端点相交，且不存在重叠边段；这条闭折线称为简单多边形的边界。它在图论上是一条圈公理库路与圈Path and cycle in a graph由相邻顶点序列形成的路，以及首尾闭合的圈。，几何上则带有直线段嵌入与循环次序。

Jordan 曲线定理公理库Jordan 曲线定理Jordan curve theorem平面中简单闭曲线的补集恰有内外两个连通分支且曲线是共同边界。证明上述简单边界把平面分成一个有界内部、一个无界外部和边界本身；这是定义良好性的后续保证，不是识别“不自交闭折线”前必须先掌握的构造材料。本页的简单多边形指闭包“内部 $\cup$ 边界”，不含孔洞。顶点按逆时针排列时，有向面积

$$A=\frac{1}{2}\sum _{i=0}^{n-1}(x_i{y}_{i+1}-x_{i+1}{y}_i)$$

为正；顺时针时为负。符号依赖坐标系方向约定；方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。只是判断局部转向和检测相交的算法工具，不参与简单多边形对象的定义。

直觉 ​

“简单”只表示边界不穿过自己，不表示多边形凸、边数少或外观规整。凹陷可以任意深，只要沿边界走一圈时每个非相邻边段互不相遇，仍能清楚区分内部与外部。这个拓扑保证是点内判定、三角剖分和多边形布尔运算能够建立不变量的起点。

顶点列表不仅是一组点，还规定相邻关系和方向。同样的点集按不同顺序连接，可能得到简单多边形，也可能得到自交折线；因此凸包或点集排序不能替代边界输入。

例子与边界 ​

轴对齐的 L 形边界是凹简单多边形：其某些内角大于 $\pi$，但边没有自交，内部仍是一个连通有界区域。四个点按矩形周界顺序连接也给出简单多边形；若改按对角交替连接，就形成“蝴蝶结”，两条非相邻边在内部相交，不再满足定义。

连续重复顶点会产生零长度边，非相邻边只在端点“轻触”会让边界不再是 Jordan 曲线，共线边重叠则使同一边界片段被走多次。这些退化输入不能靠“肉眼仍像一个区域”忽略；几何算法应拒绝它们，或先明确一种更宽的弱简单多边形模型。

一个外框加一条内框可以描述带孔多边形区域，却不是单个简单多边形的内部，因为边界有两个连通分支。类似地，自交多边形可用奇偶规则或绕数定义填充区域，但那是另一种对象，不能直接套用简单多边形的三角剖分结论。

推论与应用 ​

简单边界使点可稳定分类为 interior、exterior 或 boundary，也保证存在不引入新顶点的三角剖分。计算几何中的点内判定、可见性、多边形面积与裁剪算法都依赖这里的非自交和退化约定；若输入允许孔洞或自交，数据结构和证明都要同步改变。

有向面积还提供全局方向检查，但面积非零本身不能证明简单性：蝴蝶结各部分的有向贡献可能抵消或留下非零值。验证输入仍需检查非相邻边相交，而不是用一个数值替代拓扑条件。

参考资料

• Joseph O’Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, 1998, Chs. 1–2.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Ch. 3.