Re: [gulliver] [ANN] ocaml-osm-route : un ch'tit programme de routage dans des fichiers OSM

[David MENTRE <dmentre at linux-france dot org>]

Salut Étienne,

Étienne Loks <etienne dot loks at laposte dot net> writes:

> La base postgis permettrait par ailleurs de faire d'autres requêtes
> spatiales un minimum optimisées.

Je ne dis pas que mon choix de structure de données soit le plus
optimal. Des gens qui ont sérieusement réfléchit au problème ont
certainement trouvés des représentations plus astucieuses que moi.

> Mais pour un sujet si sensible en terme de performance (surtout si
> l'idée derrière est de l'intégrer éventuellement dans une appli web), il
> peut être envisagé de disposer d'une structure de donnée spécifique pour
> le routage donc c'est très intéressant.

Oui, c'est un peu dans cette idée là que j'avais fait.

> D'ailleurs cela donne quoi en terme de performance ?

J'ai pas vraiment fait d'étude de perf. À vue de nez, sur
hexagone.osm.bz2 (2,6 millions de points, 250.000 /ways/), il faut moins
de 3 minutes pour faire la structure de données compact.

Il faut environ 1s45 pour la re-charger en mémoire à partir du
cache. Environ 1s pour trouver un point voisin de coordonnées (donc 2s
pour deux points). La recherche d'un chemin entre deux points est
quasi-instanée mais vu la longueur de mon exemple, c'est pas vraiment
significatif.

> Pour que cela soit effectivement utilisable, il faudra un peu plus de
> maturité d'OSM pour que certains manques ne produisent pas des choses
> aberrantes.

Oui. Il faudrait compter le nombre de composantes connexes du graphe des
routes. Idéalement il n'y en a qu'une. C'était dans mes idées des choses
à faire.

> Il serait intéressant de tester ton programme sur un
> itinéraire sur les Pays-bas ou l'Angleterre voire sur un trajet Paris
> intra-muros (je le ferrai quand je me pencherai dessus).

Là aussi, je voulais le faire. Pour l'instant je n'ai pas vraiment
testé.

> Je suis sûr que ton programme pourrait intéresser pas mal de personnes,
> en as tu parlé sur les listes de diffusion d'OSM (je ne suis pour
> l'instant inscrit que sur les listes francophones) ? Éventuellement crée
> une page wiki ?

Non, je ne l'ai pas fait. Je ne voulais pas vraiment faire une « annonce
» officielle vu l'état du projet. Mais s'il y a un intérêt...

> Si dans l'optique du « forget it », tu ne comptes pas le faire, tu me
> permets de m'en charger ?

Bien sûr, c'est du libre ! ;-) Mais bon, j'ai été clair sur mes
intentions.:-)

Si tu fais ces annonces, tu peux me garder en Cc: ?

> Pour info, pour ceux qui ne connaitraient pas, il existe ausi pyroute
> (http://wiki.openstreetmap.org/index.php/Pyroute) qui fait du routage
> directement depuis le fichier OSM et qui n'est, de fait, pas très
> performant.

J'ai même pas testé. Ce serait intéressant de faire la comparaison.

Amicalement,
d.

PS: Le programme devrait être relativement facile à compiler, il n'a
     besoin que du OCaml de base, avec les compilos optimisés/natifs
     (ocamlopt.opt).
-- 
David Mentré <dmentre at linux-france dot org> -- http://gulliver.eu.org/