一种LiDAR点云生成格网DEM的快速算法

提出一种LiDAR点云快速生成DEM的算法。该算法首先将原始点云文件转换为点云流文件;然后对点云流文件的每个区块采用逐点内插法进行Delaunay三角剖分;最后对生成的三角网流文件进行格网划分,对每个格网点内插生成规则格网DEM。将原始点云文件转换为流文件后,可以对点云数据分块处理,处理完一个分块后即可释放内存,解决了普通计算机处理海量点云数据内存不足、效力低下的问题。     

泰森多边形和狄洛尼三角网的林木空间格局分析

Voronoi图依据地物之间邻近关系对空间进行剖分,Delaunay三角网是Voronoi图的对偶图.文章以单株木为平面点构建Voronoi图和Delaunay三角网,Voronoi图多边形面积表示林木影响范围,Delaunay三角网中每个三角形边长表示对应林木之间距离.在岳阳平江福寿林场设置12块标准地进行试验,计算基于Voronoi图的角尺度、传统的角尺度、基于Delaunay三角网的集聚指数和Voronoi图多边形面积的变异系数,结果表明:这4个指数均能反映样地林木之间的空间分布,变异系数对空间均匀分布和聚集分布有较好的区分度.     

三维露天采场模型的生成算法

本文给出了一种基于约束Delaunay三角剖分的三维露天采场模型的生成算法.算法结合采场数据的特点,利用约束Delaunay三角剖分把台阶线、地表特征线等嵌入三角网,使生成的三维模型更接近实际采场,提高了露天采场三维模型的精度,增强了三维显示效果.通过精确的三维可视化显示,可以使矿山工作者形象直观地看到地形和采场布置,...     

Delaunay三角网的鄱阳湖水陆地形数据整合研究

针对如何提高水域的综合开发管理能力,实现水陆一体化地形整合的问题,该文在原有DEM格网数据整合的基础上,提出利用基于约束边Delaunay三角网方法进行水陆地形数据整合的方法,即利用迭代交换法实现约束线的嵌入,从而构建约束Delaunay三角网。以鄱阳湖为研究区域,以DEM格网数据和鄱阳湖岸线矢量数据为数据源,利用约束Delaunay三角网方法,创建基于岸线的Delaunay三角网,实现水陆地形无缝整合。实验结果表明,与利用DEM规则格网数据拼接方法进行比较分析,得出在岸线约束条件下构建的Delaunay三角网能更好地表达边缘处地形数据的整合,平滑效果较好。     

基于Delaunay三角剖分的多尺度POI提取技术研究与实现

简要概括了电子地图图面表达中多尺度POI分布的重要性,分析了Delaunay三角剖分算法和POI分级原则,提出了基于Delaunay三角剖分增量算法,添加三角网面积、边长及POI权重作为约束条件的多尺度POI提取技术,并在多城市电子地图制作中实践,验证了该方法的可行性。     

一种采用流计算的Delaunay三角网切块剖分算法

针对海量LiDAR点云Delaunay三角网剖分的时间与空间性能的矛盾问题,提出了一种采用切块的流计算Delaunay构网算法。首先利用三角网墙（DeWall）从点云上切割特定大小与形状的独立数据块,避免分治算法的深度递归与内存溢出;然后运用分治算法对切块剖分,并给出了切块边界错误三角形删除算法;重复上述过程完成子网剖分,并依据非耦合区域分解模式合并为最终三角网。引入流计算的思想,以进一步提高算法的空间性能。分析与实验表明:该算法占用了较低内存,并取得了接近为O（nlg（δ））（δ为一个切块点数,且δ≤n）的时间复杂度。     

带约束折线的平面散点集Delaunay三角剖分

首先将原始散点与约束点一起进行三角剖分,形成初始Delaunay三角网,然后再将各条约束线段通过局部更新,依次嵌入已存在的三角网中,从而生成带有约束折线的平面散点集的Delaunay三角剖分。该算法思路简捷,易于编程,生成的三角网形态优良。     

一种高阶Delaunay三角网生成算法

Delaunay三角剖分是构建数字地形模型的有效方法,但是该方法可能产生人工大坝和局部极小问题,使得地形模型不能很好地反映原始地形的真实面貌。本文在Delaunay三角网的基础上引入了高阶Delaunay三角网,并给出了一种高阶Delaunay三角网生成算法。实验表明,高阶Delaunay三角网能够有效地减少地形的局部极小数量,是建立数字高程模型的一种新方法。因此,采用高阶Delaunay三角网建立的地形模型更接近于实际地形。     

一种动态构建Delaunay三角网的算法

Delaunay三角剖分算法是构建数字高程模（DEM）的主要算法。在分析现有的Delaunay三角剖分的3种算法之后,指出现有算法存在的不足。并提出一种TIN的动态建模方法,利用分块技术来改进搜索方法,大大提高了Delaunay三角网的构建速度。实验结果表明,此算法和前面3种算法相比,效率有了很大提高。     

约束Delaunay三角剖分的“岛屿”类图斑符号填充

针对传统方法对“岛屿”类图斑进行符号填充会造成敏感区域符号布局不合理或符号空间冲突的问题，本文提出了一种约束Delaunay三角剖分的“岛屿”类图斑符号填充方法。首先，对“岛屿”类图斑对应的离散点群进行规则网格化和不规则三角剖分，用于计算等值点；然后，依据附加准则增加“凸”形和“凹”形附加点，顺次连接等值点和附加点作为Delaunay三角剖分的约束边界；最后，构建均匀变化的约束Delaunay三角网，在三角网内进行图元积分，填充“岛屿”类图斑符号。利用电子海图中岛屿边界点数据进行试验分析，与传统方法相比，本文方法填充的“岛屿”类图斑符号变化均匀，交互性较强，便于用户修改和切换，进行二次填充。试验结果表明，本文方法适用于“岛屿”类图斑的符号填充。     

