基于四叉树索引构建TIN的高效合成算法

不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。     

二维Delaunay三角网局部更新:点插入与点删除

二维Delaunay三角网的局部更新在地学分析、道路CAD、城市规划等领域有着广泛的用途,点插入和点删除则是其中最重要、最基本的操作。该文针对原有逐点插入法和凸耳权值点删除算法存在的不足,利用动态包围三角形和特征三角形分别对其进行改进,在设计的具有拓扑关系Delaunay的三角网数据结构基础上,实现Delaunay三角网的快速局部更新,且使之满足Delaunay特性。最后通过模拟实验验证了算法的正确性和高效性。     

二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

等高线约束的Delaunay三角网在土石方量计算中的应用

土石方量计算是工程建设的重要步骤,其计算精度是提高工程质量的首要问题。针对利用无约束不规则三角网计算土石方量时存在的计算精度问题,该文利用三维激光点云数据,根据约束Delaunay三角网的构建原理,探讨了基于等高线约束的Delaunay三角网方法在土石方量计算中的应用。首先,以土石方的等高线作为约束线,利用迭代算法对无约束不规则三角网进行剖分,构建等高线约束Delaunay三角网,并进行土石方量计算。然后,将计算结果与无约束不规则三角网、方格网法计算结果进行对比与误差分析,验证了该方法的计算精度,为基于三维点云数据的土石方量精确计算提供了参考。     

基于线性和岛屿约束的Delaunay三角网构建算法研究

针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足.算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现.     

二维Delaunay三角网的任意点插入算法研究

针对目前各种点插入算法的不足,提出一种二维Delaunay三角网任意点插入算法。首先基于凸壳区分点的位置,并利用三角形面积坐标、重心和点与有向线段关系三者构建的融和算法搜索插入点所在三角形,然后通过构建和优化新三角形完成点的插入,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

一种高准确度的约束Delaunay三角网生成算法研究

约束线段的嵌入是CDT两步法的关键步骤之一,目前该方面的研究还不够完善,主要忽视了影响区域是凹多边形和影响区域内包含悬挂点的情况.该文研究带有约束条件的Delaunay三角网的生成问题,考虑了约束线段影响区域的特殊情况,采用递归割耳法嵌入约束线段,先将影响区域调整为简单多边形,再递归寻找并割去多边形的耳,最终将影响区域重新三角剖分.该方法可有效提高约束DIelaunay三角网的质量.     

Delaunay三角网约束的Harris-SURF图像匹配算法

Harris算法提取的角点定位精度高,但不具尺度不变性,SURF算法虽具有尺度不变性和旋转不变性,但提取的特征点并非视觉角点。针对此问题,该文提出一种Delaunay三角网约束下的Harris-SURF图像匹配方法。首先,采取阈值评估策略对图像进行SURF粗匹配,利用RANSAC算法进行粗差剔除,得到的匹配点用于构建Delaunay三角网;然后以相似三角形作为约束,将其作为Harris特征点精匹配的限制区域,提高Harris点匹配的可靠性。实验表明,该算法具有匹配准确率高、鲁棒性较好等特点,对无人机影像的匹配效果明显优于其他算法。     

基于众源轨迹数据的道路中心线提取

从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而,由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题,提出一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网,根据整体长边约束准则删除长边以提取道路面域多边形;然后对道路面多边形二次构建Delaunay三角网,提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验,将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10%以上。另外,以复杂环形道路为例,证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此,该方法不仅适合大数据处理、结果精度高,且算法成熟、易于实现。     

一种基于TIN的地形剖面线生成算法

在目前已有基于规则格网(Grid)生成地形剖面线的基础上，提出了一种适用于不规则三角网(TIN)的剖面线生成算法。该算法充分利用TIN中各三角形间存在的拓扑关系，实现了与剖面线相交三角形的快速搜索，大大提高了算法的执行效率。由于地形简化后的TIN仍保留三角形间的拓扑关系，该剖面线生成算法还适用于多分辨率的海量TIN数据。     

A TIN compression method using Delaunay triangulation

This study introduces a new Triangulated Irregular Network(TIN) compression method and a progressive visualization technique using Delaunay triangulation. The compression strategy is based on the assumption that most triangulated 2.5-dimensional terrains are very similar to their Delaunay triangulation. Therefore, the compression algorithm only needs to maintain a few edges that are not included in the Delaunay edges. An efficient encoding method is presented for the set of edges by using vertex reordering and a general bracketing method. In experiments, the compression method examined several sets of TIN data with various resolutions, which were generated by five typical terrain simplification algorithms. By exploiting the results, the connecting structures of common terrain data are compressed to 0.17 bits per vertex on average, which is superior to the results of previous methods. The results are shown by a progressive visualization method for web-based GIS.     

DEM内插方法与可视性分析结果的相似性研究

