Question

三角剖分

平面上散布许多点。只以这些点作为三角形顶点，用线段连接产生三角形，三角形数量越多越好。所有线段形成一个“三角剖分”，通常有许多种。

因为三角形数量越多越好，所以三角剖分的外围一定是凸包。

三角形的建构顺序、建构地点都相当自由，也因此各种凸包演算法都可以顺便求得三角剖分。

三角剖分的三角形个数、边数

计算凸包的三角剖分，再用剩下的点递迴分割所在的三角形，最后处理共线的点。

令 h 是凸包点数，令 k 是其馀点数。凸包的三角剖分得到 h-2 个三角形；剩下的点，逐次用于三角剖分，每次都多出两个三角形。由此可知，无论三角剖分长相如何，一个三角剖分固定有(h-2)+2k 个三角形，是 O(N)。

同理可知，无论三角剖分长相如何，一个三角剖分固定有(2h-3)+3k 条边，亦是 O(N)。

这也呼应了平面图欧拉公式 v-e+f=2。

三角剖分的数量

计算不同的三角剖分有多少种，目前除了穷举法以外没有更好的演算法，也无人知道这是 P 问题抑或是 NP-complete 问题。

Flip Graph

一个三角剖分，翻转一条边，可以得到另一个三角剖分。注意到并不是每一条边都能翻转的。

二维平面上，给定一个点集合，把所有三角剖分依照翻转关係连接成一张无向图，称作 Flip Graph，是连通的。

Flip Graph 有著许多谜团，例如点到点最短路径（两个三角剖分之间的最少翻转次数）、直径、连接性，目前都没有演算法。

Tetrahedralization

推广到三维空间称作“四面体剖分”。

四面体剖分的 Flip Graph 目前完全不知道长什麽样。

演算法（Graham's Scan）

仿照“ Convex Hull: Graham's Scan ”，扫除凸包顶点的过程即可进行三角剖分。一如既往，共线的点不好处理。时间複杂度 O(NlogN)，主要取决于排序的时间。

演算法（Incremental Method）

仿照“ Convex Hull: Incremental Algorithm ”，如果当前输入点在三角形内部，则直接连线至三角形顶点；如果当前输入点在所有三角形外部，则连线至凸包的切点与凹点。要小心当前输入点在三角形上的情况。时间複杂度 O(N^2)。

如果预先按照 XY 座标排序所有点（平移的扫描线），就能保证当前输入点都在所有三角形外部。

当前输入点与凹点的连线，不超过三角剖分的边数 O(N)；当前输入点与切点的连线，等同 Andrew's Monotone Chain，时间複杂度是 O(NlogN)。分开分析，总时间複杂度 O(NlogN)。

演算法（Divide and Conquer）

仿照“ Convex Hull: Divide and Conquer ”，寻找外公切线的过程即可合併左右两个三角剖分。时间複杂度 O(NlogN)。

Minimum Weight Triangulation

Minimum Weight Triangulation

线段长度总和最小的三角剖分，至今时间複杂度仍旧不明。

判断一个三角剖分是不是线段长度总和最小的三角剖分，则是 NP-hard 问题。

Minimum Weight Triangulation 的用途是制做一个节省印刷墨水的三角剖分。

Acute Triangulation

Acute Triangulation

每一个角都是锐角（小于 90°）的三角剖分。目前已经有演算法，但是还没有一个定论，有兴趣的话请自行搜寻论文。

Acute Triangulation 的用途是制做一个美观的三角剖分。

Delaunay Triangulation（Minmax Angle Triangulation）

Voronoi Diagram 与 Delaunay Triangulation

Delaunay 是 Voronoi 的博士班学生。Delaunay Triangulation 起初是从 Voronoi Diagram 发展来的。

Voronoi Diagram 变 Delaunay Triangulation：以直线连结相邻的点。简单来说就是平面对偶、边拉直。时间複杂度 O(N)。

Delaunay Triangulation 变 Voronoi Diagram：以直线连结相邻的三角形的外接圆圆心，并且补上凸包每一条边的中垂线。时间複杂度 O(N)。

Delaunay Triangulation 的数量

只有三点以下共圆，Voronoi Diagram 与 Delaunay Triangulation 只有唯一一种，互相对应。

出现四点以上共圆，Voronoi Diagram 仍然只有唯一一种，Delaunay Triangulation 则有许多种。

性质：三角形外接圆，内部不含任何点

【待补证明】

性质：最小的角尽量大

【待补证明】

Voronoi Diagram 与 Delaunay Triangulation，聚集了邻近的点，排斥了偏远的点。

