shortest path between 2 set of coordinates

Question

Elysi Cochin 2019-3-25

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/452196-shortest-path-between-2-set-of-coordinates

回答： sam mertens 2019-7-9

I have 2 set of coordinates --> set_1 and destination

If i select a cordinate in set_1 and destination (eg: from set_1 [10.5, 4.5] and from destination [2.5, 8.5]

I need to reach destination coordinates [2.5, 8.5] only through the coordinates in set_1 , also through the shortest path

I need to show the movement from [10.5, 4.5] to [2.5, 8.5] in graph

set_1 = 
[7.5,6.5;7.5,7.5;4.5,8.5;7.5,6.5;8.5,6.5;9.5,6.5;9.5,5.5;8.5,1.5;7.5,4.5;6.5,4.5;3.5,5.5;2.5,6.5;10.5,4.5]

destination =
[7.5,9.5;8.5,10.5;2.5,8.5;8.5,10.5;6.5,9.5;6.5,2.5;5.5,3.5;5.5,3.5;1.5,1.5;3.5,3.5]

9 个评论
显示 7更早的评论隐藏 7更早的评论

Adam Danz 2019-3-25

I don't have time to fiddle with this interesting question now but here's what the solution will likely involve. You can get started with it and if no one else provides a solution and you get stuck, follow up here with questions.

use pdist() to calculate the distance between all points along the blue line and the target red-point. Then use min() to determine which blue point is closest to the red point.
Now you have the index value of the blue point where you're starting and the index value of the blue point where you're ending - all points in between will be your path of least resistance. Then you just need to add the final red point coordinate.

Adam Danz 2019-3-25

I continued in the answer section below.

请先登录，再进行评论。

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

Answer 1

Adam Danz 2019-3-25

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/452196-shortest-path-between-2-set-of-coordinates#answer_367290

编辑：Adam Danz 2019-3-25

(continuing from comments under the question)

set_1 = [7.5,6.5;7.5,7.5;4.5,8.5;7.5,6.5;8.5,6.5;9.5,6.5;9.5,5.5;8.5,1.5;7.5,4.5;6.5,4.5;3.5,5.5;2.5,6.5;10.5,4.5]; 
destination = [7.5,9.5;8.5,10.5;2.5,8.5;8.5,10.5;6.5,9.5;6.5,2.5;5.5,3.5;5.5,3.5;1.5,1.5;3.5,3.5]; 
% select starting index of set_1
startIdx = 8;             % set_1(startIdx,:)
% Select stop coordinate
des = [2.5 8.5];            
dist = sqrt(sum((repmat(des(1,:), size(set_1,1), 1) - set_1).^2, 2));
[~, minDistIdx] = min(dist); 
% Select all indices between
pathIdx = min([startIdx, minDistIdx]) : max([startIdx, minDistIdx]); 
% Full path coordinates
if minDistIdx < startIdx
    fullPath = [des; set_1(pathIdx,:)];
else
    fullPath = [set_1(pathIdx,:); des];
end
% Plot results
plot(set_1(:,1), set_1(:,2), 'b-o')                                 % set_1 line
hold on
plot(set_1(startIdx,1),set_1(startIdx,2), 'bx', 'LineWidth', 3, 'MarkerSize', 9)      % start coordinate
plot(destination(:,1), destination(:,2), 'r-o')                     % destination line
plot(des(1),des(2), 'rx', 'LineWidth', 3, 'MarkerSize', 9)        % final coordinate
plot(fullPath(:,1), fullPath(:,2), '-', 'LineWidth', 5, 'color', [1 1 0 .5])

Use flipud(fullPath) if you need the path coordinates to be in a certain order.

This should be stress tested. There might be combinations that break the code and require circular wrapping.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Adam Danz 2019-3-25

Note that the path in my example was chosen only because the final blue marker is closest to the red target marker. You can also imagine a path going leftward instead of rightward and that path might actually be shorter (??) but the final blue marker on that path is a bit further from the one chosen.

So this algorithm doesn't necessarily find the shortest path. It just finds the closest exit point to the target point.

请先登录，再进行评论。