排序点阵列产生的MATLAB

一个信封我的下一个向量：排序点阵列产生的MATLAB

A = [0;100;100;2100;100;2000;2100;2100;0;100;2000;2100;0]; 
B = [0;0;1450;1450;1550;1550;1550;1550;2500;2500;3000;3000;0]

如果我们小区A和B，我们就会得到下图：

然后，我想知道如何缩短积分以获得下一个积分：

正如你所看到的，有一些条件，如：所有这些都形成直角;线条之间没有交集。

在此先感谢您的回复！

来源

2016-07-29 lisandrojim

你能保证这一点吗？“正如你所看到的，有一些条件是这样的：它们都形成直角，线条之间没有交集。这会一直如此吗？ –

没有一个明确的算法，这听起来不太明确。你可以尝试像[边界]（http://www.mathworks.com/help/matlab/ref/boundary.html#buh3c7k-3）这样的高收缩因子，但我不会打赌太多成功。正如@Stewie所暗示的：已经存在的解决方案远不是微不足道的。 –

我可以生成这个输出：http://i.stack.imgur.com/s4TEj.jpg –

如果所有交点必须在90度角，我们可以形成可能的连接图。

# in pseudo-code, my matlab is very rusty 
points = zip(A, B) 
graph = zeros(points.length, points.length) # Generate an adjacency matrix 
for i in [0, points.length): 
    for j in [i + 1, points.length): 
    if points[i].x == points[j].x or points[i].y == points[j].y: 
     graph[i][j] = graph[j][i] = 1 
    else 
     graph[i][j] = graph[j][i] = 0

注意：断开连接点可能很重要/改进性能。

之后，解决方案简化为找到Hamiltonian Cycle。不幸的是，这是一个NP难题，但幸运的是，MATLAB解决方案已经存在：https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph--source--destination-（尽管我还没有测试过它）。

来源

2016-07-29 23:29:03 user3080953

这可以在传统的递归“迷宫”的“爬壁”溶液来解决：

%%% In file solveMaze.m 
function Out = solveMaze (Pts,Accum) 

    if isempty (Pts); Out = Accum; return; end % base case 

    x = Accum(1, end); y = Accum(2, end); % current point under consideration 
    X = Pts(1,:);  Y = Pts(2,:);   % remaining points to choose from 

    % Solve 'maze' by wall-crawling (priority: right, up, left, down) 
    if  find (X > x & Y == y); Ind = find (X > x & Y == y); Ind = Ind(1); 
    elseif find (X == x & Y > y); Ind = find (X == x & Y > y); Ind = Ind(1); 
    elseif find (X < x & Y == y); Ind = find (X < x & Y == y); Ind = Ind(1); 
    elseif find (X == x & Y < y); Ind = find (X == x & Y < y); Ind = Ind(1); 
    else error('Incompatible maze'); 
    end 

    Accum(:,end+1) = Pts(:,Ind); % Add successor to accumulator 
    Pts(:,Ind) = [];    % ... and remove from Pts 

    Out = solveMaze (Pts, Accum); 
end

呼叫如下，给定A和B如上述;

Pts = [A.'; B.']; Pts = unique (Pts.', 'rows').'; % remove duplicates 
Out = solveMaze (Pts, Pts(:,1));     % first point as starting point 
plot(Out(1,:), Out(2,:),'-o');     % gives expected plot

来源

2016-07-30 22:28:46

真的很棒！ + 1添加原始点数！坚持; scatter（A，B）;' –

如果您将第一个点添加为最后一个条目，则循环将自动关闭。 – Adriaan

@Adriaan循环* *是关闭的，因为我初始化累加器的起始点没有从'Pts'数组中移除，所以它最终会返回它。如果我这样调用它，它会是“开放的”：'Out = solveMaze（Pts（：，2：end），Pts（：，1））' –

排序点阵列产生的MATLAB

回答

相关问题