Unexpected intersection of two overlapping polygons - a multipoint

[grimsa]

Version used: 1.18.2 with jts.overlay property set to ng.

Result from JTS test builder (1.18.2) is correct - i.e. the whole smaller area is included:

Failing test case:

    @Test
    void unexpectedIntersection() {
        var smallerArea = new GeometryFactory().createPolygon(new Coordinate[]{
                new Coordinate(7.04972080711741E-9d, 0.0d),
                new Coordinate(2.2101801468358406E-9d, 1.4126466987753772d),
                new Coordinate(1.2696784445936622d, 1.41264669888319d),
                new Coordinate(1.2696784494332027d, 1.078129033360885E-10d),
                new Coordinate(7.04972080711741E-9d, 0.0d),
        });
        var biggerArea = new GeometryFactory().createPolygon(new Coordinate[]{
                new Coordinate(7.04972080711741E-9, 0.0),
                new Coordinate(0.0, 2.0577913328003916),
                new Coordinate(4.498851115482424, 7.063229687109256),
                new Coordinate(13.596527845590671, 7.06322968918812),
                new Coordinate(19.94490668468672, 1.693592821538914E-9),
                new Coordinate(7.04972080711741E-9, 0.0)
        });

        var intersection = smallerArea.intersection(biggerArea);

        // Expected: POLYGON ((0.0000000022101801 1.4126466987753772, 1.2696784445936622 1.41264669888319, 1.2696784494332027 0.0000000001078129, 0.0000000070497208 0, 0.0000000022101801 1.4126466987753772))
        // Actual: MULTIPOINT ((0.0000000022101801 1.4126466987753772), (0.0000000070497208 0))

        assertTrue(intersection instanceof Polygonal);
    }

A few things I tried:

• Flipping the arguments (biggerArea.intersection(smallerArea)) has no effect
• Normalizing any of the geometries before computing the intersection produces the correct result

[dr-jts]

This looks similar to #784. It uses very high precision numbers as well.

I think the reason it works in TestBuilder is that the numbers get rounded off slightly in the numeric parsing routines.

[grimsa]

Yeah, I figured that it is likely due to precision, e.g.

• 1.078129033360885E-10d in Java code is represented as
• 0.0000000001078129 in WKT which gets pasted into test builder. So in this case there is a difference of 0.0000000000000000033360885.

Somewhat of a side topic - maybe we are wrong to use the floating precision model in our app in the first place? I have not found anything conclusive written on the topic yet. The closest thing is probably the JTS FAQ suggesting using lower precision values in input geometries, but it's not clear if using a fixed precision model is sufficient, or whether coordinates have to just be rounded before overlay operations (e.g. using GeometryPrecisionReducer).

Maybe you could suggest if it would seem that using a fixed precision model could be something worth pursuing? Our context is something like this:

• Our application is in the engineering domain - it generates engineering drawings / 3D models of photovoltaic PV systems
• The coordinates we produce have to be accurate to 5-6 decimal places
• As a user designs a system, there are a number of steps in which the same geometry is both modified by the user, transformed, overlayed, etc. - in other words, we are serializing-deserializing-applying various operations to a geometry repeatedly, then doing the same on derived geometries

For individual operations, I expect the fixed precision model would work flawlessly, but I'm a little worried that with all the serialization-deserialization and repeated/chained overlay operations the inaccuracies/rounding errors could add up.

[dr-jts]

Interesting application!

I understand your concern about always working in fixed precision. Although it sounds appealing, I can't give any guarantee that the inaccuracy won't cascade. My bet would be that it should be fine, especially if you carry a few more digits of precision than needed by the application. But you'd have to try it to see.

Apart from that, you could do all overlay operations using the Snapping Noding technique (see this code). This is what JTS uses as a fallback when it encounters a robustness issue (TopologyException) using standard noding. In fact, the case above works correctly when Snapping Noding is used.

The problem is that JTS isn't detecting the incorrect answer after regular noding. I recently committed an improved heuristic check for overlay (#812), but unfortunately that isn't handling this case. (I have in mind another heuristic that will solve #784, but it won't work for this case either).

There is another potential heuristic check that will catch this case. That is using a check based on Area-Only Overlay, which is fully robust. However, this is a WIP, and it will potentially degrade performance (which may not be an issue for your use case, which I assume involves relatively small geometries?). I will continue to work on this. It could be invoked using a runtime switch, so it would be optional.

[dr-jts]

There is also the possibility that further investigation will reveal why these cases are failing, and identify a fix. I'll look into this when I can.

[grimsa]

Thanks a lot for the detailed answer! Yes, the geometries we work with are fairly simple, so performance would likely not be an issue.

[dr-jts]

As you mention, something that is less invasive than a fixed-precision model is to round geometries slightly before overlay operations. Only a very small rounding should be sufficient. For better performance you could do a point-wise rounding first, and then check validity, and only if invalid use GeometryPrecisionReducer.