Triangulation of non-convex hull

Dear all, Today I have a question. How can we triangulate a non-convex hull in any dimension? For example, in attachment files, a picture of the 2D non-convex hull and I am looking to divide them into a sequence of triangles. I already read the paper in attachment file to get better understand and I tried 3 MATLAB functions:

• 1. trep = triangulation(tri, x,y);
• 2. T = delaunayn(dataset,{'Qt','Qbb','Qc','Qz'});
• 3. shp = alphaShape(x,y,2);Unfortunately, these functions do not work with non-convex hulls!Please, any idea to solve this problem in 2D and in nD.

Kind regards Ammar

[Ammar]

Dear all, any answer to this question, please?

[Jan]

@Ammar: It is unlikely, that somebody reads the 12 pages of the attached paper. Are you sure, that you are allowed to publish this, because you have a written consent from the copy right owner?

What exactly is your question? 3 commands, the corresponding documentation and the shown paper should clarify the problem already.

[Ammar]

Dear Jan Simon, Thank you very much for your comment. Yes, the commands are working very well but with the just convex hull, i.e. they are not working with non-convex hull. Please, do have any idea how can we triangulate non-convex hull in d dimensional dataset? Regards .Ammar.

[Jan]

alphaShape is not restricted to convex hulls. Note that the triangulation of a non-convex hull is not unique and you need any additional knowledge to determine, which points belong to the surface and which don't. And alphaShape does exactly this.

[Ammar]

Dear Jan, Thank you very much for this information. Forgive me if it is silly question, depend on my understanding the alphaShape works just with 2D and 3D not more !

Answer 1

[KSSV]

Read about delaunayTriangulation. Also have a look on this package: https://in.mathworks.com/matlabcentral/fileexchange/25555-mesh2d-delaunay-based-unstructured-mesh-generation