通过平铺三角形来细分任意多边形

Question

我需要使用近似均匀的三角形平铺来填充任意多边形.我该怎么做？您可以提供对现有算法的引用,甚至可以提供您自己的想法或提示.

推测如下:

• 多边形可能是凸的(但如果你想出一个适用于凹形的算法,可以获得奖励积分)
• 多边形具有任意数量的边(3个或更多)
• 曲面细分量(最好是算法添加的顶点数)应该是参数化的
• 可以通过算法划分多边形的边缘
• 三角形的大小和形状应该几乎一致(即角落倾向于60度)
• 优选地,顶点处的数量边缘应该是很少而不是很多.这可能是从前一点开始的(即算法应该产生"干净的网格").

这不是一个容易解决的问题,我希望"启发式"解决方案可能是最有效的......(对吧？)

Answer 1

不三角你想要做什么？

（该网站上对算法的解释比我能想到的要好。）

Answer 2

正如 Jason Orendorff 指出的那样，您应该尝试使用 Triangle 来生成高质量的网格。它有很多选项可供您尝试获得各向同性网格。然后，您可以尝试使用迭代算法来创建中心良好的三角剖分。此出版物页面上列出了更多详细信息。我已经实现了 2007 年的论文“Well-Centered Planar Triangulation - an Iterative Approach”，它在中等大小的网格上给出了不错的结果。正心三角剖分是指所有三角形的外心都位于相应三角形内部的三角剖分。由于您想要稍微不同的东西，您可以简单地尝试更改所涉及的错误指标。您可以找到三角形之间“不全等”的衡量标准，并将该错误最小化。这样的误差函数很可能是非凸的，因此所描述的非线性共轭梯度优化是您可以做的。