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

Thu Aug 9 12:53:16 EDT 2007

I don't really see the problem with expressing Equals in terms of the 
DE-9IM.  To my mind, this just adds some value to this predicate by 
putting it under the same theoretical framework as the rest of the 
"standard" predicates.  If you don't like it, just ignore that definition. 

I don't see the reason to be concerned about whether Contains and Equals 
"have the same standing" or "will be adopted".  The functionality is 
there, is well-defined and clearly documented.  Use it or don't use it - 
your choice.

Your original question was concerning the behaviour of contains and 
within on two topologically equal polygons.  According to my analysis, 
the observed behaviour is consistent with the definition of contains and 
within in both GEOS/JTS and OGC-SFS.  If you don't like this behaviour, 
you'd better take it up with the OGC.

You wrote "How can 2 simple geometries be equal *and* contained *and* 
within?".  The reason is simple.  Think of contains as >= and within as 
<=.    If A = B, then obviously A <= B and A >= B - there's no 
contradiction here.

Martin

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

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022