[pgrouting-users] Splitting a network to create intersections

pgRouting pgrouting-users
1

A few weeks ago, Steve Mather posted, and one of his questions was about splitting up a trail network so as to create intersections, but without splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically "it's not that hard" which is good to hear, though I'm still trying to wrap my head around how exactly I would do this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it has problems that again I don't quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also creating the unsplit original segments?

--
Greg Allensworth, Web GIS Developer
BS A+ Network+ Security+ Linux+ Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510 San Francisco CA 94104
PH: 415-979-0343 x302 FX: 415-979-0371 email: gregor@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org

2

Hi Greg,

You can try like this simple example with 2 crossing lines:

CREATE TABLE split(id serial,geom geometry);
INSERT INTO split(geom) VALUES(ST_GeometryFromText(‘LINESTRING(0 0,1 1)’));

INSERT INTO split(geom) VALUES(ST_GeometryFromText(‘LINESTRING(0 1,1 0)’));

SELECT ST_Dump(ST_Split(a.geom,b.geom)) FROM split a, split b WHERE a.id != b.id;

This should return 4 line segments.

Daniel

···

On Tue, May 7, 2013 at 9:16 AM, Greg Allensworth <gregor@greeninfo.org> wrote:

A few weeks ago, Steve Mather posted, and one of his questions was about splitting up a trail network so as to create intersections, but without splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically “it’s not that hard” which is good to hear, though I’m still trying to wrap my head around how exactly I would do this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it has problems that again I don’t quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also creating the unsplit original segments?

–
Greg Allensworth, Web GIS Developer
BS A+ Network+ Security+ Linux+ Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510 San Francisco CA 94104
PH: 415-979-0343 x302 FX: 415-979-0371 email: gregor@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

3

On 5/6/2013 8:16 PM, Greg Allensworth wrote:

A few weeks ago, Steve Mather posted, and one of his questions was about
splitting up a trail network so as to create intersections, but without
splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically "it's not that hard" which is good to hear,
though I'm still trying to wrap my head around how exactly I would do
this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it
has problems that again I don't quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also
creating the unsplit original segments?

Greg,

I think you want to look at this thread:

http://postgis.17.x6.nabble.com/Break-lines-at-intersections-td4663814.html

If you using postgis 1.5 then note 2nd & 3rd posts from the bottom.

select st_astext(st_dump(st_union(the_geom)).geom) from lines;

-Steve

4

Thanks a million. Steve, I'm not sure how I missed that link; it explains a lot. And dkastl, thank you too; that one small example of combining dump and split, clarifies some of the basic logic. Together these are a fine start.

-G

On 5/6/2013 8:50 PM, Stephen Woodbridge wrote:

On 5/6/2013 8:16 PM, Greg Allensworth wrote:

A few weeks ago, Steve Mather posted, and one of his questions was about
splitting up a trail network so as to create intersections, but without
splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically "it's not that hard" which is good to hear,
though I'm still trying to wrap my head around how exactly I would do
this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it
has problems that again I don't quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also
creating the unsplit original segments?

Greg,

I think you want to look at this thread:

http://postgis.17.x6.nabble.com/Break-lines-at-intersections-td4663814.html

If you using postgis 1.5 then note 2nd & 3rd posts from the bottom.

select st_astext(st_dump(st_union(the_geom)).geom) from lines;

-Steve
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Greg Allensworth, Web GIS Developer
BS A+ Network+ Security+ Linux+ Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510 San Francisco CA 94104
PH: 415-979-0343 x302 FX: 415-979-0371 email: gregor@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org

5

Hi Greg,

If you could encapsulate this process into a stored procedure like:

select pgr_node_network(table_in text, table_out text, ...);

That would be a nice addition to pgrouting.

I think the tricky part will be transfering the attribute columns from table_in records to the potentially multiple records that these get chopped into in table_out. I saw somewhere, that someone was using st_contains to find the original segment, but I suspect that there is a better way to do this.

I would suggest bouncing the question off the postgis list because this is really better answered by them.

Thanks,
   -Steve

On 5/7/2013 10:53 AM, Greg Allensworth wrote:

Thanks a million. Steve, I'm not sure how I missed that link; it
explains a lot. And dkastl, thank you too; that one small example of
combining dump and split, clarifies some of the basic logic. Together
these are a fine start.

-G

On 5/6/2013 8:50 PM, Stephen Woodbridge wrote:

On 5/6/2013 8:16 PM, Greg Allensworth wrote:

A few weeks ago, Steve Mather posted, and one of his questions was about
splitting up a trail network so as to create intersections, but without
splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically "it's not that hard" which is good to hear,
though I'm still trying to wrap my head around how exactly I would do
this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it
has problems that again I don't quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also
creating the unsplit original segments?

Greg,

I think you want to look at this thread:

http://postgis.17.x6.nabble.com/Break-lines-at-intersections-td4663814.html

If you using postgis 1.5 then note 2nd & 3rd posts from the bottom.

select st_astext(st_dump(st_union(the_geom)).geom) from lines;

-Steve
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

6

Allen,

Jump on the postgis list archives, there has been a great exchange between Nicolas Ribot and myself on how to node a network of streets. The outcome is a very usable stored procedure, that will likely get included in pgrouting and has been posted on the list.

-Steve

On 5/7/2013 10:53 AM, Greg Allensworth wrote:

Thanks a million. Steve, I'm not sure how I missed that link; it
explains a lot. And dkastl, thank you too; that one small example of
combining dump and split, clarifies some of the basic logic. Together
these are a fine start.

-G

On 5/6/2013 8:50 PM, Stephen Woodbridge wrote:

On 5/6/2013 8:16 PM, Greg Allensworth wrote:

