Algorithm for Set Operations

[EricZimmermann]

Hello,

I'm looking to find the algorithm for implementing the sym difference between two polygons but I can't seem to find the src file which implements it. I'm trying to understand how these pieces are computed.

Thank you!

[jorisvandenbossche]

The actual algorithm is actually implemented in the GEOS library, as shapely's function is essentially a small python binding to GEOSSymDifference_r.

I don't know if there is a single place to point to where this is implemented, but the C API function we call is essentially defined here: https://github.com/libgeos/geos/blob/4c3bd72ba73e9688b0712d9878d073559c84e4d6/src/geom/Geometry.cpp#L570

[mwtoews]

The actual algorithm is done by GEOS' OverlayNG done in C++ which was ported from JTS' OverlayNG done in Java. See also blog posts here or here, or other posts labeled with "overlay". The actual algorithm is not easy to "see", so most users (including myself) just have faith that they somehow work!

[EricZimmermann]

Thanks everyone! This should solve my issues! I am assuming I can approximate these differences by rasterizing my polygons and computing the difference with binary maps. The idea of snapping means I can estimate my error to arbitrary precision (at the cost of memory) by selecting the resolution of a grid to rasterize onto :)

[mwtoews]

There is also a grid_size parameter to snap geometries to a grid, which has the same effect as rasterizing methods. But raster methods are fine too!