A faster union of polyshapes

Do you know a faster way to achieve this union of polyshape objects?

load('borders2.mat')
n = length(a);
warning('off','MATLAB:polyshape:repairedBySimplify')
tic
Q = polyshape(zeros(0,2));
for k=1:n
    Q=union(polyshape(a{k}),Q);
end
toc
plot(Q)

Output:

Elapsed time is 2.571824 seconds.

Answer 1

[Bruno Luong]

using union of polyshape, just different order

WARNING: code not fully tested and NOT commented not fully optimized. But it looks like about 3.5 time faster on TMW server with this specific example.

load('borders2.mat');
warning('off','MATLAB:polyshape:repairedBySimplify')

tic
n = length(a);
Q = polyshape(zeros(0,2));
for k=1:n
    Q=union(polyshape(a{k}),Q);
end
toc

Elapsed time is 2.961106 seconds.

% plot(Q)

tic
A = cellfun(@(a) polyshape(a), a, 'unif', 0);
a = cellfun(@(P) P.Vertices, A, 'unif', 0);
m = length(A);
while (m > 1)
    xy = cat(1,a{:});
    n = cellfun('size', a, 1);
    id = repelem((1:m)',n);

    [~, ~, J] = unique(xy,'rows');
    isbrd = accumarray(J,1) == 2;
    isbrd = isbrd(J);
    idbdr = id(isbrd);
    [~,is] = sortrows(xy(isbrd,:));
    idbdr = reshape(idbdr(is),2,[]).';
    idbdr = sortrows(idbdr);
    b = [true; any(diff(idbdr,1,1),2); true];
    lp = diff(find(b));
    b(end) = false;
    idpair = idbdr(b,:);
    lt = sum(n(idpair),2);
    r = lp ./ (lt-2*lp);
    [~,imax] = max(r);
    p = idpair(imax,:);

    P = union(A{p(1)}, A{p(2)});
    A{p(1)} = P;
    A(p(2)) = [];
    a{p(1)} = P.Vertices;
    a(p(2)) = [];
    m = length(A);
end
Q = A{1};
toc

Elapsed time is 0.740952 seconds.

close all
plot(Q)

[Sim]

oh gosh, that's great, chapeau!!! I did not arrive that far with my attempts.... :-) :-) :-) :-)

On my machine this is around 3.6 times faster!

Elapsed time is 2.101454 seconds.
Elapsed time is 0.573378 seconds.

[Bruno Luong]

This edit code a little bit leaner and illustrate the order of the union is performed along the procedure

load('borders2.mat');
warning('off','MATLAB:polyshape:repairedBySimplify')
LogFlag = true; % switch to false to disable graphical check

if LogFlag
    H = [];
    hold on
end

tic
A = cellfun(@(a) polyshape(a), a(:), 'unif', 0);
a = cellfun(@(P) P.Vertices, A, 'unif', 0);
for m = length(A):-1:2
    n = cellfun('size', a, 1);
    id = repelem((1:m)',n);
    xy = cat(1,a{:});
    [~, ~, J] = unique(xy,'rows');
    isbrd = accumarray(J,1) == 2;
    isbrd = isbrd(J);
    [~,is] = sort(J(isbrd));
    idbdr = id(isbrd);
    idbdr = reshape(idbdr(is),2,[]).';
    idbdr = sortrows(idbdr);
    b = [true; any(diff(idbdr,1,1),2); true];
    lp = diff(find(b));
    b(end) = false; % shoud be faster than remove it that will make deep copy
    idpair = idbdr(b,:);
    lt = sum(n(idpair),2);
    r = lp ./ (lt-2*lp);
    [~,imax] = max(r);
    p = idpair(imax,:);

    if LogFlag
        set(H, 'FaceColor', 'none');
        h1 = plot(A{p(1)});
        h2 = plot(A{p(2)});
        H = [H, h1, h2];
        input('Type <CR> to continue: ','s')
    end
    P = union(A{p});
    A{p(1)} = P;
    A(p(2)) = [];
    a{p(1)} = P.Vertices;
    a(p(2)) = [];

end
Q = A{1};
toc

if LogFlag
    try
        delete(H);
    end
end
plot(Q)

[Sim]

I am amazed by this code!!! Many many Thanks!!! In my opinion, this could be added to the Matlab File Exchange!!!!

[Bruno Luong]

You are welcome. I'm working on a version that could be 5-6 time faster. Still buggy though.