以实际采样的散点数据为原始数据,利用反距离权、样条函数、克里格、自然邻点内插、TIN内插5种内插方法生成规则格网DEM,并对其可视性分析结果进行对比分析和相关分析,揭示不同内插方法对可视性分析结果的影响规律和可视性分析对内插方法的敏感程度。结果表明,可视性分析对内插方法比较敏感,不同的内插方法会得到不同的可视性分析结果,其中相关程度最强的是样条函数内插和克里格内插、自然邻点内插和TIN内插。     

基于TIN数据三维地质体的折剖面切割算法

为有效分析地质模型的内部结构,研究直接利用折切面对模型数据进行几何切割的算法。该算法面向基于TIN数据表达的三维地质体,包括"折剖面的生成"和"被切割地质体的拆分"两大关键步骤;采用向二维平面投影的策略,将复杂的切割转化为交线的快速连接、三角形重新剖分和点与多边形的包含测试等简单操作。对不同复杂程度的三维地质模型进行切割实验,发现化繁为简和二维投影策略极大地提高了算法效率。     

Wavelet triangulated irregular networks

GIS applications have recently begun to emerge on the Internet. The management of three-dimensional geographic datasets in this distributed environment poses a particularly challenging problem, which highlights the need for a good data representation. This paper presents a new multiresolution data representation: the Wavelet Triangulated Irregular Network (WTIN). Compared to the traditional cell-based Digital Elevation Model (DEM) format and the Triangulated Irregular Network (TIN) format, it is more compact and suitable for scalable distributed GIS services. This format is based on the second-generation wavelet theory and is specially designed for geographical height field data. The modified Butterfly scheme is used for constructing the wavelet transform. For every point in the geographic surface, only a single wavelet coefficient is used, which makes the final data representation very efficient and easy to compress. Because the transform used in the data representation is a linear filter operation, the computational efficiency is better than other multiresolution data formats for terrain surfaces. Results from numerical experiments on real data are given to demonstrate that the proposed data representation can be efficiently implemented. The results show that the proposed WTIN data format can provide multiresolution data sets, which achieve significant compression while preserving geographical features. The quality is found to be quite acceptable for geographical terrain representation.     

Change detection for 3D vector data: a CGA-based Delaunay–TIN intersection approach

In this paper, conformal geometric algebra (CGA) is introduced to construct a Delaunay–Triangulated Irregular Network (DTIN) intersection for change detection with 3D vector data. A multivector-based representation model is first constructed to unify the representation and organization of the multidimensional objects of DTIN. The intersection relations between DTINs are obtained using the meet operator with a sphere-tree index. The change of area/volume between objects at different times can then be extracted by topological reconstruction. This method has been tested with the Antarctica ice change simulation data. The characteristics and efficiency of our method are compared with those of the Möller method as well as those from the Guigue–Devillers method. The comparison shows that this new method produces five times less redundant segments for DTIN intersection. The computational complexity of the new method is comparable to Möller’s and that of Guigue–Devillers methods. In addition, our method can be easily implemented in a parallel computation environment as shown in our case study. The new method not only realizes the unified expression of multidimensional objects with DTIN but also achieves the unification of geometry and topology in change detection. Our method can also serve as an effective candidate method for universal vector data change detection.     

Dynamic hybrid terrain representation based on convexity limits identification

Hybrid digital terrain models combine terrain data with different topologies and resolutions. Cartographic digital terrain models are typically composed of regular grid data that can be locally refined by adding a Triangulated Irregular Network (TIN) that represents morphologically complex terrain parts. Direct rendering of both datasets to visualize the digital terrain model generates discontinuities, as the meshes are disconnected. The utilization of complete/partial precomputed tessellation solutions solves the problem of quality, but limits the applicability of the representation to models with a fixed relative position between datasets. In this paper, we present a new scheme for hybrid terrain representation that permits the dynamic generation of the adaptive tessellation required to join the grid and TIN models. Our proposal permits the dynamic modification of the relative position between datasets. This increases the representation capabilities for those applications where this property is interesting as, for example, urban and landscape planning applications. The algorithm we propose is based on the identification of convex areas on the TIN and the efficient generation of triangles to join the models based on this convex structure. As a result, high quality models without discontinuities are obtained, increasing the flexibility of previous solutions based on fixed precomputations.     

三维含拓扑地质剖面三角剖分可视化研究

三维剖面是地质对象表达和地质问题分析中最基本和最常用的数据。该文分析三维复杂地质折剖面可视化存在的问题,并提出展开剖分算法。该方法保证了各点之间的水平距离与剖面拓扑关系不变,能够对由"多边形-弧段-结点"矢量结构构成的三维折剖面进行有效剖分。在此基础上实现了三维剖面的可视化,尤其合理解决了纹理映射中的纹理变形与重复接缝等问题。