A few weeks ago, Steve Mather posted, and one of his questions was about
splitting up a trail network so as to create intersections, but without
splitting unnecessarily.

http://pgrouting-users.974093.n3.nabble.com/pgrouting-users-A-vs-Dijkstra-and-the-nature-of-the-A-implementation-td4025099.html

The reply was basically "it's not that hard" which is good to hear,
though I'm still trying to wrap my head around how exactly I would do
this. Any explanation of the logic would be helpful there.

This fellow at StackExchange posted some code, but but he says that it
has problems that again I don't quite follow.

http://gis.stackexchange.com/questions/34687/how-to-split-osm-roads-into-individual-segments-at-intersections

Any comments on his approach, and what would be going wrong with it also
creating the unsplit original segments?

Greg,

I think you want to look at this thread:

http://postgis.17.x6.nabble.com/Break-lines-at-intersections-td4663814.html

If you using postgis 1.5 then note 2nd & 3rd posts from the bottom.

select st_astext(st_dump(st_union(the_geom)).geom) from lines;

-Steve
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

7

On 5/7/2013 8:57 AM, Stephen Woodbridge wrote:

If you could encapsulate this process into a stored procedure like:
select pgr_node_network(table_in text, table_out text, ...);
That would be a nice addition to pgrouting.

https://github.com/gregallensworth/PostGIS/blob/master/PGRouting_create_intersections.txt

The technique given by dkastl was causing multiple splits of the same line: if a line is crossed by two separate other lines, then there may be multiple overlapping cut-ups.

But ST_Node() on the ST_Union() seems to work just perfectly. And it accommodates linear intersections, while ST_Split() bails in those cases.

I think the tricky part will be transfering the attribute columns from
table_in records to the potentially multiple records that these get
chopped into in table_out. I saw somewhere, that someone was using
st_contains to find the original segment, but I suspect that there is a
better way to do this.

Eventually I gave up on this, and am writing an external program to do it instead. What I have so far, FYI:

- ST_INTERSECTS() isn't suitable as it would find any original line segments which intersect, and by nature there should be multiple such matches (at least 2, at endpoints).

- ST_CONTAINS() only works for very simple cases, it seems due to rounding errors. While linestring (0 0, 10 10) does contain (2 2, 3 3), the linestrings cut up from (0 6, 2 0) don't necessarily map back to the original one precisely.

- What I have come up with is inefficient but seems effective:
ORDER BY ST_INTERSECTION(ST_BUFFER(original.geom,0.01),ST_BUFFER(splits.geom,0.01))
DESC LIMIT 1;
It's crude, but seems logical: the line which has the most overlap with this one, accounting for the fact that they may in fact only intersect at one point and diverge very slightly, is most likely to be the original.

- But actually applying this to fetch and update the fields, is so far a boondoggle. The "record" datatype in Pl/PgSQL won't allow access to fields named in a variable, the "row" datatype assumes a fixed table name in the declaration, etc. This question seems to be asked a lot, the answers other than "you can't" assume significant foreknowledge of the target table.

--
Greg Allensworth, Web GIS Developer
BS A+ Network+ Security+ Linux+ Server+
GreenInfo Network - Information and Mapping in the Public Interest
564 Market Street, Suite 510 San Francisco CA 94104
PH: 415-979-0343 x302 FX: 415-979-0371 email: gregor@greeninfo.org
Web: www.GreenInfo.org www.MapsPortal.org

Subscribe to MapLines, our e-newsletter, at www.GreenInfo.org

8

Greg,

Before you spend much more time on this, check out this thread:

https://groups.google.com/forum/?fromgroups=#!topic/postgis-users/nTN67mm8IuA

And scroll down to the node-table-proc.sql attachment and give it a try.

-Steve

On 5/9/2013 10:24 PM, Greg Allensworth wrote:

On 5/7/2013 8:57 AM, Stephen Woodbridge wrote:

If you could encapsulate this process into a stored procedure like:
select pgr_node_network(table_in text, table_out text, ...);
That would be a nice addition to pgrouting.

https://github.com/gregallensworth/PostGIS/blob/master/PGRouting_create_intersections.txt

The technique given by dkastl was causing multiple splits of the same
line: if a line is crossed by two separate other lines, then there may
be multiple overlapping cut-ups.

But ST_Node() on the ST_Union() seems to work just perfectly. And it
accommodates linear intersections, while ST_Split() bails in those cases.

I think the tricky part will be transfering the attribute columns from
table_in records to the potentially multiple records that these get
chopped into in table_out. I saw somewhere, that someone was using
st_contains to find the original segment, but I suspect that there is a
better way to do this.

Eventually I gave up on this, and am writing an external program to do
it instead. What I have so far, FYI:

- ST_INTERSECTS() isn't suitable as it would find any original line
segments which intersect, and by nature there should be multiple such
matches (at least 2, at endpoints).

- ST_CONTAINS() only works for very simple cases, it seems due to
rounding errors. While linestring (0 0, 10 10) does contain (2 2, 3 3),
the linestrings cut up from (0 6, 2 0) don't necessarily map back to the
original one precisely.

- What I have come up with is inefficient but seems effective:
ORDER BY
ST_INTERSECTION(ST_BUFFER(original.geom,0.01),ST_BUFFER(splits.geom,0.01))
DESC LIMIT 1;
It's crude, but seems logical: the line which has the most overlap with
this one, accounting for the fact that they may in fact only intersect
at one point and diverge very slightly, is most likely to be the original.

- But actually applying this to fetch and update the fields, is so far a
boondoggle. The "record" datatype in Pl/PgSQL won't allow access to
fields named in a variable, the "row" datatype assumes a fixed table
name in the declaration, etc. This question seems to be asked a lot, the
answers other than "you can't" assume significant foreknowledge of the
target table.