logo标签列表

多边形的三角剖分

cgeometrytriangulation
6

我正在尝试三角化一个多边形，以便在3D模型中使用。当我尝试对具有以下点的多边形使用耳朵方法时，我得到了红线所示的三角形。由于这些三角形内没有其他点，因此这可能是正确的。但我想要将黑线内部的区域三角化。有人知道任何可以做到这一点的算法吗？

enter image description here

你可以将图形切割成凸多边形并进行三角剖分。但对于大而复杂的图形来说会变得混乱。 - Daniel Fischer
你的三角剖分有任何约束（Delaunay？）或者有时间限制吗？否则答案会比较笼统。 - pmr
没有任何限制，模型只需生成一次，所以时间不是一个大问题。 - user978281
5个回答
8
有很多算法可以三角化一个多边形而不需要首先进行单调多边形的划分。其中一种在我的教材Computational Geometry in C中有描述，与之相关联的代码可以从该链接免费下载（使用C或Java编写）。 您必须首先按照边界遍历的顺序排列点。我的代码假定逆时针，但是这当然很容易更改。另请参见维基百科文章。也许您的问题是，没有一致地组织边界点？
2
喬瑟夫，我很喜歡你的書，我在書架上放了幾個版本。它與Edelsbrunner、Shamos＆Perparata以及Hjelle＆Daehlen並列，是任何使用TINs的人必備的寶藏。 - SmacL
@Shane：感谢你的赞美！ :-) - Joseph O'Rourke
2
通常的方法是使用梯形分解将简单多边形分割成单调多边形，然后对单调多边形进行三角剖分。第一部分可以通过扫描线算法实现。正确的数据结构（如双连通边列表）可以加速处理。我所知道的最好的描述可以在计算几何中找到。 这个 和 这个 也很有帮助。
1

维基百科建议将多边形分解为单调多边形。您可以通过检查所有角度是否小于180度来检查多边形是否凹陷 - 任何拥有大于180度角度的角都是凹陷的，您需要在该角处进行分割。

1

如果您能使用C++，那么您可以使用CGAL，特别是这里给出的示例（此处链接），该示例可以对一组非相交多边形进行三角剖分。此示例仅在您已经知道黑线段的情况下才有效。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接