Made RelateComputer aware of the LineIntersector used by GeometryGraphOperation

[FObermaier]

Fixed isProper check for use of PrecisionModel in RobustLineIntersector
Fixed RelateOp to pass its LineIntersector to RelateComputer.
Added unit test.

[jnh5y]

Hi Felix, your PR seems to be failing some unit tests in Travis CI (https://travis-ci.org/locationtech/jts/builds/203437382).

Is a 'mvn clean install' passing the all the tests for you?

[FObermaier]

Is a 'mvn clean install' passing the all the tests for you?

I assume no, but the failing unit tests have a very poor precision model (PrecisionModel(1.0)).
Changing that to PrecisionModel(10.0) causes the failing and exceptioning tests to pass.

[dr-jts]

Need Javadoc to explain what this does

[dr-jts]

It would be better to put the spelling fixes into a separate PR, or at least a separate commit.

[dr-jts]

This is a pretty major change to Relate semantics. I want to confirm that this does not change the semantics of the Geometry relate methods, right? I.e. it is only invoked via the new RelateComputer constructor?

[dr-jts]

I'm also concerned that applying a PrecisionModel to Relate computation is actually more complex than just using a precision in single LineIntersector tests. I don't have a counter-example right now, but will be trying to validate this. Generally introducing precision models correctly requires some sort of snap-rounding, since rounding must be done globally across the geometries, not just on single intersection tests.

To verify this will require a lot more unit tests, since there are many cases to be covered. There should also be some better documentation to explain the semantics of precision-based relationship computation.

[FObermaier]

Actually I have not touched Geometry.relate functions. The current PR will use the PrecisionModelof the RelateOp which is determined at Construktion.

[dr-jts]

Hmm.. if the changes do not affect the Geometry.relate semantics, then why are there failing unit tests?

[FObermaier]

RelateOp itself instantianates RelateComputer with RelateOp.li. RelateOp.li is actually GeometryGraphOperation.li which is instantiated upon construction.

Therefor the assigned precision model is used, without changing anything in Geometry.releate.

The failing/exceptioning unit test come from the Xml test suite.
Actually one is failing because the expected result is (at least) questionable:

 <case>
   <desc>AA - B sliver crossing A triangle in line segment with length &lt; 1</desc>
   <a>
     POLYGON(
       (0 0, 200 0, 0 198, 0 0))
   </a>
   <b>
     POLYGON(
        (280 60, 139 60, 280 70, 280 60))
    </b>
  <test>
 -  <op name="relate" arg3="212101212" arg1="A" arg2="B">
 -    true
 -  </op>
 -</test>
 -<test>
    <op name="intersection" arg1="A" arg2="B">
      POINT(139 60)
    </op>
 </test>
<!-- some more test -->
</case>

According to the DE-9IM relate pattern we have boundaries intersecting, but the result of the Intersection computation we only get a POINT.

There are three others that are exeptioning (NonNodedIntersection), which might indicate that my approach is a bit too short.

[dr-jts]

The relate algorithm in JTS was intentionally designed to always use full floating precision. This was because at the time it was not obvious to me how to implement a precision model in relate (or indeed whether this was useful). Since then it's become clear that this would be useful, but also that it requires a snap-rounding approach to produce a correct implementation.

That's why the unit test you mention has a relate result which appears to be inconsistent with the overlay result. In fact it is - and that's by design!

But... it's not possible to "fix" this by simply using the LineIntersector with a precision model. Snap-rounding is needed. Here's a classic counter-example:

A: MULTIPOLYGON (((100 200, 300 200, 300 100, 100 100, 100 200)),
((200 200.01, 300 300, 100 300, 200 201)))

B: LINESTRING (200 250, 200 150)

The two MultiPolygon components do not intersect, and thus relate reports they do not cover the linestring (at full precision). But with a precision model of say scale=1, the components will collapse to intersect, and then cover the linestring. However, this collapse has to be computed across the entire geometry - it can't be done on a segment-wise basis.

[FObermaier]

But using a PrecisionModel(1.0) with coordinates that require at least PrecisonModel(100.0) for proper representation is questionable, too, isn't it.

[dr-jts]

Not sure what you're referring to. In current JTS relate always uses a floating precision model.

[FObermaier]

I argue that your example multipolygon has coordinates which cannot be represented with the precision model you suggest. If you'd use a PrecisionModel(100.0) the result would be the same as if you were using a double floating one.

But hey, I'm open for the snap round approach. Could you give me a hint?

[dr-jts]

I see your point. But I think the onus is on you to prove that your approach works!

Snap-rounding is a bit more complicated than just a hint can cover. There is snap-rounding code in JTS already, if you want to try and understand it better. I'm not recommending using it directly, though - there is a more efficient approach possible. But it requires significant development work.

[dr-jts]

Regardless of whether the LineIntersector precision approach is correct, it's not a good thing to change the semantics of the current JTS relate operation. So the code will have to be modified so that the client can indicate that it wants to use the Geometry precision in the operation.

I prefer an API that allows specifying the precision to use for the relate operation, since often I think the PrecisionModel is not set according to the precision of the input (either by omission, or because the geometries are created in a context which cannot be changed by the client).

[FObermaier]

I'm not recommending using it directly, though - there is a more efficient approach possible

Is "An intersection-sensitive algorithm for snap rounding" by Mark de Berg, Dan Halperin and Mark Overmars a good choice or do you have sth else in mind.

[dr-jts]

That's one of the several variants of SR. The one already in JTS is another possibility.

What I really meant was that full-blown SR is pretty slow, and is probably not needed for relate, since relate is essentially a local determination. In fact, in the case where the input is valid at the provided precision model it may well be that your approach of simply rounding during segment intersection is effective. However, I would really prefer to see this validated by a more extensive set of unit tests.

I also have concerns about the potential for ambiguous cases. For instance, does the following have a boundary intersection? And is it rotational-invariant? (Standard SR is not, and it's not clear if this is even feasible).

A: MULTIPOLYGON (((0 10, 10 10, 0 0, 0 10)), ((6 5, 10 5, 10 0, 6 0, 6 5)))

B: LINESTRING (5 6, 2 9)

As said before, this should be implemented as an option, not in the default code path, since it changes existing semantics. In the absence of a well-understood semantics and full set of unit tests, this will allow gaining practical experience in how it behaves.