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

Todd Jellett todd.jellett at caris.com
Thu Jul 26 14:42:24 EDT 2007

Hi Chris,

By "true predicate" I am just referring to the set of five mutually 
exclusive, complete predicates that the SFS is based on and yes, there 
is probably a better term that 'true'. Original?
Contains and Intersects are explicitly defined as "for user convenience 
predicates" on page 2-19 of the SFS but Equals is just listed as a 
method. Is changing Equals to be based on the DE-9IM and promoting it to 
the same standing as the true/basic/core predicates part of the SFS, or 
is this an extension to the SFS? Will it be adopted? Equals is not built 
on true/basic/core predicates the way Contains/Intersects is.

By "violating the mutual exclusivity of the predicates" I am just saying 
that Contains and Equals are not members of the set of mutually 
exclusive, complete predicates (so therefore, there is no problem with 
mutual exclusivity) and I previously thought they were. In my original 
question, I excluded Intersects but included Equals and Contains in the 
group that I thought were mutually exclusive.


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

More information about the geos-devel mailing list