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