# [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.

Todd

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

```