稳健、快速的复杂多边形（带孔）三角剖分 c/c++ 库，具有许可许可
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16042940/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Robust, fast complex polygon (with holes) triangulation c/c++ library with permissive license
提问by raptor
I am a developer of the open-source game, Bitfighter. As per the following SO post, we have used the excellent 'Triangle' library for mesh-zone generation for use with our in-game AI (robots):
我是开源游戏Bitfighter的开发者。根据以下 SO 帖子，我们使用了出色的“三角形”库来生成网格区域，以便与我们的游戏内 AI（机器人）一起使用：
Polygon Triangulation with Holes
However, we ran into a small snag when wanting to package our game for Debian - the use of the 'Triangle' library will make our game be considered as 'non-free'.
然而，当我们想要为 Debian 打包我们的游戏时遇到了一个小问题——使用“Triangle”库会使我们的游戏被视为“非免费”。
We have been extremely pleased with the performance of the 'Triangle' library, and don't really want to give it up; however, we don't like dealing with license issues either. Therefore we have embarked upon a quest to find a suitable, permissively-licensed replacement that can match 'Triangle' in its robustness and speed.
我们对“Triangle”库的表现非常满意，不想放弃；但是，我们也不喜欢处理许可证问题。因此，我们着手寻找合适的、许可许可的替代品，使其在稳健性和速度方面能够与“Triangle”相匹敌。
We're looking for a C or C++ library for dividing large, complex, areas into triangles, that can handle any type of irregular polygons placed together in any manner, as well as holes. Robustness is our primary need, with speed almost as important.
我们正在寻找一个 C 或 C++ 库，用于将大而复杂的区域划分为三角形，它可以处理以任何方式放置在一起的任何类型的不规则多边形以及孔洞。健壮性是我们的主要需求，速度几乎同样重要。
I have found poly2tri, but it suffers from a bug in which it cannot handle polygons with coincident edges.
我找到了poly2tri，但它存在一个错误，即它无法处理具有重合边的多边形。
We have found several libraries, but all seem to suffer from one thing or another: either too slow, or don't handle holes, or suffer from some bug. Currently we are testing out polypartitionand we have high hopes.
我们已经找到了几个库，但似乎都遇到了这样或那样的问题：要么太慢，要么不处理漏洞，要么遇到一些错误。目前我们正在测试多分区，我们寄予厚望。
What are the best alternatives to the great 'Triangle' library, but have a permissive license?
伟大的“三角形”图书馆的最佳替代品是什么，但有一个宽松的许可证？
回答by raptor
I found a solution. It was poly2triafter all, with the use of the excellent Clipperlibrary, and some minor algorithmic additions to the inputs.
我找到了解决方案。毕竟它是poly2tri，使用了优秀的Clipper库，并在输入中添加了一些小的算法。
Our process is as follows:
我们的流程如下：
- Run all our holes through Clipper using a union with NonZero winding (this means that inner holes are wound the opposite direction as outer ones). Clipper also guarantees nice clean input points with no repeats within epsilon.
- Filter our holes into ones that are wound counter-clockwise and clockwise. Clockwise holes meant the hole was circuitous and that there was another concentric area inside that needed to be triangulated
- Using poly2tri, triangulate the outer bounds and each clockwise polygon found, using the rest of the holes as inputs to poly2tri if they were found within one of the bounds.
- 使用带有非零缠绕的联合将我们所有的孔穿过 Clipper（这意味着内孔与外孔的缠绕方向相反）。Clipper 还保证在 epsilon 内没有重复的良好干净的输入点。
- 将我们的孔过滤成逆时针和顺时针缠绕的孔。顺时针孔意味着孔是迂回的，里面还有另一个需要三角测量的同心区域
- 使用 poly2tri 对外部边界和找到的每个顺时针多边形进行三角测量，如果在边界之一内找到其余的孔，则使用其余的孔作为 poly2tri 的输入。
Result:poly2tri seems to triangulate just about as fast as Triangle and has so far been very robust with everything we've thrown at it.
结果：poly2tri 似乎与 Triangle 进行三角剖分的速度一样快，并且到目前为止我们所投入的一切都非常稳健。
For those interested, here are our code changes.
对于那些感兴趣的人，这里是我们的代码更改。
Update
更新
I have attempted to pull out our clipper-to-poly2tri code, with our robustness additions, into a separate library which I started here: clip2tri
我试图将我们的 clipper-to-poly2tri 代码连同我们的健壮性添加到一个单独的库中，我从这里开始： clip2tri
回答by sloriot
You can have a look at the 2D Triangulations package of CGAL. An example to triangulate a polygon with holes is given here. The license of the package is GPLv3+.
您可以查看 CGAL 的 2D Triangulations 包。此处给出了对带孔的多边形进行三角剖分的示例。该软件包的许可证是 GPLv3+。
Note that it should not be too hard to extract only this package if needed.
请注意，如果需要，只提取这个包应该不会太难。
回答by Rob Bantin
As a small side-note:
作为一个小的旁注：
I recently had to implement a complex polygon clipper & triangulator for cutting window frames into house walls.
我最近不得不实现一个复杂的多边形剪裁器和三角测量器，用于将窗框切割成房屋墙壁。
While I was happy with the Vatti clipper results, the Delaunay triangulation used in poly2tri was too heavy to allow smooth dragging of the window frame along the barycentric coordinates of the wall face. After scratching my head a little bit, I ended up tricking this much simpler triangular to work with holes:
虽然我对 Vatti 裁剪器的结果很满意，但 poly2tri 中使用的 Delaunay 三角剖分太重，无法沿着墙面的重心坐标平滑拖动窗框。在挠了挠头后，我最终欺骗了这个更简单的三角形来处理孔：
http://wiki.unity3d.com/index.php?title=Triangulator
http://wiki.unity3d.com/index.php?title=Triangulator
What I did was horizontally subdivide the wall face by the height of the shortest clipping poly. In my case they are always rectangles, but they needn't be. Anyway, it forces the clipper to only work with regular or concave polys, and hence enables you to get away with a cheaper triangulation method.
我所做的是按照最短剪裁多边形的高度水平细分墙面。在我的情况下，它们总是矩形，但它们不一定是。无论如何，它迫使剪刀只能使用规则或凹面多边形，从而使您能够使用更便宜的三角测量方法。
Here are some screenshots showing it working:
以下是一些显示它工作的屏幕截图：
https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak
https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak
Hope this helps.
希望这可以帮助。
