一种基于Delaunay图的多块结构网格奇点识别方法

一种基于delaunay图的多块结构网格奇点识别方法
技术领域
1.本发明涉及流体力学领域，特别涉及一种计算流体力学的多块结构网格生成方法。

背景技术：

2.在数值计算中，多块结构网格的划分往往采用人工方式。一方面，人工分块花费大量的时间成本，需要使用者具备相当的经验和技巧。另一方面，不合理的网格分块会导致结构网格总数过大、质量较差等问题。因此，有必要研究提高多块结构网格划分效率的方法和技术。
3.多块结构网格的分块主要有两个步骤，即识别奇点和拓扑分块。识别几何构型内部的奇点是结构分块的关键；奇点，即结构网格中邻边数不为4的网格节点，奇点可改变网格的方向、控制局部网格密度等，但也会造成局部网格质量下降。因此，合理地放置奇点能够辅助生成质量较高的多块结构网格。
4.目前，交叉场法较广泛地用于多块结构网格的奇点识别方面。交叉，是具有四个正交方向的向量的集合，在结构网格中代表了这个位置上的关联边的方向；交叉场即是关于这些向量集的场，又叫正交标架场、4对称方向场，在四边形网格生成中，描述了网格的方向，合理的交叉场分布能够使得所生成的网格满足特定的单元尺寸和方向要求。目前，交叉场法的主要流程是，首先在非结构网格中求解泊松方程得到交叉场，并根据网格中的三角形单元上的交叉连续性判断其中是否存在奇点。交叉场法的优势在于，具有完备的理论体系，对于不同的几何构型，都能够得到较合理的奇点分布，生成的网格块结构也具有良好的正交性。但另一方面，由于交叉场的求解要求在非结构网格中求解泊松方程，相对来说计算量较大、复杂度较高；同时，拓扑分块时方法受数值误差的影响较大。

技术实现要素：

