用于计算镶嵌三角形边缘的最大 'even' 方向的算法？

Question

我继承了一些遗留代码，可以旋转三角形之间的边以改进拓扑分布，该算法运行良好，但计算量很大。

给定由共享一条边的两个三角形组成的四边形的伪代码是:

/* split 0-2 */
score_02 = (area(v0, v1, v2) / perimeter(v0, v1, v2)) + 
           (area(v0, v2, v3) / perimeter(v0, v2, v3));
/* split 1-3 */
score_13 = (area(v1, v2, v3) / perimeter(v1, v2, v3)) + 
           (area(v0, v1, v3) / perimeter(v0, v1, v3));

/* negative number when (0-2) is an improved state */
result = score_13 - score_02;

这非常有效，可以在 2D 三角区域上提供很好的曲面分割(参见示例)。

我主要担心的是这不是很有效(周长计算涉及 6 次平方根调用)。

是否有其他/更好的方法来计算(上)之前、(下)之后的放松状态，例如:

---

未能使用好的方法可能:

• 使其中一个三角形的面积为零
  (取决于输出的用途，这可能会产生级联效应 - 例如，法线面积为零的面在用作其他流程)。
• 分割不当可能会导致贴图纹理失真或严重变形。

---

有人指出(在现已删除的答案中)可以使用简单的最短边方法，但是这并不能提供良好的分布(注意边界)例如:

---

注意 1) 这可能是一个众所周知的问题，因为它没有记录在代码，这不是一件容易搜索的事情:)

注 2) 到目前为止，我还没有认真研究替代方法，我可能会这样做并在此处发布发现。

Answer 1

您可以尝试生成受约束的 delaunay 三角剖分。对于给定的点集，这是您可能拥有的“最好的”(可证明的)三角剖分。

如果你可以在内部或边缘添加更多的点(不改变形状)(称为斯坦纳点)，你可以保证更好的三角形(在最小内角和面积方面)。

参见:http://www.cs.cmu.edu/~quake/triangle.defs.html#conform .

CGAL 有这些的实现。