[pgrouting-users] Test case - can't find route

Stephen Woodbridge woodbri at swoodbridge.com
Mon May 14 11:13:40 EDT 2012


Hugo,

You data MUST be noded. That means that the end of one segment MUST NOT 
hit the interior of a connecting edge. The connect in edge must be split 
so there is a node there.


o - nodes

Invalid: two edges A and B where the end of A is on edge B but there is 
no node on B that matches the end of A:

            o
            |
            A
            |
            o
o-----B-----------------o


Valid: To fix the above issue, you must split edge B into B and C where 
the end of A touches B. So the intersection of A, B and C is one node 
with the same coordinate values.
            o
            |
            A
            |
            |
o-----B----o------C-----o

-Steve


On 5/14/2012 10:47 AM, Hugo wrote:
> Hello all,
>
> Thanks a lot for your answers. They were really helpful.
> Using the initial test case, when building the topology i was using a
> very small tolerance and that's why pgrouting was not able to calculate
> a route. Increasing that tolerance would solve the problem but raise
> other problems such as: at junctions the route would go back to nearest
> edge point and then again forward to complete the route (see image
> below, calculated route in blue).
>
> Inline image 2
>
> I have also decided to try to split all the multilinestrings to simple
> linestrings (made up of only two points). These scenario gives the best
> results when calculating the best route and allows for smaller
> tolerance. However, obviously it takes a higher computational cost.
>
> Do you think that this last approach would not be advisable for
> calculating routes to be show on a webmap?
>
> Thanks once again.
> Cheers,
> Hugo
>
>
> On Fri, May 11, 2012 at 1:52 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
>     Hi Hugo,
>
>     I have not been able to load this test case up yet, but my intuition
>     is that the topology is a problem as you suggest. Can you post the
>     results of this query and what tolerance did you use with
>     assign_vertex_id();
>
>     select gid, source, target, x1, y1, x2, y2 from roads;
>
>     Tolerance needs to be set to a value in the unit of the coordinate
>     system you are using for your edges. So if you are using degrees
>     thena reasonable tolerance= 0.000001 if you are use 6 decimals of
>     precision. Or if your data is in meters or feet then 1.0 might be
>     appropriate. Basically the tolerance is the maximum distance between
>     two end points that you want to be considered as the same point.
>
>     -Steve
>
>
>     On 5/11/2012 4:27 AM, Hugo wrote:
>
>         Hello all,
>
>         I've been using the same workshop to try out pgrouting. And i
>         have also
>         tried with the a-star algorithm which is giving the same
>         results. Here
>         are the queries i'0ve tried:
>
>         select * from shortest_path_astar(
>         'select gid as id,
>              source::integer,
>              target::integer,
>              length::double precision as cost,
>              length::double precision as reverse_cost,
>              x1, y1, x2, y2
>              from roads',
>              8, 5, true, true
>         )
>
>         select * from shortest_path(
>         'select gid as id,
>              source::integer,
>              target::integer,
>              length::double precision as cost,
>              length::double precision as reverse_cost
>              from roads',
>              8, 5, true, true
>         )
>
>           From what i was able to check, i thiink this might be related
>         with the
>         topology that is built with the function assign_vertex_id() but i'm
>         really not sure. I think i will try to explode the road network into
>         simple lines (having only two points defining each line) and try
>         it out
>         again to see if that makes any changes.
>
>         Any addiotional hints?
>         Cheers,
>
>         Hugo
>
>         On Fri, May 11, 2012 at 7:21 AM, Javier Mr
>         <javiersdevmail at ymail.com <mailto:javiersdevmail at ymail.com>
>         <mailto:javiersdevmail at ymail. com
>         <mailto:javiersdevmail at ymail.com>>> wrote:
>
>             Hi,
>
>             i would sugest using A-Star algorithm (specially form large
>             datasets). As Daniel has said the query would be very
>         usefull. Check
>             the directed graph and has_reverse_cost booleans parameters
>         in the
>             core query. Just in case this is a link to a workshop, the one i
>             used to get pgrouting up and running:
>         http://workshop.pgrouting.org/ chapters/shortest_path.html#
>         dijkstra
>         <http://workshop.pgrouting.org/chapters/shortest_path.html#dijkstra>
>
>             Regards.
>             Javier
>
>                 *De:* Daniel Kastl <daniel at georepublic.de
>         <mailto:daniel at georepublic.de>
>         <mailto:daniel at georepublic.de <mailto:daniel at georepublic.de>> >
>                 *Para:* pgRouting users mailing list
>         <pgrouting-users at lists.osgeo. org
>         <mailto:pgrouting-users at lists.osgeo.org>
>         <mailto:pgrouting-users at lists. osgeo.org
>         <mailto:pgrouting-users at lists.osgeo.org>>>
>                 *Enviado:* Viernes 11 de Mayo de 2012 1:23
>                 *Asunto:* Re: [pgrouting-users] Test case - can't find route
>
>
>                 Hello Hugo,
>
>                 Thank you for reporting this!
>                 Could you also share your query?
>
>                 Daniel
>
>
>                 On Fri, May 11, 2012 at 2:32 AM, Hugo
>         <hfpmartins at gmail.com <mailto:hfpmartins at gmail.com>
>         <mailto:hfpmartins at gmail.com <mailto:hfpmartins at gmail.com>>> wrote:
>
>                     Hello all,
>
>                     This is my first post to this mailing list as i have
>         just
>                     started to look into pgrouting more deeply.
>                     When making some routing with this fantastic piece
>         of work,
>                     on a big network i was able to find some porblems where
>                     pgrouting is not finding any route. I attach a very
>         simple
>                     and small data set (roads and vertices_tmp as
>         shapefiles)
>                     that illustrates the problem. If you look into teh image
>                       below, pgrouting is not able to calculate route
>         between
>                     point 8 and 5. I'm using the Dijkstra algorithm and have
>                     built the topology as explained in the docs. I'm using
>                     pgrouting 1.0.3 under postgres 8.4 with postgis 1.5.
>         What to
>                     do in the topology so that a route can be found and
>         how can
>                     i do it in a bulk form to apply to a much bigger
>         roads dataset?
>
>                     Thanks in advance. Cheers,
>                     Hugo
>                     Inline image 1
>                     --
>                     Hugo Martins
>
>
>                     ______________________________ _________________
>                     Pgrouting-users mailing list
>         Pgrouting-users at lists.osgeo. org
>         <mailto:Pgrouting-users at lists.osgeo.org>
>         <mailto:Pgrouting-users at lists. osgeo.org
>         <mailto:Pgrouting-users at lists.osgeo.org>>
>
>         http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
>
>
>
>                 --
>                 Georepublic UG & Georepublic Japan
>                 eMail: daniel.kastl at georepublic.de
>         <mailto:daniel.kastl at georepublic.de>
>         <mailto:daniel.kastl@ georepublic.de
>         <mailto:daniel.kastl at georepublic.de>>
>                 Web: http://georepublic.de <http://georepublic.de/>
>
>
>                 ______________________________ _________________
>                 Pgrouting-users mailing list
>         Pgrouting-users at lists.osgeo. org
>         <mailto:Pgrouting-users at lists.osgeo.org>
>         <mailto:Pgrouting-users at lists. osgeo.org
>         <mailto:Pgrouting-users at lists.osgeo.org>>
>
>         http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
>
>
>             ______________________________ _________________
>             Pgrouting-users mailing list
>         Pgrouting-users at lists.osgeo. org
>         <mailto:Pgrouting-users at lists.osgeo.org>
>         <mailto:Pgrouting-users at lists. osgeo.org
>         <mailto:Pgrouting-users at lists.osgeo.org>>
>
>         http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
>
>
>
>         --
>         Hugo Martins
>
>
>
>         ______________________________ _________________
>         Pgrouting-users mailing list
>         Pgrouting-users at lists.osgeo. org
>         <mailto:Pgrouting-users at lists.osgeo.org>
>         http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
>
>     ______________________________ _________________
>     Pgrouting-users mailing list
>     Pgrouting-users at lists.osgeo. org
>     <mailto:Pgrouting-users at lists.osgeo.org>
>     http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>     <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
>
>
>
> --
> Hugo Martins
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users



More information about the Pgrouting-users mailing list