shortest path in 2D matrix between two coordinate points

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

Answer 1

[KSSV]

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.

[Sohaib Bin Altaf]

Sir, the yellow ones are not paths, these are walls. As you said in (1) if any point has 1, it is crossing the wall. that's what i need to do... let's suppose if i have two points (5,5) and (45,45).. i just want the shortest path... the coordinate points that lie on the shortest path between (5,5) and (45,45)

[KSSV]

P0 = [5,5] ;
P1 = [45,45] ;

x = [P0(1) P1(1)] ;
y = [P0(2) P1(2)] ;

plot(x, y, 'b*-', 'LineWidth', 2, 'MarkerSize', 15);
coeffs = polyfit(x, y, 1);
% Get fitted values
X = linspace(min(x), max(x), 200);
Y = polyval(coeffs,X);
% Plot the fitted line
hold on;
plot(X, Y, 'r-', 'LineWidth', 3);

[Sohaib Bin Altaf]

I guess the 200 in linspace needs to be adjusted in such a way that it gives me the exact coordinates lying on this line connecting both points. So then i can get my required coordinates in X and Y. Can you help me what value will be suitable here.

[Image Analyst]

Have you solved this or not? Simply round X and Y to get the quantized values (indexes of the array):

rows = round(Y)
columns = round(X)

Remember, arrays are indexes NOT as array(x,y) but as array(y, x).

You could also use improfile() to get a profile of a line going across the span, then examine the returned profile to count how many intensity values represent walls.

[Sohaib Bin Altaf]

can you check the code below, it gives me the results, but why is the y-axis in reverse order, why it starts from top. i have used "axis xy" command but it doesn't help much... it sets the axis but the coordinates are still not plotted the way i want... i need it in the way i have shown in the picture attached to this comment... to fit into the system i am working on... May be imagesc command is the reason but i have tried surf aslo... looking forward for any help

clc

clear all

close all

M = zeros(50);

% draw lines

for x = [20,30]

    M(x,:) = 1;
end

for y = [13,25,37]

    for x = [1:20, 30:50]

        M(x,y) = 1;
    end
end

p1 = [15,25];

p2 = [33,45];

% 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;

imagesc(M)

fprintf('You passed %i walls', walls)

[Image Analyst]

images and graphs have the y direction go in opposite directions. If you want to graph things over an image you have to set the y direction of the graph to be reverse so that it matches the image.

axis ydirection, where ydirection is ij, places the origin at the upper left corner of the axes. The y values increase from top to bottom. The default for ydirection is xy, which places the origin at the lower left corner. The y values increase from bottom to top.

[Sohaib Bin Altaf]

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]

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

Answer 2

[Image Analyst]

Use bwdistgeodesic().

See Steve's 5 part blog on shortest paths.

http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/

[Sohaib Bin Altaf]

thanks a lot.

Answer 3

[Sohaib Bin Altaf]

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)