镶嵌任意多边形由平铺三角形 [英] Tessellating an arbitrary polygon by tiling triangles

问题描述

我需要使用三角形的近均匀平铺填补任意多边形。我将如何做到这一点？您可以提供任何引用现有的算法甚至根本想法还是你自己的味道。

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.

以下是presumed：

The following is presumed:

• 在多边形可能是凸的（但加分，如果你想出了一个算法，适用于凹形）
• 的多边形具有边缘的任意数量（3个或更多）
• 镶嵌的金额（$ P $的算法加入顶点pferably数）应该被参数化
• 的多边形的边缘可通过该算法被划分
• 三角形应几乎均匀的尺寸和形状（即角是趋于60°）
• preferably人数为顶点的边缘应该是少数，而不是很多。这可能会在previous点跟踪（即算法应该产生一个干净目）。

这不是一个容易解决的问题，我想到的是一个试探的解决方案可能是最有效的？（是吗？）

This is not an easy problem to solve and I expect that a "heuristic" solution may be the most efficient... (right?)

推荐答案

随着杰森Orendorff指出的那样，你应该尝试使用三角形生成高质量的网格。它有很多，你可以玩，试图让各向同性网格选项。然后，你可以尝试使用迭代算法创建一个良好居中三角。更多详细信息都列在此出版物页面。我已经实现了2007年论文嗯为中心的三角剖分 - 迭代的方法，并给出了中等大小的网格像样的成绩。良好的三角中心是在三角形的所有circumcenters躺在各自的三角形内。既然你想要的东西稍有不同，你可以简单地尝试改变涉及错误的度量。可以找到非一致性三角形中的量度，并且最大限度地减少误差。最有可能这样的错误功能将非凸，所以介绍的非线性共轭梯度优化，以及你可以做的。

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.

这篇关于镶嵌任意多边形由平铺三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！