通过平铺三角形来镶嵌任意多边形
我需要使用近乎均匀的三角形平铺来填充任意多边形。我该怎么做？您可以提供对现有算法的参考，甚至可以提供您自己的简单想法或提示。
假设如下：
- 多边形可能是凸的（但如果您想出适用于凹形状的算法，则会加分）
- 多边形具有任意数量的边（3 条或更多）
- 镶嵌数量（最好是顶点数量）由算法添加）应该被参数化
- 多边形的边可以由算法划分
- 三角形的大小和形状应该几乎一致（即角将趋于 60 度）
- 优选地，顶点处的边数应该很少而不是很多。这可能是从上一点得出的（即算法应该产生“干净的网格”）。
这不是一个容易解决的问题，我希望“启发式”解决方案可能是最有效的......（对吗？）
I need to fill an arbitrary polygon using a near-uniform tiling of triangles. How would I do this? You may provide either references to existing algorithms or even simply ideas or hints of your own.
The following is presumed:
- The polygon may be convex (but bonus points if you come up with an algorithm that works for concave shapes)
- The polygon has an arbitrary number of edges (3 or more)
- The amount of tessellation (preferably the number of vertices added by the algorithm) should be parametrized
- The polygon's edges may be divided by the algorithm
- Triangles should be nearly uniform in size and shape (i.e. corners will tend towards 60 degrees)
- Preferably the number edges at a vertex should be few rather than many. This will likely follow from the previous point (I.e. the algorithm should produce a "clean mesh").
This is not an easy problem to solve and I expect that a "heuristic" solution may be the most efficient... (right?)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
Triangle 能满足您的要求吗？
（该网站上对算法的解释比我能想到的更好。）
Does Triangle do what you want?
(The explanations of the algorithms on that site are better than whatever I could come up with.)
从算法上来说，实际上听起来并不那么复杂。或者我错过了什么？
一些伪代码：
它会给你 45°/45°/90° 角的三角形。如果您想要尽可能接近 60°，您应该首先用六边形对多边形表面进行细分（六边形的大小就是您的“细分量”），然后检查六个 60°/60° 中的每一个/60° 三角形组成这些六边形。对于这些三角形，您可以执行与上述伪代码中的正方形相同的操作，但您不需要将那些完全位于多边形内部的三角形分开，因为它们本身就是三角形。
这有什么帮助吗？我认为，应该适用于任何多边形（凸面/凹面/其中有孔），因为您对相交的正方形/三角形所做的操作确实可以处理此类多边形。
Doesn't actually sound that complicated, algorithmically. Or am I missing anything?
Some pseudocode:
It will give you triangles with 45°/45°/90° angles though. If you want as close to 60° as possible, you should start with tessellating the surface of your polygon with hexagons (with the size of the hexagon being your "amount of tessellation") and then checking each of the six 60°/60°/60° triangles that make up these hexagons. For these triangles you do the same as with the squares in the above pseudocode, except for the fact that you don't need to split the ones that cleanly inside your polygon as they are already triangles themselves.
Is this of any help whatsoever? Should work for any polygon (convex/concave/with holes in them), I think, given that what exactly you do for intersecting squares/triangles handles such polygons.
正如 Jason Orendorff 指出的那样，您应该尝试使用 Triangle 来生成高质量的网格。它有很多选项可供您尝试获得各向同性网格。然后，您可以尝试使用迭代算法来创建中心良好的三角剖分。 此出版物页面上列出了更多详细信息。我已经实现了 2007 年的论文“Well-Centered Planar Triangulation - an Iterative Approach”，它在中等大小的网格上给出了不错的结果。正心三角剖分是指所有三角形的外心都位于相应三角形内部的三角剖分。由于您想要稍微不同的东西，您可以简单地尝试更改所涉及的错误指标。您可以找到三角形之间“不全等”的衡量标准，并将该错误最小化。这样的误差函数很可能是非凸的，因此所描述的非线性共轭梯度优化是您可以做的。
As Jason Orendorff pointed out, you should try to use Triangle to generate a quality mesh. It has lots of options that you can play with to try to get an isotropic mesh. Then, you could try to use an iterative algorithm to create a well-centered triangulation. More details are listed on this publications page. I have implemented the 2007 paper "Well-Centered Planar Triangulation -- an Iterative Approach," and it gives decent results on medium sized meshes. A well-centered triangulation is one in which all the circumcenters of triangles lie inside the respective triangle. Since you want something slightly different, you could simply try to change the error metric involved. You could find a measure of "non-congruence" among the triangles and minimize that error. Most likely such an error function will be non-convex, so the non-linear conjugate gradient optimization described is as well as you can do.
这可以使用简单的耳朵剪裁方法对凹/凸多边形完成（假设我们不需要支撑孔）。
http://citeseerx.ist。 psu.edu/viewdoc/summary?doi=10.1.1.115.291
这是 2 个步骤，因此迭代剪辑“最佳”耳朵以获得更均匀的结果可能会更有效，因此您不必重新排列拓扑作为第二遍 (YMMV)。
（请注意，此处使用 2 个步骤的原因是并不总是需要计算更均匀的分布）。
完全披露，当我需要一个快速曲面细分器时，我自己也遇到了这个问题用于实时建模应用程序的多边形。
用 C 编写的工作实现，
它接受并返回 POD 的（
float[2]数组，填充uint[3 ]数组）：polyfill_2d_beautify.c（调整拓扑以获得更均匀的结果）
还制作了
polyfill_2d.c到 Rust 的端口（注意，耳朵剪裁基于 libgdx，对交叉检查进行了空间优化，可以扩展到数千条边，而不会造成如此显着的性能影响，因为剪裁每只耳朵都是每次检查所有其他点）。
This can be done for concave/convex polygons using a simple ear-clipping method (assuming we don't need to support holes).
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
This is 2 steps, so it may be more efficient to iteratively clip the 'best' ear to get more even results, so you don't have to re-arrange topology as a second pass (YMMV).
(Note that the reasons 2 steps are used here is that calculating more even distribution isn't always needed).
Full disclosure, I ran into this problem myself, when I needed a fast tessellator for polygons for a real-time modeling application.
Working implementation written in C,
which take and return POD's (
float[2]array, filling in auint[3]array):polyfill_2d_beautify.c (adjusts topology for more even results)
also made a port of
polyfill_2d.cto Rust(Note, the ear clipping is based on libgdx with spatial optimizations to the intersection checks, to scale up to thousands of sides without such a significant performance hit, since clipping every ear was checking all-other-points each time).