How to select, or filter, the external border/boundary in a set of (x,y)-points? [Part 2]

Hi, in a previous question, I asked about a method to obtain the external border from a set of points.

I then tried to apply the same method, proposed by @Dyuman Joshi, i.e.

% Obtain coordinates corresponding to outside border by performing
% exclusive OR on the data, between "border b1" and "border b2":
z = setxor(b1,b2,'rows','stable');

to a larger dataset, that composes numerous "borders". The larger dataset is the following (here attached as well):

% load borders and plot them
load('borders2.mat','a')
figure; hold on 
for i = 1 : length(a)
     line(a{i}(:,1),a{i}(:,2),'color','k'); 
end
hold off

When I tried to use iteratively the method proposed by @Dyuman Joshi, I got a wrong output (and stuck) and I do not know how to solve the issue.. any idea or suggestion?

% remove iteratively "common edges", and plot the external common border
figure; hold on 
b=a{1};
for i = 2 : length(a)
    c=a{i};
    b=setxor(b,c,'rows','stable');
    plot(b(:,1),b(:,2),'r')
end
hold off

Note: as alternative method, I also tried to use the boundary function, with the maximum shrinking factor, but, still, it does not follow the exact shape of the external common border (as I would like).

[Dyuman Joshi]

The points that still appear on the inside (of outer boundary) are the points of intersection of 3 or more borders, which makes sense.

One approach would be to eliminate the intersection points (as mentioned below) before processing the data via for loop, but that seems difficult to implement.

I'll keep you updated if I find a solution.

load('borders2.mat','a')
figure
hold on
for i = 1 : length(a)
    line(a{i}(:,1),a{i}(:,2),'color','k');
end

%a = cellfun(@(x) unique(x,'rows', 'stable'), a, 'uni', 0);

b=a{1};

for i = 2:numel(a)
    c=a{i};
    b=setxor(b,c,'rows','stable');
end

plot(b(:,1),b(:,2),'ro ','MarkerSize',5)

[Sim]

Many thanks @Dyuman Joshi!! And thanks a lot to @Kanishk Singhal for the precious suggestions!

I did not notice that the "internal" points, that remain after using setxor, are the points of intersection of 3 or more borders..! Good to know.. :-) I am also trying to remove them... Yes, in case you find a suitable way to remove them please let me know! I will also write a possible solution here, if I am able to get it :-)

Answer 1

[Bruno Luong]

Use the right tool: polyshape class

load('borders2.mat')

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

[Sim]

Astonishing answer @Bruno Luong, many many thanks!! It works very well!! :-) :-)

[Dyuman Joshi]

That's neat! I did try to come up with a solution which would utilize polyshape but failed.

I didn't know about this particular union, even though I spent quite some time thinking about approaches with union, setxor, intersect functions used for numerical arrays.

[Sim]

Thanks @Dyuman Joshi, for your time and efforts! I would upvote you for your efforts! :-)

[Sim]

just a small note... when I have already around 50 polyshape objects to join through the union function, the for-loop becomes extremely extremely slow.... therefore, it would be very very difficult to join thousands of objects as in my case :-( :-(

% Code
tic
warning('off','MATLAB:polyshape:repairedBySimplify')
Q = polyshape(zeros(0,2));
n = 10;
for i=1:n
     Q = union(polyshape(a{i}),Q);
end
toc

% Times
n=10
Elapsed time is 0.553638 seconds.

n=20
Elapsed time is 1.779556 seconds.

n=30
Elapsed time is 3.675060 seconds.

n=40
Elapsed time is 7.695874 seconds.

n=50
Elapsed time is 14.114006 seconds.

n=60
Elapsed time is 29.007251 seconds.

I plotted the times as well:

s = [10 0.553638
     20 1.779556
     30 3.675060
     40 7.695874
     50 14.114006
     60 29.007251];
plot(s(:,1),s(:,2),'o-')

[Bruno Luong]

You might do union in the hierarchical way and groupping neiboring regions with the same areas as much as possible or, second strategy: share the biggest proportion of border first. It requires some processing and might be different implementation (recursive) than the for loop.

[Star Strider]

Brilliant!

+1

My polyshape approach also failed.

[Sim]

Thanks @Bruno Luong... :-) Unfortunately, I am not able after different attempts.. I will try more, and maybe I can open a new thread.. maybe someone has already solved the same problem.....

UPDATE: I opened a new question... :-)

[Bruno Luong]

IMHO it requires quite a bit of programming and reflexion. Your attemps seem too quick to be effective.

[Sim]

OK, thanks :-) ...btw, it is 2-3 days I am trying to find a solution for this task... :-)

Answer 2

[Kanishk Singhal]

If you plot after the loop,

figure; hold on 
b=a{1};
for i = 2 : length(a)
    c=a{i};
    b=setxor(b,c,'rows','stable');
end
plot(b(:,1),b(:,2), '.')
hold off

you will get a plot like this.

Most boundary is removed but this the data is not perfect, some points which are inside are must be shared at unique to a cell.

Here you have two possibilities,

1. Either clean the data remove these points or add these points in another cell.
2. You get all the points from b, plot the points but make some kind of distance function which can identify these points.

In my opinion cleaning the data is a better option.

[Sim]

Thanks a lot @Kanishk Singhal! With the points2contour function (by @Tristan Ursell), I tried to sort the (x,y)-coordinates of the entire dataset, in order to get the external border (despite the internal points) and I got this:

figure;
b=a{1};
for i = 2 : length(a)
    c=a{i};
    b=setxor(b,c,'rows','stable');
end
[Xout,Yout]=points2contour(b(:,1),b(:,2),1,'cw'); % sort (x,y)-coordinates
plot([Xout Xout(1)],[Yout Yout(1)],'.-','color','r','MarkerFaceColor','r','MarkerEdgeColor','r') % after sorting

Then, I tried to remove the points that are quite distant from other ones, in order to remove the internal ones, but it did not work well....

% clean and plot
threshold_distance=1300;
[row,~]=ind2sub(size(b),find(abs(diff(b))>threshold_distance));
b(row,:)=[];
[Xout,Yout]=points2contour(b(:,1),b(:,2),1,'cw');
figure
plot([Xout Xout(1)],[Yout Yout(1)],'.-','color','r','MarkerFaceColor','r','MarkerEdgeColor','r') 

[Sim]

If we follow the approach of directly take the boundary, I found some workaround, even though I am not super happy with that approach....indeed, for me, the best would have been what I did in my previous comment, but I am not able to clear the internal points in a proper way...

The workaround would be to use the Boundary extraction (identification and tracing) from point cloud data function (with a tiny modification about the output - see here attached the file I used), based on delaunay triangulation (that I then compared with the default boudary function of Matlab)

clear all;close all; clc;
shrink_factor   = 1;
points_distance = 1000;
load('borders2.mat')
b=vertcat(a{:});
[X,bids,E,Ne] = find_delaunay_boundary03_noAngleThreshold(b,points_distance);
figure;
hold on
plot(X(:,1),X(:,2),'.b','MarkerSize',1);
plot(X(:,1),X(:,2),'ok','MarkerSize',1);
for i=1:size(bids,2)
    bndry = X(bids{i},:);
    p1=plot(bndry(:,1),bndry(:,2),'-r','LineWidth',2); hold on;
end
k=boundary(b(:,1),b(:,2),shrink_factor);
p2=plot(b(k,1),b(k,2),'b','LineWidth',2);
hold off;
legend([p1 p2],{'delaunay boundary','default boundary'},'Location','northwest')