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