Re: [postgis-users] Use of tolerances in topology
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 jomar...@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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
[postgis-users] Use of tolerances in topology
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?
regards,
Jose
CREATE OR REPLACE FUNCTION topology.ST_AddIsoEdge(atopology varchar,
anode integer, anothernode integer, acurve geometry)
--
-- n) Check if curve crosses (contains) any node
-- I used _contains_ here to leave endpoints out
--
FOR rec IN EXECUTE 'SELECT node_id FROM '
|| quote_ident(atopology) || '.node '
|| ' WHERE geom ' || quote_literal(acurve::text)
|| ' AND ST_Contains(' || quote_literal(acurve::text)
|| ',geom)'
LOOP
RAISE EXCEPTION
'SQL/MM Spatial exception - geometry crosses a node';
END LOOP;
--
-- o) Check if curve intersects any other edge
--
FOR rec IN EXECUTE 'SELECT * FROM '
|| quote_ident(atopology) || '.edge_data
WHERE ST_Intersects(geom, ' || quote_literal(acurve::text) ||
'::geometry)'
LOOP
RAISE EXCEPTION 'SQL/MM Spatial exception - geometry intersects an
edge';
END LOOP;
___
postgis-users mailing list
postgis-users@postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
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 jomar...@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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
Thanks Paul, hope you can find the time to make it, for sure it would be outstanding. On 17/04/2012 18:58, 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 jomar...@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@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
On Tue, Apr 17, 2012 at 09:58:01AM -0700, Paul Ramsey wrote: On Apr 17, 2012 Jose Carlos Martinez jomar...@cgf.upv.es wrote: On 17/04/2012 17:46, Sandro Santilli wrote: 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. 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 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. But still my observation about cost wasn't specific to ST_DWithin. The thing is I'm not sure you can use ST_DWithin for everything. An interesting case could be the one of adding a pie cut in 16 slices. There would be a central node from which 16 edges depart. Distance between each edge and the other would be close to 0, but the edges would really only touch at the endpoint. Any tolerance other than zero would prevent adding more than a single edge. Actually, now that I imagine that case I'm not sure ST_Snap would be doing the right thing in that case. Probably not. Until it's modified to always snap to the _closest_ point. --strk; ,--o-. | __/ |Delivering high quality PostGIS 2.0 ! | / 2.0 |http://strk.keybit.net - http://vizzuality.com `-o--' ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
Re: [postgis-users] Use of tolerances in topology
Sometimes some of the problems can be carry out using several st_dwithin, comparing the boundary of a geometry with the boundary or with the other geometry and using tolerances. Several st_Dwithin should be used. Any way I think some new spatial functions could be implemented to do this task in a row in c internally. On 17/04/2012 19:06, Sandro Santilli wrote: On Tue, Apr 17, 2012 at 09:58:01AM -0700, Paul Ramsey wrote: On Apr 17, 2012 Jose Carlos Martinezjomar...@cgf.upv.es wrote: On 17/04/2012 17:46, Sandro Santilli wrote: 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. 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 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. But still my observation about cost wasn't specific to ST_DWithin. The thing is I'm not sure you can use ST_DWithin for everything. An interesting case could be the one of adding a pie cut in 16 slices. There would be a central node from which 16 edges depart. Distance between each edge and the other would be close to 0, but the edges would really only touch at the endpoint. Any tolerance other than zero would prevent adding more than a single edge. Actually, now that I imagine that case I'm not sure ST_Snap would be doing the right thing in that case. Probably not. Until it's modified to always snap to the _closest_ point. --strk; ,--o-. | __/ |Delivering high quality PostGIS 2.0 ! | / 2.0 |http://strk.keybit.net - http://vizzuality.com `-o--' ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users ___ postgis-users mailing list postgis-users@postgis.refractions.net http://postgis.refractions.net/mailman/listinfo/postgis-users
