[pgrouting-users] Get the edges in correct order

pgRouting pgrouting-users
1

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

regards,
--
Antonio

2

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the edge is reversed from the direction that you traverse it on the route. This has been discussed in the past and I have posted an algorithm to correct that, but I do not have a link to it handy.

-Steve

3

Hello Steve, I know the discussion, but the problem is different.
For example, this image [1] shows a part of the city. I have marked the start and
end edges.

Now I have this query:

SELECT gid, AsText(the_geom) AS the_geom
        FROM shootingstar_sp('ways', 552, 1096, 0.1, 'length', true, true);

This image [2] shows the results.

[1] http://img828.imageshack.us/img828/7915/segments.png
[2] http://img215.imageshack.us/img215/5103/resultsi.png

I'm doing something wrong?
Thank you.

--
Antonio

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the
edge is reversed from the direction that you traverse it on the route.
This has been discussed in the past and I have posted an algorithm to
correct that, but I do not have a link to it handy.

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

4

Hi Antonio,

I'm not sure, but I did notice that your list of segments appears to be ordered by gid. You might want to check if the function shootingstar_sp has been modified and someone who added an "order by gid" clause to it.

-Steve

On 9/7/2011 11:35 PM, ancaag04@alumnos.unex.es wrote:

Hello Steve, I know the discussion, but the problem is different.
For example, this image [1] shows a part of the city. I have marked the start and
end edges.

Now I have this query:

SELECT gid, AsText(the_geom) AS the_geom
         FROM shootingstar_sp('ways', 552, 1096, 0.1, 'length', true, true);

This image [2] shows the results.

[1] http://img828.imageshack.us/img828/7915/segments.png
[2] http://img215.imageshack.us/img215/5103/resultsi.png

I'm doing something wrong?
Thank you.

--
Antonio

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the
edge is reversed from the direction that you traverse it on the route.
This has been discussed in the past and I have posted an algorithm to
correct that, but I do not have a link to it handy.

-Steve
_______________________________________________
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

5

I found that the failure depends on the size of the imported topology.

For example, if the database has 2000 or 1800 edges (or less), the order is correct.
But if the database has 4000 or 6000 edges (or more), the order is wrong (is ordered
automatically by gid).

I do not know why this happens... I have not modified any function.

-Antonio

Hi Antonio,

I'm not sure, but I did notice that your list of segments appears to be
ordered by gid. You might want to check if the function shootingstar_sp
has been modified and someone who added an "order by gid" clause to it.

-Steve

On 9/7/2011 11:35 PM, ancaag04@alumnos.unex.es wrote:

Hello Steve, I know the discussion, but the problem is different.
For example, this image [1] shows a part of the city. I have marked the start and
end edges.

Now I have this query:

SELECT gid, AsText(the_geom) AS the_geom
         FROM shootingstar_sp('ways', 552, 1096, 0.1, 'length', true, true);

This image [2] shows the results.

[1] http://img828.imageshack.us/img828/7915/segments.png
[2] http://img215.imageshack.us/img215/5103/resultsi.png

I'm doing something wrong?
Thank you.

--
Antonio

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the
edge is reversed from the direction that you traverse it on the route.
This has been discussed in the past and I have posted an algorithm to
correct that, but I do not have a link to it handy.

-Steve
_______________________________________________
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

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

6

A bunch of us will be away at the FOSS4G conference in Denver this week, so you might not get a quick answer to this. I think it might be appropriate to write up a bug report in the ticket system and copy the appropriate details of the problem from the emails.

If we have time to look into it we will post a response, but more likely it will need to wait until next week when people are back and have time to review the problem.

Thanks,
   -Steve

On 9/11/2011 11:20 PM, ancaag04@alumnos.unex.es wrote:

I found that the failure depends on the size of the imported topology.

For example, if the database has 2000 or 1800 edges (or less), the order is correct.
But if the database has 4000 or 6000 edges (or more), the order is wrong (is ordered
automatically by gid).

I do not know why this happens... I have not modified any function.

-Antonio

Hi Antonio,

I'm not sure, but I did notice that your list of segments appears to be
ordered by gid. You might want to check if the function shootingstar_sp
has been modified and someone who added an "order by gid" clause to it.

-Steve

On 9/7/2011 11:35 PM, ancaag04@alumnos.unex.es wrote:

Hello Steve, I know the discussion, but the problem is different.
For example, this image [1] shows a part of the city. I have marked the start and
end edges.

Now I have this query:

SELECT gid, AsText(the_geom) AS the_geom
          FROM shootingstar_sp('ways', 552, 1096, 0.1, 'length', true, true);

This image [2] shows the results.

[1] http://img828.imageshack.us/img828/7915/segments.png
[2] http://img215.imageshack.us/img215/5103/resultsi.png

I'm doing something wrong?
Thank you.

--
Antonio

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the
edge is reversed from the direction that you traverse it on the route.
This has been discussed in the past and I have posted an algorithm to
correct that, but I do not have a link to it handy.

-Steve
_______________________________________________
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

_______________________________________________
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

7

I've been doing more tests.

Everything is fine when using core functions, but the error occur if used wrapper
functions or subqueries (like "Advanced Routing Queries - Weighted costs" in
FOSSG2010 workshop):

SELECT rt.edge_id AS gid, AsText(ways.the_geom) AS the_geom
    FROM ways, (
    SELECT * FROM shortest_path_astar('
      SELECT gid as id,
        class_id,
                          source,
                          target,
                          length*c.cost as cost,
                          x1, y1, x2, y2,
                          reverse_cost*c.cost as reverse_cost
      FROM ways w, classes c
      WHERE class_id=c.id',
      50,26, false, false)
    ) as rt
    WHERE ways.gid=rt.edge_id;

