shortest path between 2 set of coordinates
14 次查看(过去 30 天)
显示 更早的评论
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
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
编辑: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.
更多回答(1 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Line Plots 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!