Add Snap-Rounding Overlay option

[dr-jts]

Using Snap-Rounding for noding in Overlay should provide full robustness. TopologyExceptions will never be thrown!

Design Aspects

• For now, the original Overlay algorithm is provided as the default behaviour
• Snap-rounding is invoked by specifying a noding precision model.
• Code using Overlay will have to be modified to specify the precision model if it needs to use Snap-Rounding. E.g. CascadedPolygonUnion
• the entire output geometry is rounded to the specified precision grid. So even segments which are not involved in the overlay will be affected.

Design Issues

• Should this approach become the default for Overlay?
  • The aggresive rounding might be an issue, however.
  • Likely to be less performant ? (Although it will eliminate the noding validity check)
• If SR is not the default approach, can it be used to replace the snapping heuristic?
• How can a suitable noding precision be determined automatically? (Perhaps an interative refinement approach?)

The code is in branch https://github.com/dr-jts/jts/tree/overlay-sr-classic

[dr-jts]

@strk I'm wondering if the global rounding caused by using SR will be an issue for users? It seems like a small price to pay for robustness, but I can imagine some situations where changing every coordinate might not be desirable.

[strk]

Yes it may be an issue. At least I know a person who complained about this specific drift, he reported, is also enforced by some known proprietary tool.

Me I think a global grid may be defined by a specific authority for a specific bounding box and be done with it, but as I said I've heard someone complain. Will try to have him comment here to know more :)

[strk]

@dr-jts so the global rounding issue is that different bodies may opt for different grids and this would result in data passed around to add small changes could result in global coordinates drift to adapt to this or that grid. This is what I'm hearing from govt users. I understand a global govt-driven grid would solve this issue but evidently it is easier to said that done..

[dr-jts]

@strk That's a good point. However, this should not create issues when using SR for internal computation, as long as the SR grid is finer than all the "external" grids being used. (All that is needed for SR to prevent robustness errors is a few digits of precision, so the grid can be quite fine.)

Another alternative is to use the finest grid of all the ones which will be used (assuming the others are multiples of it).

It's worth noting that snapping to grids itself may introduce topology invalidity (collapses, self-intersection), unless it is done using SR. Is this handled appropriately?

[strk]

It's not a matter of how much things are moved, even a single bit can be a problem when you move datasets from a center to another for a specific computation.

But maybe I'm being over paranoid. Note GEOS can already do precision reduction as a possible workaround to topology exceptions, so snaprounding wouldn't be worst than that.

[dr-jts]

Yes, I've seen this kind of constraint before as well. It's going to be difficult or impossible to provide full robustness while maintaining full precision, I think. Maybe the best that can be done is to not change the coordinates during an overlay op if there is no interaction between the inputs. This will require a special check, though.

And yes, SR should be basically the same impact as precision reduction. At least that's my working hypothesis - will need to be confirmed by testing.