Large negative buffer does not return empty polygon

[dr-jts]

Computing a negative buffer on some polygons returns an "inverted" polygon rather than an empty one.

Example:

POLYGON ((666360.09 429614.71, 666344.4 429597.12, 666358.47 429584.52, 666374.5 429602.33, 666360.09 429614.71))

Buffer of -15 should be empty, but returns:

POLYGON ((666361.4831382894 429593.7375842848, 666353.0817850837 429600.9554019591, 666357.3305565341 429605.6759646248, 666365.55909509 429598.30712412694, 666361.4831382894 429593.7375842848))

Originally reported on GIS StackExchange. See also GEOS 1101 and QGIS 41696.

[dr-jts]

One heuristic for dealing with this is to compute the radius of the circle with the same area as the geometry. This is an upper bound on the buffer distance which will erode the polygon completely (i.e. buffer distances less than the radius should produce an empty buffer).

For example, the effective radius of the geometry above is 11.970122020294427. So the distance of -15 should return an empty buffer result.

However, this bound is not sufficient. A buffer distance of -11.9 still produces an erroneous non-empty polygon. The radius of the MaximumInscribedCircle is 9.475544793980276. Distance = -9.5 produces an empty result, as expected.

[dr-jts]

More failure cases:

Pentagon (max inscribed circle radius = 8.2, buffer( -9 ) is non-empty)

POLYGON ((6 20, 16 20, 21 9, 9 0, 0 10, 6 20))

Pentagonal Hole (buffer( 9 ) has incorrect hole)

POLYGON ((-6 26, 29 26, 29 -5, -6 -5, -6 26), (6 20, 16 20, 21 9, 9 0, 0 10, 6 20))

[dr-jts]

My hypothesis is that this situation occurs for rings (shells and holes) which are characterized by:

1. the ring has a small number of vertices (<= 9)
2. the generated offset curve has # vertices <= # ring vertices
3. the ring is convex (this is probably implied by 2)

Given this, it is not too expensive to compute the buffer curve and then check if every vertex of the offset curve is closer to the ring than the specified buffer distance (with a small tolerance factor, say 1%). If this is the case, the generated buffer is actually empty, and the offset curve can be discarded from the buffer result.

Note that this test must be applied to each input ring. An element is discarded if it is determined to have an empty result.

Also, a related issue can happen for polygon with specific kinds of holes. In this case a range of positive buffer distances creates an incorrect result containing a hole (which should have disappeared).

[dr-jts]

Fixed by #706.