Re: Fixing geometic calculation - Mailing list pgsql-hackers

On Fri, Aug 07, 2009 at 09:12:34AM -0500, Kenneth Marshall wrote:
> On Fri, Aug 07, 2009 at 11:29:47PM +1000, Paul Matthews wrote:
> > Let us consider the ordering of real numbers in postgres. As you can see
> > from
> > the results below it has clearly returned the correct results.
> > 
> >   select( 1.0000000000000000 = 1.0000000000000002 ); => f
> >   select( 1.0000000000000000 < 1.0000000000000002 ); => t
> >   select( 1.0000000000000000 > 1.0000000000000002 ); => f
> > 
> > Imagine the situation however where postgres returned the following
> > values to
> > simple numerical inequalities. In such a case postgresql would be clearly
> > defective and unfit for purpose.
> > 
> >   select( 1.000000 = 1.000001 ); => f
> >   select( 1.000000 < 1.000001 ); => f
> >   select( 1.000000 > 1.000001 ); => f
> > 
> > If such a situation is unacceptable for the real number line, then in
> > what way
> > can it be acceptable for the real number plain.
> > 
> >   select( point(1.00000,0)  <> point(1.00001,0) ); => f
> >   select( point(1.00000,0)  << point(1.00001,0) ); => f
> >   select( point(1.00000,0)  >> point(1.00001,0) ); => f
> >   select( point(1.00000,0) <-> point(1.00001,0) ); => 1.00000000000655e-05
> > 
> > We have two points with a finite separation in the x axis. Postgres
> > thinks they
> > are not the same point, nor one left of the other, nor to the right. This is
> > clearly a both a physical and logical impossibility.

Actually, quantum theory will allow this to happen. :)

> > 
> > The cause of this is the ill conceived FP* macros. They seem represent a
> > solution to a problem that simply does not exist.
> > 
> > The first effect of these macros is to reduce the accuracy of all geometric
> > comparisons from double precision, to less than single precision. The
> > following
> > program correctly prints the correct answer. Whereas as we have seen above,
> > postgres falls in a heap.
> > 
> >   int main() {
> >     float f = 1.00000;
> >     float g = 1.00001;
> >     if( f==g ) { printf( "f=g\n" ); }
> >     if( f<g )  { printf( "f<g\n" ); }
> >     if( f>g )  { printf( "f>g\n" ); }
> >     return 0;
> >   }
> > 
> > The second effect is to take operations that would of worked correctly
> > even in
> > single precision, and to cause them to produce nonsensical result. For
> > example
> > points that can be both inside and outside a polygon at the same time.
> > 
> > Simple analysis of the postgres source code shows that the only places
> > where the
> > FPzero, FPeq, FPne, FPlt, FPle FPgt and FPge macros are defined and used
> > are in
> > the src/backend/utils/adt/geo_ops.c and src/include/utils/geo_decls.h files.
> > 
> > What is the justification for these macros? Why do they only affect
> > geometric
> > calculations, and not all numeric calculations? Why should these macro's
> > not be
> > abandoned?
> > 
> > Does anyone any any objections to me:
> > 1) removing these macros, or at least disabling EPSILON by default.
> > 2) adding in the obviously missing operators (ie: box @> point)
> > 
> 
> Hi Paul,
> 
> Floating point calculations always have a bit of inaccuracy
> because at the very minimum some values do not have exact
> floating point representations and the results can be
> implimentation dependent. I think disabling EPLSILON by
> default is a bad idea. In my work with numeric methods,
> we actually calculated EPSILON for the system we where using
> at runtime. Maybe postgresql could do the same on startup.
> 
> Regards,
> Ken