[OverlayNG] Incorrect intersection output

[Algunenano]

Comes from Postgis MVT tests. The following intersection used to return an exception, but now it returns an incorrect geometry (area that is on the first geometry but not in the second):

Single query:

Select ST_AsText(ST_Intersection('POLYGON((680 2050,682 2050,683 2054,686 2059,690 2061,694 2062,697 2065,699 2071,700 2080,701 2081,702 2081,703 2082,702 2083,701 2084,701 2085,699 2086,700 2086,699 2086,698 2085,699 2084,695 2083,689 2083,687 2083,685 2085,679 2083,677 2081,677 2078,673 2069,668 2062,667 2062,666 2062,665 2060,667 2058,667 2056,665 2055,666 2055,666 2054,667 2053,666 2052,667 2050,668 2050,670 2054,672 2052,673 2053,674 2052,676 2050,679 2050,680 2050))'::geometry, 'POLYGON((-8 -8,-8 2056,2056 2056,2056 -8,-8 -8))'::geometry));

• Input 1:

  POLYGON((680 2050,682 2050,683 2054,686 2059,690 2061,694 2062,697 2065,699 2071,700 2080,701 2081,702 2081,703 2082,702 2083,701 2084,701 2085,699 2086,700 2086,699 2086,698 2085,699 2084,695 2083,689 2083,687 2083,685 2085,679 2083,677 2081,677 2078,673 2069,668 2062,667 2062,666 2062,665 2060,667 2058,667 2056,665 2055,666 2055,666 2054,667 2053,666 2052,667 2050,668 2050,670 2054,672 2052,673 2053,674 2052,676 2050,679 2050,680 2050))
  

• Input 2:

  POLYGON((-8 -8,-8 2056,2056 2056,2056 -8,-8 -8))
  

• Current output:

  POLYGON((-8 2056,667 2056,665 2055,666 2055,666 2054,667 2053,666 2052,667 2050,668 2050,670 2054,672 2052,673 2053,674 2052,676 2050,679 2050,680 2050,682 2050,683 2054,684.2 2056,2056 2056,2056 2042.0800000000002,-8 2042.0800000000002,-8 2056))
  

• Expected output:

2 options: the old output

ERROR:  lwgeom_intersection: GEOS Error: TopologyException: Input geom 0 is invalid: Self-intersection at or near point 699 2086 at 699 2086

The proper value:

POLYGON((684.2 2056,683 2054,682 2050,680 2050,679 2050,676 2050,674 2052,673 2053,672 2052,670 2054,668 2050,667 2050,666 2052,667 2053,666 2054,666 2055,665 2055,667 2056,684.2 2056))

Note that the MVT code, when using the GEOS backend, tries this intersection which raises an exception. To follow up, it runs (an expensive) makeValid and rerun the intersection to get the proper (second) output. With the new OverlayNG behaviour it gets directly an incorrect output, which is pretty bad IMO (we moved away from clipbybox for this very same reason).

Not sure if this affects JTS too.

[pramsey]

Confirmed, it reproduces as a GEOS unit test, and also as a JTS unit test!

  //OverlayNGTest.java
  //https://trac.osgeo.org/geos/ticket/1038
  public void testMvtClipping() {
	Geometry a = read("POLYGON((680 2050,682 2050,683 2054,686 2059,690 2061,694 2062,697 2065,699 2071,700 2080,701 2081,702 2081,703 2082,702 2083,701 2084,701 2085,699 2086,700 2086,699 2086,698 2085,699 2084,695 2083,689 2083,687 2083,685 2085,679 2083,677 2081,677 2078,673 2069,668 2062,667 2062,666 2062,665 2060,667 2058,667 2056,665 2055,666 2055,666 2054,667 2053,666 2052,667 2050,668 2050,670 2054,672 2052,673 2053,674 2052,676 2050,679 2050,680 2050))");
	Geometry b = read("POLYGON((-8 -8,-8 2056,2056 2056,2056 -8,-8 -8))");
	Geometry expected = read("POLYGON((684.2 2056,683 2054,682 2050,680 2050,679 2050,676 2050,674 2052,673 2053,672 2052,670 2054,668 2050,667 2050,666 2052,667 2053,666 2054,666 2055,665 2055,667 2056,684.2 2056))");
	Geometry actual = intersection(a, b, 10);
	checkEqual(expected, actual);
  }

[pramsey]

So, input 1 is invalid... (self intersection at POINT(699 2086)) I wonder if it would work better if it was fed a valid full-resolution polygon instead? One of the benefits OverlayNG should provide for MVT is that the clipper can be fed un-quantized inputs and do the quantization during the snapping/noding process. That said, OverlayNG is supposed to be more tolerant of invalid inputs.

[pramsey]

Hm, also it looks like the OverlayNGSnapIfNeeded code path doesn't do a topological correctness check after it falls back to snapping? Need to confirm.

[pramsey]

Actually, this fails when run directly through the SnapRoundingNoder, and doesn't throw an exception even when it is wrapped in a ValidatingNoder, so it's quite good at slipping past the defences.

[mdavis]

