[postgis-users] snapToGrid strange behaviour

[Martin Davis]

Yikes!  The numerical quicksand on which we all stand just got
quicker...

I agree with Michael's analysis.  The snapping function produces
rounding error by virtue of the functions which it calls.  This means
that for different inputs, it may produce different outputs (even if
only by a few minor bits).  

This is clearly something that will have to be taken into account in any
algorithms based on snapping.  One way of doing this might be to use a
tolerance value for any numerical comparisons.  For snapped numbers the
tolerance can be 0.5 * the grid size.  Spatial functions would have to
take a tolerance value as a parameter.  (Interestingly, Oracle Spatial
provides just such a feature.)

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


> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net 
> [mailto:postgis-users-bounces at postgis.refractions.net] On 
> Behalf Of Kevin Neufeld
> Sent: January 27, 2006 11:04 AM
> To: PostGIS Users Discussion
> Subject: Re: [postgis-users] snapToGrid strange behaviour
> 
> 
> Hmmm. That's interesting. Thanx for your input Michael. For 
> some reason, 
> I assumed the snapToGrid(...) function simply rounded off geometry 
> points at a specified precision by using a simple "floor(point / 
> precision + 0.5) * precision" algorithm. Unfortunately, this 
> means for 
> me that I can't rely on spatial queries performed on snapped 
> geometries, 
> ie. touching geometries snapped to 0.001 may actually be 0.00000001 
> apart and consequently, not spatially touching. I'll have to 
> investigate 
> this further.
> 
> Thanx again for you help Michael,
> Cheers,
> Kevin
> 
> Michael Fuhr wrote:
> 
> >On Fri, Jan 27, 2006 at 08:09:37AM -0800, Kevin Neufeld wrote:
> >  
> >
> >>That's exactly what I was thinking as well. But the 
> question remains,
> >>why does snapToGrid(...) not actually snap to 0.001 as instructed?
> >>    
> >>
> >
> >Presumably it does, but wee differences are probably creeping in 
> >because 0.001 and the resulting values don't have exact binary 
> >representations.  Those errors are smaller than the double precision 
> >type's stated accuracy (15 decimal digits or so), but they make the 
> >values different when doing bit-for-bit equality tests.  So if the 
> >"same" value is arrived at by different calculations, the binary 
> >representations might be different.  Example:
> >
> >test=> CREATE TABLE foo (d1 float8, d2 float8, d3 float8, d4 
> float8, d5 
> >float8); test=> INSERT INTO foo VALUES (1.0, 1000.0, 999.0); test=> 
> >UPDATE foo SET d4 = d1 / d2, d5 = d1 - d3 / d2; test=> 
> SELECT d4, d5, 
> >d4 = d5 FROM foo;
> >  d4   |  d5   | ?column? 
> >-------+-------+----------
> > 0.001 | 0.001 | f
> >(1 row)
> >
> >test=> SELECT encode(float8send(d4), 'hex'), encode(float8send(d5), 
> >'hex')
> >test-> FROM foo;
> >      encode      |      encode      
> >------------------+------------------
> > 3f50624dd2f1a9fc | 3f50624dd2f1aa00
> >(1 row)
> >
> >  
> >
> 
> -- 
> Kevin Neufeld,
> Refractions Research Inc.,
> kneufeld at refractions.net
> Phone: (250) 383-3022 
> Fax:   (250) 383-2140 
> 
> _______________________________________________
> postgis-users mailing list postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>