Sort an array of points to generate an envelope in

问题:

I have the next vectors:

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]

If we plot A and B, we'll obtain the following graphic:

Then, I wonder how to short the points in order to have the next plot:

As you can see, there're some conditions like: all of them form right angles; there's no intersection between lines.

Thanks in advance for any reply!

回答1:

This can be solved in the traditional recursive 'maze' solution of 'crawling on walls':

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

Call as follows, given A and B as above;

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

回答2:

If all intersections must be at 90 degree angles, we can form a graph of possible connections.

# 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 

Note: it may be important/ improve performance to disconnect colinear points.

After this, the solution is reduced to finding a Hamiltonian Cycle. Unfortunately this is an NP-hard problem, but fortunately, a MATLAB solution already exists: https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph--source--destination- (although I haven't tested it).