用于多边形布尔函数的javascript模块(并集,交集,差异和异或)

Question

我有多边形集.在这个集合中,一些是外部多边形,一些可能(或可能不是)是孔.我不知道在这个阶段哪个是多边形孔.我想计算包含所有多边形的最终多边形,包括孔.

我想到了这种方法:

//'SomeLib'  that has polygon boolean fucntions
var polygonSet = [poly1,poly2,...polyn];

var union, intersection;
var combinedPoly = SomeLib.XOR(polygonSet[0], polygonSet[1]);
for( var i=2; i<polygonSet.length ; i++) {
  combinedPoly = SomeLib.XOR(combinedPoly, polygonSet[i]);
  //or if XOR is not available  
  union = SomeLib.union(combinedPoly, polygonSet[i]);
  intersection = SomeLib.intersection(combinedPoly, polygonSet[i]);
  combinedPoly = union - intersection;
}

所以我对模块的要求是

1. 只有四个多边形布尔函数
2. 如果npm模块可用它的好
3. 作为多边形组合的轻量化将是许多功能之一.我的意思是应用程序大小已经更多,所以寻找轻量级库.
4. 效率:在我的情况下,集合中的多边形数量可能不高,但多边形中的点数量很大,因此寻找O(k.log(n))而不是O(kn)

我所遇到的图书馆清单以及我理解的一些要点:

• JSCLipper 高效,没有npm模块,是与soureforge JSClipper同步的github 项目吗？
• kld-intersectionctions多边形交集存在但是union不存在(或者我无法找到),还有许多其他函数(除了polygon boolean).这是这个项目的 javscript端口
• polygon.js依赖于jQuery,效率如何？,没有npm模块,不要与polygon.js混淆
• boolean in paper.js 是paper.js lib的附加组件,而不是一个独立的模块
• raphael-boolean它是raphael lib的附加组件,而不是一个独立的模块
• tess2.js GLU tesselator移植到Javascript,包含许多tesselation函数 - 多边形布尔函数需要tesselation吗？我找不到布尔函数,没有文档,测试html页面上有一些错误,没有npm模块
• 草坪甜甜圈依赖于另一个大型图书馆JSTS
• JSTS Topology Suite大型库不是模块化的

在某些情况下,这些函数是重载其他函数的大型库的一部分,或者库与SVG或地理空间环境一起使用,或者许多函数会添加到现有库中.

请根据我的要求建议哪个库适合？是否还有用于多边形布尔函数的javscript模块库？

Answer 1

我已经开始实现Vatti多边形裁剪算法，这里是代码库。但我发现Greiner Hormann多边形裁剪算法要好得多。所以我现在不维护代码了。

我推荐Greiner Hormann在 JavaScript 中实现多边形裁剪或其他布尔运算。