# shortest path between 2 set of coordinates

71 ビュー (過去 30 日間)
Elysi Cochin 2019 年 3 月 25 日

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?
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.

### 採用された回答

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.

### その他の回答 (1 件)

sam mertens 2019 年 7 月 9 日
Hi, How to find the shortest path in the exact scenario?

#### 0 件のコメント

サインイン to comment.

サインイン してこの質問に回答します。

Translated by