<div dir="ltr">Is it possible for you to share the dataset or a subset of it, to give it a try ?<div><br></div><div style>Nicolas</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On 8 May 2013 22:04, Nicolas Ribot <span dir="ltr"><<a href="mailto:nicolas.ribot@gmail.com" target="_blank">nicolas.ribot@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="im">On 8 May 2013 21:50, 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">I tried to change my first with to just query and existing table, like:<br>
<br>
with lines as (<br>
select id as gid, * from bdaways<br>
/*<div><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></div>
*/<br>
),<br>
<br>
but when I run it I get:<br>
<br>
ERROR: line_locate_point: 2st arg isnt a point<br>
<br>
********** Error **********<br>
<br>
ERROR: line_locate_point: 2st arg isnt a point<br>
SQL state: XX000<br>
<br>
This looks like st_intersection(l1.geom, l2.geom) is not returning a point.</blockquote><div><br></div></div><div>Yes it may return an empty geometryCollection. It could be filtered in the cut_locations cte by adding a where clause geometryType = 'POINT'.</div>
<div><div class="h5">
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><br>
<br>
On 5/8/2013 3:32 PM, Nicolas Ribot wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi,<br>
<br>
Glad it helps.<br>
<br>
CTE are supported since 8.4 according to the doc:<br>
<a href="http://www.postgresql.org/docs/8.4/static/queries-with.html" target="_blank">http://www.postgresql.org/<u></u>docs/8.4/static/queries-with.<u></u>html</a><br>
</blockquote>
<br></div>
ok, cool, will give that a try also.<div><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Otherwise, the CTE's can be replaced by subqueries.<br>
The stored procedure may also help by creating temp tables instead of<br>
chaining subqueries, though I don't know if it will run faster.<br>
</blockquote>
<br></div>
One thing I noticed is that CTE's can not be indexed, so I might get better performance is I create tables and index them based on the needs of successive queries in a stored procedure. I'll need to play with this a bit to figure out what works best.<div>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Using topology should be pretty simple in your case: build a new<br>
topology based on the lines table, then query the topology.edge table,<br>
keeping initial line gid. It may be worth trying it.<br>
</blockquote>
<br></div>
I need to find the how to for working with topologies. I have seem some in the past and just need to give it a try now that I have a real use case for it.<br>
<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>
Nicolas<br>
<br>
<br>
On 8 May 2013 21:01, Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a><br></div><div>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
Hi Nicolas,<br>
<br>
Wow! thank you for an excellent example. This is very help. Since I<br>
want this to work on pg 8.4+, I'll convert this into a stored<br>
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<br>
<br>
<br>
On 5/8/2013 2:39 PM, Nicolas Ribot wrote:<br>
<br>
Hi Stephen,<br>
<br>
Building a topology would definitively help in this situation,<br>
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<br>
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></div>
<a href="http://trac.osgeo.org/postgis/__wiki/__UsersWikiSplitPolygonWithPoint__s" target="_blank">http://trac.osgeo.org/postgis/<u></u>__wiki/__<u></u>UsersWikiSplitPolygonWithPoint<u></u>__s</a><br>
<<a href="http://trac.osgeo.org/postgis/wiki/UsersWikiSplitPolygonWithPoints" target="_blank">http://trac.osgeo.org/<u></u>postgis/wiki/<u></u>UsersWikiSplitPolygonWithPoint<u></u>s</a>>)<div><div>
<br>
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<br>
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<br>
identified<br>
before their locations can be computed.<br>
<br>
Concerning the tolerance, I'm pretty sure snapping the input<br>
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<br>
1))'::geometry as geom<br>
union all<br>
select 2 as gid, 'MULTILINESTRING((1 0,1<br>
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<br>
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<br>
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<br>
line<br>
and intersection point.<br>
-- This index will be used to self-join the table to cut a line<br>
between<br>
two consecutive locations<br>
-- (idx, idx+1) pairs.<br>
-- window function is used to generate the index inside each<br>
line partition<br>
loc_with_idx as (<br>
select lgid, locus, row_number() over (partition by lgid order<br>
by locus)<br>
as idx<br>
from cut_locations<br>
)<br>
-- finally, each original line is cut with consecutive locations<br>
using<br>
linear referencing function.<br>
-- a filtering is done to eliminate points produced when lines<br>
connect<br>
at their ends<br>
select l.gid, loc1.idx as sub_id, st_line_substring(l.geom,<br>
loc1.locus,<br>
loc2.locus) as geom ,<br></div></div>
st_geometryType(st_line___<u></u>substring(l.geom, loc1.locus,<div><br>
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></div>
and st_geometryType(st_line___<u></u>substring(l.geom, loc1.locus,<div><br>
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<br>
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>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br></div>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<div><div><br>
<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<br>
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<br>
10's of<br>
millions of street segments. These street segments are<br>
LINSTRING or<br>
MULTILINESTRING geometries with some arbitrary number of<br>
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<br>
the same<br>
structure (see comment about primary key below), and in the new<br>
table all the geometries are broken at intersections and<br>
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<br>
segment<br>
has column foo='abc' and was split into 3 new segments,<br>
each of the<br>
three new segments would also have foo='abc'. The exception<br>
to this<br>
might be that the new table needs a new primary column as<br>
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<br>
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<br>
st_contains<br>
to find which original segment it belonged to so we can<br>
move the<br>
attributes to the new segment. This method also loose any<br>
association to the original record and forces the use of<br>
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<br>
this will<br>
likely be a memory problem. Also running the st_contains()<br>
does not<br>
seems to me to be optimal.<br>
<br>
3. Is there a good recipe for doing this somewhere that I<br>
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?<br>
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<br>
this might<br>
be a nice function to add to that if we can come up with a<br>
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><br>
<br>
select st_union(foo.the_geom) as the_geom from (<br>
select 'MULTILINESTRING((0 1,2 1))'::geometry as<br>
the_geom<br>
union all<br>
select 'MULTILINESTRING((1 0,1 2))'::geometry as<br>
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>_____________________<div><br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<mailto:<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.<u></u>osgeo.org</a>><br></div>
<mailto:<a href="mailto:postgis-users@lists." target="_blank">postgis-users@lists.</a>__<a href="http://osgeo.org" target="_blank"><u></u>osgeo.org</a><br>
<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>><br>
<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><br>
<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> <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> <<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>
<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> <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>><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><div>
<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></div></div><br></div></div>
</blockquote></div><br></div>