一尘不染

通过平铺三角形来镶嵌任意多边形

algorithm

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

假定以下内容:

  • 多边形可能是凸面的(但如果您想出一种适用于凹面形状的算法,则可以得到加分)
  • 多边形具有任意数量的边(3个或更多)
  • 细分的数量(最好是算法添加的顶点数量)应参数化
  • 多边形的边缘可以通过算法进行划分
  • 三角形的大小和形状应几乎一致(即,角会趋向于60度)
  • 优选地,顶点处的边缘数应为少而不是多。这很可能是从上一点开始的(即算法应产生“干净的网格”)。

这不是一个容易解决的问题,我希望“启发式”解决方案可能是最有效的…(对吗?)


阅读 515

收藏
2020-07-28

共1个答案

一尘不染

正如Jason
Orendorff指出的那样,您应该尝试使用Triangle生成高质量的网格。它具有许多选项,您可以使用这些选项来尝试获得各向同性的网格。然后,您可以尝试使用迭代算法来创建中心良好的三角剖分。更多详细信息在此出版物页面上列出。我已经实施了2007年的论文“以中心为中心的三角剖分-
迭代方法”,它在中型网格上给出了不错的结果。中心良好的三角剖分是所有三角形的外接点都位于相应三角形内的三角剖分。由于您想要一些稍有不同的内容,因此您可以简单地尝试更改所涉及的错误指标。您可以在三角形之间找到一种“非一致性”的度量,并将该误差降至最低。这样的误差函数很可能是非凸的,因此所描述的非线性共轭梯度优化是您所能做到的。

2020-07-28