c# - 如何使三角形网格成凸多边形？

Question

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

我需要得到的是优化的网格，其中过多的三角形被合并成一个凸多边形。像这样：

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

PS我正在使用C#。

Answer 1

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

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

（来自http://www.philvaz.com/compgeom/）

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

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

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

希望有帮助。

Answer 2

我没有任何算法链接来解决这个问题，但我认为比一次将凸多边形构建一个三角形更好的方法可能是首先将三角形合并成最大的简单多边形（即：它们可以是凹的，但没有孔）你可以，然后将这些大多边形分解成它们的凸成分。

由于内角大于 180 度，您知道这些分割将发生在哪些顶点，然后您只需选择要沿其分割的入射边。选择最佳边缘进行分割的精确方法不是一个简单的问题，但合理的启发式方法可能是在分割后最大化 <180 度内角的数量。