网格总分并行式Delaunay三角网建模方法

针对大规模点云数据,提出了Delaunay三角网构建的一种算法,算法通过自适应网格空间分割,实现了海量点云数据的规模均衡网格化逻辑分割;对网格内的顶点按距中距离进行排序,通过各网格由外而内的插入法建立三角网;按先总后分的方式优先保障网格之间三角网的生成,避免了分治-综合建模算法复杂而低效的三角网整合过程;建立了网格的拓扑闭包检测机制,针对各个子网格适时启动独立并行的线程对余下的内部点按传统的拓扑插入算法进行独立建模,从而并行高效、由总到分地实现了海量点集数据的三角网建模工作,显著地提高了空间大数据的三角网建模能力。     

Delaunay三角形构网的分治扫描线算法

Delaunay三角网作为一种主要的DTM表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。     

散乱点云数据空间三角网构建方法的研究

点云数据三维建模主要是对目标物体的表面进行网格建模。三角形作为三维建模的基本表示元素,不仅性质简单,而且可以有效地表示物体表面复杂的几何属性。Delaunay三角网是当前使用最广泛的三角剖分方法,它能够最大限度地避免狭长三角形的产生,并且无论从何处开始建网都能保持网型的唯一性。本文在已有生长算法研究的基础上提出了一个新的算法:即在二维生长算法的基础上,利用空间三角形的法向量来进行第三点的搜索构建空间三角网。该算法的优点是:适合大量点云数据构建空间三角网、构建的空间三角网可以很好地反映出物体的表面特征。     

复杂矿体模型多域自适应网格剖分方法

针对轮廓线拼接法在复杂矿体建模时无法处理多域邻接特征的问题，应用Delaunay细分方法实现了一种适用于多域复杂矿体的网络剖分方法，不仅可以生成多域表面模型，还可以同时对不同域的矿体进行网格剖分，便于后期进行多域复杂矿体的有限元模拟。该方法通过约束Delaunay三角剖分来近似域和曲面，以及在Delaunay细分中确保对域的近似精度和对单元的网格质量。在约束Delaunay三角剖分的基础上，通过多标签算法对子域进行封装，并对中间域进行分离或通过距离场对中间域进行拟合，修改多域多面体的预测构造方法，实现了对多域多面体的自适应网格剖分方法。对河北省北洺河铁矿复杂矿体建模的试验结果表明，该方法除了可以生成无缝、连续的多域模型之外，通过网格优化还可以生成高质量的四面体和三角网格，避免轮廓线拼接法大量退化和奇异三角形的存在。同时该方法在逆向工程、有限元分析、科学计算可视化等领域中也都具有重要的应用价值。     

A method for the extraction of partition lines from long and narrow patches that account for structural features

The extraction of partition lines for long and narrow patches (LN patches) is an important yet difficult problem in the generalization of thematic data. When current methods are used to process polygons with irregular shapes or complex branch convergence zones, the extracted line structural features tend to be inaccurate and topologically erroneous. In this article, we propose an improved partition lines extraction algorithm of constrained Delaunay triangulation to counter these issues. The proposed method aims to maintain consistency between the extracted line structure characteristics and the actual object structure, especially for complex branch convergence zones. First, we describe three types of aggregation patterns (Type A, B, and C aggregation zones) that occur in partition line extractions for LN patches of complex branch convergence zones using Delaunay triangulation. Then, a partition line extraction algorithm that accounts for the direction between the edges of triangles and the distance of nodes in aggregation zones is proposed. Finally, we test our method for a dataset relating to Guizhou Province, China. Compared with the current method that uses quantitative indicators and visualization, the results indicate that our method not only has applicability for simple situations but also is superior for preserving structural features of complex branch convergence zones.     

基于边界结点的GPS控制网边界异步环自动搜索算法

针对某些GPS数据处理软件搜索异步环不全的问题,本文提出了一种简单有效的基于边界结点的GPS控制网异步环自动搜索的算法。这种算法借鉴了Delaunay三角网的思想,通过建立Delaunay三角网,找出三角网上所有具有3条或3条以上边界边的边界结点,并依次搜索有边界结点的边界异步环和无边界结点的边界异步环,针对边界异步环,根据不同的观测时段数给出所有的基线组合,最后计算边界异步环的闭合差;并且根据此算法编写了软件,最后利用某县GPS平面控制网验证了该方法的可行性。     

一种基于最优三角剖分的多分辨率地表描述结构

在Guibas平面剖分算法的基础上,采用一种称之为Delaunaypyramid的塔型分层结构模型来近似描述二维半地形表面,该模型能够记录离散高程点数据集的每个子集在XOY平面的最优三角剖分,对于地形数据压缩和多细节层次化描述有很大的便利。同时文中也分析了采用这种结构的内存开销和时间复杂度,讨论了离散数据点定位的方法,并运用该结构交互生成三维地形。     

基于MapX Mobile的等值线绘制方法研究

在PDA上绘制等值线是移动GIS的一项重要内容。本文介绍了以MapX Mobile控件为图形平台,在Embedded Visual C++4.0环境下编程绘制等值线的方法,包括用逐点插入法生成Delaunay三角网,基于三角网的等值线追踪方法,及等值线图的显示、放大、缩小、漫游、属性查询等。并将其移植到PDA环境下,以实际离散高程点为实验数据来绘制等高线图,验证了上述方法的可行性。