modélisation numérique d'un lieu public

Bonjour à tous,
je travaille actuellement sur un projet (étudiant) qui consiste à créer un mini gps pour permettre aux personnes malvoyantes de se déplacer dans un lieu public.
Ce que nous arrivons pas à trouver, c'est comment réussir à modéliser le plan du lieu (ex: plan d'une gare) sous forme de matrice numérique pour pouvoir ensuite effectuer toutes sortes d'opérations (ex: déplacement, obstacle...) en programmation (matlab, C...)
Merci de votre aide
Cordialement
mickael

Il faudrait ne repérer que les faces. Je pense que tu devrais t'inspirer de l'affichage 3D classique pour modéliser l'environnement.

Le chemin le plus court, c'est l'algorithme de Dijkstra :
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Bon, je croyais que tu faisais un univers en 3D, c'est vrai qu'avec un GPS c'est pas terrible
Alors, le mieux c'est de prendre les données d'entrée en continue, c'est à dire en définissant des systèmes d'inéquations pour les obstacles. Ensuite avec une définition de taille minimale, tu crées ta matrice et tu applique ton algo Dijkstra.
Comme ça, une fois terminé, tu peux rendre plus précis ta matrice ou au contraire, chercher quelque chose qui ne soit pas trop long à calculer.

Bon pour la modélisation de départ d'un obstacle, le mieux est de prendre un polygone convexe. Donc tu ne mémorise que les coordonnées des sommets du polygone en gardant le même sens (trigonométrique par exemple).
Quand tu découpe ton univers en matrice, c'est comme si tu faisais un quadrillage où chaque carré représente un point de la matrice.
Ici, je suppose que les obstacles sont largement plus gros qu'un petit carré (j'expliquerais après).
Donc on a notre matrice, et dedans, il faut marquer les cases inaccessibles , c'est à dire qu'il faut indiquer toutes les cases touchant un obstacle.
Dans l'environnement, une petite case est carrée, donc caractérisé par ses 4 points sommets.
Si 1 des 4 sommets est dans un des polygones des obstacle, alors il faut considérer ce point comme inaccessible. Je reviens sur le fait que je considère les cases comme petites devant les obstacles, car sinon, on pourrait avoir des points des sommets hors de l'obstacle, alors qu'il est en collision avec l'obstacle (ce n'est pas impossible à résoudre, mais c'est moins optimisé).
Voilà, là tu obtiens la matrice des cases accessibles et inaccessibles.
Maintenant, c'est simplement Dijkstra dont le changement d'état est le passage d'une case à une autre consécutive.
Un dernier point pour conserver les distances. Pour le graphe de l'algo, les arcs pour aller à gauche, à droite, en haut ou en bas peuvent être mis à 1, et les arcs pour se déplacer en diagonale, doivent être de Racine(2). Si tu ne fais pas ça, ton environnement sera étiré sur les diagonales vis-à-vis de ton algorithme.

4 murs, ce sont 4 rectangles.
Le sens trigonométrique c'est le sens inverse des aiguilles d'une montre.
Un polygone est définit, par exemple, par 4 points A,B,C et D.
Tu prends M un point, et tu veux tester si M est dans le polygone ou pas.
Pour faire ça, c'est comme le test de visibilité dans un moteur 3D, sauf que là c'est en 2D.
Pour chaque faces ([AB], [BC], [CD], [DA]), tu calcules le vecteur normal N->. En 2D, c'est juste une rotation de Pi/2 du vecteur de la face (par exemple, rotation de Pi/2 du vecteur AB-> ). Pas besoin de le normaliser, car on se contente de calculer un produit scalaire.
Si on calcule le produit scalaire (N->, MA-> ) pour le segment [AB], en regardant le signe du produit scalaire, on sait si l'on est d'un côté ou de l'autre du segment. Du coup, si on est du même côté pour tous les segments du polygone convexe fermé, c'est qu'on est à l'intérieur.
Voilà, pour choisir M, c'est un sommet de la petite case de la grille qui découpe l'environnement. Donc, il faut appliquer l'algo 4 fois (4 M différents) pour revenir à ce que je disais avant : il suffit qu'un point soit dans un polygone, pour considérer toute la case comme inaccessibles.

PS: sans schéma c'est pas évident à expliquer. Je te suggères de chercher les algorithmes de faces cachés en 3D pour comprendre et simplifier avec la 2D.