A faster union of polyshapes

Question

Sim 2023-7-12

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1994973-a-faster-union-of-polyshapes

评论： Bruno Luong 2023-7-15

采纳的回答： Bruno Luong

borders2.mat

在 MATLAB Online 中打开

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Bruno Luong 2023-7-12

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1994973-a-faster-union-of-polyshapes#answer_1272143

编辑：Bruno Luong 2023-7-12

在 MATLAB Online 中打开

borders2.mat

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 个评论
显示 2更早的评论隐藏 2更早的评论

Bruno Luong 2023-7-13

编辑：Bruno Luong 2023-7-13

在 MATLAB Online 中打开

borders2.mat

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)