File Exchange

Alpha shapes

version 1.3 (3.46 KB) by

Alpha shape of 2D/3D point set.

Updated

Computes the basic Alpha shape of a 2D/3D point set by Delaunay triangulation.

OUTPUT:
- Area/Volume
- Triangulation of Alpha shape
- Boundary of Alpha shape
- Plot

TooBoiling

Kumar Saurabh

Yang Zhixiong

Yang Zhixiong (view profile)

very nice code! Thx! :D
Could you please share the reference corresponding to this algorithm?

phuongle

Agnieszka Drynda

Agnieszka Drynda (view profile)

Hi Jonas,
Thanks for the code.
But I have a problem, when I run the code for an example 2, all the time I receive the problem:
Out of memory. The likely cause is an infinite recursion within the program.

Error in alphavol (line 20)
subplot(221), alphavol(X,inf,1);

Weihai

Ahmed Yehia

aranav_kacker

aranav_kacker (view profile)

Hi Jonas,
Thanks a lot for the code, really helped me out.
But I am facing a slight problem regarding the probe radius, as when i set it to 0.1 i get an accurate shape whereas it becomes incorrect at larger/smaller values.

zhao chuan

zhao chuan (view profile)

Hi Jonas,
Thanks for your code.It's very nice!Moreover, I want to get boundary points in a row, not in a mess,so how to realize that?

varun

varun (view profile)

Thnx for the code. I have a query that once a alpha shape is created using a set of 3d points. I have n number of points containing x,y,z. How can I seperate coordinate of those points lying inside the alpha shape.

Marcus Fantham

Marcus Fantham (view profile)

This is exactly the thing I was looking for, thanks!

Carsten Killer

Sergei P.

John

John (view profile)

Excellent. It is very easy to use and provides much better detail than using plot3 on a data-set.

David

Murat Aykin

Kamuran Turksoy

Kamuran Turksoy (view profile)

Once you define the alpha shape based on n number or points 2D, how would you check if a new point is inside the shape or not? Thanks

Vi

Vi (view profile)

Thank you very much for this useful code. I have a question, it would be great if you could help. Consider 3D data sampled from the same type of physical object whose shape/size varies from one sample to another, which means the radius as a parameter of triangulation varies across samples as well. What would then be the best criterion for the choice of radius? Any idea(s) would be very helpful. Many thanks in advance.

Vi

Yahui

Yahui (view profile)

What does the command "freeBoundary(TriRep(T,X))" mean? I didn't see any function about freeBoundary, but it works. So confused!

Yahui

Yahui (view profile)

Thanks! very useful.

Edwin

Edwin (view profile)

This code is awesome! Thnaks!

Carsten Mørch

Carsten Mørch (view profile)

Maurizio De Pitta'

Maurizio De Pitta' (view profile)

Hi Jonas,
I am not sure I understand your last edit to the code. Changing DELAUNAYN to DELAUNAY (line 66) fails alphavol to work on 3D data sets.

Gustavo Oliveira Santos

Gustavo Oliveira Santos (view profile)

Dear Jonas,

My name is Gustavo and I am PhD student in Ecology in Brazil. I am working in a R code to estimate home range of arboreal mammals. Because these species are arboreal, I am trying to estimate three-dimensional volume based on Kernel probability density functions. Unfortunately, these tetrahedrons are non-convex and I am having a lot of difficult to estimate these volumes. I got very excited when I saw your Matlab forum statements (http://www.mathworks.com/matlabcentral/fileexchange/28851-alpha-shape-volume). The R have a package alphashape3d to deal with these issues, but the functions are new and extremely unstable (the results are crazy, the R crash or no values are returned). The package geometry also is very useful, but it have functions to estimate only convex tetrahedrons.

I am ecologist, not math, and the I have a lot of difficulty with deal with this 3D geometry. Additionally, I have not intimacy with Matlab code. I would like to know if you could help me, or to indicate who can help me to solve this problem. I could send to you a dataset (dataframe com 3 columns [x,y,z] that describe the kernel surface of 95% probability of the opossum to you inspect the data.

If you or other people are interested in helping me. Please send a email to gu_tapirus@hotmail.com

Thomas Clark

Thomas Clark (view profile)

Ahhh... thankyou! SO overdue as part of the triangulation toolset that we get.

Yavor Kamer

Md Wahid

Md Wahid (view profile)

hi, just a quick note. 'delaunay()' requires at least 2 inputs (x,y as a vector, probably couldnt take matrix). i was trying with the 2d example that provided in the code. changed in the 65th line as 'delaunay(X(:,1),X(:,2))'. now it works, the graph looks nice. thanks for the code. i didnt look inside or try with the theory yet, could be wrong! just to let you know...

Jonas Lundgren

Jonas Lundgren (view profile)

Jorge Leandro, tilde represents an unused argument. This notation was introduced in MATLAB 2009b. You can safely replace tilde by a dummy variable.

Jorge Leandro

Jorge Leandro (view profile)

As I try to run one of your examples, Matlab (7.8.0 R2009) complains with the following message: "??? Error: File: alphavol.m Line: 78 Column: 3
Expression or statement is incorrect--possibly unbalanced (, {, or [."

Examining the referred line, I see:
[~,rcc] = circumcenters(TriRep(T,X));

It seems that Matlab cannot understand the tilde as an output value. I tried to change it to [cc rcc] = circumcenters... and now Matlab complains about line 194, which reads:
[~,p,r] = dmperm(C);
Again, the tilde seems to be the problem.
By the way, as far I as know, tilde is used as a negation operator in Matlab. What is its use here? Any clue on how to solve this problem?

Regards.

Jonas Lundgren

Jonas Lundgren (view profile)

Borc, Yes I am aware of these artefacts in the 3D case. Thats why the code only delivers volume and not boundary faces. I will give this some thought.

Borc

Borc (view profile)

Thanks for this nice code!
One Question:
There are some artefacts inside the volume (like rectangles). How could I avoid them?
As an example run the "3D Example - Ring" with the plotsettings 'FaceColor','r' and 'FaceAlpha',0.5 to see the artefacts inside the volume.
A solution would be very helpfully for me.

Borc

ping

Jonas Lundgren

Jonas Lundgren (view profile)

Yuri, try the command "axis equal".

Yuri K

Yuri K (view profile)

It looks like the algorithm unequally connects point vertically and horizontally.
Try this data, for example:
n = 1000;
k = 10;
x = linspace(0,1,n)';
y(:,1) = k*x + randn(n,1) - k/2;
y(:,2) = -k*x + randn(n,1) + k/2;
xx = [x;x];
yy = y(:);
alphavol([xx yy], 0.5, 1);

HARI KRISHNAN

thanks a lot

Ajay

Ajay (view profile)

Works well and easy to use, thanks much.

Jonas Lundgren

Jonas Lundgren (view profile)

k Z, Thank you for the feedback. It seems to be a problem with DelaunayTri and nonunique data points. DelaunauyTri is also very slow for equally spaced data. I will switch to delaunayn and remove nonunique data points - when I have the time.

k Z

k Z (view profile)

Hi, nice code. Although the algorithm is useful when nonconvex data is used, I tested on convex data to check how robust it is. I try the sphere function. The volume of the sphere using alpha=Inf is not the same as the sphere volume, in this case the function convhulln computes more accurately the volume. It seems that summing the volume of all tetrahedron counts more that the overal volume, at least for this case. Check this please.