javascript module for polygon boolean functions (union, intersection, difference and XOR) [closed]

Question

I have polygon set. In this set some are exterior polygons and some may (or may not) be holes. I don't know at this stage that which are polygon holes. I want to calculate the final polygon combining all the polygons including holes.

I thought of this approach:

//'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;
}

So my requirement for module is

1. just four polygon boolean functions
2. if npm module is available its good
3. light weight as polygon combined would be one of many function. I mean as application size is already more, so looking for light weight library.
4. efficiency: in my case number of polygons in set may not be high but points in polygon are in large numbers so looking for O(k.log(n)) not O(k.n)

List of the libraries that I came across and some points as I understood:

• JSCLipper efficient, no npm module, is the github project in sync with soureforge JSClipper ?
• kld-intersections polygon intersection present but union not present( or I am not able to find) , has many other functions (other than polygon boolean). This is javscript port of this project
• polygon.js dependent on jQuery, efficiency? , no npm module, dont confuse with polygon.js
• boolean in paper.js its add-on of paper.js lib, not an independent module
• raphael-boolean its add-on of raphael lib, not an independent module
• tess2.js GLU tesselator ported to Javascript, contains many functions for tesselation - does tesselation is required for polygon boolean functions? I could not found the boolean functions, no documentation, there is some error on test html page, no npm module
• turf-donuts dependent on another big library JSTS
• JSTS Topology Suite big library not modular

In some cases these functions are part of big libraries that are overloaded with other functions or libraries work with SVG or Geo-spatial environement or many are add on to existing library.

Please suggest for my requirement which library is appropriate? Are there any more javscript modular libraries for polygon boolean functions?

Answer 1

I use my own methods that operate on SVG convex polygons:

1. Set Convex Polygons Counter-Clockwise Points

2. Polygons - Fix for Convex/CCW

3. Point Inside Convex Polygon: Jordan Curve Theorem

4. Line Intersect Polygon - vector analysis

5. Intersecting Polygons - vectors analysis

6. Composite Intersecting Polygon - Jordan Curve Theorem

7. Convex Polygons - Trim, Uses Sutherland-Hodgman clipping algorithm

These are shown here.

Also, you may want to check out this.

Answer 2

I had started implementing Vatti polygon clipping algorithm, here is the code repository. But I found Greiner Hormann polygon clipping algorithm is much better. So I am not maintaining the code now.

I recommend Greiner Hormann implementation in JavaScript for polygon clipping or other boolean operations.