Finding Shortest Path Without Crossing Restricted Areas

I want to find the shortest path around the rectangles, for the obstacles I have the code which is shown below.

clc
clearvars
close all

obst = xlsread('engel');

xo = obst(:,1);     %X coordinate

yo = obst(:,2);     %Y coordinate

wo = obst(:,3);     %Width

ho = obst(:,4);     %Height

for i= 1:length(obst)
    rectangle('Position', [xo(i) yo(i) wo(i) ho(i)])
    i = i+1; 
end

The coordinates are attached as coordinates.xlsx, First column is X and the Second column is Y coordinates. It does not matter which point we start, but I want to find the shortest path without crossing the rectangles in the figure. I CANNOT move diagonally, I can only move in X&Y coordinates

Thanks.

Answer 1

[Athul Prakash]

I suggest implementing the Dijkstra's algorithm for this problem. An explanation is found here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Consider every co-ordinate you can move to as a node in a graph and each node is connected to 4 adjacent nodes, since we move in X&Y directions. While doing this, check whether a node falls within one of the rectangles - such nodes are not connected to from any other node.

Hope you got the idea.

Answer 2

[Image Analyst]

If you can qunatize your coordinates into a digital image, you can use bwdistgeodesic() like shown in Steve's blog series on shortest paths.

See how this path avoids the red letters: