Ordering rows based on value

Suppose I have a matrix of values as follows:

matches = [1,2;1,4;2,5;3,4;3,6;5,6;];

Is there a way to "connect these rows together based on a common value in the rows column. The desired result is as follows:

connected = [1,2,5,6,3,4,1]

Answer 1

[Andrei Bobrov]

k1 = bsxfun(@minus,matches(:,1),matches(:,2)');
[ii,jj] = find(k1 == 0);
a = unique([ii;jj]);
out1 = unique(matches(a,:)');
f=matches(setdiff(1:6,a),:);
[ff,bb,cc] = unique(f','first');
[~,id] = sort(bb,'descend');
out2 = ff(id);
connected = [out1;out2(2:end)]

[Harold]

Is there any function in MATLAB that will automatically detect duplicate values in a row and delete them? That's the thing that is driving me crazy.

Answer 2

[Geoff]

Try this:

matches = [1,2;1,4;2,5;3,4;3,6;5,6;];

connected = matches(1);

while size(matches,1) > 0
    [r,c] = find(matches == connected(end), 1);
    if isempty(r)
        disp('End of chain');
        break;
    end
    connected(end+1) = matches(r, 3-c);
    matches(r,:) = [];
end

disp(connected);

It's a little destructive. It systematically removes rows from the matches matrix until there are no more links or there are no rows left. It copes with ambiguity (if there is any) by selecting the first available value (determined by whatever find deems as the first value). In some some cases, this might end the chain prematurely.

[Harold]

Thank you. This works perfectly. When you say "in some cases", can you think of any where the loop would prematurely end?

[Geoff]

Well it depends on your data. For this data, it's fine. And maybe you'll always throw 'sane' data at it. I just imagined that some data sets won't produce a closed loop, will branch, or contain a side-loop that itself is closed.

Imagine the above data with [6 7; 7 8; 8 3] on it. If we happen to follow [6 7] instead of [3 6] then we'll touch all the values: [1 2 5 6 7 8 3 4 1]. But if we follow [3 6] first, we'll skip over the side-loop and produce the original output.

Anyway, I just think about that stuff, but I don't know what your data is representing or what its constraints are. If this solves your problem I'm happy. Don't forget to close off the question by accepting.

[Harold]

I posted an answer of what it is I'm trying to do.

Answer 3

[Harold]

My data represents row indices of a cell array. Here is what I'm trying to do.

Each row of a 6x4 cell array contains (x,y) co-ordinates. So for example my data is:

line = {[-24.7697910000000,-15.8191235000000],[-20.6771670000000,-3.54125200000000],[-12.6771670000000,20.4587480000000],[-20.6771670000000,-3.54125200000000];[-24.7697910000000,-15.8191235000000],[-20.6771670000000,-3.54125200000000],[-11.9803417500000,-14.5401785500000],[-24.7697910000000,-15.8191235000000];[-12.6771670000000,20.4587480000000],[-20.6771670000000,-3.54125200000000],[4.32283300000000,-1.04125200000000],[-12.6771670000000,20.4587480000000];[-11.9803417500000,-14.5401785500000],[13.0196582500000,-12.0401785500000],[-11.9803417500000,-14.5401785500000],[-24.7697910000000,-15.8191235000000];[-11.9803417500000,-14.5401785500000],[13.0196582500000,-12.0401785500000],[4.32283300000000,-1.04125200000000],[13.0196582500000,-12.0401785500000];[4.32283300000000,-1.04125200000000],[-12.6771670000000,20.4587480000000],[4.32283300000000,-1.04125200000000],[13.0196582500000,-12.0401785500000];}

First row of data

row1 = {[-24.7697910000000,-15.8191235000000],[-20.6771670000000,-3.54125200000000],[-12.6771670000000,20.4587480000000],[-20.6771670000000,-3.54125200000000];}

The first 2 points define 1 line, the last 2 points define another line. These two lines are connected by a common point, which for this particular row happens to be [-20.6771670000000,-3.54125200000000].

I'm trying to find this common point and then delete it, resulting in:

vector1 = [-24.7697910000000,-15.8191235000000]    [-12.6771670000000,20.4587480000000]

I do this for every row in the cell array "line"

Then what I do is look for common points in each row of vector so that I can connect the lines. Ultimately what I'm looking for is:

connected = {[-24.7697910000000,-15.8191235000000],[-20.6772,-3.5413],[-12.6772,20.4587],[4.3228,-1.0413],[13.0197,-12.0402],[-11.9803,-14.5402],[-24.7698,-15.8191]}

With matches I was hoping to "grab" the rows from vectors. There's got to be a simpler method than all the loops I'm doing.

[Geoff]

Well, that's okay, but I meant that I don't know WHY your data is like it is. What do the lines represent? Why do they have anything in common with other rows? Is this a polygon?

If you worry about things that can't happen when writing an algorithm then you waste time coding. Conversely, if you don't consider all possibilities then you waste time debugging.

If the system forms a closed loop, then my answer should work. But whether it comes out clockwise or anticlockwise will depend on what order the data is presented.

[Harold]

Yes, this is a closed looped polygon. The thing that I'm worried about is plotting. Imagine a cube situated in x,y,z space and concerning ourselves only with the side faces. Each face is divide by one diagonal into two triangles (facets), 8 facets for the entire model. Now imagine a x,y plane that intersects the cube at some z value. What I'm dong is calculating the intersection points that the plane makes with each facet. The goal is to create the contour that the plane makes with the cube(or any model that I have). So for each facet I will 2 pairs of (x,y) points (a line). What I'm trying to do is connect all the lines by searching for common points in each line. If a common point exists, then delete this common point and keep the other 2 points from the line. The reason why I want to delete the common point is because I need to plot these points. If I keep this common point, I may have plotting issues such as crossing over.

[Harold]

If you run this code you can see what I'm trying to avoid:

for d = 1:6

c = connected(d);

points([2*d-1:2*d],:) = (line(c,:))';

end

points = cell2mat(points)

plot(points(:,1),points(:,2))