Buffer Memory overflow situations

[dr-jts]

The current JTS buffer algorithm can suffer from memory overflow issues when processing some kinds of buffers. These are usually associated with poor performance as well.

The cause of the memory (and performance) issue is because a buffer operation generates a "braided" buffer curve which contains a huge number of self-intersections. When the curve is noded during buffer construction, this results in an explosion of topology graph edges, and exceeds available memory.

Braided buffer curves occur in three distinct situations:

Complex Input

Input geometry is very "wiggly", and buffer distance is "reasonable" (i.e. less than the extent of the geometry)

• GEOS-693
• GEOS-383 - negative buffer distance of -8665. Geometry extent is ~ 100K. Actual result is empty. Buffer curve has 82K points - when noded it produces 2.4M lines with 4.9M points!

Braided Input

Input geometry itself contains braided linework

• GEOS-344
• GEOS-502

Huge Buffer Distance

A moderate-to-large input geometry with a buffer distance that is much bigger than the geometry extent

• GEOS-1119 - geometry has ~420K vertices, of extent ~= 400K. Buffer distance is 99M (over 100x larger)

Possible Approaches

Buffer-By-Step

For Huge Buffer Distance situations, the buffer can be generated by a Buffer-By-Step (BBS) approach. In this case a "reasonable" (say, a distance equal to the extent of the input) buffer distance is used as the first step. It should succeed. The result can then be buffered again in a second step to attain the desired buffer distance. Since the buffer from the first step is generally much smoother, the second step should execute correctly and quickly.

BBS can be invoked at the start of the buffer code, via a check on the initial buffer distance. This probably should have some "hysteresis" - the buffer distance threshold should be larger than the step distance (perhaps 2 or 3x the input extent size?)

Notes:

• input extent distance can be computed as the diagonal length of the input geometry.
• Point and MultiPoint geometries are exempt from this heuristic.
• Only needed for positive buffer distances. Huge negative distances are handled by the existing heuristic of checking if the buffer disappears completely.

Buffer-By-Union

For Complex Input and Braided Input situations, a Buffer-By-Union approach should work. Buffer-By-Union (BBU) involves creating buffers around small sections of the input linework, and then unioning them (including the original input, in the case of area input). This is robust and often faster. (Note that BBU can also work for the Huge Buffer Distance situation. But it is less performant than BBS, since the section buffers will have a high degree of overlap)

The big issue is how to determine that a buffer situation is too complex to complete before system resources (memory and time) are overloaded. One possibility is to put a limit on the number of buffer curve node points generated. If this is exceeded, the standard buffer can be terminated and the BBU approach can be used instead.

Notes:

• these strategies apply only to the Round endcap/Round join buffer style.
• BBU works for both positive and negative buffer distances
• Should "small" geometries (< ~100 vertices?) be exempt from these heuristics, since they can't generate a huge number of self-intersections?