Combining cells within a cell array that have intersecting values

I have a cell array where each cell contains the verticies of a shape, and I'm trying to combine cells containing shared values so that I can sum together shapes with shared vertices.

For example:

Cell array c2 would look like:

[26067,26064,26063,23414,23415,23416,26066]

[23057,19894,19900,19899,19896,19895,23056]

[18084,18080,18081,18082,18083]

....

in this case is 10423 x 1 cell.

Then the code I've tried so far is:

for count1 = 1:length(c2)
    for count2 = 1:length(c2)
        if count1 ~= count2
            Li = intersect(cell2mat(c2(count1)),cell2mat(c2(count2))); %Checks if there are intersecting values in the cells
            if(isempty(Li)== 0) % If there are intersecting cells
                Combination = unique(union(cell2mat(c2(count1)),cell2mat(c2(count2)))); %Makes the unique combination of cell values
                c2(count1)= {Combination}; %Replaces the checking cell with the union
                c2(count2)= {NaN};    %Replaces the checked cell so we dont have to count again and these values are transfered
            end
        end
    end
end

c2(any(cellfun(@(x) any(isnan(x)),c2),2),:) = []; % Remove all cells that are NaN

Now this is working but is extremly inefficent with the multiple loops to just check each combination. Is there a more efficent way to solving this problem?

[Bob Thompson]

Why do all of the vertices not have the same number of elements? It would be really nice if they did, as you could just put the entire thing into a 2D array. Is it possible to enter NaNs for the missing values?

[Matt Lycas]

They do not have the same number of elements as the shapes originate from Vorroni tesselation. I have tried switching it to a matrix and filling it with NaNs and its sort of like this:

    maxLengthCell=max(cellfun('size',c2,2))*2;  %finding the longest vector in the cell array
    for i=1:length(c2)
        for j=cellfun('size',c2(i),2)+1:maxLengthCell
             c2{i}(j)=NaN;   %zeropad the elements in each cell array with a length shorter than the maxlength
        end
    end
    A=cell2mat(c2);
    A(A == 0) = NaN;
%%
for count1 = 1:length(A)
    for count2 = 1:length(A)
        Li = intersect(A(count1,:),A(count2,:));
        if(isempty(Li)== 0)
            Combination = unique(union(A(count1,:),A(count2,:)));
            Combination(maxLengthCell+1:end)=[];
            A(count1,:)= Combination;
        end
    end
end

The thing is I stoped this way and went back to the cell arrays as I would need to make it the width of potentially all verticies intersecting. Here I just guessed it would max out at twice the most verticied shape but when I tried it out this was an underestiamte.

Answer 1

[Matt J]

You should just represent your shapes as polyshape objects. Then it is easy to weed out redundant vertices using the simplify() method of the polyshape class.

[Matt Lycas]

I see what you mean and am trying it out now. Looks very promising so far. Thank you for the help.

[Matt J]

You're welcome. Please Accept-click the answer if it gets you to a solution.

[Matt J]

Matt Lycas' comment moved here:

Again, thank you, this solution is extremly fast.

for i = 1:length(c) 
if all(c{i}~=1)   % If at least one of the indices is 1, then it is an open region and we can't patch that.
    c{i,2} = polyarea(v(c{i},1),v(c{i},2));
    c{i,3} = polyshape(v(c{i},1),v(c{i},2));
end
end

d = cell2mat(c(:,2));

d = d<25;

c2 = c(d,:);
%%
pout = union([c2{:,3}]);
plot(pout)

And boom thats it, works great. Thanks for the help!