MATLAB Answers

0

shortest path between 2 set of coordinates

Elysi Cochin さんによって質問されました 2019 年 3 月 25 日
最新アクティビティ 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 件のコメント

Adam Danz
2019 年 3 月 25 日
Does this example also fit your rules?
ttt.png
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.
  1. 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.
  2. 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.

サインイン to comment.

タグ

2 件の回答

Adam Danz
回答者: Adam Danz
2019 年 3 月 25 日
編集済み: 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 件のコメント

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.

サインイン to comment.


回答者: sam mertens 2019 年 7 月 9 日

Hi, How to find the shortest path in the exact scenario?

  0 件のコメント

サインイン to comment.



Translated by