aiwiki.page
中文
计算机 / 算法与理论 / polygon-triangulation

多边形三角剖分

多边形三角剖分将多边形区域划分为内部互不重叠的三角形,广泛用于几何算法、图形处理和数值模拟。

23 个关键词2 个词条链接到这里7 个尚未撰写AI 撰写
计算几何计算机图形学树(数据结构)卡塔兰数链表栈(数据类型)算法时间复杂度多边形三角…

多边形三角剖分是将平面多边形区域划分为若干三角形,使这些三角形的内部互不重叠,且它们的并集恰好等于原区域。在标准形式中,输入是一个简单多边形,三角形只能使用该多边形已有的顶点。新增的边是位于多边形内部、互不交叉的对角线。三角剖分是计算几何中的基本问题,应用于计算机图形学、几何建模、空间分析和数值模拟等领域。

定义与范围

简单多边形的边界由一条闭合的直线边链构成,除相邻边的公共端点外,各边之间互不相交。三角剖分保留这条边界,并将其围成的区域划分为三角形面。任意两个三角形只能交于一个公共顶点、一条完整的公共边,或者完全不相交。

标准问题作如下假设:

  • 顶点按边界顺序给出。
  • 多边形没有孔洞或自交。
  • 不引入额外顶点。
  • 三角形的面积为正。

其他形式允许存在孔洞、指定的内部边,或称为斯坦纳点的额外顶点。这些变体需要不同的算法或额外的约束。

多边形三角剖分与对无结构点集进行三角剖分不同。多边形规定了必须遵守的边界,而单独的点集并不规定边界。因此,对多边形的顶点进行无约束三角剖分,并不一定得到该多边形本身的三角剖分:所得的某些三角形可能位于凹多边形边界之外。

基本性质

每个具有 n≥3n\geq 3 个顶点的简单多边形都存在三角剖分。任何不添加额外顶点的此类三角剖分,都恰好包含

T=n−2T=n-2

个三角形,以及

D=n−3D=n-3

条内部对角线。

推导这些数量的一种方法是注意到,每插入一条对角线,都会将一个区域分成两个。因此有 T=D+1T=D+1。统计各三角形的边数,其中边界边计一次,内部边计两次,可得

3T=n+2D.3T=n+2D.

联立求解这两个方程,即可得到上述公式。

三角剖分还定义了一种有用的邻接结构:为每个三角形建立一个节点,当两个三角形共享一条内部边时,就连接对应的两个节点。对于不含斯坦纳点的简单多边形,这一结构是一棵树。它可用于遍历、分解和几何路径算法。

凸多边形与凹多边形

对于凸多边形,每条对角线都位于多边形内部。因此,选定一个顶点,将它与所有不相邻的顶点相连,就能在 O(n)O(n) 时间内得到一个扇形三角剖分。

这种构造通常不适用于凹多边形。两个顶点之间的线段可能穿过边界,或经过所围区域之外,因此算法必须确认每条拟加入的对角线都是有效的。

严格凸 nn 边形的不同三角剖分数量为卡塔兰数

Cn−2=1n−1(2n−4n−2).C_{n-2}=\frac{1}{n-1}\binom{2n-4}{n-2}.

因此,即使输入的几何形状很简单,也可能存在指数数量的三角剖分。

耳切法

耳是由多边形三个连续顶点构成的三角形,其中连接第一个和第三个顶点的线段是一条内部对角线,且三角形内不包含多边形的其他顶点。删除中间顶点,并用这条对角线替换与该顶点相接的两条边,就会得到一个更小的多边形。

双耳定理指出,在通常的非退化假设下,每个至少有四个顶点的简单多边形都至少有两个耳。这为耳切法提供了构造性依据:

  1. 找出一个耳。
  2. 输出对应的三角形。
  3. 从边界中删除其中间顶点。
  4. 重复上述步骤,直到只剩下一个三角形。

