# A faster union of polyshapes

18 views (last 30 days)
Sim on 12 Jul 2023
Commented: Bruno Luong on 15 Jul 2023
Do you know a faster way to achieve this union of polyshape objects?
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.

Bruno Luong on 12 Jul 2023
Edited: Bruno Luong on 12 Jul 2023
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.
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 on 15 Jul 2023
I am amazed by this code!!! Many many Thanks!!! In my opinion, this could be added to the Matlab File Exchange!!!!
Bruno Luong on 15 Jul 2023
You are welcome. I'm working on a version that could be 5-6 time faster. Still buggy though.