排序點陣列產生的MATLAB

Question

一個信封我的下一個向量：

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，我們就會得到下圖：

然後，我想知道如何縮短積分以獲得下一個積分：

正如你所看到的，有一些條件，如：所有這些都形成直角;線條之間沒有交集。

在此先感謝您的回覆！

Answer 1

如果所有交點必須在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-（儘管我還沒有測試過它）。

Answer 2

這可以在傳統的遞歸「迷宮」的「爬壁」溶液來解決：

%%% 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