shortest path in 2D matrix between two coordinate points

6 views (last 30 days)
As in the attached image, i have a 2D matrix of 50 by 50. The matrix contains zeros (blue) and ones(yellow). Imagine it as a floor, The yellow or ones mean the walls. In this whole matrix a transmitter(T) and receiver (R) can be placed anywhere and i need to know how many walls the signal penetrates when it reaches from T to R. Lets suppose the T is at (x,y) and R is at (i,j). I take the shortest path between T and R. If i get the shortest path i can calculate the number of 1s in the path and that will be the number of walls which i need.
Can anyone help in this regard.. Thank you

Accepted Answer

KSSV
KSSV on 5 Jul 2018
YOu have the following options to check:
1. Do interpolation of the points along the path, if any point has 1, it is crossing the wall. Note that, for this you need to generate lot many points along the path so that a point lies on the yellow path.
2. Generate the points along the path, get the nearest neigboours to those points and see, any point is from yellow path.
3. Find the intersection between shortest paths and yellow paths. This would be better a solution.
  8 Comments
Sohaib Bin Altaf
Sohaib Bin Altaf on 9 Jul 2018
Yes you are right, "axis xy" command inverts the y-axis as i require but the coordinate system still does not represents the value the way i need. when i use "surf" instead of imagesc the axis are fine but the coordinate system plots it differently, like (x,y) is plotted as (y,x).
Even if i don't plot the matrix into figure, still the results are similar as if i plot an image.
Sohaib Bin Altaf
Sohaib Bin Altaf on 9 Jul 2018
you can see in the attached image i have entered as [15,10] but it is plotted as [10,15]. Please check the figure attached to this comment

Sign in to comment.

More Answers (2)

Image Analyst
Image Analyst on 5 Jul 2018
Use bwdistgeodesic().
See Steve's 5 part blog on shortest paths.

Sohaib Bin Altaf
Sohaib Bin Altaf on 10 Jul 2018
This thing worked for me:
clc
clear all
close all
M = zeros(50);
% draw lines
for y = [20,30]
M(:,y) = 1;
end
for x = [13,25,37]
for y = [1:20, 30:50]
M(x,y) = 1;
end
end
p1 = [12,48];
p2 = [39,5];
% get direction
d = p1-p2;
d = d/max(abs(d)); % limit to 1 px step size
steps = 0:1:max(abs(p2-p1));
for i=length(p1):-1:1
p_line(:,i) = round(p2(i) + steps.*d(i));
end
idx = sub2ind(size(M), p_line(:,1), p_line(:,2));
walls = sum(M(idx));
M(idx) = 2;
M = flipud(M)
M = rot90(M,-1)
imagesc(M)
set(gca,'YDir','normal')
set(gca,'XDir','normal')
fprintf('You passed %i walls', walls)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!