Indeed, the reason that this overlay "does not work" (leaving aside the question of error vs bad output) is that the input polygon is invalid. The contract for overlay operations is that the input is valid. This seems reasonable to me, since "invalid" includes an infinitude of insane geometry, so attempting to "handle" it would be onerous, at best. (And anyway that's what MakeValid is for).

The fact that the old overlay algorithm errored is just a happy accident. The reason the new one does not is that the invalidity is a "out-and-back" collapsed segments, positioned in just such a way to make the polygon orientation test return the wrong answer (CW instead of CCW). This means the polygon is actually treated like a hole - leading to the result produced. This occurs in the topological side of the overlay algorithm, so that's why all noders produce a similar result.

[mdavis]

Now let the discussion of how to handle this begin!

My opening thought is that this either should not be part of the MVT unit tests, or the MVT pipeline needs some ability to clean invalid polygons (assuming it uses GEOS - I guess wagyu does not have this issue?)

[Algunenano]

The fact that the old overlay algorithm errored is just a happy accident.

As far as I am aware, the contract used to be that intersects would either return either a valid output or an error, but never an invalid value. Was that really the case? Has it changed with the new overlay?

My opening thought is that this either should not be part of the MVT unit tests, or the MVT pipeline needs some ability to clean invalid polygons (assuming it uses GEOS - I guess wagyu does not have this issue?)

I could do that, but that would make all polygon MVTs 20x slower so, to be honest, I would rather remove the GEOS backend altogether and forget that's an option than deal with this all over again.

I guess wagyu does not have this issue?

No, wagyu works fine.

[mdavis]

Replying to Algunenano:

As far as I am aware, the contract used to be that intersects would either return either a valid output or an error, but never an invalid value. Was that really the case? Has it changed with the new overlay?

No, the contract is (and was) only that valid inputs would produce valid output (apart from topology exceptions due to numerical robustness. The new overlay has introduced different behaviour for some invalid inputs, but the contract has not changed.

It's too inefficient to always detect invalidities in input in order to error out. Instead, this is left up to the client to implement if it is known to be needed.

[mdavis]

Replying to Algunenano:

My opening thought is that this either should not be part of the MVT unit tests, or the MVT pipeline needs some ability to clean invalid polygons (assuming it uses GEOS - I guess wagyu does not have this issue?)

I could do that, but that would make all polygon MVTs 20x slower so, to be honest, I would rather remove the GEOS backend altogether and forget that's an option than deal with this all over again.

Are these invalidities occurring because of transformation to tile coordinate space before overlay? If so, then using the fixed precision (Snap-Rounding) mode of overlay should allow doing the transformation rounding and the overlay in one step, and thus avoid the creation of invalid inputs.

[Algunenano]

Are these invalidities occurring because of transformation to tile coordinate space before overlay?

There are 4 possible reasons for these invalidities:

• User input.
• The simplification process. Internally the process does a ST_Simplify and ST_RemoveRepeatedPoints with some tolerance. This could be removed but it would affect performance in some cases.
• The coordinate transformation from map units to MVT units.
• The polygon clipping to the tile.

Wagyu is dealing nicely with all 4 of them without major issues. For GEOS/JTS to be a good contestant I think it needs to be able to take a valid polygon and do the coordinate transformation and the clipping in a fast way. We could leave with requiring user input to be valid, but calling MakeValid at any moment in the process kills performance.

[mdavis]

Replying to Algunenano:

There are 4 possible reasons for these invalidities:

• User input.
• The simplification process. Internally the process does a ST_Simplify and ST_RemoveRepeatedPoints with some tolerance. This could be removed but it would affect performance in some cases.
• The coordinate transformation from map units to MVT units.
• The polygon clipping to the tile.

Wagyu is dealing nicely with all 4 of them without major issues.

Use input can be wildly invalid. I'm impressed if wagyu can handle *any* kind of invalidity. Or is it just handling "mild" invalidity (i.e. collapsed topology, as opposed to "figure-8"s)?

Plain DP simplification can introduce figure-8 topology invalidity. But perhaps if the simplification tolerance is below or near the precision grid size, this isn't an issue.

For GEOS/JTS to be a good contestant I think it needs to be able to take a valid polygon and do the coordinate transformation and the clipping in a fast way.

OverlayNG using Snap-Rounding can definitely handle tasks 3 & 4. It may also remove the need for #2, since rounding coordinates effectively collapses repeated points if they round to a single point. (And the comment above about about simplification being fairly safe if it uses a small tolerance applies here as well).

As I mentioned earlier, OverlayNG with Snap-Rounding is not yet exposed via the C API. So if that's what the MVT code is using, we'll have to retry this once OverlayNG-SR is available there.

We could leave with requiring user input to be valid, but calling MakeValid at any moment in the process kills performance.

Agreed, calling MakeValid is a showstopper. And I can't see being able to handle *any* invalid use input. However, "mildly" invalid data should be feasible to handle. "Mildly" invalid includes data which contains topology collapse (either originally or due to rounding). For example, the data in this ​MVT issue works with OverlayNG-SR.

[mdavis]

One further note: I think it is possible to improve the ring orientation algorithm to be able to handle topology collapses such as the one in this data. So that would allow OverlayNG to process this kind of invalidity correctly.

[mdavis]

To confirm the above: indeed it is possible to improve the ring orientation algorithm to "harden" it to deal with topology collapses. That fixes the problem reported in this issue.

[pramsey]

This should be fixed with acbe90de in master?

[Algunenano]

Looks good. Thanks!