9

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

推测如下：

  • 多边形可能是凸的（但如果您想出适用于凹形的算法，则可以加分）
  • 多边形具有任意数量的边（3 个或更多）
  • 镶嵌的数量（最好是算法添加的顶点数）应该参数化
  • 多边形的边可以被算法分割
  • 三角形的大小和形状应该几乎一致（即角趋向于 60 度）
  • 顶点处的边数最好少而不是多。这可能会从前一点开始（即算法应该产生一个“干净的网格”）。

这不是一个容易解决的问题，我希望“启发式”解决方案可能是最有效的......（对吗？）

4

4 回答 4

5

三角做你想做的事吗？

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

于 2010-01-04T14:42:27.627 回答
4

从算法上讲，实际上听起来并不那么复杂。还是我错过了什么？

一些伪代码：

  • 在多边形周围放置一个轴对齐的封闭正方形。
  • 将每个正方形细分为四个子节点（类似四叉树），其中迭代次数决定了您的“镶嵌量”。
  • 每个生成的正方形要么完全位于多边形外部（=忽略），要么完全位于多边形内部（=沿对角线分成两个生成的镶嵌三角形）或与多边形相交。
  • 交点正方形的确切情况留给读者作为练习。;-) [至少在这个时间点上。]

不过，它会为您提供 45°/45°/90° 角的三角形。如果您想要尽可能接近 60°，您应该首先用六边形细分多边形的表面（六边形的大小是您的“细分量”），然后检查六个 60°/60° 中的每一个/60° 构成这些六边形的三角形。对于这些三角形，您对上述伪代码中的正方形执行相同的操作，除了您不需要将多边形内的三角形完全拆分，因为它们本身已经是三角形。

这有什么帮助吗？我认为，应该适用于任何多边形（凸面/凹面/有孔），因为您对相交的正方形/三角形所做的确切操作可以处理这些多边形。

于 2010-01-04T13:34:26.470 回答
3

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

于 2010-01-04T22:27:48.263 回答
1

这可以使用简单的耳夹方法对凹/凸多边形完成（假设我们不需要支撑孔）。

这是 2 个步骤，因此迭代地裁剪“最佳”耳朵以获得更均匀的结果可能会更有效，因此您不必将拓扑重新排列为第二遍 (YMMV)。
（请注意，此处使用 2 个步骤的原因是并不总是需要计算更均匀的分布）。

完全披露，我自己遇到了这个问题，当我需要一个用于实时建模应用程序的多边形快速镶嵌器时。

用 C 编写的工作实现，
它接受并返回 POD（float[2]数组，填充uint[3]数组）：

（注意，耳朵裁剪是基于 libgdx 对交叉点检查进行空间优化，可以扩展到数千个边而不会造成如此显着的性能影响，因为每次裁剪每只耳朵都是检查所有其他点）。

示例输出

于 2015-07-02T08:36:23.763 回答