Distance between distance between [ x_0,y_00] to [x_10,y_100] coordinates in Cell array

1 次查看（过去 30 天）
rest12
rest12 2018-9-19
回答： Guillaume 2018-9-19
I have a cell array having [x,y] coordinates as shown below.
{{[ x_0,y_00]},
{[ x_1,y_10],[ x_1,y_11],[ x_1,y_12],[ x_1,y_13],[ x_1,y_14],[ x_1,y_15]},
{[ x_2,y_20],[ x_2,y_21],[ x_2,y_22],[ x_2,y_23],[ x_2,y_24],[ x_2,y_25]},
{[ x_3,y_30],[ x_3,y_31],[ x_3,y_32],[ x_3,y_33],[ x_3,y_34],[ x_3,y_35]},
{[ x_4,y_40],[ x_4,y_41],[ x_4,y_42],[ x_4,y_43],[ x_4,y_44],[ x_4,y_45]},
{[ x_5,y_50],[ x_5,y_51],[ x_5,y_52],[ x_5,y_53],[ x_5,y_54],[ x_5,y_55]},
{[ x_6,y_60],[ x_6,y_61],[ x_6,y_62],[ x_6,y_63],[ x_6,y_64],[ x_6,y_65]},
{[ x_7,y_70],[ x_7,y_71],[ x_7,y_72],[ x_7,y_73],[ x_7,y_74],[ x_7,y_75]},
{[ x_8,y_80],[ x_8,y_81],[ x_8,y_82],[ x_8,y_83],[ x_8,y_84],[ x_8,y_85]},
{[ x_9,y_90],[ x_9,y_91],[ x_9,y_92],[ x_9,y_93],[ x_9,y_94],[ x_9,y_95]},
{[x_10,y_100]}}
The values of y coordinates are random. How can I find the minimum distance between [ x_0,y_00] to [x_10,y_100]. distance? Can someone please guide me.
  2 个评论
Guillaume
Guillaume 2018-9-19
The question is really badly explained. If I understand correctly, your cell array represent a directly acyclic graph where the points on each layer of your upper level cell array is connected to each point on the next layer, and you want to find the shortest path going from the 1st cell to the last cell using only one point from each intermediate cell array.
Is that correct?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Guillaume
Guillaume 2018-9-19
I would build a digraph from your cell array, where each node is a point and the edges are weighted by the distance between the points. The difficult bit will be to build the graph but once that is done, the shortest path is trivially found using shortestpath.
%demo cell array, x goes from 0 to 10, y is random between -10 and 10
c = [{{[0, 0]}}; arrayfun(@(x) num2cell([repmat(x, 5, 1), sort(randperm(21, 5))'-11], 2)', (1:9)', 'UniformOutput', false); {{[10, 0]}}]
%build graph:
g = digraph; %empty graph to start with
vartnodenames = {'ID', 'X', 'Y'}; %variable names for node table
%add 1st layer as a node
g = g.addnode(table(1, c{1}{1}(1), c{1}{1}(2), 'VariableNames', vartnodenames));
lastlayerids = 1; %will be used in a loop to build edges
lastnode = 1; %node index last inserted
lastcoordinates = c{1}{1}; %coordinates of points of previous layer in the loop
%add other layers
for layer = 2:numel(c)
newlayerids = lastnode + (1:numel(c{layer})); %ids of nodes in new layer
newcoordinates = vertcat(c{layer}{:}); %coordinate of nodes in new layer
g = g.addnode(table(newlayerids', newcoordinates(:, 1), newcoordinates(:, 2), 'VariableNames', vartnodenames));
[s, e] = ndgrid(lastlayerids, newlayerids); %cartesian product of nodes from previous layer and nodes from new layer => edges between the two layers
distances = hypot(lastcoordinates(:, 1) - newcoordinates(:, 1)', lastcoordinates(:, 2) - newcoordinates(:, 2)'); %weigth for edges = distance between layer nodes
g = g.addedge(s, e, distances);
lastnode = lastnode + numel(c{layer}); %update for next layer
lastlayerids = newlayerids;
lastcoordinates = newcoordinates;
end
%find shortest path between 1st and last node
[nodes, distance, edges] = shortestpath(g, 1, lastnode);
%plot
h = plot(g, 'XData', g.Nodes.X, 'YData', g.Nodes.Y);
highlight(h, nodes);
highlight(h, 'Edges', edges);

更多回答（1 个）

KSSV
KSSV 2018-9-19
A = {{rand(2,1)},{rand(2,1)},{rand(2,1)},{rand(2,1)},{rand(2,1)}} ;
A = cell2mat([A{:}]) ;
A = A';
d = pdist2(A(1,:),A) ;
[val,idx] = max(d) ;
iwant = A(idx,:)
  1 个评论
rest12
rest12 2018-9-19
编辑：rest12 2018-9-19
thanks for your reply. But I think maybe my question is not very clear. Let me try to explain to you here. I need to find the minimum total distance between [ x_0,y_00] to [x_10,y_100]. Since there are different coordinates between [ x_0,y_00] to [x_10,y_100] the distance value could be different. So I need to find the minimum distance path using these points.
For example. the minimum distance path could be:
[ x_0,y_00] --> [ x_1,y_10] --> [ x_2,y_22] --> [ x_3,y_33] --> [ x_4,y_41] --> [ x_5,y_55] ........... [x_10,y_100]
Or it could be :
[ x_0,y_00] --> [ x_1,y_18] --> [ x_2,y_23] --> [ x_3,y_38] --> [ x_4,y_47] --> [ x_5,y_50] ........... [x_10,y_100]

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by