[geos-devel] Binary Predicate Bug - Even Worse!

[Todd Jellett]

Martin Davis wrote:
> I agree with Chris and Paul. The predicates are clearly not intended 
> to be mutually disjoint. They are probably intended to capture the 
> most common use cases in single functions (which allows for some 
> aggressive optimization - some day 8^).
>
> Refractions: 3, Jellet: 1 - we win! 8^)
>
This is not quite the answer I was looking for.

What I expected was something more along the lines of:

Yes, the named spatial relationship predicates based on the DE-9IM 
(Disjoint, Touches, Crosses, Within, and Overlaps) are indeed mutually 
exclusive. For a complete proof that these predicates are mutually 
exclusive see the reference:

Clementini Eliseo, Di Felice P., van Oostrom p., A Small Set of Formal 
Topological Relationships Suitable for End-User Interaction, in D. Abel 
and B. C. Ooi (Ed.), Advances in Spatial Databases, Third International 
Symposium. SSD ’93. LNCS 692. Pp. 277-295. Springer-Verlag. Singapore 
(1993).

Here is an quoted excerpt from section 4.3 of this paper

"In this section, we will prove that the five relationships are mutually 
exclusive, that is, it cannot be the case that two different 
relationships hold between two features; furthermore, we will prove that 
they make a full covering of all possible topological situations, that 
is, given two features, the relationship between them must be one of the 
five."

You (Todd) are probably being confused by the fact that Contains and 
Equals are not true predicates. If you look at page 2-15 of the SFS, in 
the second paragraph, you will see the five unique predicates listed. On 
page 2-19, the SFS defines for user convenience, the predicates Contains 
and Intersects. Note that these two, are not defined uniquely but 
instead are defined in terms of one of the five unique and mutually 
exclusive predicates. ( a.Contains(b) <=> b.Within(a) and 
a.Intersects(b) <=> !a.Disjoint(b) )

Equals is not even listed as a predicate in SFS. It is just listed as a 
method. In ISO 19107, it can be seen that Equals comes from the 
transfiniteSet class along with the other set theoretical operations 
like intersection, union and difference. In 19107, the GM_Object class 
is derived from transfiniteSet. The SFS chose to optimize away the 
transfiniteSet class so the Equals method ended up in the Geometry base 
class (corresponds to GM_Object in ISO 19107) with all the other set 
theoretical methods.

So in conclusion, having Within, Contains, and Equals all come back true 
for two given geometries does not violate the mutual exclusivity of the 
predicates because Within is the only true predicate.