clear;
close all;
taille_ecran = get(0,'ScreenSize');
L = taille_ecran(3);
H = taille_ecran(4);

% Lecture et affichage de l'image :
Im = imread('maldive.jpg');
%Im = Im(10:80,10:100,:);
figure('Name','Probleme du maitre-nageur','Position',[0.2*L,0,0.8*L,H]);
imagesc(Im);
axis equal;
axis off;
hold on;

% Vitesse de deplacement du maitre-nageur :
vitesse = double(rgb2gray(Im));
[nb_lignes,nb_colonnes] = size(vitesse);

% Les matrices I et J contiennent les numeros de lignes et de colonnes des pixels:
[J,I] = meshgrid(1:nb_colonnes,1:nb_lignes);

% Matrice d'adjacence M et matrice des poids P :
N = nb_lignes*nb_colonnes;
M = zeros(N);
P = zeros(N);
for m = 1:N
    i = I(m);
    j = J(m);
    for n = 1:m-1
        k = I(n);
        l = J(n);
        D = (l-j)^2+(k-i)^2; % D est la distance au carré
        if D <= 2
            M(m,n) = 1;
            M(n,m) = 1;
            P(m,n) = sqrt(D)/((vitesse(m)+vitesse(n))/2);
            P(n,m) = P(m,n);
        end
    end
end

% Positionnement du maitre-nageur :
disp('Positionnez le maitre-nageur en cliquant sur l''image !');
[j1,i1] = ginput(1);
j1 = round(j1);
i1 = round(i1);
plot(j1,i1,'or','MarkerFaceColor','r','MarkerSize',10,'LineWidth',4);
drawnow;

% Calcul des chemins optimaux par l'algorithme de Dijkstra :
origine = sub2ind(size(Im),i1,j1);
[couts,chemins] = dijkstra(M,P,origine);

while true
	% Positionnement du noye :
	disp('Positionnez le noye en cliquant sur l''image !');
	[j2,i2] = ginput(1);
	j2 = round(j2);
	i2 = round(i2);
	plot(j2,i2,'xr','MarkerSize',10,'LineWidth',4);

	% Affichage du chemin optimal :
	% A completer et decommenter
    sortie = sub2ind(size(Im),i2,j2);
	chemin_optimal = chemins{sortie};
	[i,j] = ind2sub(size(Im),chemin_optimal);
	plot(j,i,'-r','LineWidth',2);
end
