[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