我是开源游戏
Bitfighter的开发人员.根据以下SO文章,我们使用了优秀的“Triangle”库,用于网格区域生成,用于我们的游戏AI(机器人)：
Polygon Triangulation with Holes
然而,当想要为Debian打包游戏时,我们遇到了一个小小的障碍 – 使用“三角形”图书馆将使我们的游戏被视为“非免费”.
我们对“三角”图书馆的表演非常满意,不想放弃;但是,我们也不喜欢处理许可证问题.因此,我们已经开始寻求一种合适的,经过许可的替代品,可以在其坚固性和速度上匹配“三角”.
我们正在寻找一个C或C库,用于将大型,复杂的区域划分为三角形,可以处理以任何方式放置在一起的任何类型的不规则多边形以及孔.鲁棒性是我们的主要需求,速度几乎同样重要.
我发现poly2tri,但是它有一个错误,它不能处理具有重合边缘的多边形.
我们已经找到了几个图书馆,但似乎都有一件事或另外一件事情：太慢了,或者没有处理漏洞,或者遇到一些错误.目前我们正在测试polypartition,我们寄予厚望.
什么是伟大的“三角”图书馆的最佳选择,但有许可许可证？
解决方法
我找到了一个解决方案.毕竟使用了优秀的
Clipper库,还有一些小的算法补充了输入.
我们的过程如下：
>使用非零绕组的联合,通过Clipper运行我们的所有孔(这意味着内孔与外侧相反的方向缠绕). Clipper还保证良好的干净输入点,并且不会在epsilon内重复.
>将我们的孔过滤成逆时针和顺时针缠绕的孔.顺时针孔意味着孔是迂回的,并且内部有另一个同心区需要进行三角测量
>使用poly2tri,将外边界和每个顺时针多边形三角剖分,如果在其中一个边界内找到,则将其余的孔用作poly2tri的输入.
结果：poly2tri似乎三角测量与Triangle几乎一样快,迄今为止,我们抛出的一切都非常强大.
对于那些有兴趣的人,here are our code changes.
更新
