Coordinates of the shortest path between two points in a 2D grid

30 次查看（过去 30 天）
Tejas
Tejas 2020-7-13
移动：Matt J 2023-12-18
I have a square grid of a specific size, say 50 x 50. There are two points, a source, say (1,1), and a destination, say (26,35). Is there a function I can utilize to get a column vector with the coordinates of the shortest path that an agent might take going from the source to the destination. The agent can travel horizontally, vertically, and diagonally.
One of the ways I can see of doing this would be to create a graph from the grid and use shortestpath function. However, the node number would have to be related to the coordinate with a function, and ideally I would like to avoid going into that complication. Any help is appreciated.
  2 个评论
Matt J
Matt J 2020-7-13
However, the node number would have to be related to the coordinate with a function.
I don't see why that would be true. Why not a look-up table instead?
Tejas
Tejas 2020-7-13
I'm not sure how I could describe the connections between each pair of points in the grid to make a graph of it. As far as I understand it, for each point, I'd have to check whether its neighboring points are within the grid (all permutations of x+1 and y+1), and if they are, assign the corresponding node as being connected. In your opinion, would this be easier to implement than trying to find the shortest path using grid coordinates?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2020-7-13
编辑：Matt J 2020-7-13
I'm not sure how I could describe the connections between each pair of points in the grid to make a graph of it.
Creating the graph for a given set of grid dimensions M,N is quite easy (example below).
M=10;N=10; %grid dimensions
[I,J]=ndgrid(1:M,1:N);
IJ=[I(:),J(:)];
D=pdist2(IJ,IJ);
A=(D>=0.001 & D<=sqrt(2)*1.001).*D; %adjacency matrix
G=graph(A);
  8 个评论
显示 6更早的评论
Tejas
Tejas 2020-10-3
@Image Analyst, Steve's blog is far too difficult for me to include in my code. I need to understand what exactly is happening and be able to explain it to someone who will be using the simulation as well. Since Matt's code already works for me and is something I understand, I'd be happier with a more efficient manipulation of it than a completely different route. I tried some things and failed, which is why I asked here.
Matt J
Matt J 2020-10-3
Steve's blog is far too difficult for me to include in my code. I need to understand what exactly is happening
Well, I'm not sure what the difference is between what Steve blog's proposes and what Walter proposes, but the idea of using bwdistgeodesic() should be conceptually quite simple. You are framing the path traversal as the movement between two points in a binary image while stepping only on the white pixels. The main challenge is setting up an appropriate image (I showed how to do that here) and also locating a subset of the pixels which correspond to your points.

请先登录，再进行评论。

更多回答（2 个）

Walter Roberson
Walter Roberson 2020-7-13
编辑：Walter Roberson 2020-7-13
For the case where each location has the same "cost" to move over, and not all locations are passible, then:
https://www.mathworks.com/help/images/ref/bwdistgeodesic.html
Create a binary grid with 1 for the grid points that can be travelled through, 0 for impassible.
Call bwdistgeodesic passing in the binary image and the row and the column of the destination.
Now for any given source point, examine the corresponding point in the transform. If it is inf then you cannot reach the destination.
Otherwise repeat: move in the direction that decreases the count the most; if there are multiple places with the same count then there are multiple shortest path and you can choose any of them. When you get to 0 you have arrived.
The same transform matrix can be used for multiple source points to the same destination.
If you have the opposite situation, one source point and multiple destinations to investigate, just reverse source and destination for the above algorithm.
If all locations are passible (within the grid) and all of them have the same cost, then there are other algorithms that are much more simple.
  3 个评论
显示 1更早的评论
Matt J
Matt J 2020-7-13
编辑：Matt J 2020-7-13
For now though, my simulation is restricted to a plane with equal cost of each step and no obstacles.
That's not entirely true. Because your path planning is constrained to purely horizontal, vertical, and diagonal steps, it is equivalent to maneuvering through an image like that below, where the black regions are obstacles and the start/end points are the red sub-lattice points. Bear in mind also that my solution, as currently code, treats diagonal paths as having sqrt(2) times higher cost than vertical or horizontal steps. You can adjust that, if you wish, of course.
N=11;
BW=eye(N)+fliplr(eye(N))>0;
BW(1,:)=1; BW(:,1)=1;
BW(end,:)=[];BW(:,end)=[];
BW=repmat(BW,5,5);
BW(end+1,:)=1; BW(:,end+1)=1;
imagesc(BW); colormap(gray(256))
[I,J]=ndgrid(1:N-1:size(BW,1));
hold on; scatter(I(:),J(:),'ro','MarkerFaceColor','r','SizeData',60); hold off
George Abrahams
George Abrahams 2023-12-18
移动：Matt J 2023-12-18
I'll expand upon @Walter Roberson's answer, as I suspect people are arriving at this post with that in mind.
If there are obstacles and distance is all that you care about, bwdistgeodesic is probably the most efficient solution.
Your pixels might be weighted depending on some preference variable, however. For example, you might want to find the shortest walking path between 2 points on a map while minimizing increases in elevation (going up hills). Or, you might want to follow the veins in a retinal scan by following the path of lowest intensity, like in the figure below.
In this case, you'll need an undirected graph with an algorithm like Dijkstra's, implemented by the built-in shortestpath.
As you have figured, you'll need to therefore find someway of converting the image into a graph, with edges between connected pixels being assigned the relevent weights. For this, you could use my bwgraph function on File Exchange, along with the NodeWeights name-value argument. I posted an example of that here.

请先登录，再进行评论。

Image Analyst
Image Analyst 2020-7-13
See Steve's 5-part blog for a thorough discussion.
http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2020a

Community Treasure Hunt

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

Start Hunting!

Translated by