libgeos
Buffer operation: use fallback to lower precision when result geometry is invalid
Fix for "GEOSBufferWithStyle produce invalid geometry when quadsegs = 0" https://trac.osgeo.org/geos/ticket/1131
The issue can be solved by falling back on lower precision in BufferOp::computeGeometry(), but currently the result of BufferBuilder::buffer() is assumed to always be valid. I suggest adding validity check to BufferBuilder::buffer() and throwing when it fails, so the caller can retry with lower precision.
JTS recently had the buffer quadSegs behaviour improved/clarified: JTS-778.
So the first thing to do is to port that fix, and see if that solves this problem. If not can then investigate further.
It turns out the fix from JTS-778 doesn't have any effect on this issue. (It's still worthwhile though, so I'll be making a PR for it).
At the moment this looks like some kind of robustness issue in GEOS which isn't in JTS. Perhaps due to a noding failure which for some reason isn't being detected. This will require more investigation.
I'm really reluctant to accept the fix in this PR, though, because running validation is costly and it penalizes every call to buffer.
Yes, this is a robustness issue.
I made a diagram showing layout of vertices in BufferBuilder::edgeList at this line:
https://github.com/libgeos/geos/blob/4526237dfadd47eb4fc2f54a3578d45e6d63b9d9/src/operation/buffer/BufferBuilder.cpp#L429
Labels are edge index / point index in edge, image is not to scale, close points are really close (see second image). I think the exact cause here is point [0/9] gets connected to [0/10, 1/0, 4/1, 5/0, 6/2] that is not leftmost in the group of 4 close points, and that throws off edge depth calculation for the graph (I didn't look at all depth values though).
Here are coordinates of the 4-point group in the middle, where multiple buffer lines intersect:
JTS documetation states that BufferOp result is always valid, so if intention is the same in GEOS, it seems that either BufferBuilder::buffer() (or BufferOp methods that call it) should check for validity and throw, or BufferBuilder::buffer() should be somehow fixed and assertion added that checks for validity. I understand the efficiency concern though.
I may be missing something but I don't see a good way to handle this situation using C API, since there's no precision parameter for buffer operation.
The raw buffer offset curve linework can be visualized using the JTS TestBuilder Magnify Topology mode:
I suspect that this is not being correctly noded in GEOS, and so the buffer topology building produces an incorrect result. In JTS this works, so perhaps there's some difference in the noder code, or (more likely) in the robust math.
Definitely the buffer operation should always produce valid output. So this needs to be fixed - somehow. In JTS the noding is checked post-processing, and if it fails it allows the buffer code to drop through to a fixed-precision retry. Perhaps for some reason this isn't being caught in GEOS.
(In fact, perhaps buffer should always use a fine fixed-precision grid, since the result is almost always a fairly coarse approximation anyway. This is on the list as an upgrade for JTS - but it's a fairly large task to wade into).
Further investigation reveals the following:
- in JTS, the fast noding produce an invalid arrangement (not fully noded), but the buffer topology building finds an inconsistency because of this, throws, and thus invokes snap-rounding which completes successfully
- In GEOS, the noding is wrong, but for some reason this doesn't trigger an error in topology-building, so the buffer is built incorrectly
Not sure that trying to fix the GEOS topology building will be very easy. So the easy thing to do is to in fact check whether buffer is valid, as this PR suggests. In fact, buffer output tends to be simpler than the input, so this may not be a huge performance hit. (It will certainly be faster than checking the noding arrangement, since that can be very large).
I think the answer is that we do not want a post-buffer validity check, people can do that themselves if it's something they care about.