CODEWITHSUNDEEP
algorithmmatlabshortest-path
rauldg
rauldg

Reputation: 421

Shortest path between two points in a Grid (Matlab)

I'm trying to find the shortest path between two points in a grid with no obstacles and move in all directions (N NE E ES S SW W WN).

It seems to be a common task... Is this not implemented already in Matlab? When Matlab plots two points joined by a line ( plot(X,Y,'-') ) seems to internally do this calculation as I guess that the generated image is a grid too.

Example: From [1,1] to [3,6] one solution is [1,1; 2,2; 2,3; 2,4; 3,5; 3,6]

I have tried:

    dist_x = length(linspace(p1(1),p2(1), dist(p1(1),p2(1))+1));
    dist_y = length(linspace(p1(2),p2(2), dist(p1(2),p2(2))+1));
    num_points = max(dist_x, dist_y);
    x = round(linspace(p1(1),p2(1),num_points));
    y = round(linspace(p1(2),p2(2),num_points));

But I think that it returns more points than it should and maybe there is an implemented routine.

Thanks a lot

Upvotes: 3

Views: 2120

Answers (1)

rauldg
rauldg

Reputation: 421

The solution (given by J.F. Sebastian) is the Bresenham Line Algorithm.

Upvotes: 3

Related Questions