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

Question

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

然而，当我们想为 Debian 打包我们的游戏时遇到了一个小障碍——使用“Triangle”库将使我们的游戏被认为是“非免费的”。

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

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

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

我们已经找到了几个库，但似乎都受到一件事或另一件事的影响：要么太慢，要么不处理漏洞，要么遭受一些错误。目前我们正在测试polypartition，我们寄予厚望。

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

score 19 · Accepted Answer

我找到了解决方案。毕竟它是poly2tri，使用了出色的Clipper库，并在输入中添加了一些小的算法。

我们的流程如下：

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

结果： poly2tri 似乎与 Triangle 一样快地进行三角剖分，并且到目前为止，我们对它所做的一切都非常健壮。

对于那些感兴趣的人，这里是我们的代码更改。

更新

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

score 1 · Accepted Answer

您可以查看 CGAL 的 2D Triangulations 包。这里给出了一个用孔对多边形进行三角剖分的例子。该软件包的许可证是 GPLv3+。

请注意，如果需要，仅提取此包应该不会太难。

score 1 · Accepted Answer

作为一个小旁注：

我最近不得不实现一个复杂的多边形剪裁器和三角剖分器，用于将窗框切割成房屋墙壁。

虽然我对 Vatti 剪裁器的结果很满意，但 poly2tri 中使用的 Delaunay 三角剖分太重，无法沿着墙壁表面的重心坐标平滑拖动窗框。在摸了摸头之后，我最终欺骗了这个更简单的三角形来处理孔：

我所做的是将墙面水平细分为最短剪裁多边形的高度。在我的情况下，它们总是矩形，但它们不一定是。无论如何，它会强制限幅器仅适用于常规或凹面多边形，因此您可以使用更便宜的三角测量方法。

以下是一些显示它工作的屏幕截图：

希望这可以帮助。

3 回答 3