三角剖分转凸多边形算法咨询及两种约束剖分输入效果对比

一、相关算法与参考资料 #

• 贪心三角合并算法：迭代合并相邻三角形，仅保留合并后仍为凸多边形的组合，优先选择能提升平均尺寸、降低尺寸偏差的合并对。经典参考《Polygonization of Triangulated Surfaces》（Held, M.），书中详细对比了不同合并策略对尺寸指标的影响，给出了针对“大平均尺寸+小偏差”目标的贪心规则。
• 区域生长式合并：从任意三角形出发，逐步尝试合并相邻三角形，直到无法保持凸性为止。过程中引入尺寸方差作为决策权重，优先合并能让整体尺寸分布更均匀的三角形组，适合批量生成高质量凸多边形。
• 能量优化型凸划分：将合并过程建模为能量最小化问题，能量函数包含两个核心项：一是多边形尺寸的方差（用于最小化偏差），二是平均尺寸的倒数（用于最大化尺寸）。通过贪心迭代或梯度下降求解，这类方法在《Convex Partitioning of Polygons》（Chazelle, B.）的基础上扩展而来，可适配三角剖分场景。

二、约束Delaunay三角剖分（CDT）的优势 #

是的，以CDT作为输入通常能得到更符合你需求的结果，核心原因：

• CDT生成的三角形更接近等边，天然具有更均匀的尺寸分布，减少了普通约束三角剖分中常见的狭长三角形。这类优质三角形为合并大尺寸凸多边形提供了更好的基础，能直接降低最终多边形的尺寸偏差。
• CDT的三角形邻接关系更合理，相邻三角形的夹角更优，合并成凸多边形的成功率更高。相比普通约束剖分，更少出现因三角形形状极端导致无法合并的情况，进而提升了平均多边形尺寸。
• 即便在存在尖锐约束的场景下，CDT生成的小三角形数量仍少于普通约束剖分，整体尺寸分布的可控性更强，最终凸多边形的偏差也更小。

内容的提问来源于stack exchange，提问作者Bas Smit