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

[Chris Hodgson]

Excellent research Todd, good to have it here to help others with any 
similar confusion.

I'd just like to add that the only thing special about Disjoint, 
Touches, Crosses, Within, and Overlaps is that they are both mutually 
exclusive and complete as a set of predicates and thus good for using as 
logical building blocks to more complicated operations. It doesn't mean 
that contains/intersects/equals aren't also perfectly valid and useful 
logical predicates. They are also based on the DE-9IM. Your idea of 
"true" predicates might better be described as "basic" or "core" ... 
"true" implies that other predicates are somehow "false" when perhaps 
composite or complex would be a better term.

Talking about "violating the mutual exclusivity of the predicates" 
doesn't make much sense when you're talking about predicates that aren't 
part of the small set which is proved to be mutually exclusive.

Anyways, good to have all the references put together.

Chris

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