[postgis-users] Use of tolerances in topology

[Nicklas Avén]

ST_Dwithin is not only brute force, at least in theory.

The faster distance algorithm is used in the range when the expanded
bounding boxes intersect but not the geometries own bounding boxes
intersect.

First the && operator checks if the expanded bounding boxes intersects,
if not the answer is false

Then in ST_DWithin the actual bounding boxes of the geometries is
checked if they intersect and if they don't and none of the geometries
is a point (then brute force will be faster) the algorithm described in
the link is used:
 http://trac.osgeo.org/postgis/wiki/NewDistCalcGeom2Geom

But if they do intersect it will be brute force until first distance
found that satisfies the second argument to ST_DWithin.

For tolerance purposes the faster algorithm is quite useless since in
almost all cases the bounding boxes will intersect on small distances,
so Paul is right that it is mostly brute force.

Regards
Nicklas



On Tue, 2012-04-17 at 09:58 -0700, Paul Ramsey wrote:
> Your understanding is correct, the approach is mostly brute force, and
> I have a pile of code lying about waiting to go in that implements
> what you describe in terms of building internal indexes.
> 
> P.
> 
> On Tue, Apr 17, 2012 at 9:29 AM, Jose Carlos Martinez
> <jomarlla at cgf.upv.es> wrote:
> > Thanks Sandro, I understand now.
> >
> > About  trying to enhance ST_Dwithin, last time I checked PostGIS code it was
> > implemented using brute force (after comparing the boxes). Maybe one way to
> > improve the algorithm (DT_Dwithin) will be to use spatial indexes inside a
> > geometry. According to my tests (long time ago with JTS) I remember it could
> > be faster to build a spatial index every time for a geometry and use it than
> > using brute force (with geometries with more than 20 vertexes or so).
> >
> > Anyways Im not sure if PostGIS is still using brute force with st_dwithin,
> > if so then forget everything I said.
> > Regards,
> >
> >
> > On 17/04/2012 17:46, Sandro Santilli wrote:
> >>
> >> On Tue, Apr 17, 2012 at 05:35:42PM +0200, Jose Carlos Martinez wrote:
> >>>
> >>> Hi Sandro, Im learning from topology.sql how the topology functions
> >>> are working with more detail.
> >>>
> >>> I have a question about how the tolerances are managed, for example:
> >>>
> >>> I see (ST_AddIsoEdge) that you have used some times spatial
> >>> predicates as st_contains or st_intersects. As you know these
> >>> predicates (and others too) just work in a good way if the
> >>> geometries are snapped to each other previously,  so my question is
> >>> why you didnt use st_Dwithin with a tolerance? or maybe these
> >>> functions expect the geometries to be already snapped by totopogeom
> >>> for example and they shouldnt be used directly?
> >>
> >> Those functions are ISO functions and as such are not specified to
> >> deal with a tolerance. Handling of tolerance is not always
> >> straightforward as using ST_DWithin. It may also have a big cost.
> >>
> >> So take all those functions as being expected to be already snapped.
> >>
> >> I'm open to suggestion about enhanced versions taking tolerance into
> >> consideration. But it must be possible to invoke such functions in
> >> a fast way, when caller already did their checking and noding and what
> >> not.
> >>
> >> The idea is that all the ST_ prefixed functions end up being just wrappers
> >> around more flexible functions in core.
> >>
> >> --strk;
> >>
> >>   ,------o-.
> >>   |   __/  |    Delivering high quality PostGIS 2.0 !
> >>   |  / 2.0 |    http://strk.keybit.net - http://vizzuality.com
> >>   `-o------'
> >>
> >> _______________________________________________
> >> postgis-users mailing list
> >> postgis-users at postgis.refractions.net
> >> http://postgis.refractions.net/mailman/listinfo/postgis-users
> >
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>