[geos-devel] Robustness of Binary Predicates

[Todd Jellett]

Hi all,

I have a question concerning the robustness of the Binary Predicates 
(disjoint, contains, etc.). I see on the JTS site that they are claimed 
to be "completely robust" but I don't see anywhere where the "extraneous 
(secondary) intersection points created from snapping the primary 
intersection points" are detected and processed when using a FIXED 
precision model. The monotone chains only find the primary intersection 
points.

Here is an example which creates "extraneous intersection points".
From:    John D. Hobby, "Practical Segment Intersection with Finite 
Precision Output", Comput. Geom Theory Appl., 13:199-214, 1999

Use precision model with a scale of 1 to setup a FIXED precision model 
with 1 significant figure (Whole Numbers).
LINESTRING (-1.0 -2.0, 9.0 5.0, 0.0 0.0, 13.0 6.0)
LINESTRING (9.0 4.0, 5.0 3.0)

The first LineString consists of 3 segments of which 2 of these segments 
intersect at (5.45,2.52). This intersection point "should" then be 
snapped to the precision model giving (5.0,3.0). Snapping this 
intersection point causes the point to move to the other side of the 
middle segment of the LineString which in turn causes 2 extra 
intersection points to be created ( (4.0,2.0) and (6.0, 3.0) when snapped).

In this particular case it is not these 2 extraneous intersection points 
that are causing me to question the robustness of the Binary Predicates, 
instead it is the *not snapping of the primary intersection point* by 
the Binary Predicates..

This sets up ambiguities such as disjoint = true and touches = false but 
intersection = MULTIPOINT (5.0 3.0, 6.0 3.0, 8.0 4.0).
Should be POINT (5.0 3.0) shouldn't it?

I realize that the final robustness issues of the intersection, union, 
etc. are just being addressed, but to get the 2 sets of operations to be 
consistent and only address robustness issues of the intersection, 
union, and differences, won't it mean that you will have to ignore real 
nodes and edges in the graph when computing one of these? Wouldn't this 
defeat the whole purpose of the graph(s)? How could this work without 
ambiguities?

The Binary Predicates seem to "almost be working at infinite precision".
Shouldn't both the predicates and the set theoretics *both* be operating 
at the precision of the precision model provided?

Note: These extra intersection points can occur even if the precision 
model is FLOATING (ie FIXED with 15 significant figures).

Let me know if any of this is not clear.
I used geos 2.2.0 for my tests.

Todd