Finding concave hull around abstract shape

Hallo together,

I have quite some abstract shape and try to found a more rectangular concave hull around it. I attached the polyshape data.

Now I wanna achieve a boundary faced like this and generate a patch object out of it:

I tried already a lot. Using the boundary function or alphaShape, but I could never reach a similar results. Either I had hole in my polyshape object at the end, or there was to much area close to the circle attached to the new polyshape object. Of course the with red indicated areas to be added to the final polyshape object dont have to be exactly like in the picture but similar I wanna achieve.

Also similar shapes should be solvelable.

Does somebody have a idear how to solve this? I would be really glad.

Thanks a lot!

Answer 1

[Star Strider]

I am not certain what you want. The information creates a 2D polyshape.

The boundary function is likely most appropriate here, although you will have to experiment with various values of the shrink factor to get the result you want.

Try this —

LD = load('matlab_answer_example.mat')

LD = struct with fields:
    new_polyShape1: [1x1 polyshape]

ps = LD.new_polyShape1

ps = 
  polyshape with properties:

      Vertices: [722x2 double]
    NumRegions: 1
      NumHoles: 0

xv = ps.Vertices(:,1);
yv = ps.Vertices(:,2);

[ixb1,v1] = boundary(xv, yv, 0.1)

ixb1 = 211×1

1 722 721 720 719 718 717 716 715 714

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

v1 = 2.5577e+03

[ixb2,v1] = boundary(xv, yv, 0.8)

ixb2 = 240×1

1 722 721 720 719 718 717 716 715 714

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

v1 = 821.0291

figure
plot(ps, 'DisplayName','Original Polyshape')
hold on
plot(xv(ixb1), yv(ixb1), '-c', 'DisplayName','Shrink = 0.1')
plot(xv(ixb2), yv(ixb2), '-m', 'DisplayName','Shrink = 0.8')
hold off
axis('equal')
legend('Location','best')

.

Answer 2

[Matt J]

ps = load('matlab_answer_example.mat').new_polyShape1;

tic;
V=cell2mat(arrayfun(@(i) upsamp(polybuffer(ps,-i)),[0,1],'UniformOutput',0)');

shp=alphaShape(V,6,'HoleThreshold',2*area(ps));
toc

Elapsed time is 1.110689 seconds.

plot(shp,'EdgeColor','none');hold on
plot(ps, 'FaceColor','none','EdgeColor','red');hold off
axis equal

function V=upsamp(ps)


 V=ps.Vertices;
 V(any(~isfinite(V),2),:)=[];

 V(end+1,:)=V(1,:);
 N=height(V);

 V=interp1(V,linspace(1,N,100*N));
 V(end,:)=[];


end

[Nicolas Kaiser]

Thanky Matt! That looks for this case already like what I wanted to achieve. I will check if I can adjust it also to different case. Maybe also to find in general a better approach.

[Matt J]

I've modified it slightly to make it faster.

Answer 3

[John D'Errico]

I don't know the soure of this data. But, can you start with the two pieces as separate entities, form polyshapes from each, and then use the union tool? For example, here I'll separate the two into pieces artificially.

load matlab_answer_example.mat
I1 = 70:570;
I2 = [1:70,571:722];
xy = new_polyShape1.Vertices;
S1 = polyshape(xy(I1,:));
S2 = polyshape(xy(I2,:));

Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been modified to create a well-defined polyshape.

H1 = plot(S1);
H1.FaceColor = 'r';
hold on
H2 = plot(S2);
H2.FaceColor = 'b';
hold off

S3 = union(S1,S2);
plot(S3)

[Nicolas Kaiser]

Okay let me try to explain my aim and the origin of my question. I uploaded the corresponding data.

In general I have multiple circels in region 1 and in region 2. The assigment of the circels to this regions are deterministic. For region 1 and region 2 I calculated the convex hull around the corresponding circles, leading to polyShape_1 and polyShape_2. In same cases thats all what I have to do. Unfortunatly in same cases, like the case mentioned before the two polyShapes overlap.

I want now to adjust the polyshapes to resolve the overlapping area without excluding a circle from the assigned region and polyShape_1 or polyShape_2. Additionaly I want, that both polyshapes have a distance of x (x=1) towards each other. This should be always possible due to adjustment of the placement of the circles. But I also, as stated in the original question, do not want to just cut-out the overlapping part from each polyshape to gain a more rectangular or straight polyshape.

I hope I could explain it now better.

[Steven Lord]

What specifically do you expect the two polyshapes to look like in this case after you've adjusted them?

clear all
load MatlabAnswer_polyShapes.mat
whos

  Name                     Size            Bytes  Class        Attributes

  polyShape_1              1x1              3529  polyshape              
  polyShape_2              1x1              3497  polyshape              
  polyShapes_1_CutOut      8x1             40136  polyshape              
  polyShapes_2_CutOut      4x1             20068  polyshape              

plot(polyShapes_1_CutOut, FaceColor='r')
hold on
plot(polyShapes_2_CutOut, FaceColor='c')

Do you want one of the polyshapes to contain only the cyan circles and the other only the red?

figure
plot(polyShapes_1_CutOut, FaceColor='r')
hold on
plot(polyShapes_2_CutOut, FaceColor='c')
plot(polyShape_1, FaceColor = 'none', EdgeColor = 'r')
plot(polyShape_2, FaceColor = 'none', EdgeColor = 'c')
polyShape_3 = subtract(polyShape_2,polyShape_1);
plot(polyShape_3, FaceColor = 'none', EdgeColor = 'k')

The subtract function got part of the way there, though the edge goes through one of the cyan circles. Is this on the right track for what you're hoping to create?

And just to confirm that you mean what I think you mean, when you say "Additionaly I want, that both polyshapes have a distance of x (x=1) towards each other." do you mean that you want the shortest distance between a point on the polyshape surrounding the cyan circles and a point on the polyshape surrounding the red circles to be 1 unit (exactly 1 unit or at least 1 unit?) So if we applied polybuffer with a distance of 1 to one of the polyshapes, it would not overlap (or not even touch) the other?

[Nicolas Kaiser]

Sorry for the late response. You summarized it quite well. So one polyshapes should include the cyan coloured circles and the other one the red coloured circles. Exactly if we apply polybuffer to one of the polyshapes with a distance of 1 they should touch but should not overlapp (so exactly 1).

In the end I want to gain a polyshape that doesn't have the exact boundary the subtraction of the overlapping area from both polyshapes would have, to prevent a polyshape like in the post of John D'Errico but more like one in the post of Matt J. So to speak I want the resulting polyshape to be more straight and "smooth".