Creating curved alpha hull, similar to R-package

Hello everyone,

So I am in the process of converting some plotting code from R to matlab. I am trying to create some figures which utlize the R-package alphahull. This creates some lovely curved hull shapes which enclose some 2D data points. See the curved bounday line in the R example below:

Maltab does have an alphashapes function but this seems to tesselate around the object and does not produce curved lines.

% point creation
points = randi(64,[100 2]);

% get alpha hull
hull = alphaShape(points(:,1), points(:,2),10);

% get boundary faces
[BF, vert] = boundaryFacets(hull);

% get ployshape based on vertices
ployShape = polyshape(vert(:,1),vert(:,2));

subplot(211)
% plot points
scatter(points(:,1),points(:,2),[] ,[0 1 0], "filled");
hold on

% plot shape
plot(ployShape, 'FaceColor',"none");
title('Alpha Hull')

% set axis lims
ylim([-1 65]);
xlim([-1 65]);

And in practice I get the outline shape more easily with the boundary function: See below:

% get boundary indices
K = boundary(points(:,1), points(:,2));

subplot(212)
% plot points
scatter(points(:,1),points(:,2),[] ,[0 1 0], "filled");
hold on

% plot boundary line
plot(points(K,1), points(K,2), 'k')
title('Boundary lines')
% set axis lims
ylim([-1 65]);
xlim([-1 65]);

Does anyone have a good idea of how to convert the straight boundary lines into lines which curve inwards towards the center of mass?

Answer 1

[Bruno Luong]

Just plot the boundary as concave. Some time it doesn't work since the vert returned are not in order, I don't know why and couldn't be careless. Also at sharp corner the boudary might cross. Up to you to fix thos problems.

% point creation
points = randi(64,[100 2]);
% get alpha hull
alpha = 10;
hull = alphaShape(points(:,1), points(:,2),alpha);

Warning: Duplicate data points have been detected and removed.

% get boundary faces
[BF, vert] = boundaryFacets(hull);
%subplot(211)
% plot points
scatter(points(:,1),points(:,2),[] ,[0 1 0], "filled");
hold on
axis equal
V = vert.';
V = V(:,[1:end 1]);
for k = 1:size(V,2)-1
    xy1 = V(:,k);
    xy2 = V(:,k+1);
    T = xy2-xy1;
    xym = (xy1+xy2)/2;
    s = min(norm(T)/alpha/2,1);
    c = sqrt(1-s.^2);
    T = alpha * T / norm(T);
    N = [T(2);-T(1)];
    xyc = xym + N*c;
    tt = asin(s);
    n = max(ceil(2*tt/0.075),1);
    theta = linspace(-tt,tt,n+1);
    xy = xyc - cos(theta).*N + sin(theta).*T;
    plot(xy(1,:),xy(2,:),'k','LineWidth',2);
end

Answer 2

[John D'Errico]

How can you do what R does? You can write the code. You will not find this directly in MATLAB that I know of. (I'm the author of alpha shape codes in 2-d and in 3-d. This variation of alpha shape is not something I've seen in MATLAB. My codes are close to the tessellation based code you will find in MATLAB.) However, it is a direct variation of the basic alpha shape algorithm, where a ball of fixed radius is allowed to roll around the exterior of the point cloud. So those curved segments are just the shape of the alpha ball, as far as it can intrude into the point cloud.

The basic difference is that code appears to use the shape of the alpha ball around the perimeter, so constructing those curved segments. In comparison, the tessellation based codes use the alpha ball to "erode" simplexes from a delaunay tessellation. Then what you see is the perimeter of the simplexes that remain.

Personally, I don't really like this variation. Why not? Because it will ALWAYS result in very spiky boundaries, with those devil shaped horns poking out at all angles. And that does not seem to make sense, when I am trying to represent some domain of interest. The standard tessellation based version of alpha shape is equivalent to the convex hull for sufficiently large alpha, and that seems to be a good idea to me. (So you would never catch me writing it anyway.) Those concave curved arcs may LOOK pretty, but they make little sense to me. (Just personal preference, but I can like what I like.)

If you do write it, then you might be willing to post it on the File Exchange, so others can benefit from it too. I'm sure someone else will like it, even if I don't.

Edit:

Let me explain more clearly why I think this basic idea is wrong, even though it may look pretty. Consider a simple point cloud:

xy = rand(1000,2)*2 - 1;
xy(sum(xy.^2,2) > 1,:) = [];
S = alphaShape(xy,1)

S = 
  alphaShape with properties:

             Points: [791×2 double]
              Alpha: 1
      HoleThreshold: 0
    RegionThreshold: 0

plot(xy(:,1),xy(:,2),'.r')
hold on
plot(S)

So the alpha shape in MATLAB approximates this point cloud well enough. But if we looked at what the R code would do, each edge around the perimeter would be a tiny little wave, dipping inwards. It would be a wonderful thing, if you happen to be modelling pictures of sea urchins. But in general, I expect that a closed curved surface will be better approximated by straight line segments than by inwardly everywhere concave curved segments.

Next, once you have that alpha shape, computations done with it and using it will be far more efficient IF they are based on a triangulation of the enclosed domain. For example testing to see if a point lies inside the simple triangulation shape are trivial. Not so much when you have this horned thing.

And, yes, this may be biased by my use of alpha shapes to represent color gamuts in some of my prior work, where efficient computations were very much necessary, and where the surfaces usually were fairly smooth.

[Image Analyst]

@Michael Savage see John's wonderful collection of code in his File Exchange:

https://www.mathworks.com/matlabcentral/fileexchange/?term=authorid%3A679

There's something there for everyone. 🙂

Answer 3

[Image Analyst]

I believe boundary has an additional input that says how closely the boundary "hugs" the outer points.

If you want to smooth the points and generate additional ones that go inside toward the centroid, you can use a smoothing function like sgolayfilt or spline but it will also possibly go further away in some smoothed parts. Or maybe use activecontour. See attached demos.