我试图对多边形进行三角剖分以用于 3d 模型。当我尝试在具有如下点的多边形上使用耳朵方法时，我得到红线所在的三角形。由于这些三角形内没有其他点，这可能是正确的。但我希望它只对黑线内的区域进行三角测量。任何人都知道可以做到这一点的任何算法吗？
问问题
3666 次
5 回答
8
有许多算法可以对多边形进行三角剖分，而这些算法不需要首先分割成单调多边形。一个在我的教科书Computational Geometry in C中进行了描述，其中包含与之相关的代码，可以从该链接（C 或 Java 中）免费下载。您必须首先拥有与边界遍历相对应的点。我的代码假定逆时针，但当然很容易改变。另见维基百科文章。也许这是您的问题，您没有始终如一地组织边界点？
于 2012-01-17T01:23:15.270 回答
2
通常的方法是使用梯形分解将简单的多边形拆分为单调多边形，然后对单调多边形进行三角剖分。第一部分可以通过扫描线算法来实现。使用正确的数据结构（例如双连接边列表）可以加快速度。据我所知，对此的最佳描述可以在Computational Geometry中找到。这和这似乎也有帮助。
于 2012-01-16T23:38:05.167 回答
1
维基百科建议您将多边形分解为单调多边形。您只需检查所有角度是否小于 180 度，即可检查多边形是否为凹面 - 任何角度超过 180 度的角都是凹的，您需要在该角处将其折断。
于 2012-01-16T22:44:32.423 回答
0
您需要使用 EarClipping 算法，而不是 Delaunay。请参阅以下白皮书：http ://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
于 2012-01-18T07:39:04.653 回答