Maybe this is not a bug in pgRouting...
This could be caused by PosgreSQL (automatically "order by" when the number of
columns is greater than "..." rows).

thanks

-Antonio

A bunch of us will be away at the FOSS4G conference in Denver this week,
so you might not get a quick answer to this. I think it might be
appropriate to write up a bug report in the ticket system and copy the
appropriate details of the problem from the emails.

If we have time to look into it we will post a response, but more likely
it will need to wait until next week when people are back and have time
to review the problem.

Thanks,
   -Steve

On 9/11/2011 11:20 PM, ancaag04@alumnos.unex.es wrote:

I found that the failure depends on the size of the imported topology.

For example, if the database has 2000 or 1800 edges (or less), the order is
correct.
But if the database has 4000 or 6000 edges (or more), the order is wrong (is
ordered
automatically by gid).

I do not know why this happens... I have not modified any function.

-Antonio

Hi Antonio,

I'm not sure, but I did notice that your list of segments appears to be
ordered by gid. You might want to check if the function shootingstar_sp
has been modified and someone who added an "order by gid" clause to it.

-Steve

On 9/7/2011 11:35 PM, ancaag04@alumnos.unex.es wrote:

Hello Steve, I know the discussion, but the problem is different.
For example, this image [1] shows a part of the city. I have marked the start
and
end edges.

Now I have this query:

SELECT gid, AsText(the_geom) AS the_geom
          FROM shootingstar_sp('ways', 552, 1096, 0.1, 'length', true, true);

This image [2] shows the results.

[1] http://img828.imageshack.us/img828/7915/segments.png
[2] http://img215.imageshack.us/img215/5103/resultsi.png

I'm doing something wrong?
Thank you.

--
Antonio

On 8/31/2011 11:28 PM, ancaag04@alumnos.unex.es wrote:

Hello, i'm using A-star like this:

SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 2124, 2168, 0.1);

The path is correct but sometimes I don't get the edges in the correct order.
Is this normal?

I think the edges are always in the correct order, but some times the
edge is reversed from the direction that you traverse it on the route.
This has been discussed in the past and I have posted an algorithm to
correct that, but I do not have a link to it handy.

-Steve
_______________________________________________
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

_______________________________________________
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

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

8

Hi!

I have the same problem, see also
http://gis.stackexchange.com/questions/15568

Any news on the subject? I'm proficient with Postgre, so I would be
willing to have a look at the problem, but would welcome a bit of
guidance where to start, in order to speed up the search for the
problem.

Yours,
  Florian
--
DI Florian Hackenberger
florian@hackenberger.at
www.hackenberger.at

9

Hi Florian,

Thank you for you offer to look into the problem.
On GIS StackExchange someone mentions wrong order due to a JOIN. I haven’t seen this post before. What I remember is people telling that the edges are in the correct order, but sometimes the edge needs to be flipped because end point of an edge is connected with the end point of the next one for example. When you draw the line it looks OK, but if you navigate from start to end point of each edge, then sometimes the order is wrong.
Is this the problem you mean?

In that case in the wrapper function you had to check if start and end point of the geometries match, otherwise flip an edge to make it fit. The order of the core function should give the right order of ID’s, but the wrapper function, that returns the geometry, only cares about the geometry not it’s direction.

Understandable?
I haven’t heard about the JOIN problem yet, so this could be some different issue.

Regards,
Daniel

On Wed, Oct 12, 2011 at 7:00 PM, Florian Hackenberger <f.hackenberger@chello.at> wrote:

Hi!

I have the same problem, see also
http://gis.stackexchange.com/questions/15568

Any news on the subject? I’m proficient with Postgre, so I would be
willing to have a look at the problem, but would welcome a bit of
guidance where to start, in order to speed up the search for the
problem.

Yours,
Florian

DI Florian Hackenberger
florian@hackenberger.at
www.hackenberger.at

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

10

On Wednesday 12 October 2011, Daniel Kastl wrote:

Thank you for you offer to look into the problem.
On GIS StackExchange someone mentions wrong order due to a JOIN. I
haven't seen this post before.

That was me :-). It's definitely not the issue with the flipped edges (I
read about that), but an unrelated problem.

Can you reproduce it?

Yours, Florian

--
DI Florian Hackenberger
florian@hackenberger.at
www.hackenberger.at

11

On Thu, Oct 13, 2011 at 12:18 AM, Florian Hackenberger <f.hackenberger@chello.at> wrote:

On Wednesday 12 October 2011, Daniel Kastl wrote:

Thank you for you offer to look into the problem.
On GIS StackExchange someone mentions wrong order due to a JOIN. I
haven’t seen this post before.

That was me :-). It’s definitely not the issue with the flipped edges (I
read about that), but an unrelated problem.

Can you reproduce it?

Hi Florian,

Sorry, I don’t have much time right now to try to reproduce it.
But I think I remember now there is an attribute returned by at least some wrapper functions that adds another ID column with the order of the edges. So you could sort by this attribute afterwards.

I think the “Shooting Star Smart” wrapper function has this “id”, see:
https://github.com/pgRouting/pgrouting-contrib/blob/master/wrapper/routing_core_smart.sql#L465
… and then ORDER BY id:
https://github.com/pgRouting/pgrouting-contrib/blob/master/wrapper/routing_core_smart.sql#L766

If you can read the pl/pgsql functions you should be able to see if the function you use contain this id attribute as well.

Daniel

Yours, Florian

–
DI Florian Hackenberger
florian@hackenberger.at
www.hackenberger.at

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