Greiner-Hormann Polygon Clipping
This is an experimental implementation of the Greiner-Hormann polygon clipping algorithm, with additional degeneracy handling.
- Support
- Supports holes
- Supports multi-polygon inputs
- Operations
- union
- intersect
- subtract
- Relatively Stable but may produce invalid results in some cases. This is because:
- Degeneracy handling is not a fully answered question with GH
- GH has no built in provision for clipping multiple polygons or dealing with holes
The end goal of this is to provide a base polygon clipping library that will support set-theoretic geometry operations for use in TurfJs, as a replacement for the JSTS dependency.
Benchmarks
node bench
Tests
npm test
Tests cases for all operations as well as the built in utilities will be executed.
Known Issues
- The current implementation cannot return lines or points, so some degenerate sets will simply return nothing.
- Needs some refactor
- Not fully optimized - decomposing clipping calls could be greatly improved using cascade unions and bounding box pre-checks
Sources
- Greiner-Hormann algorithm
- Degeneracy handling (see notes)
- Python Polyclip
- Python Polyclip + some degeneracy handling
Notes
- It's been noted that the Degeneracy handling paper ("Clipping of Arbitrary Polygons with Degeneracies") has been withdrawn because it doesn't truly solve all cases it claims to. As such, I've deviated somewhat from it's recommendations, but in general I'm using the techniques (such as in/on/out Vertex labelling and intersection removal) described in the paper