shortest path between 2 set of coordinates

15 views (last 30 days)
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 Comments
Adam Danz
Adam Danz on 25 Mar 2019
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
Adam Danz on 25 Mar 2019
I continued in the answer section below.

Sign in to comment.

Accepted Answer

Adam Danz
Adam Danz on 25 Mar 2019
Edited: Adam Danz on 25 Mar 2019
(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 Comment
Adam Danz
Adam Danz on 25 Mar 2019
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.

Sign in to comment.

More Answers (1)

sam mertens
sam mertens on 9 Jul 2019
Hi, How to find the shortest path in the exact scenario?

Categories

Find more on Line Plots in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!