This PR adds heuristics to MaximumInscribedCircle and LargestEmptyCircle to prevent long-running (and memory-intensive) processing for nearly flat and very thin inputs.
There are two problems solved:
if the input extent is very small in one dimension (i.e. almost flat), the cell grid was initialized with cells of very small size, causing a memory explosion. This is avoided by using a single initial grid cell covering the extent.
Very thin (low-area) geometries (or LEC boundaries) cause a long search to find a cell with a centre inside the geometry (since very few cells in the search space satisfy this condition). A heuristic is used to determine a maximum number of iterations permitted. This means that the computed result may lie outside the input geometry. This can be mitigated by using a smaller tolerance distance; but there is no way to guarantee the centre will lie inside.
This PR adds heuristics to
MaximumInscribedCircleandLargestEmptyCircleto prevent long-running (and memory-intensive) processing for nearly flat and very thin inputs.There are two problems solved:
This fixes the issue reported in https://github.com/libgeos/geos/issues/875.