5.为了解决上述问题，本发明提供一种能够提高多块结构网格拓扑分块的自动化程度和效率，其算法简单、计算效率高，同时根据识别到的奇点，结合人工分块，划分质量较高的多块结构网格的多块结构网格奇点识别方法。
6.为了实现上述目的，本发明提供发的技术方案是：一种基于delaunay图的多块结构网格奇点识别方法，包括以下步骤：s1：获取几何构型的边界节点；s2：计算所述边界节点上的交叉；s3：在计算域内添加辅助点，并指定所述辅助点上的交叉；s4：对所述边界点和辅助点进行delaunay三角化，得到delaunay图；s5：循环delaunay图中的所有单元，判断其中是否存在奇点，若存在奇点确定所述奇点的类型；s6：计算所有奇点的位置和方向，并以此辅助结构网格分块。
7.进一步的，所述步骤s1具体包括：将几何构型的曲线和直线离散成节点形成边界节点。离散的节点要求保证几何外形的完整性，能够利用离散点插值到原几何边界上。
8.进一步的，所述步骤s2具体包括：交叉是相互垂直的四个向量的几何，交叉用一个角度θ表示：式中，c
θ
表示交叉，表示交叉中的某个向量，(*)
t
表示矩阵的转置；对于边界上的节点，其与相邻两点组成的内角大小为θc，定义一个整数，式中，round(x)函数表示对实数x进行取整；当nc为偶数时，交叉方向与内角平分线的方向一致；当nc为奇数时，交叉方向为角平分线方向逆时针旋转45
°
。
9.进一步的，在所述步骤s3中：所述辅助点上交叉方向应与周围交叉方向保持连续，且相邻两个交叉的连续要求其方向的角度差的绝对值不超过45度。
10.进一步的，所述步骤s4进一步包括：s41：构造包含所有散点的超级三角形，储存在三角形链表中；s42：依次插入散点，在三角形链表中出外接圆包含插入点的影响三角形，删除影响三角形的公共边，连接插入点与影响三角形的所有顶点；s43：根据delaunay准则优化得到的新三角形，并放入三角形链表；s44：重复步骤s42直到所有散点插入完成，并删除与超级三角形相关的三角形。
11.进一步的，所述步骤s5进一步包括：循环所有delaunay三角形，其三个节点上的交叉组成了一个局部交叉场；利用交叉场的连续，判断一个局部交叉场内是否存在奇点；进一步的，所述步骤s5进一步包括：在局部交叉场中，三角形的三个顶点1、2、3以逆时针顺序排列，对应的交叉分别为θ1、θ2和θ3，则奇点的类型由下式计算，式中，k是奇点的类型，
∆
θ
ij
=θ
j-θi表示两个交叉之间的最小角度差，其范围是[-π/4，π/4]。该式识别到的奇点只有两种类型：k=+1和k=-1；当k=0时，认为该局部交叉场是连续的，即不存在奇点；当k=+1时，认为该局部交叉场中存在一个5价奇点，即该奇点相邻边的个数为5；当k=-1时，认为该局部交叉场中存在一个3价奇点，即该奇点相邻边的个数为3。
[0012]
进一步的，所述步骤s6进一步包括：对于包含奇点的三角形，其顶点的坐标分别为(x1,y1)、(x2,y2)、(x3,y3)，奇点的坐标s(xs,ys)计算为对于类型k的奇点，共有k+4个方向；奇点方向的计算首先要确定一个初始方向β0，所述奇点的其它方向则计算为，
对于初始方向β0，首先确定所处三角形中的交叉之差最小的边，所述边的中点求为β(x
β
,y
β
)，则β0即为矢量的方向，即式中，(xs,ys)和(x
β
,y
β
)分别是点s和β的坐标。
[0013]
本发明相对于现有技术的有益效果是：本发明基于几何边界的delaunay图，利用交叉场理论可快速、高效地计算出奇点；结合人工分块，在不失合理性的情况下，提高了划分多块结构网格的自动化程度和效率。
附图说明
[0014]
图1是本发明流程图；图2是本发明提供的一关于圆形的实施例；图3是本发明提供的一关于翼型的实施例；图4是本发明提供的一关于方形和弧形组合的实施例；图5是对应图3实例的辅助点示意图（左图）和delaunay图示意图（右图）；图6是对应图4实例的辅助点示意图（左图）和delaunay图示意图（右图）；图7是对应图5实例的辅助点示意图（左图）和delaunay图示意图（右图）；图8是对应图3实例的奇点位置、方向以及多块结构网格分块的示意图；图9是对应图4实例的奇点位置、方向以及多块结构网格分块的示意图；图10是对应图5实例的奇点位置、方向以及多块结构网格分块的示意图。
具体实施方式
[0015]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0016]
本发明公开的一种基于delaunay图的多块结构网格奇点识别方法，图1是方法的流程图，具体步骤如下：步骤1、读取几何边界节点；如图2、图3和图4中所示，阴影区域为几何计算域，首先读取其边界节点。对于图2中的实例，计算域为半径为1的圆形区域；对于图3中的实例，计算域外边界是边长为32的矩形，内边界是弦长为1的naca0012翼型；对于图4中的实例，计算域由正方形（边长为10）与1/4圆弧（半径为1）组成。
[0017]
步骤2、计算边界节点上的交叉；交叉，是具有四个正交方向的向量的集合；交叉场即是关于这些向量集的场，是网格奇点识别的依据，借助于奇点和交叉场能保证结构分块的正交性。每个交叉由4个等价的单位向量组成，因此可用一个角度θ表示：式中，c
θ
表示交叉，表示交叉中的某个向量(*)
t
表示矩阵的转置；当两个交叉的方向相差π/2的整数倍时，认为他们是等价的，即对于点i、j，其上的交叉方向分别为θi和θj，当θj=θi+kπ/2，时，则它们是等价的。并且，可以通过加或减π/2的整数倍角度的方式改变交叉的方向。
[0018]
为求解边界上的交叉，对于边界上的节点，其与相邻两点组成的内角大小为θc，定义一个整数，式中，round(x)函数表示对实数x进行取整；当nc为偶数时，交叉方向与内角平分线的方向一致（也即边界的切线方向）；当nc为奇数时，交叉方向为角平分线方向逆时针旋转45
°
。
[0019]
步骤3、在计算域内添加辅助点，并指定其上的交叉；利用delaunay准则对圆弧形或其他几何部分进行三角化时结果不理想，因此本实施例采用在计算域内增加辅助点的方式增加此时delaunay三角化的合理性。
[0020]
辅助点的个数应尽量少，其位置应处于圆弧形几何的圆心，或者处于单连通域的中心位置。对于图2中的实例，如图5左图所示，辅助点添加在圆形中心，其上的交叉设为0rad；对于图2-2中的实例，如图6左图所示，不添加辅助点；对于图2-3中的实例，如图7所示，在计算域中心和右上角的圆弧中心分别添加辅助点，两个点上的交叉都设为0rad。
[0021]
步骤4、对边界点和辅助点进行delaunay三角化，得到delaunay图；delaunay图用来求解计算域中的奇点的位置和方向。利用delaunay准则对几何边界上的节点和辅助点进行三角化。delaunay准则要求在某个三角形的外接圆内，除包含该三角形的三个节点外，不包含其他节点。常用的delaunay三角化的简要步骤为：（1）构造包含所有散点的超级三角形，储存在三角形链表中；（2）依次插入散点，在三角形链表中出外接圆包含插入点的三角形（即该点的影响三角形），删除影响三角形的公共边，连接插入点与影响三角形的所有顶点；（3）根据delaunay准则优化得到的新三角形，并放入三角形链表；（4）重复第（2）步直到所有散点插入完成，并删除与超级三角形相关的三角形。
[0022]
如图5、图6、图7中的右图所示，是对所有边界点和辅助点进行三角化得到的delaunay图。
[0023]
步骤5、循环delaunay图中的所有单元，判断其中是否存在奇点，并确定其类型；循环所有delaunay三角形，其三个节点上的交叉组成了一个局部交叉场。利用交叉场的连续，可判断一个局部交叉场内是否存在奇点。在局部交叉场中，三角形的三个顶点1、2、3以逆时针顺序排列，对应的交叉分别为θ1、θ2和θ3，则奇点的类型由下式计算，
式中，
∆
θ
ij
=θ
j-θi表示两个交叉之间的最小角度差，其范围是[-π/4，π/4]。该式识别到的奇点只有两种类型：k=+1和k=-1；当k=0时，认为该局部交叉场是连续的，即不存在奇点；当k=+1时，认为该局部交叉场中存在一个5价奇点，即该奇点相邻边的个数为5；当k=-1时，认为该局部交叉场中存在一个3价奇点，即该奇点相邻边的个数为3。
[0024]
循环所有delaunay三角形单元，出包含奇点的单元，对于图2中的实例，到了4个3价奇点，如图8所示；对于图3中的实例，到了2个5价奇点，如图9所示；对于图4中的实例，到了1个5价奇点，1个3价奇点，如图10所示。
[0025]
步骤6、计算所有奇点的位置和方向，并以此辅助结构网格分块。
[0026]
对于包含奇点的delaunay三角形，奇点的位置在三角形的几何中心位置。具体地，对于包含奇点的三角形，其顶点的坐标分别为(x1,y1)、(x2,y2)、(x3,y3)，奇点的坐标s(xs,ys)计算为对于类型k的奇点，共有k+4个方向；奇点方向的计算首先要确定一个初始方向β0，该处的其它方向则计算为，进一步地，对于初始方向β0，首先确定所处三角形中的交叉之差最小的边，该边的中点求为β(x
β
,y
β
)，则β0即为矢量的方向，即式中，(xs,ys)和(x
β
,y
β
)分别是点s和β的坐标。
[0027]
用箭头标记奇点的方向，图8、图9、图10分别指出了对应图2、图3、图4中的实例的奇点的位置和方向；之后，图8、图9、图10用虚线标记出了以奇点为辅的多块结构网格分块。
[0028]
奇点的位置和方向的识别大大地减少了结构网格分块的难度。根据奇点的信息，可将几何计算域划分成一块块具有四条边的结构拓扑。之后，生成的多块结构网格可用于流体力学或结构力学的数值计算中。
[0029]
本发明由于只用到关于边界上的节点和添加的辅助点的delaunay图来计算奇点的位置和方向，因此相比于原交叉场法大大减少了计算量和流程复杂度。基于几何边界的delaunay图，利用交叉场理论可快速、高效地计算出奇点；结合人工分块，快速生成结构分块，以提高多块结构网格划分的自动化程度及效率。
[0030]
以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步
详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：

