% *** ---------------------------------------------------------------------------------------- *** %
% ***| Funcion que crea el Mapa de Coste Acumulado(MCA) a partir del Mapa de Coste Local(MCL)| *** %      
% ***| y define la matriz 'flechas' que contiene el camino minimo desde un punto al resto    | *** %
% *** ---------------------------------------------------------------------------------------- *** %

function flechas = livewire(mapa_coste_local,semilla)

[filas,columnas] = size(mapa_coste_local);                

flechas = zeros(filas,columnas,2);                          % Posiciones de los pixeles que recorren el camino minimo
expanded = zeros(filas,columnas);                           % Matriz donde se marcan a '1' los pixeles ya Expandidos
active = zeros(filas,columnas);                             % Matriz donde se marcan a '1' los pixeles que forman parte de la Lista Activa
mapa_coste_acumulado = inf*ones(filas,columnas);            % Mapa de Coste Acumulado desde el pixel 'semilla' al resto

mapa_coste_acumulado(semilla(1),semilla(2)) = 0;
expanded(semilla(1),semilla(2)) = 1;

vecinos = ver_vecinos(semilla,filas,columnas);              % Vector que define los 8-vecinos del pixel 'semilla'

for v = vecinos
     
    active(semilla(1)+v(1),semilla(2)+v(2)) = 1 ;               % Se marcan los pixeles candidatos a expandirse (8-vecinos del expandido)
    
    mapa_coste_acumulado(semilla(1)+v(1),semilla(2)+v(2)) = ...
        sqrt(abs(v(1))+abs(v(2)))*mapa_coste_local{semilla(1),semilla(2)}(v(1)+2,v(2)+2);
    
    flechas(semilla(1)+v(1),semilla(2)+v(2),1) = semilla(1);    % Se coge la posicion del pixel que sigue al actual
    flechas(semilla(1)+v(1),semilla(2)+v(2),2) = semilla(2);
    
end

% Calculando el Mapa de Coste Acumulado para todos los pixeles no INF
while sum(sum(expanded)) < filas*columnas
    
    q = minimo(mapa_coste_acumulado,active);                % Busca el siguiente pixel a expandir (minimo de la Lista Activa)
    vecinos = ver_vecinos(q,filas,columnas);                % Vector que define los 8-vecinos del pixel q
    
    expanded(q(1),q(2)) = 1;                                % Se marca como pixel Expandido
    active(q(1),q(2)) = 0;                                  % Se quita de la Lista Activa

    for v = vecinos
        
        if expanded(q(1)+v(1),q(2)+v(2)) == 0                   % pixeles no Expandidos aun
           
            % MCA(q) = min{MCA(q)antiguo , MCL(p,q)escalado + MCA(p)}    (Actualizando el MCA)
            if mapa_coste_acumulado(q(1)+v(1),q(2)+v(2)) > ...
                    sqrt(abs(v(1))+abs(v(2)))*mapa_coste_local{q(1),q(2)}(v(1)+2,v(2)+2) + mapa_coste_acumulado(q(1),q(2))
                              
                mapa_coste_acumulado(q(1)+v(1),q(2)+v(2)) = ...
                    sqrt(abs(v(1))+abs(v(2)))*mapa_coste_local{q(1),q(2)}(v(1)+2,v(2)+2) + mapa_coste_acumulado(q(1),q(2));
            
                active(q(1)+v(1),q(2)+v(2)) = 1;                % Se marcan los pixeles candidatos a expandirse (8-vecinos del expandido no expandidos aun)
                
                flechas(q(1)+v(1),q(2)+v(2),1) = q(1);          % Se coge la posicion del pixel que sigue al actual
                flechas(q(1)+v(1),q(2)+v(2),2) = q(2);
                
            end
        end
        
    end
end
