给定多边形和固定点,找到三角网格

Question

假设我有一个多边形,我想对它进行网格化.为了进一步对我得到的网格施加约束,我将提供一个固定点列表(必须位于多边形内),以便它们必须通过生成的三角形元素连接.

什么是matlab命令呢？我尝试了delaunay命令,但它无法在凹面多边形上工作,因为该delaunay命令将始终返回一个包含凸面区域的元素列表.

Answer 1

您要使用的功能是DelaunayTri,您将按照以下步骤执行此操作:

• 创建多边形中边缘点的列表.
• 获取多边形的所有顶点,并将它们与要包含在多边形内的其他固定点组合.
• 创建一个约束三角剖分(正如我在这里和这里的其他答案中所说明的那样).
• 如您所述,这将创建凸包的三角剖分(即使您有凹多边形),因此您必须使用该方法删除约束边之外的三角形inOutStatus(也在上面链接的答案中说明).

这是一些示例代码:

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

而现在的变量faces,并vertices可以用来绘制网格多边形.

使用旧版本的MATLAB ...

查看存档版本文档(注意:需要MathWorks帐户),可以看到DelaunayTri第一次出现在版本7.8.0(2009a)中.在此之前,可用于执行2-D Delaunay三角测量的唯一内置功能delaunay是基于Qhull,因此无法支持非凸面的约束三角测量或三角测量.

较新的DelaunayTri使用CGAL.因此,对于早于7.8.0的版本的用户,一个选项是在MATLAB中创建MEX文件以接口CGAL例程.例如,如果您要对凹面多边形进行三角剖分,则可以创建一个MEX文件来连接CGAL中的一个凸分区例程,以便将凹多边形分解为一组凸多边形.然后delaunay可以用于对每个凸多边形进行三角测量,并且最终的三角测量集合成凹多边形的一个更大的三角剖分.