Developed and implemented new polygon clipping algorithm (Zeeuw clipping)

1
Wout
12/13/2017 3:33 PM

The last year I've been working on creating a new polygon/polyline clipping algorithm based on the Vatti clipping algorithm. I'm appropriately naming the algorithm Zeeuw clipping after yours truely the creator. It was explicitly designed to deal with overlapping edges and coincident vertices correctly, which the original Vatti clipping algorithm does not address.

The implementation uses floating point arithmetic, so rounding errors may play a role in the results, but nevertheless the effect should be negligible and the algorithm is expected to be stable.

Feel free to try it out here, any feedback is welcome! At the moment it only supports the intersection operation. Next year I will work on union, xor and diff when this implementation has been tested some more.

In the coming months I will put together a document explaining the algorithm, which will be available for purchase. Part of the package will be the article, source code and test data, so people interested in this topic can learn from the insights I've gained.

Wout

Wout
12/25/2017 11:11 AM

I've added union, difference and exclusive-or clip operations and fixed some bugs. I'll still be tweaking and testing the clipper some more in the coming months.

- Wout

1