[pgrouting-users] Problem with long edges

Julien-Samuel_Lacroi · October 27, 2010, 6:59pm

Hi,

I use shortest_path_astar() to do the routing in my application. If I understand correctly, this mean that I can do routing from one line segment to another line segment.

I have a problem with line segment that are big loops (see attached image). In my example, the green and red points are my start and end point. Ideally I would like to pass through 95-29, but both points are on edge 95-28. If I understand correctly, I can't use shortest_path_astar(). Right?

Any idea to make this work?

Best regards,
Julien

--
Julien-Samuel Lacroix
Mapgears
http://www.mapgears.com/

dkastl · October 28, 2010, 1:52am

Hi Julien,

It is Shooting Star, that takes line segments as start and end point. Dijkstra and A* route from vertex to vertex.
Indeed your example might lead to the wrong result, if two line segments have the same start and end point. You could split one of them into two segments, but Shooting Star would be the easier solution.

Btw., if you have really long loops like the one of your screenshot, you need to take care not to make the bounding box too small, when you select just a part of your network.

Daniel

2010/10/28 Julien-Samuel Lacroix <jlacroix@mapgears.com>

Hi,

I use shortest_path_astar() to do the routing in my application. If I understand correctly, this mean that I can do routing from one line segment to another line segment.

I have a problem with line segment that are big loops (see attached image). In my example, the green and red points are my start and end point. Ideally I would like to pass through 95-29, but both points are on edge 95-28. If I understand correctly, I can’t use shortest_path_astar(). Right?

Any idea to make this work?

Best regards,
Julien

–
Julien-Samuel Lacroix
Mapgears
http://www.mapgears.com/

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

Julien-Samuel_Lacroi · October 28, 2010, 5:16pm

Hi,

Thank you for your answer. It would probably be better for me to use Shooting Star indeed. However in my example, the start and the end are on the same segment, but since my segment is really long and is a loop, the "real" shortest path would pass through another segment. Is it then the right thing to do to split my really long segment in 2?

Best regards,
Julien

On 10-10-27 09:52 PM, Daniel Kastl wrote:

Hi Julien,

It is Shooting Star, that takes line segments as start and end point.
Dijkstra and A* route from vertex to vertex.
Indeed your example might lead to the wrong result, if two line segments
have the same start and end point. You could split one of them into two
segments, but Shooting Star would be the easier solution.

Btw., if you have really long loops like the one of your screenshot, you
need to take care not to make the bounding box too small, when you
select just a part of your network.

Daniel

2010/10/28 Julien-Samuel Lacroix <jlacroix@mapgears.com
<mailto:jlacroix@mapgears.com>>

    Hi,

    I use shortest_path_astar() to do the routing in my application. If
    I understand correctly, this mean that I can do routing from one
    line segment to another line segment.

    I have a problem with line segment that are big loops (see attached
    image). In my example, the green and red points are my start and end
    point. Ideally I would like to pass through 95-29, but both points
    are on edge 95-28. If I understand correctly, I can't use
    shortest_path_astar(). Right?

    Any idea to make this work?

    Best regards,
    Julien

    --
    Julien-Samuel Lacroix
    Mapgears
    http://www.mapgears.com/

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

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de

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

--
Julien-Samuel Lacroix
Mapgears
http://www.mapgears.com/

Stephen_Woodbridge1 · October 28, 2010, 7:56pm

Well, the "right"? thing to do would be for the underlying pgRouting code to add transient virtual segments at the start and end of the selected segment. this would resolve this issue independent of the data loaded. The way this would look is like this:

In the graph we have three segments A, B, and C joining node 1,2,3,4

(1)------A------(2)-*------B-----*--(3)---*---C--------(4)
S E F

And the route (S) start and (E)or(F) end points.

(1)------A------(2)-*------B-----*--(3)-------C--------(4)
+-(S)---------------+---(F)------------+
+-(S)----------(E)--+

We would then split edge B for the S point and add two new segments 2-S and S-3, and then do the same for the F point and add 3-F and F-4. For the case where the S and E are both on the same segment, you would split B and both S and E and add three segments 2-S, S-E, E-3.

Then for for shooting star, just make sure the starting and ending segment are not the same. If they are then move one to the adjacent segment.

This would also work for the shortest path and Astar and would resolve the issue of trimming the start and end segments.

-Steve

On 10/28/2010 1:16 PM, Julien-Samuel Lacroix wrote:

Hi,

Thank you for your answer. It would probably be better for me to use
Shooting Star indeed. However in my example, the start and the end are
on the same segment, but since my segment is really long and is a loop,
the "real" shortest path would pass through another segment. Is it then
the right thing to do to split my really long segment in 2?

