projet info calcul de chemin minimal par géodésie

bonjour à tous,

J'ai un gros problème pour mon projet d'info que je dois rendre ce jeudi et soutenir vendredi prochain, je suis complètement perdu; et l'on n'a pas beaucoup avancé.

Mon projet doit se traiter uniquement avec des classes. Il consiste à importer une image sous format ppm, où l'on a entre autres, un pixel rouge (point de départ), un pixel bleu (point d'arrivée) et au milieu des murs en noir. Le but est en s'intéressant au voisinage de chacun des pixels (on part de l'arrivée), calculer les distances minimales par rapport au pixel d'arrivée jusqu'à arriver au pixel rouge. On s'intéresse donc aux voisinages V4 (pixels en haut, en bas, à droite, à gauche) du pixel considéré, et V8 (ceux en diagonales plus ceux de V4). Les pixels de V4 sont à une distance 1 du pixel considéré et les pixels de V8 n'appartenant pas à V4 sont à sqrt(2) du pixel considéré.

Mon problème se situe dans l'établissement dans une carte de distances minimales et dans le tracé du chemin minimal reliant A (départ) à B(arrivée). Il faut que j'utilise une file de priorité pour stocker les distances visiblement, et je ne comprends toujours pas ce que c'est (malgré le tuto sur ce site).

Etant donné la complexité du projet, j'ai pas mal de classes, et je ne peux donc pas poster tout leur contenu sinon mon post serait hyper long. J'ai juste 3 classes avec leur .cpp qui me sont fournies, image.hpp qui crée une image à partir d'un vector de color. La classe color qui permet de créer un pixel (défini comme 3 chars non signés r, g et b) et une classe excpetion_cpe qui traite les exceptions lancées par la classe image. On m'a aussi fournit le main et le makefile (d'ailleurs je ne vois pas comment le modifier vu que j'ai rajouté des classes).

Est ce que quelqu'un de la communauté serait prêt à m'aider par message perso, vu que le contenu du programme est trop lourd pour être posté?

Merci d'avance

J.Phi;)

Bonjour,

En fait ton problème n'est pas de trouver le plus court chemin par géodésique (en gros tu ne considères pas la courbure de la terre, sinon il faudrait que tu calcules des intégrales elliptiques). Ton problème peut être résolu par un Dijkstra ou un A*, je te conseilles de partir sur ce dernier à l'aide du code récemment partagé: Algorithme A*

merci de votre réponse, j'ai lu l'algo A*, il est très intéressant mais je vois surtout de la programmation procédurale, je ne vois pas comment transformer cette algo en version orientée objet avec des classes.:?

Amusant le pléonasme dans le titre. Parce qu'une géodésique n'est rien d'autre qu'un synonyme de "plus court chemin"...

Ensuite, je ne pense pas que l'on puisse parler d'algorithme orienté objet. Je dirais que pour programmer, il faut 4 choses (je ne les classe pas par importance) :
- La connaissance du domaine d'application du code
- La connaissance de la syntaxe d'un langage de programmation
- La connaissance des algorithmes permettant d'obtenir les résultats
- La connaissance des moyens d'organiser le code pour réussir à en garder la maîtrise dès qu'il fait plus de 7 lignes.

La programmation orienté objet est clairement dans la quatrième catégorie, alors qu'un algorithme de plus court chemin est dans la troisième. Ça ne veut pas dire que c'est incompatible, juste que c'est orthogonal, et que des questions comme "transformer cette algo en version orientée objet" n'ont pas trop de sens.

oui mais par exemple tu peux avoir des algos qui appartiennent à la 3ème catégorie mais qui peuvent être codés de manière procédurale (sans classe mais avec des structures et beaucoup de fonctions en un seul programme).

Ce que je voulais dire par "version orienté objet" même si mon vocabulaire est mal choisi, c'est que l'algo de la 3ème catégorie que tu proposes, si tu le sépares en plusieurs classes qui ont des relations caractéristiques entre elles, tu quittes le monde du procédural (que je juges plus simple) pour celui de la poo.

Et c'est ce que je dois faire, je ne dois pas le traiter de manière procédurale.