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

正如Jason Orendorff指出的,您应该尝试使用三角形生成高质量的网格。它有很多选项,您可以尝试使用这些选项来获得各向同性网格。然后,您可以尝试使用迭代算法来创建中心良好的三角剖分。更多详情列于 this publications page . 我已经实现了2007年的论文“居中的平面三角剖分——一种迭代方法”,它在中等大小的网格上给出了不错的结果。中心良好的三角剖分是指三角形的所有外心都位于相应三角形内的剖分。因为您想要一些稍微不同的东西,所以您可以简单地尝试更改所涉及的错误度量。您可以在三角形之间找到“不一致”的度量,并最小化该误差。这种误差函数很可能是非凸的,所以所描述的非线性共轭梯度优化就是你所能做到的。

做 Triangle

从算法上来说,听起来并没有那么复杂。还是我遗漏了什么?

• 在多边形周围放置一个与轴对齐的封闭正方形。
• 将每个正方形细分为四个子元素(类似于四叉树),其中迭代次数决定“细分量”。
• 每个生成的正方形要么干净地位于多边形外部(=忽略),要么干净地位于多边形内部(=沿对角线拆分为两个生成的细分三角形),要么与多边形相交。
• 交叉点广场的确切情况留给读者作为练习。;-)[至少在这个时候。]

它会给你45°/45°/90°的三角形。如果希望尽可能接近60°,应首先使用六边形对多边形表面进行细分(六边形的大小为“细分量”),然后检查构成这些六边形的六个60°/60°/60°三角形中的每一个。对于这些三角形,您可以与上面伪代码中的正方形执行相同的操作,只是不需要分割多边形内部干净的三角形,因为它们本身已经是三角形。

这有什么帮助吗?我认为应该适用于任何多边形(凸面/凹面/有孔),考虑到你对相交的正方形/三角形所做的处理就是这样的多边形。

• 对多边形进行细分
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
• 旋转三角形之间的边,当边旋转到新状态时,由周长划分的区域较小。

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

完全公开,我自己也遇到了这个问题,当时我需要一个用于实时建模应用程序的多边形快速细分器。

哪个取回吊舱( float[2] 数组,填充 uint[3] 数组):

• polyfill_2d.c (细分)

• polyfill_2d_beautify.c (调整拓扑以获得更均匀的结果)

• 还做了一个 port of polyfill_2d.c to Rust

(注意,ear裁剪基于libgdx,对交叉点检查进行了空间优化,可以扩展到数千条边,而不会对性能造成如此大的影响,因为裁剪每个ear都是在检查。) 所有其他要点 每次)。