A faster union of polyshapes

18 views (last 30 days)
Sim
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?
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.

Accepted Answer

Bruno Luong
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.
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)
  4 Comments
Sim
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
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.

Sign in to comment.

More Answers (0)

Categories

Find more on Elementary Polygons in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!