1.一种基于delaunay图的多块结构网格奇点识别方法，其特征在于，包括以下步骤：s1：获取几何构型的边界节点；s2：计算所述边界节点上的交叉；s3：在计算域内添加辅助点，并指定所述辅助点上的交叉；s4：对所述边界点和辅助点进行delaunay三角化，得到delaunay图；s5：循环delaunay图中的所有单元，判断其中是否存在奇点，若存在奇点确定所述奇点的类型；s6：计算所有奇点的位置和方向，并以此辅助结构网格分块。2.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，所述步骤s1具体包括：将几何构型的曲线和直线离散成节点形成边界节点。3.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，所述步骤s2具体包括：交叉是相互垂直的四个向量的几何，用一个角度θ表示：式中，c
θ
表示交叉，表示交叉中的某个向量，(*)
t
表示矩阵的转置；对于边界上的节点，其与相邻两点组成的内角大小为θ
c
，定义一个整数，式中，round(x)函数表示对实数x进行取整；当n
c
为偶数时，交叉方向与内角平分线的方向一致；当n
c
为奇数时，交叉方向为角平分线方向逆时针旋转45
°
。4.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，在所述步骤s3中：所述辅助点上交叉方向应与周围交叉方向保持连续，且相邻两个交叉的连续要求其方向的角度差的绝对值不超过45度。5.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，所述步骤s4进一步包括：s41：构造包含所有散点的超级三角形，储存在三角形链表中；s42：依次插入散点，在三角形链表中出外接圆包含插入点的影响三角形，删除影响三角形的公共边，连接插入点与影响三角形的所有顶点；s43：根据delaunay准则优化得到的新三角形，并放入三角形链表；s44：重复步骤s42直到所有散点插入完成，并删除与超级三角形相关的三角形。6.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，所述步骤s5进一步包括：循环所有delaunay三角形，其三个节点上的交叉组成了一个局部交叉场；利用交叉场的连续，判断一个局部交叉场内是否存在奇点。7.根据权利要求6所述的多块结构网格奇点识别方法，其特征在于，所述步骤s5进一步包括：在局部交叉场中，三角形的三个顶点1、2、3以逆时针顺序排列，对应的交叉分别为θ1、θ2和θ3，则奇点的类型由下式计算，
式中，k是奇点的类型，
∆
θ
ij
=θ
j-θ
i
表示两个交叉之间的最小角度差，其范围是[-π/4，π/4]。8.根据权利要求1所述的多块结构网格奇点识别方法，其特征在于，所述步骤s6进一步包括：对于包含奇点的三角形，其顶点的坐标分别为(x1,y1)、(x2,y2)、(x3,y3)，奇点的坐标s(x
s
,y
s
)计算为对于类型k的奇点，共有k+4个方向；奇点方向的计算首先要确定一个初始方向β0，所述奇点的其它方向则计算为，对于初始方向β0，首先确定所处三角形中的交叉之差最小的边，所述边的中点求为β(x
β
,y
β
)，则β0即为矢量的方向，即式中，(x
s
,y
s
)和(x
β
,y
β
)分别是点s和β的坐标。

技术总结

本发明公开了一种基于Delaunay图和交叉场的奇点识别方法，该方法基于Delaunay图和交叉场，为生成高质量的四边形结构网格提供依据，只用到边界上的节点和添加的辅助点进行Delaunay三角化，在得到的Delaunay图中，仅利用这些节点上的交叉即可计算得到奇点的位置和方向，根据几何外形，可利用奇点进行多块结构网格划分；该方法算法简单，计算量小，能够辅助使用者划分高质量的多块结构网格。助使用者划分高质量的多块结构网格。助使用者划分高质量的多块结构网格。