[pgrouting-users] Test case - can't find route
Hugo
hfpmartins at gmail.com
Tue May 22 18:46:22 EDT 2012
Hello again,
Thanks Stephen. As i firstly suspected and you pointed out it was all
related with the topology.
Thnaks a lot for the help.
Cheers,
Hugo
On Mon, May 14, 2012 at 4:13 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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<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<javiersdevmail at ymail.com>
>> >
>> <mailto:javiersdevmail at ymail. com
>>
>> <mailto:javiersdevmail at ymail.**com <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<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<pgrouting-users at lists.osgeo.org>
>> >
>> <mailto:pgrouting-users at lists. osgeo.org
>>
>> <mailto:pgrouting-users at lists.**osgeo.org<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<Pgrouting-users at lists.osgeo.org>
>> >
>> <mailto:Pgrouting-users at lists. osgeo.org
>> <mailto:Pgrouting-users at lists.**osgeo.org<Pgrouting-users at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>>
>> <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@**georepublic.de<daniel.kastl at georepublic.de>
>> >
>> <mailto:daniel.kastl@ georepublic.de
>>
>> <mailto:daniel.kastl@**georepublic.de<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<Pgrouting-users at lists.osgeo.org>
>> >
>> <mailto:Pgrouting-users at lists. osgeo.org
>> <mailto:Pgrouting-users at lists.**osgeo.org<Pgrouting-users at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>> <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<Pgrouting-users at lists.osgeo.org>
>> >
>> <mailto:Pgrouting-users at lists. osgeo.org
>> <mailto:Pgrouting-users at lists.**osgeo.org<Pgrouting-users at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>>
>> <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<Pgrouting-users at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>> <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<Pgrouting-users at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting- users
>>
>> <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 <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 <Pgrouting-users at lists.osgeo.org>
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>
--
Hugo Martins
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20120522/830fe14f/attachment-0001.html
More information about the Pgrouting-users
mailing list