Most efficient way to split a polygon with lines, C++ API

Question

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):

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.

Answer 1

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:

• 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).