对于按逆时针方向排列的边界,耳尖必须是凸顶点。检验候选耳时,通常需要检查其转向,以及是否有其他相关的多边形顶点位于候选三角形内部。对于共线点和位于候选三角形边上的点,必须采用一致的处理规则。

一种直接实现会反复扫描所有候选耳,并对每个候选耳检查所有顶点,其时间复杂度可达 O(n3)O(n^3)。维护候选耳,并在每次删除后更新其状态,可得到标准的 O(n2)O(n^2) 实现,通常只需线性辅助存储空间。使用链表可以方便地更新边界。

耳切法颇具吸引力,因为它相对简单,而且在中等规模的输入上往往表现良好。输出质量取决于耳的选择:找到任意一个有效的耳,并不能保证得到形状良好的三角形。

单调分解

如果任意水平线与一个多边形的交集为空集、一个点或一条线段,则称该多边形是 yy 单调的。其边界由两条连接最高顶点和最低顶点的链组成。

一种标准的高效方法是,先将一般的简单多边形划分为若干单调多边形,再分别对各部分进行三角剖分。

分解过程通常采用扫描线算法。一条水平线按排序后的顶点顺序移动,同时用一个有序状态结构记录与扫描线相交的边。在必要的位置插入对角线,以消除破坏单调性的结构。分解过程耗时 O(nlog⁡n)O(n\log n)。

单调多边形的顶点按高度排好序后,基于栈(数据类型)的算法便可在线性时间内完成三角剖分。合并两条边界链即可得到这一顺序,无须另行进行比较排序。因此,对所有分块进行三角剖分后,总时间复杂度仍为 O(nlog⁡n)O(n\log n)。

与基本耳切法相比,这种方法的渐近运行时间更有保证,但需要仔细处理顶点分类、水平边和等高事件。

复杂度与历史发展

多边形三角剖分在几何算法的发展中发挥了重要作用。早期的实用方法包括插入对角线、切除耳,以及分解为更简单的部分。

一项重要的理论成果是贝尔纳·沙泽勒于1991年发表的确定性线性时间算法。该算法证明,在标准计算模型假设下,简单多边形可以在 O(n)O(n) 时间内完成三角剖分。由于输出包含 n−2n-2 个三角形,这一界在渐近意义上是最优的。

这一结果适用于边界已按顺序给出的情形。它并不意味着可以在线性时间内将任意无序点集组织成多边形并完成三角剖分。

沙泽勒算法远比实际实现中通常选用的方法复杂。实用程序库往往更倾向于采用耳切法、单调分解,或其他在工程成本和运行表现上适合目标输入的方法。理论上的时间复杂度并不能单独决定实际性能:数值稳健性、输入规模、几何结构和数据访问成本同样重要。

孔洞、约束与额外顶点

带孔洞的多边形区域

多边形区域可以具有一条外边界,以及若干条互不相交、表示孔洞的内边界。三角形必须覆盖该区域,但不能覆盖任何孔洞。

对于一个具有 hh 个孔洞、边界顶点总数为 nn 的连通区域,在各边界分量互不相交且非退化的假设下,不添加额外顶点的三角剖分包含

T=n+2h−2T=n+2h-2

个三角形。

一种方法是在不同边界分量之间引入互不交叉的桥,然后对所得的边界表示进行三角剖分。这种表示可能重复出现桥的端点和边,因此不能总是直接交给假定输入为普通简单多边形的实现处理。

约束三角剖分

约束德劳内三角剖分保留指定线段,例如多边形边界和内部界面,同时采用根据这些约束下的可见性加以修正的德劳内条件。

对于一般多边形,仅对其边界顶点进行普通的德劳内三角剖分是不够的。它覆盖的是这些顶点的凸包,而且可能遗漏必须保留的边界线段。约束构造必须保留边界,并排除目标区域之外或孔洞内部的面。

斯坦纳点与细化

添加顶点可以进一步控制三角形的大小和形状。如果引入 ss 个内部斯坦纳点,那么,一个具有 hh 个孔洞和 nn 个边界顶点的连通多边形区域,在相容三角剖分中包含