Best regards,
Julien

On 10-10-27 09:52 PM, Daniel Kastl wrote:

Hi Julien,

It is Shooting Star, that takes line segments as start and end point.
Dijkstra and A* route from vertex to vertex.
Indeed your example might lead to the wrong result, if two line segments
have the same start and end point. You could split one of them into two
segments, but Shooting Star would be the easier solution.

Btw., if you have really long loops like the one of your screenshot, you
need to take care not to make the bounding box too small, when you
select just a part of your network.

Daniel

2010/10/28 Julien-Samuel Lacroix <jlacroix@mapgears.com
<mailto:jlacroix@mapgears.com>>

Hi,

I use shortest_path_astar() to do the routing in my application. If
I understand correctly, this mean that I can do routing from one
line segment to another line segment.

I have a problem with line segment that are big loops (see attached
image). In my example, the green and red points are my start and end
point. Ideally I would like to pass through 95-29, but both points
are on edge 95-28. If I understand correctly, I can't use
shortest_path_astar(). Right?

Any idea to make this work?

Best regards,
Julien

--
Julien-Samuel Lacroix
Mapgears
http://www.mapgears.com/

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

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de

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

dkastl · October 29, 2010, 1:37am

Hi Julien,

Steve is right. You need to split your linestring and find out, which part is relevant for your routing result.
When you take this demo with OSM data you will see, that it works: http://websi.openvrp.com/

It uses Shooting Star and adds “virtual” segments at the end. Anton made a wrapper function, that is called “shooting_star_smart”:
http://pgrouting.postlbs.org/browser/sandbox/wrappers/routing_core_smart.sql

There is no documentation about it, but it has been mentioned a couple of times already in the forum. You can try it, if you like, and modify the function if you want. You need to add a table called “network_info”. There is a function for it, that creates the table, if it doesn’t exist yet. I don’t remember all parameters, but it shouldn’t be difficult to find in the wrapper SQL.

Daniel

2010/10/29 Stephen Woodbridge <woodbri@swoodbridge.com>

Well, the “right”? thing to do would be for the underlying pgRouting code to add transient virtual segments at the start and end of the selected segment. this would resolve this issue independent of the data loaded. The way this would look is like this:

In the graph we have three segments A, B, and C joining node 1,2,3,4

(1)------A------(2)-------B-----–(3)—*—C--------(4)
S E F

And the route (S) start and (E)or(F) end points.

(1)------A------(2)-------B-----–(3)-------C--------(4)
±(S)---------------±–(F)------------+
±(S)----------(E)–+

We would then split edge B for the S point and add two new segments 2-S and S-3, and then do the same for the F point and add 3-F and F-4. For the case where the S and E are both on the same segment, you would split B and both S and E and add three segments 2-S, S-E, E-3.

Then for for shooting star, just make sure the starting and ending segment are not the same. If they are then move one to the adjacent segment.

This would also work for the shortest path and Astar and would resolve the issue of trimming the start and end segments.

-Steve

On 10/28/2010 1:16 PM, Julien-Samuel Lacroix wrote:

Hi,

Thank you for your answer. It would probably be better for me to use
Shooting Star indeed. However in my example, the start and the end are
on the same segment, but since my segment is really long and is a loop,
the “real” shortest path would pass through another segment. Is it then
the right thing to do to split my really long segment in 2?

Best regards,
Julien

On 10-10-27 09:52 PM, Daniel Kastl wrote:

Hi Julien,

It is Shooting Star, that takes line segments as start and end point.
Dijkstra and A* route from vertex to vertex.
Indeed your example might lead to the wrong result, if two line segments
have the same start and end point. You could split one of them into two
segments, but Shooting Star would be the easier solution.

Btw., if you have really long loops like the one of your screenshot, you
need to take care not to make the bounding box too small, when you
select just a part of your network.

Daniel

2010/10/28 Julien-Samuel Lacroix <jlacroix@mapgears.com
mailto:[jlacroix@mapgears.com](mailto:jlacroix@mapgears.com)>

Hi,

I use shortest_path_astar() to do the routing in my application. If
I understand correctly, this mean that I can do routing from one
line segment to another line segment.

I have a problem with line segment that are big loops (see attached
image). In my example, the green and red points are my start and end
point. Ideally I would like to pass through 95-29, but both points
are on edge 95-28. If I understand correctly, I can’t use
shortest_path_astar(). Right?

Any idea to make this work?

Best regards,
Julien

–
Julien-Samuel Lacroix
Mapgears
http://www.mapgears.com/

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org mailto:[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@lists.osgeo.org)
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de

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

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