<div dir="ltr">Hi,<div><br></div><div style>Glad it helps.</div><div style><br></div><div style>CTE are supported since 8.4 according to the doc: <a href="http://www.postgresql.org/docs/8.4/static/queries-with.html">http://www.postgresql.org/docs/8.4/static/queries-with.html</a></div>
<div style>Otherwise, the CTE's can be replaced by subqueries.</div><div style>The stored procedure may also help by creating temp tables instead of chaining subqueries, though I don't know if it will run faster.<br>
</div><div style><br></div><div style>Using topology should be pretty simple in your case: build a new topology based on the lines table, then query the topology.edge table, keeping initial line gid. It may be worth trying it.</div>
<div style><br></div><div style>Nicolas</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On 8 May 2013 21:01, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Nicolas,<br>
<br>
Wow! thank you for an excellent example. This is very help. Since I want this to work on pg 8.4+, I'll convert this into a stored procedure since I can't use CTE subqueries.<br>
<br>
Now I have some work cut out to do on this. :)<br>
<br>
Thanks again,<br>
-Steve<div><div class="h5"><br>
<br>
On 5/8/2013 2:39 PM, Nicolas Ribot wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5">
Hi Stephen,<br>
<br>
Building a topology would definitively help in this situation, though it<br>
may take some time on very large dataset I guess.<br>
If you plan to use some topological functions on the dataset in addition<br>
with pgRouting functions, it may be worth the effort.<br>
<br>
Concerning st_union and its magic "segmentize" feature, would it be<br>
possible to divide the initial set of lines into smaller areas and<br>
process these subsets to avoid filling up the memory ?<br>
<br>
Looking at this subject recently (cutting lines by points, cf.<br>
<a href="http://trac.osgeo.org/postgis/wiki/UsersWikiSplitPolygonWithPoints" target="_blank">http://trac.osgeo.org/postgis/<u></u>wiki/<u></u>UsersWikiSplitPolygonWithPoint<u></u>s</a>) I<br>
found that linear referencing functions can help in such a case.<br>
<br>
The principle is to get the location index of intersection points for<br>
each line, and then to cut this line by its locations, using<br>
st_line_substring.<br>
It appears to be very efficient, using st_dwithin to trigger spatial<br>
index, then joining on the lines primary keys, which should be fast.<br>
<br>
In your usecase, intersection nodes between lines have to be identified<br>
before their locations can be computed.<br>
<br>
Concerning the tolerance, I'm pretty sure snapping the input dataset to<br>
a grid would help to run a precise st_intersection between lines.<br>
<br>
Based on the linestring sample data, here is the query using linear<br>
referencing. It uses CTE subqueries to identify each step:<br>
<br>
with lines as (<br>
select 1 as gid, 'MULTILINESTRING((0 1,2 1))'::geometry as geom<br>
union all<br>
select 2 as gid, 'MULTILINESTRING((1 0,1 2))'::geometry as geom<br>
union all<br>
select 3 as gid, 'LINESTRING(1 1.5,2 2)'::geometry as geom<br>
),<br>
-- multilinestrings are dumped into simple objects<br>
-- if multilinestrings have several parts, one should generate a unique<br>
id based<br>
-- on their gid and path into the collection.<br>
dumped_lines as (<br>
select gid, (st_dump(l.geom)).geom<br>
from lines l<br>
),<br>
-- This query computes the locations, for each input line, of the<br>
intersection points with other lines.<br>
-- this will be used to cut lines based on these locations.<br>
-- to be able to cut lines from their beginning to their end, we<br>
generate the 0 and 1 location index<br>
cut_locations as (<br>
select l1.gid as lgid, st_line_locate_point(l1.geom,<br>
st_intersection(l1.geom, l2.geom)) as locus<br>
from dumped_lines l1 join dumped_lines l2 on (st_dwithin(l1.geom,<br>
l2.geom, 0.01))<br>
where l1.gid <> l2.gid<br>
-- then generates start and end locus for each line, to be able to cut them<br>
UNION ALL<br>
select l.gid as lgid, 0 as locus<br>
from dumped_lines l<br>
UNION ALL<br>
select l.gid as lgid, 1 as locus<br>
from dumped_lines l<br>
order by lgid, locus<br>
),<br>
-- This query generates a row_number index column for each input line<br>
and intersection point.<br>
-- This index will be used to self-join the table to cut a line between<br>
two consecutive locations<br>
-- (idx, idx+1) pairs.<br>
-- window function is used to generate the index inside each line partition<br>
loc_with_idx as (<br>
select lgid, locus, row_number() over (partition by lgid order by locus)<br>
as idx<br>
from cut_locations<br>
)<br>
-- finally, each original line is cut with consecutive locations using<br>
linear referencing function.<br>
-- a filtering is done to eliminate points produced when lines connect<br>
at their ends<br>
select l.gid, loc1.idx as sub_id, st_line_substring(l.geom, loc1.locus,<br>
loc2.locus) as geom ,<br>
st_geometryType(st_line_<u></u>substring(l.geom, loc1.locus, loc2.locus)) as type<br>
from loc_with_idx loc1 join loc_with_idx loc2 using (lgid) join<br>
dumped_lines l on (l.gid = loc1.lgid)<br>
where loc2.idx = loc1.idx+1<br>
-- filter out point geometries occuring if intersection point is at<br>
line's start or end point.<br>
-- there must be a faster way to filter out theses geometries.<br>
and st_geometryType(st_line_<u></u>substring(l.geom, loc1.locus, loc2.locus))<br>
<> 'ST_Point';<br>
<br>
<br>
A new unique ID key can be computed based on line gid and subgid<br>
generated by the query.<br>
Initial line attributes can be moved to the new segments using the line<br>
gid key.<br>
<br>
Nicolas<br>
<br>
<br>
On 8 May 2013 16:27, Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br></div></div><div><div class="h5">
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
Hi all,<br>
<br>
This question comes up reasonably often on the pgRouting list and<br>
has been posted he on occasion under titles like "How to break<br>
streets at intersections?"<br>
<br>
It seems to me that this would be a good function to create in<br>
either postgis or pgrouting.<br>
<br>
THE PROBLEM:<br>
<br>
I have a table of 10's of thousands of street segments to 10's of<br>
millions of street segments. These street segments are LINSTRING or<br>
MULTILINESTRING geometries with some arbitrary number of attribute<br>
columns. The geometries may cross one another and are not noded<br>
correctly for use with pgRouting.<br>
<br>
THE RESULTS:<br>
<br>
We want to process the table and create a new table with the same<br>
structure (see comment about primary key below), and in the new<br>
table all the geometries are broken at intersections and all the new<br>
pieces of the original segment that have been broken have the<br>
original attributes propagated to them. So if the original segment<br>
has column foo='abc' and was split into 3 new segments, each of the<br>
three new segments would also have foo='abc'. The exception to this<br>
might be that the new table needs a new primary column as the old<br>
primary key will now be duplicated for the multiple parts.<br>
<br>
POTENTIAL SOLUTIONS:<br>
<br>
1. I think one way to do this would be to create a topology and load<br>
the table into it, then extra a new table from the topology.<br>
Although I'm not sure of the specifics for doing this or the<br>
efficency of doing it this way.<br>
<br>
2. Another way seems to be using a query like:<br>
<br>
select (st_dump(bar.the_geom)).* from (<br>
select st_union(foo.the_geom) as the_geom from mytable foo<br>
) as bar;<br>
<br>
And then taking each of the dump.geom objects and using st_contains<br>
to find which original segment it belonged to so we can move the<br>
attributes to the new segment. This method also loose any<br>
association to the original record and forces the use of st_contains<br>
to re-associate the new segments to the original segments.<br>
<br>
My concern with this is that the st_union has to load the whole<br>
table which may be 10's of millions of street segments and this will<br>
likely be a memory problem. Also running the st_contains() does not<br>
seems to me to be optimal.<br>
<br>
3. Is there a good recipe for doing this somewhere that I have not<br>
found? or other better approaches to this problem?<br>
<br>
What would be the best way to add tolerance to the problem? using<br>
snap to grid?<br>
<br>
Thoughts on how to do this efficiently?<br>
<br>
Since I'm working on the pgRouting 2.0 release I thought this might<br>
be a nice function to add to that if we can come up with a generic<br>
way to do this.<br>
<br>
Thanks,<br>
-Steve<br>
<br>
<br>
-- Example to demonstrate st_union above<br></div></div>
select st_astext((st_dump(bar.the___<u></u>geom)).geom) from (<div class="im"><br>
select st_union(foo.the_geom) as the_geom from (<br>
select 'MULTILINESTRING((0 1,2 1))'::geometry as the_geom<br>
union all<br>
select 'MULTILINESTRING((1 0,1 2))'::geometry as the_geom<br>
union all<br>
select 'LINESTRING(1 1.5,2 2)'::geometry as the_geom<br>
) as foo<br>
) as bar;<br>
<br>
"LINESTRING(1 1.5,2 2)"<br>
"LINESTRING(1 0,1 1)"<br>
"LINESTRING(1 1,1 1.5)"<br>
"LINESTRING(1 1.5,1 2)"<br>
"LINESTRING(0 1,1 1)"<br>
"LINESTRING(1 1,2 1)"<br></div>
______________________________<u></u>___________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a> <mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/cgi-__bin/mailman/listinfo/postgis-__users" target="_blank">http://lists.osgeo.org/cgi-__<u></u>bin/mailman/listinfo/postgis-_<u></u>_users</a><br>
<<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a>><div class="im"><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
<br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-<u></u>bin/mailman/listinfo/postgis-<u></u>users</a><br>
</div></div></blockquote></div><br></div>