Skip to content

tcql/greiner-hormann

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Greiner-Hormann Polygon Clipping

Build Status

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

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

About

Greiner-Hormann polygon clipping, with degeneracy handling

Resources

Stars

Watchers

Forks

Packages

No packages published