[geos-devel] Robustness of Binary Predicates

[Martin Davis]

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". 

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).

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.
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).

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

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