如何将三角形网格转换为凸多边形？

Question

4

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

我需要得到优化的网格，其中过多的三角形被合并成凸多边形。就像这样: enter image description here

有人能给我一些算法的链接来完成这个吗？提前感谢！

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

- PanCotzky

我尝试合并两个相邻的三角形，然后添加更多的三角形到多边形中，每次都检查结果多边形是否是凸多边形。这种方法可以工作，但结果非常不优化。最好我需要一些算法，可以给我最优化的结果。就像网格优化算法一样。但我会感激你提供的任何帮助。 - PanCotzky

生成的形状是否只能使用原始网格中存在的边缘，还是可以根据需要添加边缘？ - ryanm

2个回答

0

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

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

- ryanm

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- celion · Accepted Answer

Hertel-Mehlhorn算法是处理这个问题的标准方法，它可以总结为：

1.从多边形P的三角剖分开始； 2.删除一个非必要的对角线； 3.重复执行上述两步。

该算法在多项式时间内运行，并具有最优性的边界，尽管它不一定是最优的。

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

通常会产生“外观更美观”的效果的一个启发式策略是，在每个步骤中合并最长的对角线。

希望能对您有所帮助。