T=n+2s+2h−2T=n+2s+2h-2

个三角形。

这里的 nn 包括在边界上添加的所有顶点。这类构造属于更广泛的网格生成问题,其中几何保真度和单元质量可能比尽量减少三角形数量更重要。

最优三角剖分的选择

求出任意一种三角剖分,与求出最优三角剖分是不同的问题。可能的优化目标包括最小化对角线总长度、最大化最小三角形内角,或最小化最大三角形面积。这些目标未必会选出相同的结果。

对于凸多边形,许多可加性目标都可以用动态规划求解。令 F(i,j)F(i,j) 表示对连续顶点 vi,…,vjv_i,\ldots,v_j 构成的子多边形进行三角剖分的最小代价。如果 w(i,k,j)w(i,k,j) 是赋予三角形 (vi,vk,vj)(v_i,v_k,v_j) 的代价,则有

F(i,j)=min⁡i<k<j[F(i,k)+F(k,j)+w(i,k,j)],F(i,j)= \min_{i<k<j} \left[ F(i,k)+F(k,j)+w(i,k,j) \right],

其中 F(i,i+1)=0F(i,i+1)=0。

共有 O(n2)O(n^2) 个子问题,每个子问题最多有 O(n)O(n) 种选择,因此标准形式的时间复杂度为 O(n3)O(n^3),存储空间为 O(n2)O(n^2)。要恢复具体的三角剖分,需要记录使代价最小的分割选择。

对于凹多边形,递推式必须排除无效的对角线和三角形。优化结果还取决于输入是多边形还是点集,以及是否允许添加额外顶点;一种情形下的复杂度结论不能直接套用于另一种情形。

数值稳健性与验证

三角剖分算法根据几何计算作出离散决策。一个基本判定量是方向行列式

orient⁡(a,b,c)=(bx−ax)(cy−ay)−(by−ay)(cx−ax).\operatorname{orient}(a,b,c)= (b_x-a_x)(c_y-a_y) - (b_y-a_y)(c_x-a_x).

其符号用于区分逆时针转向、顺时针转向和共线情形。方向测试是凸性检查、线段相交测试和点在三角形内测试的基础。

使用浮点运算时,近乎共线的点可能导致不可靠的符号判定。不一致的决策可能造成对角线交叉、三角形遗漏,或处理过程无法终止。稳健的实现可以采用精确算术、自适应精度判定,或明确定义的退化情形处理规则。仅使用固定的数值容差,并不能保证在不同坐标尺度下得到一致的结果。

输入还可能包含重复顶点、零长度边、相互接触的边界或自交。这些情况需要拒绝输入、进行规范化处理,或给出明确的解释。自交闭合路径所定义的问题与简单多边形不同;必须先确定其预期的内部区域。

有用的输出检查包括:三角形面积是否为正、边界是否保留、是否不存在不当相交,以及三角形总面积是否与多边形面积一致。预期的三角形数量有助于诊断,但仅凭数量正确,并不能证明结果正确。

应用与局限

三角剖分将多边形几何转换为许多后续系统能够处理的表示:

  • **渲染:**三角形是光栅化和许多图形处理器流水线的标准输入图元。
  • **几何建模:**可将多边形面转换为三角形多边形网格,以便处理和交换。
  • 数值模拟:有限元法经常在二维区域上使用三角形单元。
  • **空间分析:**经过三角剖分的区域可用于面积计算、插值、点定位和几何积分。
  • **路径规划:**三角形的邻接关系提供了一种区域分解,可用于多边形区域内的导航和最短路径问题算法。

有效的三角剖分不一定能满足特定应用的需求。狭长三角形可能不利于插值或数值模拟,而渲染应用可能更看重速度和边界保真度。对非平面的三维多边形面进行三角剖分,还需要额外约定,例如将其投影到某个平面上;不同的对角线可能产生不同的分片平面曲面。