Generating an alpha shape with a predetermined connectivity list

Hello!

I am generating a 3D shape in order to enforce boundary conditions within a simulation. I have generated a boundary from empirical data and created a triangulated mesh over the boundary outputting the vertices coordinates as a mx3 matrix and a corresponding connectivity list between vertices from which I can create my boundary. In order to determine if an object is inside or outside the 3D shell boundary I used a ray casting algorithm however this takes too long to run for what I want to do. I had previously worked with the inbuilt inShape function which runs a lot faster but requires an alpha shape to operate.

Is it possible to generate an alpha shape of a series of points with a predefined connectivity list.

Any help would be greatly appreciated. Many thanks.

[Stanley Strawbridge]

This is a really interesting questions, It would be great to have this answered!

[Jeffrey Clark]

@Sebastian Berger, you could use Delaunay triangulation in 2-D and 3-D - MATLAB (mathworks.com) by adding a centroid point for the data you have and letting it build the "solid" that you can then test future points agains using Triangle or tetrahedron enclosing point - MATLAB pointLocation (mathworks.com)

Answer 1

[Garmit Pant]

Hello Sebastian

From what I gather, you need to determine whether an object is inside or outside a 3D shell boundary. You have calculated the connectivity list between the 3D objects and you want to use the connectivity list to compute the alpha shape to use with the MATLAB “inShape” function.

You can create an alpha shape for a set of points in MATLAB using the built-in function “alphaShape”. However, you can not use a pre-computed connectivity list to calculate the shape. The function takes as the 2D or 3D points that need to be enveloped by the bounding area. You can however manipulate the shape created by changing the properties of the alpha shape like “Alpha” (alpha radius), “HoleThreshold” and “RegionThreshold”.

If you wish to continue to use the connectivity list that you have calculated, you can create a triangulation object with your connectivity list. The following code snippet defines a 2D triangulation:

You can use the MATLAB function “pointLocation” to return the IDs of the triangles or tetrahedra enclosing the query points. 

%Define and plot the points in a 2-D triangulation.  
P = [ 2.5    8.0 
    6.5    8.0 
    2.5    5.0 
    6.5    5.0 
    1.0    6.5 
    8.0    6.5]; 
%Define the triangulation connectivity list.  
T = [5  3  1; 
    3  2  1; 
    3  4  2; 
    4  6  2]; 
%Create and plot the triangulation representation.  
TR = triangulation(T,P) 

For further understanding on the methods mentioned above, you can refer to the following MATLAB Documentation:

1. “alphaShape” function: https://www.mathworks.com/help/releases/R2022a/matlab/ref/alphashape.html
2. “triangulation” function: https://www.mathworks.com/help/releases/R2022a/matlab/ref/triangulation.html
3. “pointLocation” function: https://www.mathworks.com/help/releases/R2022a/matlab/ref/triangulation.pointlocation.html

I hope you find the above explanation and suggestions useful!

Answer 2

[Matt J]

No, it's not possible. For a given set of points, the connectivity lists of its alpha-shapes are a 1D function of the alpha radius. In general, this function is not 1-1. Therefore, the user cannot be allowed to assign a connectivity list to an alpha-shape manually and arbitrarily, as it wouldn't likely be consistent with any alpha radius.

That said, you probably don't need an alpha shape analysis here. There are at least 3 offerings on the FEX for testing whether a point lies inside an arbitrary triangulated volume,

https://www.mathworks.com/matlabcentral/fileexchange/43381-intriangulation-vertices-faces-testp-heavytest?s_tid=srchtitle

https://www.mathworks.com/matlabcentral/fileexchange/48041-in_polyhedron?s_tid=srchtitle

https://www.mathworks.com/matlabcentral/fileexchange/37856-inpolyhedron-are-points-inside-a-triangulated-volume?s_tid=srchtitle