Contexte

Dans le cadre du développement de nos solutions de cartographie et de navigation indoor, nous utilisons des graphes de navigation pour calculer des itinéraires à l’intérieur de bâtiments, y compris sur plusieurs étages. Aujourd’hui, la création de ces graphes à partir de plans (fichiers geojson, taxonomie proche d’OpenStreetMap) est réalisée manuellement, ce qui est chronophage et source d’erreurs.

Objectif du stage

L’objectif du stage est de concevoir, développer et valider un algorithme permettant d’automatiser la génération de graphes linéaires de navigation à partir de plans de bâtiments (fichiers geojson). L’algorithme devra notamment :

- Extraire les éléments pertinents (couloirs, portes, escaliers, ascenseurs, etc.) à partir de la taxonomie fournie.

- Générer un graphe de navigation cohérent, multi-étage, prêt à être utilisé par nos outils de calcul d’itinéraires.

- Proposer une interface ou un outil facilitant la validation et la correction manuelle du graphe généré.

État de l’art (synthèse)

La génération automatique de graphes de navigation indoor est un sujet actif, avec plusieurs approches :

- Méthodes basées sur la géométrie : extraction des axes centraux (skeletonization, medial axis) des polygones représentant les espaces navigables (couloirs, halls, etc.), puis connexion des intersections, portes, escaliers, etc.

- Utilisation de la taxonomie OSM : certains outils (ex : IndoorOSM, Mapbox, Valhalla) exploitent la structure des données OSM pour générer des graphes, mais l’automatisation reste limitée pour les plans propriétaires ou non-standards.

- Approches par apprentissage automatique : plus récentes, elles visent à détecter automatiquement les chemins praticables à partir d’images ou de plans, mais nécessitent des jeux de données annotés.

- Outils existants : Il existe des outils open-source (par ex. osm2graph, IndoorOSM2Graph) mais peu sont adaptés à des plans custom ou multi-étage.

Défis principaux :

• Gestion des multi-étages (liaison entre niveaux, ascenseurs, escaliers)

• Prise en compte des contraintes d’accessibilité (PMR, etc.)

• Nettoyage et standardisation des données d’entrée

Missions

• Étudier l’état de l’art et les outils existants (open source, articles, etc.)

• Proposer une méthodologie adaptée à nos données et besoins

• Développer un prototype d’algorithme (langage au choix, Python ou TypeScript recommandés)

• Tester et valider l’algorithme sur des cas réels

• Documenter le travail et proposer des pistes d’amélioration

Profil recherché

• Étudiant(e) en géomatique, informatique, ou domaine connexe (M1/M2, préférence M2)

• À l’aise avec la manipulation de données géographiques (GeoJSON, SIG, etc.)

• Bon niveau en informatique (algorithmique, manipulation de graphes, Python ou équivalent)

• À l’aise avec la géométrie dans l’espace, rigoureux(se), sens pratique

• Intérêt pour la cartographie, la navigation indoor, l’algorithmique

Compétences appréciées

• Connaissance d’OpenStreetMap et de sa taxonomie

• Expérience avec des librairies de traitement géométrique (Shapely, NetworkX, QGIS, etc.)

• Notions sur les graphes et les algorithmes de plus court chemin

Modalités

• Stage de 4 à 6 mois, gratification selon profil

• Lieu : Montpellier avec télétravail hybride possible

• Rémunération : en fonction du profil du candidat

• Encadrement par une équipe experte en cartographie et navigation