Given Polygon and Fix Points, Find the Triangle Meshes

Question

Let's say I have a polygon, and I want to mesh it. In order to further put constraints on the mesh I get, I will supply a list of fix points ( which must lie inside the polygon) so that they must be connected by the triangle elements generated.

What is the matlab command to do it? I tried delaunay command, but it can't work on concave polygon because the delaunay command will always return me a list of elements that encompass a convex area.

Answer 1

The function you want to use is DelaunayTri, and you would follow these steps to do it:

• Create a list of the edge points in your polygon.
• Take all of the vertex points of your polygon and combine them with the additional fixed points you want to include inside the polygon.
• Create a constrained triangulation (as I've illustrated in other answers here and here).
• As you noted, this will create a triangulation of the convex hull (even if you have a concave polygon), so you would have to remove triangles outside of the constrained edges using the method inOutStatus (also illustrated in the answers linked above).

Here's some sample code:

polygonVertices = [0 0;...  %# Concave polygon vertices
                   0 1;...
                   1 1;...
                   0.5 0.5;...
                   1 0];
polygonEdges = [1 2;...  %# Polygon edges (indices of connected vertices)
                2 3;...
                3 4;...
                4 5;...
                5 1];
otherVertices = [0.5.*rand(5,1) rand(5,1)];   %# Additional vertices to be added
                                              %#   inside the polygon
vertices = [polygonVertices; otherVertices];  %# Collect all the vertices
dt = DelaunayTri(vertices,polygonEdges);  %# Create a constrained triangulation
isInside = inOutStatus(dt);  %# Find the indices of inside triangles
faces = dt(isInside,:);      %# Get the face indices of the inside triangles

And now the variables faces and vertices can be used to plot the meshed polygon.

Working with older versions of MATLAB...

Looking through the archived version documentation (note: a MathWorks account is required to do so), one can see that DelaunayTri first appeared in version 7.8.0 (2009a). Prior to that, the only built-in functionality available for performing 2-D Delaunay triangulation was delaunay, which was based on Qhull and was thus unable to support constrained triangulations or triangulations of non-convex surfaces.

The newer DelaunayTri uses CGAL. As such, one option for users of versions older than 7.8.0 is to create MEX-files to interface CGAL routines in MATLAB. For example, if you're faced with triangulating a concave polygon, you can create a MEX-file to interface one of the convex partitioning routines in CGAL in order to break the concave polygon into a set of convex polygons. Then delaunay could be used to triangulate each convex polygon, and the final set of triangulations grouped into one larger triangulation of the concave polygon.