I'm looking for the most efficient way to split a polygon (possibly with holes) with a set of lines (which can intersect) in C++ with GDAL/OGR or any other library which can prove useful.

As shown in the figure below, I would like to split the polygon with the red lines, which would result in multiple polygons (possibly with holes):

enter image description here

Performance is a big issue as I need to make such calculation thousands of times. For now, I'm doing the following:

  • Build a MULTILINESTRING with every lines
  • Buffer it (distance 0.001, precision is not a big issue)
  • Compute the difference with the POLYGON

Profiling shows that Difference() is a bottleneck.

Some solutions rely on PostGIS (e.g. ST_Split) or other command line/query language tools with no direct binding in the C++ API of GDAL/OGR.

  • I would focus on Intersect (lines and polygon) instead of Difference.
    – klewis
    May 18 '18 at 14:58
  • @klewis Thanks to your comment, I played with Intersect and could find a better solution :)
    – Nicolas
    May 24 '18 at 21:10

In case it can help someone, I finally came up with this solution, using directly GEOS for better performance:

  • Build a MULTILINESTRING containing all the edges of the exterior and interior rings of the POLYGON and add all the red lines
  • Use geos::noding::GeometryNoder to correctly node the network and get non-intersecting LINESTRINGs whose extremities are shown in green below:

enter image description here

  • Polygonize this collection of connected and non-intersecting LINESTRINGs. It will produce all the tiny polygons we can guess on the picture. Fully enclosed polygons will be correctly interpreted as holes (e.g. the hole at the bottom), other holes which are not enclosed will produce new polygons which need to be filtered out (e.g. the hole at the top).

This solution is way faster and produces an exact decomposition (no buffer trick).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.