I. Tetrahedralization
数学大学
I. Tetrahedralization
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
I. Tetrahedralization
计算几何 · 03. Triangulation
Polyhedron Decomposition
多面体分解：把多面体切成四面体是三维「三角剖分」的对应物。
四面体化
三维的基本单元是四面体，对应平面的三角形
难点
并非所有无洞多面体都能不加点剖成四面体
Schonhardt's Polyhedron
Schönhardt 多面体：著名的反例——内部不存在任何对角线，无法四面体化（不加Steiner点）。
构造
三棱柱顶面旋转一定角度制成
含义
三维剖分必须允许添加辅助顶点
Seidel's Polygon
Seidel 算法相关：随机增量法在三维剖分与凸包中的延续应用。
随机增量
随机序插入维持期望意义上的高效
关联
Seidel 多边形示例说明剖分输入的复杂性来源
本节要点
- ✓四面体化是三维版三角剖分
- ✓Schönhardt 多面体：不加点的剖分反例
- ✓随机增量法是三维算法的主流手法
延伸主题：了解 Schönhardt 构造细节对比二维与三维剖分难度
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1从二维到三维，剖分问题最本质的差别是什么？
参考答案二维剖分由两耳定理保证总是可行且不加辅助点；三维存在不可四面体化的多面体（Schönhardt），必须添加 Steiner 顶点，且剖分的组合结构复杂度大增。维度升高带来的是质的困难。
2Schönhardt 多面体的凹结构出现在哪里？
参考答案把三棱柱顶面旋转后，三条竖棱上各形成一个内凹的二面角，凹陷处三个顶点两两不可见——没有任何一对顶点能连成内部对角线，四面体化因此被完全阻断。
3为什么四面体化要允许添加 Steiner 点？
参考答案Schönhardt 类多面体内部「无路可连」，只有加入辅助顶点（如在内部或面上添点）才能切开凹结构。允许 Steiner 点后，任何多面体都可完成四面体化。