wiki:ToleranceDiscussion

What functions need a tolerance/precision and how should it be implemented

Aiming at 2.1 The double precision floating point values in the coordinates and function returns sometimes makes things difficult.
It is for instance impossible to find a point that is intersecting a linestring except some special cases.

What makes things difficult is that the number of decimals that the double precision value can hold depends on how many digits is needed on the left of the decimal sign.

The good thing is that double precision hold way more precision than needed in mapping. It is not common to use maps for better precision than decimeters or centimeters.

So, we need some way to do the calculations with best possible precision and then from a given tolerance or decided from the precision of the input take the inaccuracy in account.

List of functions that should take tolerance and precision.

Native PostGIS

  • ST_Distance, would be nice if the output was based on the input precision.

In GEOS

  • ST_Intersects with tolerance

Should behave like ST_Dwithin with the tolerance as the second argument. But ST_Intersects is way faster than ST_Dwithin so hopefully it is possible to implement in that algoritm

Snap rounding

GEOS/JTS is moving toward the "snaprounding" approach.
Paper here: http://www.ics.uci.edu/~goodrich/pubs/snap.pdf
Martin's mail here: http://lists.osgeo.org/pipermail/geos-devel/2012-February/005651.html

I guess our goal would be sharing the "grid" between postgis and GEOS. A regular grid (like shown in the paper) would only take a size (vertical and horizontal) to share. An irregular grid (FP expanding grid?) would take an equivalent calculus to compute.

GEOS PrecisionModel

The geos::geom::PrecisionModel GEOS PrecisionModel Class was ported from JTS to the GEOS C++ API, but there is no C API for this feature. Adding a PrecisionModel to the GEOS functionality uses a precision grid to "snap" all coordinates, which could eliminate some rounding and robustness issues with some functions.

The functionality can be previewed graphically with JTS TestBuilder, in the top menu Edit > Precision Model ... For example, if you want to have millimetre tolerance, set the fixed to "1000.0", now an input geometry of 'POINT (130.111 281.999)' will remain the same, but an input of 'POINT (130.1111 281.9999)' will auto magically snap to 'POINT (130.111 282)'. Other functions, such as buffer, will also have results that conform to no more than millimetre precision (three decimal places).

In order for this functionality to be used in PostGIS, it would first need to be exposed to the GEOS C API. Secondly, PostGIS would need to somehow communicate the precision model to be used, based on some metadata. As a first pass idea, the topology extension has a few metadata tables, where a tolerance could somehow be specified. I'm not sure how it could be implemented to other geometries without a server runtime variable (e.g., Customized Options).

Last modified 6 years ago Last modified on Mar 28, 2012 3:17:04 PM