Voronoi Diagram 的外表是中垂线与距离，Delaunay Triangulation 的内裡则是圆与角度。

演算法（Edge Flip Algorithm）

随意求出一个三角剖分。不断翻转不符空圆性质的边，使最小角逐渐增大（或者最小角不变、次小角增大，以此类推），就得到 Minmax Angle Triangulation。时间複杂度不明。

【待补证明】

演算法（Incremental Method）

online 演算法，随时维护一个 Minmax Angle Triangulation。

每当输入一点，马上寻找不符空圆性质的三角形们，形成一个多边形，清除内部的边，连接当前输入点与多边形顶点们，就得到 Minmax Angle Triangulation。时间複杂度 O(N^2)。

採用 Flip Edge Algorithm，配合特殊资料结构，可以加速至 O(NlogN)。此处略过不提。

演算法（Divide and Conquer）

O(NlogN)。

Compatible Triangulation

Compatible Triangulation

两个三角剖分，点数相同，每一点相互对应，每一个三角形的三个顶点也相互对应，称作 Compatible Triangulation。

Compatible Triangulation 在 3D 动画领域相当重要，主要是让物体外观可以平滑变形。

至今仍无演算法可求得 Compatible Triangulation？

https://cs.uwaterloo.ca/~tmchan/morph_soda.pdf

Polygon Triangulation

Polygon Triangulation

简单多边形，沿对角线切割，成为许多三角形。对角线、多边形互不交错。通常有许多种。

N 个顶点，N-2 个三角形，N-3 条对角线。

“耳 ear”是凸点与邻点组成的三角形，而且未与其他边相交。“嘴 mouth”是凹点与邻点组成的三角形。剩下的点没有取名。

耳适合当作剖分对象。但是简单多边形一定有耳吗？

三角形的相邻关係，恰是一棵树。超过一点的树，至少有两叶。

叶必是耳。超过三点的多边形，至少有两耳，且两耳不重叠。

也就是说，简单多边形无论长相，必有耳。甚至可以不断刵耳，直到剩下三角形，得到三角剖分！

演算法（Enumeration）

穷举所有点，判断是否为耳（的凸点）？若为耳，则刵之。

判断一个点是否为耳（的凸点）有两种方式：一、穷举多边形所有点。皆在三角形外，便是耳。二、穷举多边形所有边。皆在三角形外，便是耳。大家习惯使用第一种方式。

多边形的资料结构是 circular linked list，以便快速刵耳。

未知点最初共 N 点。刵 1 次，至多添 2 点；刵 N-3 次，至多添 2N-6 点。未知点至多 3N-6 点。判断一个点是否为耳需时 O(N)，总时间複杂度为 O((3N-6) * N) = O(N^2)。

Polygon Trapezoidalization

Polygon Trapezoidalization

简单多边形，每个顶点发射水平线（垂直线），切割成许多梯形、三角形。梯形剖分只有唯一一种。

梯形剖分的用途是建立区域相邻关係，形成有向无环图！扫描线的顺序就是拓朴顺序，方便设计高速演算法。有洞多边形亦然。

UVa 12310 ICPC 2479 3702

Convex Partition

简单多边形，切成许多个凸多边形。

演算法是 Hertel-Mehlhorn Algorithm。我没有研究。

Envelope（Under Construction!）

Convex Hull 与 Envelope 互为点线对偶

点集合求凸包，点线对偶，直线集合以半平面交集求包络线。

也就是说，求半平面交集的困难度等同于求凸包的困难度。

【待补文字】

UVa 11756

增加一个维度的 Convex Hull

点座标(x, y) 改成(x, y, x^2+y^2) 之后，呈现抛物面。

平面与抛物面的交集，投影至 XY 平面，恰是圆。圆半径为 r，平面与切面距离为 r^2。

【待补图片】

求得新座标的 3D Convex Hull：

自下方无限远处仰视（下凸包投影至 XY 平面），就是 Nearest Point Voronoi Diagram 的对偶图，空圆的三角剖分，也就是 Delaunay Triangulation。

自上方无限远处俯视（上凸包投影至 XY 平面），就是 Farthest Point Voronoi Diagram 的对偶图。

【待补图片】

增加一个维度的 Envelope

点座标(x, y) 改成(x, y, x^2+y^2) 之后，呈现抛物面。

两个座标，其两个切面交集，投影至 XY 平面，恰是中垂线。

【待补图片】

求得新座标的切面的 3D Envelope：

自下方无限远处仰视（下包络面投影至 XY 平面），就是 Delaunay Triangulation。

自上方无限远处俯视（上包络面投影至 XY 平面），就是 Voronoi Diagram。

【待补图片】