cell comparison with other cells in different rows

I have a 6x2 cell array. Each cell is a 1x2 cell that contains an x and y co-ordinate. I want to be able to compare the contents of each cell of every row with the contents of each cell of the other rows. Each row of the cell array stands for a line. Essentially what I need to do is to determine which rows are connected together by finding the common endpoint.

I saw something on here that I think I can utilize. It's called nchoosek. This function basically finds all possible rows combination's for a give size. The following code uses this function. The problem that I am having is that I get all zero's for the keys.

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

comparisons = nchoosek(1:size(endpoints,1),2);
N = size(comparisons,1);
keys = cell(N,1);
for j = 1:N
    keys{j}=isequal(endpoints{comparisons(j,1),:},endpoints{comparisons(j,2),:});

end

Answer 1

[Richard Brown]

For the record, it would be better to use arrays rather than cell arrays for the coordinates (in fact for the whole thing, but that's ok).

Anyway, this should do the trick:

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

n = size(ep, 1);
V = nchoosek(1:n, 2);
key = false(n, 1);
% Convert the points to vectors
ep = cellfun(@(x) cell2mat(x), ep, 'UniformOutput', false);
is_same = @(x, y) norm(x - y, inf) / norm(x, inf) < 100*eps;

for i = 1:size(V, 1)
   % Do the four comparisons
   i1 = V(i,1);
   i2 = V(i,2);
   key(i) = is_same(ep{i1, 1}, ep{i2, 1}) || ...
            is_same(ep{i1, 1}, ep{i2, 2}) || ...
            is_same(ep{i1, 2}, ep{i2, 2}) || ...
            is_same(ep{i1, 2}, ep{i2, 2});
end
matches = V(key, :);

[Harold]

Yes, thank you very much. At least I was on the right track with the for loop. I will have to dig into this solution to see how each function contributes to the overall solution. Thanks again, this would have taken me probably another 1-2 days to figure out completely.

[Richard Brown]

It's pretty simple - the only particularly obfuscated line is the cellfun one - it just converts all of the points into arrays rather than cell arrays (so you can add, subtract, take norms, etc), while keeping the overall cell array structure.

The is_same line is a convenient anonymous function for comparing two vectors - basically just saves a whole lot of typing, given that you need to compare four different pairs each pass through the main loop.

[Harold]

Thanks for all your help. I can now start on coding a solution to get the vertices in a match that are not in both vectors.

Answer 2

[Andrei Bobrov]

[EDIT] :)

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

M = cell2mat(cellfun(@(x)cell2mat(x),ep,'un',0));
cmb = nchoosek(1:size(M,1),2);
ic = arrayfun(@(i1)any(ismember(M(cmb(i1,1),:),M(cmb(i1,2),:))),(1:size(cmb,1))');
pout = cmb(ic,:);

[Harold]

This worked pretty good. However when I looked at the problem again I realized I was going about this the wrong way. What I should of been doing is comparing the normal vectors of every facet. If any two normal vectors are the same, then the endpoints lie on the same line. So for example, if you have a rectangle and then draw one diagonal the diagonal splits the rectangle into two facets (triangles) of which each have the same normal vector. I'm trying to modify your solution to work with a matrix that is 6x3. Each column represents x, y, z points.

[Harold]

Upon further reading of nchoosek, I don't think I can use this function anymore. MATLAB help says that nchoosek is only practical for situations where n is less than about 15. The number of facets in a 3d model that I'm analyzing can be greater than 15.

[Richard Brown]

If you're only calling nchoosek with k of 2, you can go much higher than 15. The number of possible combinations is just n*(n-1)/2. And if nchoosek is too slow (once you get into the thousands), then you can easily do it with two nested loops.

[Harold]

I think I need to modify your solution somehow. The results that I got are not exactly what is supposed to be.

pout should give [1,2;2,5;5,6;6,3;3,4;4,1]

your solution gives [1,2;3,4;3,6;5,6]

Here is the process which gives the solution that I need:

1) Start with row one

2) Search other rows that either contain the first point or the second point

3) If this point matches, then write the row to variable output

4) If this point does no match, then write the row to variable temp

5) Start procedure again starting with first row of temp and search all rows in temp for a matching point. This process repeats until all the rows are written into the output variable.

At first I was thinking about writing this as a for loop but would like to find an easier way using nchoosek. Thanks for all your help thus far.