[postgis-devel] Discussion about routing in PostGIS

[TECHER Jean David]

Hi

It seems that U are French

Can U send a mail in French???

Thanks
----------------------------------------------------------------
TECHER Jean David
Responsable Informatique 01MAP
e-mail: davidtecher at yahoo.fr
Bureau: 04 67 45 60 27
Portable: 06 85 37 36 75
site perso : http://techer.pascal.free.fr/postgis/
site pro: http://www.01map.com/download/
K-S:"The greatest trick the devil pulled off was convincing people he didn't
exist"
------------------------------------------------------------
----- Original Message -----
From: "Sylvain Pasche" <sylvain.pasche at camptocamp.com>
To: <postgis-devel at postgis.refractions.net>
Sent: Thursday, April 07, 2005 4:28 PM
Subject: [postgis-devel] Discussion about routing in PostGIS


> Hello,
>
> I am investigating the solution of integrating routing algorithm inside
> PostGIS, as it was announced previously on the list.
>
> Of course, such an integration is not a trivial task, and I guess there
> are several different scenarios and possibilities for such a
> development. I see this mail more like brainstorming, for gathering
> ideas, proposals, or listing existing things from which we could take
> inspiration. I will try not to be to biased towards the problem we need
> to solve (shortest path calculation), one goal would be to be the more
> generic possible across different problem domains.
>
> Regarding the routing algorithms, a GNU licenced library named DGLib
> (http://grass.itc.it/dglib/) is available for performing tasks such as
> shortest path, minimal spanning tree calculation and others.
>
> Background
> ==========
>
> I give below some background information, to clarify the situation.
>
> The graph library has to deal with the following information (for
> instance for the shortest path calculation):
>
> input:
> list of nodes with optional associated costs
> list of edges with associated costs.
> Relations between nodes and edges (directed or not)
>
> output:
> list of traversed nodes and edges, with associated cost (total cost can
> be calculated from this).
>
> Possible usage scenario
> ===========================
>
> Maybe some usage scenario is useful for having a better feeling about
> the data flow:
>
> * Static data:
>   * a list of nodes with associated geographical coordinates, and
> identifiers.
>   * a list of edges binding pairs of nodes together. Each edge has an
> identifier, and an initial cost which is the geographical distance
> between the two nodes.
>
> * Dynamic data:
>   * Cost for each edge of the graph. These dynamic cost can take into
> account the static geographical distance between nodes. In the real
> world, this cost could be the mean speed possible on a road multiplied
> with the road distance.
>
> The task is to compute a list of nodes/edges for the shortest path
> between two points of the graph, according to a dynamically calculated
> list of costs. It should be possible to extract the node identifiers,
> and the geographical line of the path.
>
> Design discussion
> =================
>
> Datatypes:
>
> As we can see from the above, standard PostGIS datatypes are missing
> some information, like nodes id, edges list, ...
>
> One approach is to map the algorithm on the current PostGIS datatypes,
> like in the following function (idea from O. Courtin):
>
> static PG_LWGEOM *
> dglib_shortest_path(PG_LWGEOM * geom, LWPOINT * from, LWPOINT * to,
>                 int strict, int use_cost, int directed)
>
> where:
>  stricts: from and to must belong the the graph, nearest otherwise
>  use_cost: if true, and points are 3DM/4D: uses the M value otherwise,
> uses the cost from the geography distance.
>  directed: flag for directed graph.
>
> The resulting Line will be the shortest path.
>
> However, there are some shortcomings with this approach:
>
> - The notion of nodes and edges identifier is not kept. These should be
> looked elsewhere, probably in a (x, y) -> id table.
> - To dynamically modify the cost of an edge, the whole geometry has to
> be modified.
>
>
> Another approach would be to have some specific "directed graph"
> datatypes, on which graph algorithm functions could be called. For
> instance a datatype storing the whole graph and another structure for
> the cost mapping. This way, different cost mapping structures could be
> used in a function like
>
> line1 = shortest_path(graph_structure, cost_mapping_structure1)
>
> line2 = shortest_path(graph_structure, cost_mapping_structure2)
>
> This is just simple illustration to introduce the concept of a specific
> graph datatype.
>
> Certainly there are other design approaches for this problem, I would be
> pleased to hear from you ideas/thoughts on the matter.
>
> In particular, the "how to others do" would certainly give valuable
> informations in this domain. However, I did not find any reference on
> the specific routing+sql problem. If you have informations about this it
> would be great.
>
>
> Thanks,
>
> Sylvain Pasche
>
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel