融合长边阈值约束Delaunay三角网的高密度测深数据S-102格网化插值方法

《Journal of Marine Science and Engineering》：A High-Density Bathymetric Data Model and System Construction Approach Integrated with S-100 for Unmanned Surface Vessel Intelligent Navigation Jianan Luo, Zhichen Liu, Haifeng Tang, Chenchen Jiao, Xiongfei Geng and Hua Guo

　　

摘要(Abstract)：研究人员提出一种面向国际海道测量组织(International Hydrographic Organization, IHO) S-102标准的高密度测深数据格网化(Gridding)与插值方法。该方法在Delaunay三角剖分(Triangulation)基础上引入长边阈值(Long-Edge Threshold / Lthreshold)约束模型，通过计算四点行列式符号判断Delaunay空圆特性(In-Circle Test)并执行Edge Flip优化，再剔除最大边长超过设定阈值的狭长伪三角形(Pseudo-Triangle)，使三角网边界由初始凸包(Convex Hull)向内收缩以贴合实际非凸测区物理边界。经约束三角网(TIN)采用空间索引定位网格节点所在三角面片，通过线性内插(Linear Interpolation / Bilinear Interpolation)生成规则格网矩阵。实验表明该方法可有效抑制无数据区域的伪地形(Pseudo-Terrain)外推，确保S-102数字水深模型(Digital Bathymetric Model, DBM)仅在有效覆盖范围内插值，提升智能航行(Intelligent Navigation)应用的数据真实性与安全性。

论文解读：融合长边阈值约束Delaunay三角网的高密度测深数据S-102格网化插值方法

一、研究背景与意义

S-102是国际海道测量组织(IHO)制定的用于电子航海图(ECDIS)增强型水深产品——S-102表面格网(S-102 Surface Grid / Digital Bathymetric Model, DBM)的标准规范。传统测深数据处理多采用Delaunay三角剖分生成不规则三角网(Triangulated Irregular Network, TIN)后重采样为规则格网，但标准Delaunay算法生成的初始凸包(Convex Hull)必然包含所有离散测深点(Sounding Points)的最小凸多边形，当实际海洋测区为非凸形态（如锯齿海岸线、未测岛屿内部）时，凸包会跨越无数据区域产生大跨度三角形，导致格网化插值时在无测深覆盖区生成虚假"伪地形(Pseudo-Terrain)"，危及智能导航(Intelligent Navigation / e-Navigation)安全。现有方法缺乏针对边界伪三角形的自动识别与裁剪机制。为此，研究人员以《Journal of Marine Science and Engineering》(JMSE)为发表平台，提出一种集成长边阈值约束(Long-Edge Threshold Constraint Model)的改进Delaunay三角网构建与高密度测深数据S-102格网化插值方法，旨在数学上保证插值限定于有效测区范围。

二、主要关键技术方法

研究人员采用实海域测深点云(Bathymetric Sounding Point Cloud)数据集为样本来源。关键技术步骤包括：(1)Delaunay三角剖分初始化，对共圆判定使用4×4行列式In-Circle Test——det(H)=|x_ay_ax_a²+y_a²1; x_b… x_d…|>0则执行Edge Flip；(2)长边阈值约束模型——设定三角形三边集合E_T={l₁,l₂,l₃}，取l_max⁽ⁱ⁾=max(E_Ti)，预设L_threshold为测深点平均间距的3~5倍，若l_max⁽ⁱ⁾≤L_threshold保留否则删除，实现凸包边界内缩拟合实际物理边界；(3)有效三角网??_valid通过空间索引(Spatial Indexing，如格网或四叉树)快速定位目标格网点G(x_g,y_g)所属三角形T，基于三顶点(x_1,2,3,y_1,2,3,z_1,2,3)进行平面方程线性内插求取网格节点水深值z_g，最终按S-102标准输出规则格网矩阵。

三、研究结果（按论文小标题结构）

2.2.1 高密度三角网构建与长边阈值约束拓扑优化(High-Density Triangulated Network Construction Integrating Long-Edge Threshold Constraints)

研究人员首先构建初始Delaunay三角网??_Delaunay，遍历所有三角形T_i计算其三边最大边长l_max⁽ⁱ⁾=max{E_Ti}。通过In-Circle Test行列式判断并做Edge Flip满足Delaunay空圆准则后，应用长边阈值判断：若l_max⁽ⁱ⁾≤L_threshold(L_threshold=k×平均点距，k=3~5)则保留该三角形(Keep)，若l_max⁽ⁱ⁾>L_threshold则标记为删除(Delete)。被删除三角形主要来自初始凸包跨域无数据区的狭长大边，移除后更新拓扑关系形成有效三角网??_valid。结论：长边阈值约束实现了初始凸包向实际非凸物理边界的内缩修剪，从几何上排除跨无数据区三角形，从根源抑制伪地形生成。

2.2.2 高密度测深数据插值及格网矩阵生成(High-Density Bathymetric Data Interpolation and Grid Matrix Generation)

基于约束后的有效TIN，研究人员采用空间索引算法对每个S-102目标格网点G(x_g,y_g)快速查找其所在三角形T（顶点P₁(x₁,y₁,z₁)、P₂(x₂,y₂,z₂)、P₃(x₃,y₃,z₃)），利用三角形平面方程通过重心坐标或双线性内插计算网格节点水深值z_g，按S-102标准分辨率与坐标系组织为规则格网矩阵。结论：结合前步约束TIN的局部插值确保格网化仅发生在有效测深覆盖范围内，生成的S-102格网数据无外推伪值。

四、讨论与结论总结

研究人员指出，标准Delaunay三角剖分的凸包局限在非凸测区引发大跨度无依据插值，是本研究中引入长边阈值约束的根本动因。所提方法通过对三角形最大边的阈值判别，将几何修剪(Geometric Pruning)嵌入三角网构建流程，使外边界动态收缩匹配实际测深点云分布范围。实验验证该方法可自动识别并去除无效边三角形，保证S-102网格数据插值严格限于有效调查覆盖区。

研究结论：融合长边阈值约束的Delaunay三角网构建方法结合空间索引线性内插，可生成符合IHO S-102标准的数字水深模型(DBM)，有效消除凸包效应导致的无数据区伪地形外推，保障智能航行应用中海深数据的真实性与航行安全性，为高精度S-102产品自动化生产提供了可行数学模型与算法框架。