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.
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:
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
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@swoodbridge.com <mailto:woodbri@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@ymail.com <mailto:javiersdevmail@ymail.com>
<mailto:javiersdevmail@ymail. com
<mailto:javiersdevmail@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@georepublic.de
<mailto:daniel@georepublic.de>
<mailto:daniel@georepublic.de> >
*Para:* pgRouting users mailing list
<pgrouting-users@lists.osgeo. org
<mailto:pgrouting-users@lists.osgeo.org>
<mailto:pgrouting-users@lists. osgeo.org
<mailto:pgrouting-users@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@gmail.com <mailto:hfpmartins@gmail.com>
<mailto:hfpmartins@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@lists.osgeo. org
<mailto: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
<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
<mailto:daniel.kastl@georepublic.de>>
Web: http://georepublic.de/>
______________________________ _________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
<mailto: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
<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
______________________________ _________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
<mailto: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
<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
--
Hugo Martins
______________________________ _________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
<mailto:Pgrouting-users@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@lists.osgeo. org
<mailto:Pgrouting-users@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
