shortest path between 2 set of coordinates

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]

[Adam Danz]

Are you trying to draw a line between two chosen coordinates?

[Elysi Cochin]

yes draw a line but the path should be from cordinates in set_1

[Adam Danz]

Still not clear. The figure below shows your set_1 data in blue (assuming col 1 is x and col 2 is y) and your destination data in red (same x,y assumption). From what I understand, you want to choose any coordinate along the blue line and any coordinate along the red line and connect them with a new straight line. Is that correct?

[Image Analyst]

Elysi you say "I need to reach destination coordinates [2.5, 8.5] only through the coordinates in set_1" but what if the destination coordinate (a point on Adam's red line) is not on the set_1 (blue) line? It can't be done in that case. In fact you can see that your (2.5, 8.5) point is not even in your set_1 at all.

[Adam Danz]

I see. So you want the choose a coordinate that belongs to the blue line and travel along the blue line until you're as close as possible to the target coordinate along the red line.

[Elysi Cochin]

@Adam Danz

Yes sir, thats what i want

[Adam Danz]

Does this example also fit your rules?

[Adam Danz]

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]

I continued in the answer section below.

Answer 1

[Adam Danz]

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

[Adam Danz]

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.

Answer 2

[sam mertens]

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