[postgis-users] Need a method for "noding" a street network

[Stephen Woodbridge]

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)"