多边形的三角剖分

我试图三角化多边形以用于三维模型。当我尝试使用下面点分的多边形上的耳朵方法，我得到三角形的红线所在。由于这些三角形内部没有其他点，所以这可能是正确的。但我希望它只能在黑色线条内部进行三角测量。任何人都知道任何算法会做到这一点？多边形的三角剖分

enter image description here

来源

2012-01-16 user978281

您可以将图形切成凸起部分并对其进行三角测量。尽管如此，对于大型复杂的人物来说也是一团糟。 – 2012-01-16 22:42:48

您的三角测量是否有任何限制（德劳内？）还是您有任何时间限制？否则答案将会相当宽泛。 – pmr 2012-01-16 22:43:53

没有限制，模型只生成一次，所以时间不是一个大问题。 – user978281 2012-01-16 22:53:23

有许多算法可以对多边形进行三角化，而不需要先分割成单调多边形。其中一个在我的教科书Computational Geometry in C中有描述，它有与之关联的代码，可以从该链接自由下载（使用C或Java）。您必须首先按顺序对应边界遍历点。我的代码假设逆时针，但当然这很容易改变。另请参阅Wikipedia article。也许这就是你的问题，你没有一贯的边界点组织？

来源

2012-01-17 01:23:15

爱你的书约瑟夫，有几个版本坐在我身后的书架上。坐落在Edelsbrunner，Shamos＆Perparata和Hjelle＆Daehlen之间。任何使用TIN的人都必须拥有真正的自由。 – 2012-01-17 07:55:56

@Shane：感谢您的好评！ :-) – 2012-01-17 17:50:43

也许你可以在你的答案中包含代码？ – Jonny 2014-10-20 07:29:10

你打破多边形成单调多边形Wikipedia suggest。通过简单地检查所有角度小于180度来检查多边形是否凹陷 - 任何角度超过180度的角都是凹的，并且您需要在该角处将其折断。

来源

2012-01-16 22:44:32 Soren

通常的做法是使用梯形分解将简单多边形分解为单调多边形，然后对单调多边形进行三角化。第一部分可以用扫描线算法实现。使用正确的数据结构（例如双向连接的边界列表）可以提高速度。我知道的最好的描述可以在Computational Geometry找到。 This和this也似乎有帮助。

来源

2012-01-16 23:38:05 pmr

如果可以使用C++，则可以使用CGAL，特别是可以使用here的示例，该示例可以对一组非相交的多边形进行三角测量。这个例子只有在你已经知道黑色段的情况下才有效。

来源

2012-01-17 07:37:50 sloriot

您需要使用EarClipping算法，而不是Delaunay。请参阅以下白皮书：http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

来源

2012-01-18 07:39:04 abenci

多边形的三角剖分

回答

相关问题