[geos-devel] Robustness of Binary Predicates
todd.jellett at caris.com
Wed Mar 1 11:59:54 EST 2006
Sorry, the second LineString should be:
LINESTRING (5.0 5.0, 5.0 3.0)
This one crashes in L2->touches( L1 )
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
> 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.
> geos-devel mailing list
> geos-devel at geos.refractions.net
More information about the geos-devel