多边形的三角剖分
我正在尝试对多边形进行三角测量以在 3D 模型中使用。当我尝试在具有如下虚线点的多边形上使用耳朵方法时，我得到红线所在的三角形。由于这些三角形内没有其他点，这可能是正确的。但我希望它仅对黑线内的区域进行三角测量。有人知道有什么算法可以做到这一点吗？
Im trying to triangulate a polygon for use in a 3d model. When i try using the ear method on a polygon with points as dotted below, i get triangles where the red lines are. Since there are no other points inside these triangles this is probably correct. But i want it to triangulate the area inside the black lines only. Anyone know of any algorithms that will do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
有许多算法可以对多边形进行三角剖分，不需要先将其划分为单调多边形。我的教科书C中的计算几何中描述了其中一个，其中有代码与之相关的文件可以从该链接免费下载（C 或 Java 版本）。
您必须首先获得与边界遍历相对应的顺序的点。我的代码假定逆时针方向，但这当然很容易改变。另请参阅维基百科文章。也许这就是您的问题，您没有一致地组织边界点？
There are many algorithms to triangulate a polygon that do not need partitioning into monotone polygons first. One is described in my textbook Computational Geometry in C, which has code associated with it that can be freely downloaded from that link (in C or in Java).
You must first have the points in order corresponding to a boundary traversal. My code assumes counterclockwise, but of course that is easy to change. See also the Wikipedia article. Perhaps that is your problem, that you don't have the boundary points consistently organized?
通常的方法是使用梯形分解将简单多边形分割为单调多边形，然后对单调多边形进行三角剖分。
第一部分可以通过扫描线算法来实现。使用正确的数据结构（例如双连接边列表）可以提高速度。据我所知，对此的最佳描述可以在计算几何中找到。 此和这似乎也很有帮助。
The usual approach would be to split your simple polygon into monotone polygon using trapezoid decomposition and then triangulate the monotone polygons.
The first part can be achieved with a sweep line algorithm. And speed-ups are possible with the right data-structure (e.g. doubly connected edge list). The best description of this, that I know, can be found in Computational Geometry. This and this also seem helpful.
维基百科建议将多边形分解为单调多边形。只需检查所有小于 180 度的角度即可检查多边形是否为凹面 - 任何角度超过 180 度的角都是凹面，您需要在该角处将其折断。
Wikipedia suggest that you break the polygon up into monotone polygons. You check that the polygon is not concave by simply checking for all angles being less than 180 degrees - any corners which has a angle of over 180 is concave, and you need to break it at that corner.
如果您可以使用 C++，则可以使用 CGAL，特别是 此处 可以对一组不相交的多边形。仅当您已经知道黑色线段时，此示例才有效。
If you can use C++, you can use CGAL and in particular the example given here that can triangulate a set of non-intersected polygons. This example works only if you already know the black segments.
您需要使用 EarClipping 算法，而不是 Delaunay。请参阅以下白皮书：http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
You need to use the EarClipping algorithm, not the Delaunay. See the following white paper: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf