[geos-devel] Robustness of Binary Predicates

[Todd Jellett]

Sorry, the second LineString should be:
LINESTRING (5.0 5.0, 5.0 3.0)

This one crashes in L2->touches( L1 )

Todd

Todd Jellett wrote:

> 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
>
>
>
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel