如何让三角形网格成凸多边形？

Question

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

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

有人能给我一些算法链接到acomplish是什么？提前致谢！

P.S.我正在使用C＃。

Answer 1

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

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

Answer 2

Hertel-Mehlhorn算法是这样做的标准方法;它可以概括为：

1. 以多边形P的三角剖分开始;
2. 删除无关对角线
3. 重复。

（从http://www.philvaz.com/compgeom/）

此作品在多项式时间，并且对最优一个界限，虽然它不一定是最优化的。

就你而言，你可以通过不考虑不同颜色的三角形之间的对角线来修改第2步。

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

希望有所帮助。