[postgis-users] Need a method for "noding" a street network
Stephen Woodbridge
woodbri at swoodbridge.com
Wed May 8 14:05:47 PDT 2013
Nicolas,
My query just finished running:
Total query runtime: 3716995 ms.
38079 rows retrieved.
Since I started with 17268 rows, I guess I need to rerun this and dump
the results into a new table so I can look at them. Evidently my table
was not noded as I thought.
I'm running:
"PostgreSQL 9.2.4 on i686-pc-linux-gnu, compiled by gcc-4.4.real (Debian
4.4.5-8) 4.4.5, 32-bit"
"POSTGIS="2.0.3 r11128" GEOS="3.3.8-CAPI-1.7.8" PROJ="Rel. 4.7.1, 23
September 2009" GDAL="GDAL 1.6.3, released 2009/11/19" LIBXML="2.7.8"
RASTER"
on a very old and slow system with minimal memory, so an 1+ hr probably
is not horrid, but I don't have anything to compare that against.
-Steve
On 5/8/2013 4:50 PM, Stephen Woodbridge wrote:
> On 5/8/2013 4:05 PM, Nicolas Ribot wrote:
>> Is it possible for you to share the dataset or a subset of it, to give
>> it a try ?
>
> http://imaptools.com:8081/dl/test1.sql.gz
>
> This dataset was noded to start with if that matter, I added the geom
> column and populated it from the x1, y1, x2, y2 columns. So it is not a
> real test in the sense of noding it but it is a typical sized smaller
> data set that we have to deal with.
>
> I added the where and my query is running, so I'll report back what
> happens with it.
>
> Thanks,
> -Steve
>
>> Nicolas
>>
>>
>> On 8 May 2013 22:04, Nicolas Ribot <nicolas.ribot at gmail.com
>> <mailto:nicolas.ribot at gmail.com>> wrote:
>>
>>
>>
>>
>> On 8 May 2013 21:50, Stephen Woodbridge <woodbri at swoodbridge.com
>> <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> I tried to change my first with to just query and existing
>> table, like:
>>
>> with lines as (
>> select id as gid, * from bdaways
>> /*
>>
>> 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
>> */
>> ),
>>
>> but when I run it I get:
>>
>> ERROR: line_locate_point: 2st arg isnt a point
>>
>> ********** Error **********
>>
>> ERROR: line_locate_point: 2st arg isnt a point
>> SQL state: XX000
>>
>> This looks like st_intersection(l1.geom, l2.geom) is not
>> returning a point.
>>
>>
>> Yes it may return an empty geometryCollection. It could be filtered
>> in the cut_locations cte by adding a where clause geometryType =
>> 'POINT'.
>>
>>
>>
>> On 5/8/2013 3:32 PM, Nicolas Ribot wrote:
>>
>> 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
>> <http://www.postgresql.org/docs/8.4/static/queries-with.html>
>>
>>
>> ok, cool, will give that a try also.
>>
>>
>> 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.
>>
>>
>> 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.
>>
>>
>> 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.
>>
>>
>> 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.
>>
>> -Steve
>>
>> Nicolas
>>
>>
>> On 8 May 2013 21:01, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto: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/__UsersWikiSplitPolygonWithPoint__s>
>>
>>
>>
>> <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>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto:woodbri at swoodbridge.com>>
>> <mailto:woodbri at swoodbridge.
>> <mailto:woodbri at swoodbridge.>____com
>>
>> <mailto:woodbri at swoodbridge.__com
>> <mailto: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>
>> <mailto:postgis-users at lists.__osgeo.org
>> <mailto:postgis-users at lists.osgeo.org>>
>> <mailto:postgis-users at lists.
>> <mailto:postgis-users at lists.>____osgeo.org <http://osgeo.org>
>> <mailto:postgis-users at lists.__osgeo.org
>> <mailto: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>>
>>
>>
>>
>> <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
>> <mailto:postgis-users at lists.osgeo.org>
>> <mailto:postgis-users at lists.__osgeo.org
>> <mailto: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
>> <mailto:postgis-users at lists.osgeo.org>
>> <mailto:postgis-users at lists.__osgeo.org
>> <mailto: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
>> <mailto: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
>> <mailto: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
>>
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
More information about the postgis-users
mailing list