[geos-devel] Robustness of Binary Predicates

[Todd Jellett]

Hi Martin,

Thanks for taking the time to reply. We all have so little time. I'd 
also like to say that I am not just playing "devils advocate". Although 
I disagree with some of your design decisions, I am genuinely interested 
in why you made the decisions you did. Reply when you find the time.

The most important question would be why you chose to have the Binary 
Predicates operate at "infinite precision" rather than at the precision 
of the precision model (ie in most cases at the precision of the data 
itself). The computer itself cannot work at infinite precision.

Instead of  trying to make the FIXED precision model a special case of 
the FLOATING model, we have the FLOATING precision model as a special 
case of the FIXED model. Everything falls into place better.

A few short comments below

Todd

Martin Davis wrote:

>I think there are several issues here.  One is a question of algorithm
>robustness and correctness, and the others are design decisions (= value
>judgements).
>
>The ideal of robustness in geometric algorithms is that an particular
>implementation produces answers which are correct according to some
>model.  JTS does this for binary predicates, and attempts to do this for
>boolean operations.  The latter is significantly harder than the former,
>which is why we claim robustness for the first but not the second.  Here
>I use "robust" to mean "consistent and correct within the related group
>of operations". 
>  
>
My interpretation of the spec(s) assumes predicates and boolean 
operations are within the same related group of operations.

>One design decision is whether you extend robustness to mean
>"consistency all of the predicates and boolean operations together".
>This is no doubt a worthwhile goal for some applications.  However, I
>don't think that it is an absolute requirement for using an API to do
>useful work.  (It's also worth noting that the basic set of IEEE
>floating point operations would fail this criterion).
>
>Another design decision is whether the binary predicates should take the
>precision model into account.  This also is probably a worthwhile goal,
>but doesn't seem to be top of the list as far as most people's
>functionality requirements.  It's worth repeating here that whether the
>binary predicates respect the precision model has nothing to do with
>whether they are robust (and also consistent).  If you represent
>geometry using floating point values for the coordinates, the
>topological relationship of two geometries is well-defined regardless of
>the precision model.  (And this is the most efficient and most easily
>understood semantics, IMO.  If you require the precision model to be
>taken into account this requires substantially more complex processing).
>
>  
>
IMHO the Binary Predicates must honour the precision model. How can the 
boolean operations operate at infinite precision when the computer is 
restricted to 15+ significant figures?

>A few more direct comments:
>
>  
>
>>If you are affected by round-off errors, you  have a robustness
>>    
>>
>problem  by definition don't you? 
>
>No, if your operations are consistent with the semantic model you
>specify.  Boolean operations are *always* affected by round-off error.
>  
>
IMHO a missed intersection point is not a semantic issue but rather a 
robustness issue.

>The important thing is that there is a well-defined semantics for the
>results of computation which takes this into account.  (By the way, are
>you expecting that your boolean operations should be self-consistent?
>E.g. fully associative?  Is this even possible?  If you have defined and
>implemented this semantics, I suggest you publish it right away - I've
>never seen any kind of analysis of this issue, and it would be
>fascinating to read).
>  
>
No not fully associative (because a*b is not associative (or 
commutative) on a computer with 15 digits) but we will be as accurate as 
the computer can be in our equivalent of a FLOATING model and accurate 
to the precision model (the data)  in our equivalent of a FIXED model. 
FLOATING model is a special case of FIXED (see above).

>  
>
>>Can't any piece of software claim robustness as long as it is
>>    
>>
>qualified 
>  
>
>>with a "depends on the application"? You need to define your
>>    
>>
>"robustness".
>
>We have tried to do this (with respect to our documentation resources -
>see my comment above about the lack of published analyses anywhere, not
>just in JTS).  Consider the above as further documentation.
>
>Finally, I'm honoured that you considered using my open source
>implementation as a validator for your (presumably) commercial software
>package.  I'm sorry it falls a bit short of your requirements.  It
>sounds like you have some ambitious goals for making your software fully
>robust.
>
Having taken 3 previous runs at this helps. Not as ambitious as you make 
out. Building on what we already have would be more like it.
The "Geometries" are not a commercial product but they will be used in 
commercial applications.

>  Perhaps you should consider publishing your own work in the
>open-source realm, so that the rest of us can benefit from it.  Or even
>better, fund some further work on JTS/GEOS to address some of the issues
>that you've raised.
>  
>
Unfortunately I do not own the rights to the work, my employer does.

>I'd welcome further discussion on this - accompanied by source code if
>possible!
>
>Martin Davis, Senior Technical Architect
>Vivid Solutions Inc.      www.vividsolutions.com
>Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
>Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046
>
>_______________________________________________
>geos-devel mailing list
>geos-devel at geos.refractions.net
>http://geos.refractions.net/mailman/listinfo/geos-devel
>  
>