Sort cell array base on the 2D value

Question

I have a 3X3 cell array and each element store a (x,y) point.

The point are generate by random number from [0,1].

What I want to do is sort the cell array so that it looks like following

ex: 9 points

each circle is one 2D point

index:(1,1) in the left top corner and (3,3) to the right bottom corner as the usual array index

that is to ensure the topological order.

How do I do it?

Thank in advance.

for the example

pairs = [4 9 2 6 5 1 7 8 3; 9 6 2 1 3 8 7 4 5] (row 1 = x-values, row 2 = y-values))

what I want to do is put them in the cell array so that they can be connected by read lines like the image's topology.

Answer 1

The number of permutations is factorial(9), which is not terribly large. So a brute-froce approach is feasible: test all permutations for your desired conditions, and pick the first that is valid.

In the following I'm using a 2x3x3 array, instead of a 3x3 cell array containing length-2 vectors, because it's much easier that way.

N = 3;
data = rand(2,N,N);
permutations = perms(1:N^2); %// generate all permutations
for k = 1:numel(permutations)
    dx = reshape(data(1,permutations(k,:)),N,N); %// permuted x data
    dy = reshape(data(2,permutations(k,:)),N,N); %// permuted y data
    if all(all(diff(dy,[],1)<0)) && all(all(diff(dx,[],2)>0)) %// solution found
        disp(dx) %// display solution: x values
        disp(dy) %// y values
        break %// we only want one solution
    end
end

Note that for some choices of data there may not be a solution.