带权限定Delaunay三角化的算法步骤及实现

发布网友发布时间：2022-05-16 07:28

共1个回答

热心网友时间：2023-10-15 06:10

1.二维的算法步骤及实现

带权的限定Delaunay三角剖分（Weighted CDT）的算法的输入是一个包含限定线段和限定点的平面直线图（planar straight line graph，简称PSLG），算法的输出是与限定条件（限定点和限定线段）一致的一个三角形集合。

算法4.7二维的带权限定Delaunay三角剖分

ConformingWeightedDelaunayTriangulation（PSLG）

{

规范化算法

调用算法WeightAssignment2d对PSLG中的点赋权值

建立初始大三角形

调用二维带权Delaunay空洞算法（算法4.2）生成受限点集的带权Delaunay三角剖分；

调用二维恢复受限边的算法（算法4.5）生成边界一致的带权Delaunay三角网格

删除边界外的多余的三角形，得到边界一致的带权限定Delaunay三角剖分

}

2.三维的算法步骤及实现

加权的限定Delaunay剖分的算法步骤：

输入：一个分段线性复合形（a piecewise linear complex）

输出：满足受限条件的具有带权Delaunay性质的四面体集合

算法三维的带权限定Delaunay四面体剖分算法：

ConformingWeightedDelaunayTetrahedralization（PLC）

{

调用算法4.4 WeightAssignment3d对规范化后的点和边赋权值；

建立初始大四面体

for所有的PLC中的平面

将该平面通过坐标变换转换到XOY平面上；

调用算法WeightedConstrainDelaunayTriangulation进行二维的带权限定Delaunay三角剖分

将得到的二维带权限定Delaunay三角网格坐标变换到空间中其原来位置

endfor

调用算法三维带权Delaunay空洞算法生成三维点集的带权Delaunay四面体剖分

调用算法RecoverConformSegments和算法RecoverConformFacets恢复受限边和受限面

删除边界外的多余的四面体，得到边界一致的带权限定Delaunay四面体剖分

}