Make the implementation general-purpose, turf-agnostic and dependency-less

[mourner]

This is more of a discussion suggestion than a request. Polygon clipping and boolean operations is an incredibly important task in computational geometry, and it can be valuable in applications beyond Turf and geo. So I'd love to see this algorithm implementation become general-purpose and free of dependencies and assumptions about its use. This means:

1. Make it usable outside of Turf, e.g. just for geometric intersections/unions.
2. Not care about MultiPolygon/Polygon/etc distinctions — make the API more specific and add geo/Turf-related handling in a wrapper (separate from this repo)
3. Get rid of Turf dependencies — things like clockwise and point-in-poly detection are just a few lines of code so there's not much win from reusing geo-specific Turf modules.

cc @morganherlocker

[tcql]

3 is definitely something I've been meaning to do. I'm currently also doing some wasteful / expensive stuff just to accommodate pip / clockwise checking via the turf API, so I'm sure we can gain back some cycles by cleaning that up

I'm interested in hearing more of your thoughts on 2. Would you recommend the GH api only provide the ability to clip 2 polygon rings against eachother, and nothing more? It would certainly improve the focus of the library and make it easier to test / debug.

[mourner]

If the current Greiner-Horrman implementation doesn't support true multi-ring union/intersection, I think there's a point in making it focused, and adding flavor in a Turf wrapper. Supporting holes properly is important though so can't get away with one ring. :)

Ideally though, the algorithm should take multiple rings as subject polygon and multiple rings as clipping polygon (no matter if they're holes or outer rings and whether they overlap) and then result in a valid set of polygons in the output.

[tcql]

Supporting holes properly is important though so can't get away with one ring. :)

certainly! I was just wondering if you were proposing that the turf wrapper handle dealing with that as well. Handling extra rings (like holes) is decomposed as iterative calls to the clipping algorithm with pairings of rings, so theoretically that could be done externally to support holes. But it's messy, and already done internally for Intersection and Union (I don't have Subtract really handled yet).

Ideally though, the algorithm should take multiple rings as subject polygon and multiple rings as clipping polygon (no matter if they're holes or outer rings and whether they overlap) and then result in a valid set of polygons in the output.

Right now, everything in GH is handled as plain arrays of coordinates, but it respects the nesting structure of polygon[ring[coordinates]] and in some places multipolygon[polygon[ring[coordinates]]]. I haven't completely tested multipolygon / multi-external ring clips yet though, so it probably still needs some work.

I'll have to do some testing and fiddling around to make sure this will correctly work with multiple clipping rings that overlap.

[mourner]

Decomposition into pairwise single-ring clippings does the job but it seems woefully inefficient. As far as I remember, the original algorithm could deal with any kinds of rings at the same time when running the algorithm — is this not the case?

[tcql]

As far as I remember, the original algorithm could deal with any kinds of rings at the same time when running the algorithm — is this not the case?

The explanations that I've been going off (and other implementations I've looked at) support clipping 1 ring against 1 other ring. If you come across any resources that state otherwise, I'd love to see them!

Here's the primary sources I've been looking at:

• Main GH algorithm
• Degeneracy handling

Even with the inefficiency, I've been seeing pretty good benchmarks. I haven't tried an extremely complex case compared to JSTS, but for all the operations I have tried, GH is many times faster. I do expect that this could fall down with very large / complex sets, so I have put a bit of thought into ways to optimize down the line. I recently found this discussion of cascading union operations, which could be useful for optimizing complex multi-polygon clipping operations, especially when many of the rings are disjoint from eachother (which would result in lots of wasted cycles checking for intersections that we know can't exist)

[bhousel]

FWIW, someone else is also working on this: tmpvar/2d-polygon-boolean. It's MIT licensed.

They're also using Greiner-Hormann algorithm, and implementing the Foster-Overfelt enhancement to handle degeneracies is an open github issue.

I'd really like to see this make it into Turf somehow, because I want to use it in iD for polygon operations.

[mourner]

@tchannel ha, looks like you're right! I confused the multi-ring handling with another algorithm. Cascading unions idea looks pretty nice — you could use RBush for that instead of implementing an STR-tree.

The fact GH is many times faster than JSTS means a combinations of two things in unclear proportions: that GH is fast, and that JSTS is incredibly bad. The latter can contribute a lot to the results. :)

@bhousel that 2d-polygon-boolean repo looks incredibly well written (it's the author of jsdom and he's very smart). @tchannel Perhaps it would make sense to collaborate here, especially given the unresolved issue of handling degeneracies there you already figured out. :)

[tcql]

@bhousel @mourner yea, it looks like that repo is a very clean starting point, but is lacking 2 bits: support for multiple rings (multipoly / holes) in the subject and clip, as well as degeneracy handling. I might make a fork and tinker on that today to see if it'd be easier to port over the degeneracy handling than sort out potential issues here.

[tcql]

At this point, the algorithm depends on two packages: turf-is-clockwise (which takes rings, not geojson, so we're okay there) and point-in-polygon. All other dependencies have been stripped out / replaced