sortieren eine Reihe von Punkten einen Umschlag in MATLAB

Question

Ich habe die nächsten Vektoren zu generieren:

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] 

Wenn wir A und B zeichnen, werden wir die folgende Grafik erhalten:

Dann frage ich mich, wie kurz die Punkte, um das nächste Grundstück zu haben:

Wie Sie sehen können, gibt es einige Bedingungen wie: alle von ihnen bilden rechte Winkel; Es gibt keinen Schnittpunkt zwischen Linien.

Vielen Dank im Voraus für eine Antwort!

Answer 1

Wenn alle Schnittpunkte in 90-Grad-Winkeln liegen müssen, können wir einen Graph der möglichen Verbindungen bilden.

Hinweis: Es kann wichtig sein/die Leistung zu verbessern, um kollineare Punkte zu trennen.

Danach wird die Lösung auf die Suche nach Hamiltonian Cycle reduziert. Leider ist das ein NP-schweres Problem, aber glücklicherweise existiert bereits eine MATLAB-Lösung: https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph--source--destination- (obwohl ich es nicht getestet habe).

Answer 2

Dies kann in der herkömmlichen rekursiven ‚Labyrinth‘ Lösung ‚kriechenden an Wänden‘ gelöst werden:

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

Anrufen wie folgt, angegeben A und B wie oben;

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