Find path through logical matrix (only walking right or down)

2 vues (au cours des 30 derniers jours)
Paul Muster
Paul Muster le 26 Mai 2023
Commenté : Jon le 30 Mai 2023
Hello,
I have given a logical matrix, e.g.
1 1 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1
I want to check if I can walk from the top left corner to the bottom right corner. It shall only be possible to walk "forward" meaning I can only go to the right, bottom, or bottom right diagonal. Permitted fields are marked with the value 1.
I have tried it with "bwlabel" but there are only symmetric masks possible. What I would need is the mask
0 0 0
0 1 1
0 1 1
Has anyone an idea how I can implement that, mostly as computationally efficient as possible.
Thank you very much in advance.
  3 commentaires
DGM
DGM le 26 Mai 2023
I don't see how connectivity alone can solve the problem. Using conv2() or bwlookup() will tell you whether you can make the next step from the perspective of a single pixel, but they won't tell you if you can reach any given pixel from any other pixel.
I'm inclined to think there is an obvious solution that I'm not seeing. (other than just walking through the image)

Connectez-vous pour commenter.

Réponses (1)

Jon
Jon le 26 Mai 2023
It seems natural to think of this as a graph traversal question, where the nodes in a directed graph are the locations in the matrix where there are nonzero (true) elements. Maybe a simpler way to solve this, but here's how you could do it using a directed graph
% Define matrix to be checked
M = logical([...
1 1 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1])
M = 4×6 logical array
1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1
[m,n] = size(M);
% Augment M with additional row and column of zeros to make bookkeeping
% easier
Ma = [M zeros(m,1);zeros(1,n+1)];
% Make corresponding adjacency matrix
%
numNodes = sum(Ma(:));
idx = find(Ma(:)); % linear indices of non-zero elements
[ma,na] = size(Ma);
A = zeros(ma*na); % preallocate adjacency matrix
for k = 1:numNodes
% get row and column indices corresponding to this node
[i,j] = ind2sub([ma,na],idx(k));
% add possible connections to neighbors
A(idx(k),sub2ind([ma,na],i,j+1)) = 1;
A(idx(k),sub2ind([ma,na],i+1,j+1)) = 1;
A(idx(k),sub2ind([ma,na],i+1,j)) = 1;
end
% Remove non-existent nodes from adjacency matrix
idl = logical(Ma(:));
A = A(idl,idl);
% Make directed graph
G = digraph(A);
% Find out if first and last node are connected
connected = ~isempty(shortestpath(G,1,numNodes))
connected = logical
1
  2 commentaires
Jon
Jon le 26 Mai 2023
Modifié(e) : Jon le 26 Mai 2023
You can also do this without loops
% Define matrix to be checked
M = logical([...
1 1 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1]);
[m,n] = size(M);
% Augment M with additional row and column of zeros to make bookkeeping
% easier
Ma = [M zeros(m,1);zeros(1,n+1)];
% Make corresponding adjacency matrix
numNodes = sum(Ma(:));
idx = find(Ma(:)); % linear indices of non-zero elements
szMa = size(Ma);
szA = [szMa(1)*szMa(2),szMa(1)*szMa(2)]; % size of adjacency matrix
A = zeros(szA); % preallocate adjacency matrix
% Add possible connection to all the neighbors (below, right, below-diag)
% some of these connections may be to nodes that are not in the graph
[i,j] = ind2sub(szMa,idx);
A(sub2ind(szA,idx,sub2ind(szMa,i+1,j))) = 1; % below
A(sub2ind(szA,idx,sub2ind(szMa,i,j+1))) = 1; % right
A(sub2ind(szA,idx,sub2ind(szMa,i+1,j+1))) = 1; % diagonal
% Remove non-existent nodes from adjacency matrix
idl = logical(Ma(:));
A = A(idl,idl);
% Make directed graph
G = digraph(A);
% Find out if first and last node are connected
connected = ~isempty(shortestpath(G,1,numNodes))
connected = logical
1
Jon
Jon le 30 Mai 2023
Were you able to give this a try?

Connectez-vous pour commenter.

Produits


Version

R2023a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by