OGCGeometry#union of geometries of different dimensions is incorrect

[mbasmanova]

I'm seeing incorrect results when calling OGCGeometry#union on geometries of different dimensions, e.g. point and linestring, linestring and polygon, etc.

For example, the following tests

public class TestOGCUnion
{
    @Test
    public void testPoint()
    {
        assertUnion("POINT (1 2)", "LINESTRING EMPTY", "POINT (1 2)");
    }

    @Test
    public void testPointWithLinestring()
    {
        assertUnion("POINT (1 2)", "LINESTRING (3 4, 5 6)", "GEOMETRYCOLLECTION (POINT (1 2), LINESTRING (3 4, 5 6))");
    }

    @Test
    public void testLinestring()
    {
        assertUnion("LINESTRING (1 2, 3 4)", "POLYGON EMPTY", "LINESTRING (1 2, 3 4)");
    }

    @Test
    public void testLinestringWithPolygon()
    {
        assertUnion("LINESTRING (1 2, 3 4)", "POLYGON ((0 0, 1 1, 0 1, 0 0))", "GEOMETRYCOLLECTION (LINESTRING (1 2, 3 4), POLYGON ((0 0, 1 1, 0 1, 0 0)))");
    }

    private void assertUnion(String leftWkt, String rightWkt, String expectedWkt)
    {
        OGCGeometry union = OGCGeometry.fromText(leftWkt).union(OGCGeometry.fromText(rightWkt));
        assertEquals(expectedWkt, union.asText());
    }
}

fail with

Expected :POINT (1 2)
Actual   :MULTILINESTRING EMPTY

  at com.esri.core.geometry.TestOGCUnion.testPoint(TestOGCUnion.java:26)

Expected :GEOMETRYCOLLECTION (POINT (1 2), LINESTRING (3 4, 5 6))
Actual   :LINESTRING (3 4, 5 6)

  at com.esri.core.geometry.TestOGCUnion.testPointWithLinestring(TestOGCUnion.java:32)

Expected :LINESTRING (1 2, 3 4)
Actual   :MULTIPOLYGON EMPTY

  at com.esri.core.geometry.TestOGCUnion.testLinestring(TestOGCUnion.java:38)

Expected :GEOMETRYCOLLECTION (LINESTRING (1 2, 3 4), POLYGON ((0 0, 1 1, 0 1, 0 0)))
Actual   :POLYGON ((0 0, 1 1, 0 1, 0 0))

  at com.esri.core.geometry.TestOGCUnion.testLinestringWithPolygon(TestOGCUnion.java:44)

I'm also seeing union of POLYGON ((0 0, 1 1, 0 1, 0 0)) and POLYGON ((0.5 0.5, 0.7 0.7, 0.5 0.7, 0.5 0.5)) being POLYGON ((0.7 0.7, 1 1, 0 1, 0 0, 0.5 0.5, 0.7 0.7)) and not POLYGON ((0 0, 1 1, 0 1, 0 0)). The shapes are the same, but union result has redundant points. Is this expected?

[stolstov]

@mbasmanova The first part of the issue - union of geometries of different type it is similar to the #176. The OGC union delegates to the Esri Operator_union and it produces geometry of highest common dimension only.

While the second part (extra vertices), this is something that should not happen in this case, and I'll take a look.

[stolstov]

@mbasmanova I've made this test case, and it passes (no extra vertices). Could you modify it to make it fail?

		OGCGeometry g1 = OGCGeometry.fromText("POLYGON ((0 0, 1 1, 0 1, 0 0))");
		OGCGeometry g2 = OGCGeometry.fromText("POLYGON ((0.5 0.6, 0.7 0.8, 0.5 0.8, 0.5 0.6))");
		OGCGeometry result = g1.union(g2);
		String resultText = result.asText();
		assertTrue(resultText.compareTo("POLYGON ((0 0, 1 1, 0 1, 0 0))")==0);

[mbasmanova]

@stolstov Here you go:

    @Test
    public void test()
    {
        OGCGeometry g1 = OGCGeometry.fromText("POLYGON ((0 0, 1 1, 0 1, 0 0))");
        OGCGeometry g2 = OGCGeometry.fromText("POLYGON ((0.5 0.5, 0.7 0.7, 0.5 0.7, 0.5 0.5))");
        OGCGeometry result = g1.union(g2);
        assertEquals("POLYGON ((0 0, 1 1, 0 1, 0 0))", result.asText());
    }

org.junit.ComparisonFailure: 
Expected :POLYGON ((0 0, 1 1, 0 1, 0 0))
Actual   :POLYGON ((0.7 0.7, 1 1, 0 1, 0 0, 0.5 0.5, 0.7 0.7))

BTW, I'm using assertEquals instead of assertTrue as it provides a better error message in case of test failure.

[stolstov]

@mbasmanova That's not a bug. Those vertices are result of intersection of the input geometries. They will stay in the output.

[mbasmanova]

@stolstov Sergey, thanks for clarifying. Just to double check, are you saying that even though in this case one geometry is fully contained in the other geometry, we can expect the result to be having extra vertexes (e.g. 3+ consecutive vertexes on the same line)?

[stolstov]

Yes. First step of the overlay algorithm is to split all segments at intersections. Those vertices are not removed explicitly.

[mbasmanova]

@stolstov Thanks for explaining. I don't know yet whether this will become a problem, but overall extra vertexes use extra space in both memory and disk and require more CPU for relationship checks (contains, intersects, etc.). If we needed to remove the redundant vertexes, is there a way to do that?

I'm also seeing union of POLYGON ((0 0, 1 1, 0 1, 0 0)) and POLYGON ((0.3 0.1, 2 0.1, 2 0.5, 0.3 0.5, 0.3 0.1)) being POLYGON ((0 0, 0.30000000000000004 0.3000000000000001, 0.3 0.1, 2 0.1, 2 0.5, 0.5 0.5, 1 1, 0 1, 0 0)) (notice 0.30000000000000004 0.3000000000000001 instead of 0.3 0.1). Is this expected as well?

[jgravois]

If we needed to remove the redundant vertexes, is there a way to do that?

have you seen the Generalize operation, which uses the Douglas–Peucker algorithm?

[stolstov]

@mbasmanova The asText method does not round. Those numbers are due to floating point calculations. The OperatorExportToWKT allows rounding though (see WktExportFlags.java), but OGCGeometry.asText does not have the control.

[mbasmanova]

@jgravois John, I haven't seen Generalize operation. Thanks for the pointer. I assume this is the simplify polygon operation. What's the semantics of maxDeviation? Is this max distance between original and simplified geometries?

[jgravois]

We also use the term 'simple' to describe topologically correct geometries.

Simplify - checks (and corrects for) topological validity.
Generalize - removes any vertex that won't result in an output line segment that deviates from the original more than the threshold maxDeviation.

because maxDeviation is passed through as a double, my hunch is that internally we assume the same unit of measure as the CRS of the input geometry.

[mbasmanova]

@jgravois John, thanks for explaining. @stolstov Looks like Sergey's PR #178 improves union method to perform simplification inline. With these change, we'll be able to use union in Presto directly.

[stolstov]

@mbasmanova Could you verify?

[mbasmanova]

@stolstov Sergey, the PR includes tests for the new functionality. What else needs to be done for verification?

[stolstov]

@mbasmanova Nothing else, unless you would like to do more verification.

[mbasmanova]

@stolstov The tests in the PR cover test cases I had in mind. I don't have anything else to add at this point.

[stolstov]

@mbasmanova Thank you Maria!