c# - 如何将三角形网格化为凸多边形？

Question

我有一个三角形网格。三角形有不同的“颜色”。像这样:

我需要得到的是优化后的网格，其中过多的三角形合并为凸多边形。像这样:

有人可以给我一些算法的链接来完成这个吗？提前致谢!

附言我正在使用 C#。

Answer 1

Hertel-Mehlhorn 算法是执行此操作的标准方法；可以概括为

1. 从多边形 P 的三角剖分开始；
2. 删除不重要的对角线
3. 重复。

(来自 http://www.philvaz.com/compgeom/)

这在多项式时间内有效，并且具有最优性界限，尽管它不一定是最优的。

在您的情况下，您将通过不考虑不同颜色的三角形之间的对角线来修改步骤 #2。

通常会产生“更好看”的片段的一种启发式方法是在每一步合并最长的对角线。

希望对您有所帮助。