What algorithm does Matlab's boundary function

Question

As you may have already noticed, in the newer versions of matlab the boundary function (which computes the boundary for a set of 2d or 3d points) has been improved.

Now it is possible to give the function a parameter called 'shrink factor'. If the shrink factor is 0, then the boundary traced is the traditional convex hull. The boundary is more shrinked when the shrink parameter is bigger. The default value for the shrink factor is 0.5, in case you don't specify any value.

So, I understand its use and what it does (actually I've already used the function in a project), but I don't know how it works. What are the geometrical principles of this shrink factor?

Thanks!

Answer 1

Found your question while loooking for the answer myself. Hope you've solved it by now. I've figured it out and in case someone else finds this question, here's my understanding of the boundary() function.

The boundary function is an implementation of alpha shapes. Using alpha shapes, a set of points can be assigned a polygon by using a set of circles of a specific radius: imagine an arbitrary shape drawn around the points and proceed to remove as much of this shape as possible using circles of a specific radius. Continue as long as possible, without enclosing any points. A small radius will mean more "material" can be removed, a larger radius means less "removal", i.e. a small radius creates a close cropped shape whereas an infinite radius recreates a convex hull of the set. The points determined to be edge points are then conencted with straight edges. This can create hollow areas inside the point set. See e.g. http://doc.cgal.org/latest/Alpha_shapes_2/index.html

MATLAB has an alphashape() function which calculates alphashapes with all possible alpha radii giving different shapes. This is used in the boundary function.

boundary() workflow:

(1) Create alphashape

(2) Find critical alpha radius, needed to create a single region for alpha shape

(3) Extract all alphavalues that create unique shapes above this critical value

(4) Use the shrink factor, S, to select a single alpha value to use.

Example: with S=0.25, use alpha radius with index (1-.25)*numel(alphavalues>=alpha_crit). This creates an alpha shape using the 75th smallest alpha radius giving rise to a single region (for S=0.25).

If S=1 (max shrink), gives the lowest alpha-radius that gives a single region for the alpha-shape.

If S=0 (no shrink), gives the maximum alpha-radius that gives a unique shape. (Incraesing alpha radius further has no effect).

(5) set the threshold for filling in holes in the alphashape to be the same as the alphashape's area, i.e. fill in all holes

(6) Return the indices of the original point cloud correspocing to the vertices of this alphashape.

The relevant section of the boundary.m file (lines 79-86)

Acrit = shp.criticalAlpha('one-region'); %alpha-radius required for single region
spec = shp.alphaSpectrum();%all alphavalues
idx = find(spec==Acrit);
subspec = spec(1:idx);%alphavalues up to criticalAlpha
subspec = flipud(subspec);%reverse order
idx = max(ceil((1-S)*numel(subspec)),1); %find index from shrink factor
alphaval = subspec(idx); 
shp.Alpha = alphaval; %set alpha value of alpha shape
shp.HoleThreshold = areavol; % remove holes in interior

Hope this is clear enough and useful to someone.

I use MATLAB R2014b

Answer 2

YiraDati's answer provides great details.

You can also type "open boundary" in command windows, and then all procedures are written in boundary function. And all subfunctions shown in boundary function are accessible using matlab documentation, like area(), criticalAlpha(), alphaSpectrum(), etc...