(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111418981.8 (22)申请日 2021.11.26 (71)申请人 中国石油大 学 （华东） 地址 266580 山东省青岛市黄岛区长江西 路66号 (72)发明人 宋弢　王家荣　徐丹亚　魏伟　 韩润生　李颖　 (51)Int.Cl. G06K 9/62(2022.01) G06N 20/00(2019.01) (54)发明名称 基于无监督机器学习的海洋非结构网格自 动剖分优化方法 (57)摘要 本发明公开了一种基于无监督机器学习的 全球海洋非结构化网格自动剖分与优化方法， 所 述方法包括以下步骤： 步骤一： 将全球海洋深度 数据中每一经纬度对应的海洋深度数据提取并 画出等深线图。 将不同深度等深线坐标集合进行 分类， 归类出陆地海岸线、 浅海区、 深 海区等等深 线坐标集合。 步骤二： 在不同等深线范围内， 依据 海洋深度越深， 产生随机点的密度越小的原则， 在不同深度的海域内产生不同密度的随机点。 步 骤三： 将步骤二中的随机点进行Delau nay三角剖 分形成非结构网格。 步骤四： 优化非结构网格： 利 用数学几何原理对非结构网格进行初步优化， 然 后利用基于 K‑Means聚类算法对非结构化网格进 行再次优化。 使网格中三角形更趋近于正三角 形， 网格质量 提升。 权利要求书2页 说明书7页 附图1页 CN 114417951 A 2022.04.29 CN 114417951 A 1.基于无监督机器学习的海洋非结构网格自动剖分优化方法， 其特征在于， 所述方法 包括以下步骤： 步骤一： 全球海洋深度数据预处理： 将数据中每一经纬度对应的海洋深度数据提取并 画出等深线图。 依据全球海洋深度数据提取出不同深度等深线坐标集合， 将不同深度等深 线坐标集合进 行分类， 归类出陆地海岸线、 浅海区、 较深海区、 深海区等深线坐标集合。 步骤 二： 产生随机点： 在不同等深线 范围内， 即在不同深度的海域内， 依据海洋深度越深， 产生随 机点的密度越小的原则， 在不同深度的海域内产生不同密度的随机点。 等深线上 的点依据 固定间隔取点的方式获取点坐标集。 步骤三： 产生非结构网格： 利用Delaunay三角化算法将 步骤二中海域内生成的随机点和等深线上间隔取点获取的点进行Delaunay三角剖分形成 非结构网格， 并将海洋范围外的非结构网格去除。 步骤四： 优化非结构网格： 利用数学几何 原理和K‑Means聚类算法对非结构化网格进 行优化， 使网格中三角形更趋近于正三角形， 三 角形形状因子更趋 近于1， 狭长三角形 数量减少， 网格质量 提升。 2.如权利要求1所述的方法， 其特征在于， 三角剖分指假设V是二维实数域上的有限点 集， 边e是由点集中的点作为端点构成的封闭线 段,E为e的集合。 那么该点集V的一个三角剖 分T＝(V,E)是一个平面图G， 该平面图满足条件： 除了端点， 平面图中的边不包含点集中的 任何点。 没有相交边。 平面图中所有的面都是三角面， 且所有三角面的合集是散点集V的凸 包。 本实验中运用的三角剖分是Delaunay三角剖分， 即如果点集V的一个三角剖分T只包含 Delaunay边， 那么该三角剖分为Delaunay三角剖分。 其中Delaunay边为假设E中的一条边e (两个端点为a,b)， e若满足下列条件， 则称之为Delaunay边： 存在一个圆经过a,b两点， 圆内 不含点集V中任何其 他的点。 Delaunay三角网是唯一的(任意四点不能共圆)， 在Del aunay三角形网中任一三角形的 外接圆范围内不会有其它 点存在。 在散点集可能形成的三角剖分中， Delaunay三角剖分所 形成的三角形的最小角最大。 从这个意义上讲， Delaunay三角网是 “最接近于规则化的 “的 三角网。 具体的说是指在两个相 邻的三角形构成凸四边形的对角线， 在相互交换后， 六个内 角的最小角不再增大。 采用Bowyer ‑Watson算法进行delaunay三角剖分： 首先构造一个超级三角形， 包含所有 散点， 放入三角形链表。 然后将点集中的散点依次插入， 在三角形链表中找出外接圆包含插 入点的三角形(称为该点的影响三角形)， 删除影响三角形 的公共边， 将插入点同影响三角 形的全部顶点连接起来， 完成一个点在Delaunay三角形链表中的插入。 接着根据优化准则 对局部新形成的三角形优化。 将形成的三角形放入Delaunay三角形链表。 最后循环执行上 述第2步， 直到所有散点插 入完毕。 3.如权利要求1所述的方法， 其特征在于， 非结构网格生成后 为去掉所有在海洋范围外 的三角网格， 首先将三角网格中所有三个点均在陆地轮廓上的三角形的三个顶点进行提 取， 然后将以这三个点组成的三角形从三角组合数组中去除。 再计算每个三角形 的重心坐 标， 若重心位于海岸线轮廓范围内， 则将此三角形从三角组合数组中去除。 4.如权利 要求1所述的方法， 其特征在于， K ‑Means算法的主要思想是： 在给定K值和K个 初始类簇中心点的情况下， 把每个点分到离其最近的类簇中心点所代表的类簇中， 所有点 分配完毕之后， 根据一个类簇内的所有点重新计算该类簇的中心点， 然后再迭代的进行分权　利　要　求　书 1/2 页 2 CN 114417951 A 2配点和更新类簇中心点的步骤， 直至类簇中心点的变化很小， 或者达 到指定的迭代次数。 假定给定数据样本X， 包含了n个对象， X＝{ X1， X2， X3， ...， Xn}， 其中每个对象都具有m个 维度的属性。 Kmeans算法的目标是将n个对象依据对象间的相似性聚集到指定的k个类簇 中， 每个对象属于且仅属于一个其到类簇中心距离最小的类簇中。 对于Kmeans， 首先需要初 始化k个聚类中心{C1， C2， C3， ...， Ck}， 1＜k＜n， 然后通过计算每一个对象到每一个聚类中 心的欧式距离， 如下式所示 上式中， Xi表示第i个对象1≤i≤n， Cj表示第j个聚类中心， 1≤j≤k， Xit表示第i个对象 的第t个属性1≤t≤m， Cjt表示第j个聚类中心的第t个属性。 依次比较每一个对象到每一个 聚类中心的距离， 将对象分配到距离最近的聚类中心的类簇中， 得到k个类簇{S1， S2， S3， ...， Sk}.Kmeans算法用中心定义了类簇的原型， 类簇中心就是类簇内所有对象在各个维 度的均值， 其计算公式如下 式中， Cl表示第l个聚类的中心， 1≤l≤k， |Sl|表示第l个类簇中对象的个数， Xi表示第l 个类簇中第i个对象， 1≤i≤|Sl|。 K‑Means算法收敛速度快， 聚类效果较优可且解释度比较强。 5.如权利要求1所述的方法， 其特征在于， 首先使用数学几何原 理对非结构网格进行初 步优化， 对于非结构化网格中的每一个狭长三角形ABC， 找到以最长边AB的长度为边长， 最 长边上两个顶 点A、 B为其中两个顶点的正三角形的第三个顶 点D的位置， 记 为目标点位置D， 将最大内角对应的顶点C 向目标点D方向移动一个步长的距离到点E， 直到所有的狭长三角 形均被调整记为 一次迭代。 如此 经过多次迭代， 完成非结构化网格的初步优化。 6.如权利要求1所述的方法， 其特征在于， 假定存在n个点均匀分布在一个聚类中心周 围， 将这n个点与聚类中心相连则会形成n个三角形， 若要保证三角形内角大于30度， 则n的 取值范围为 4<＝n<＝11。 则我们使用K ‑Means聚类算法将所有点以n个点聚为一类的方式进行聚类， 获取每一个 类的聚类中心， 依次判断每一个聚类中心的加入是否可以使三角网格中狭长三角形的数量 减少， 若可以， 则将此聚类中心加入点集。 通过一定时间的迭代， 最终所有聚类中心的加入 都不能使三角网格中狭长三角形的数量减少， 则视为达 到优化瓶颈。 将最终的点集中每一个点依次删除， 并判断三角网格中狭长三角形的数量是否减少， 若减少则从点集中删除此点， 若不能减少， 则保留此点。 经过多次迭代直至每一个点的删除 都不能使三角网格中狭长三角形 的数量减少， 则视为删减清洗完毕， 并将最终得到的点集 保存。 该算法可以在对三角网格进行优化的同时保障点分布的相对密度保持不变， 保障海洋 深度不同非结构化网格密度不同这 一特征。权　利　要　求　书 2/2 页 3 CN 114417951 A 3