c++ - 具有许可许可的稳健、快速的复杂多边形(带孔)三角剖分 c/c++ 库

Question

已结束。此问题不符合 Stack Overflow guidelines .它目前不接受答案。

---

我们不允许提出有关书籍、工具、软件库等方面的建议的问题。您可以编辑问题，以便用事实和引用来回答它。

关闭 7 年前。

Improve this question

我是开源游戏的开发者，Bitfighter .根据以下 SO 帖子，我们使用了出色的“三角形”库来生成网格区域，以便与我们的游戏内 AI(机器人)一起使用:

Polygon Triangulation with Holes

但是，当我们想要为 Debian 打包我们的游戏时遇到了一个小障碍 - 使用“Triangle”库会使我们的游戏被视为“非免费”。

我们对“Triangle”库的性能非常满意，并不想放弃它；但是，我们也不喜欢处理许可证问题。因此，我们已着手寻找合适的、获得许可的替代品，以在稳健性和速度上与“Triangle”相媲美。

我们正在寻找用于将大型复杂区域划分为三角形的 C 或 C++ 库，该库可以处理以任何方式放置在一起的任何类型的不规则多边形以及孔。稳健性是我们的首要需求，速度几乎同样重要。

我找到了poly2tri ，但它存在一个错误，即无法处理边缘重合的多边形。

我们找到了几个库，但似乎都遇到了这样或那样的问题:要么太慢，要么不处理漏洞，要么遭受一些错误。目前我们正在测试polypartition我们寄予厚望。

什么是伟大的“三角形”库的最佳替代品，但有一个许可？

Answer 1

我找到了解决方案。它是 poly2tri毕竟使用了优秀的Clipper库，以及对输入的一些小的算法添加。

我们的流程如下:

1. 使用带有非零绕组的接头将所有孔穿过 Clipper(这意味着内孔的缠绕方向与外孔的缠绕方向相反)。 Clipper 还保证输入点干净整洁，在 epsilon 内没有重复。
2. 将我们的孔过滤成逆时针和顺时针缠绕的孔。顺时针孔意味着孔是迂回的，并且内部还有另一个同心区域需要进行三角剖分
3. 使用 poly2tri 对外部边界和找到的每个顺时针多边形进行三角测量，如果在其中一个边界内找到其余孔洞，则将其用作 poly2tri 的输入。

结果: poly2tri 的三角剖分速度似乎与 Triangle 一样快，并且到目前为止，我们所投入的一切都非常稳健。

对于那些感兴趣的人，here are our code changes .

更新

我已经尝试将我们的 clipper-to-poly2tri 代码以及我们的稳健性添加提取到一个单独的库中，我从这里开始:clip2tri