并行化多流向策略的栅格河网提取算法

流域栅格河网提取是数字地形分析的一个重要应用。为减少数字高程模型(DEM)预处理而产生的伪河道及平行河道,提出基于并行化多流向策略的栅格河网提取算法。通过水流传输矩阵模拟水量的自然流动过程,可直接应用于原始DEM。从河网空间形态和算法运行效率两方面与串行MFD算法、R&N算法及D8算法进行对比,结果表明,多流向策略得到的河网与实际地形形态更加吻合,使用并行策略后,算法的效率比也较其他算法有明显提升。     

An enhanced approach for surface flow routing over drainage‐constrained triangulated irregular networks

The accuracy and efficiency of the simulations in distributed hydrological models must depend on the proper estimation of flow directions and paths. Numerous studies have been carried out to delineate the drainage patterns based on gridded digital elevation models (DEMs). The triangulated irregular network (TIN) has been increasingly applied in hydrological applications due to the advantages of high storage efficiency and multi‐scale adaptive performance. Much of the previous literature focuses mainly on filling the depressions on gridded DEMs rather than treating the special cases in TIN structures, which has hampered its applications to hydrological models. This study proposes a triangulation‐based solution for the removal of flat areas and pits to enhance the simulation of flow routing on triangulated facet networks. Based on the drainage‐constrained TIN generated from only a gridded DEM by the compound point extraction (CPE) method, the inconsistent situations including flat triangles, V‐shape flat edges and sink nodes are respectively identified and rectified. The optimization algorithm is an iterative process of TIN reconstruction, in which the flat areas are generalized into their center points and the pits are rectified by embedding break lines. To verify the proposed algorithm and investigate the potential for flow routing, flow paths of steepest descent are derived by the vector‐based tracking algorithm based on the optimized TIN. A case study of TIN optimization and flow path tracking was performed on a real‐world DEM. The outcomes indicate that the proposed approach can effectively solve the problem of inconsistencies without a significant loss in accuracy of the terrain model.     

基于数字高程模型的混合流向算法

从数字高程模型提取的汇水网络和汇水区等信息是分布式水文模型及应用分析的基础参数,基于地表汇水模拟的算法是提取该类信息的主要方法,其中,水流方向的确定对提取结果有着直接的影响。单流向算法因其易于实现、易于确定上游汇水区等特性,得到了广泛应用,然而单流向算法在坡度平缓区域会产生不自然的平行径流,能模拟地表水流分散径流特点的多流向算法可以在一定程度上避免此问题,但多流向算法使得不同区域的汇水单元可能存在交叉。本文结合两类流向算法各自的优点和适用性,设计实现了一种混合流向算法,以期在不同的地形条件下模拟得到更加合理的水流分配。首先,使用基于模板的形态检测方法,在给定阈值的基础上,对数字地形进行了分类,DEM被划分为山谷、山脊、鞍部、缓坡和陡坡5类。对陡坡、山谷和山脊区域运用单流向算法;对缓坡和鞍部区域采用多流向算法确定径流方向并进行水量分配。本文选取了黄土地貌和中低山丘陵的两个流域作为研究区,利用并采用了30 m和90 m两个分辨率的DEM。本文研究将混合流向算法与现有其他算法的结果进行比较。相比于多流向算法,该算法结果中的分散效应受到明显的抑制,相比于单流向算法,非自然的平行径流也大幅减少。同时,混合流向算法在较大分辨率DEM上（30 m）改进效果更加明显。     

Optimal Routefinding with Unlimited Possible Directions of Movement

Finding optimal paths through raster databases is limited by the very nature of the raster data itself. This limitation restricts the possible directions of movement through the database from the infinite possibilities found in the real world to a finite number of possibilities defined by the cell‐to‐cell movement that characterizes raster databases. A Triangulated Irregular Network (TIN)‐based alternative optimization model that allows unlimited possible directions of movement is presented. While not without its own limitations, this new approach offers a viable alternative to raster‐based optimal routefinding.     

基于DEM的平缓地区水系提取和流域分割的流向算法分析

本文以地势较为平坦的秦淮河流域为实验样区,以高精度DEM(5m分辨率)和地形图水系为基础数据,对比分析了单流向算法(D8算法)、多流向算法(Dinf法)以及添加数字化河道信息后的单流向算法(AgreeD8算法)3种算法下水系提取和流域分割的结果。实验结果表明,提取得到的水系更逼近于实际河网,该算法既有效提高了水系提取和流域分割的精度,又保留了D8算法模型简单、稳定性强、运行效率高等优点。     

数字建筑模型整体投影真正射影像制作中的遮蔽检测方法

为解决城市大比例尺真正射影像制作问题,提出了一种数字建筑模型（digital building model,DBM）整体投影遮蔽检测方法。该方法利用DBM表面以矢量三角面存储和平面图形投影内部栅格互不遮蔽的特点,首先以三角面为单元对整个建筑物进行正射投影得到房顶多边形;然后进行透视投影得到整个建筑物在像方的成像多边形,通过数字高程模型（digital elevation model,DEM）投影迭代算法得到该建筑物在传统正射影像上的成像多边形,两者求差集得到建筑物的遮蔽区域物方多边形;最后选取最优辅助影像对遮蔽区域进行纹理补偿,制作出真正射影像。实验结果表明,该方法能够快速准确地检测出影像遮蔽区域,为生成高质量真正射影像提供了保障和前提。     

Drainage skeletonization from flow-accumulated area without the use of threshold

This study presents a method of automatic drainage skeletonization from flow-accumulated area without the use of threshold which conserves drainage geometry at chosen digital elevation model (DEM) scale. To get all possible drainage at the chosen scale, stream order raster is generated by incorporating flow accumulation and flow direction raster derived from corresponding DEM. This allows generation of drainage network without the use of threshold. Resultant stream order raster, termed as raw stream order raster (RSOR), is tested against threshold defined stream order raster to evaluate its efficiency. Use of RSOR allows extraction of stream heads to greater stream head extent. Again, DEM downscaling takes care of overestimation in number of streams. So, the proposed technique is effective in controlling two basic aspects of drainage characteristics – stream number and extent. In our case, drainage estimated from re-sampled medium-scale DEM has the closest matching with that of the reference topographical map.     

The isotropic organization of DEM structure and extraction of valley lines using hexagonal grid

The automatic extraction of valley lines (VLs) from digital elevation models (DEMs) has had a long history in the GIS and hydrology fields. The quality of the extracted results relies on the geometrical shape, spatial tessellation, and placement of the grids in the DEM structure. The traditional DEM structure consists of square grids with an eight‐neighborhood relationship, where there is an inconsistent distance measurement between orthogonal neighborhoods and diagonal neighborhoods. The directional difference results in the extracted VLs by the D8 algorithm not guaranteeing isotropy characteristics. Alternatively, hexagonal grids have been proved to be advantageous over square grids due to their consistent connectivity, isotropy of local neighborhoods, higher symmetry, increased compactness, and more. Considering the merits above, this study develops an approach to VL extraction from DEMs based on hexagonal grids. First, the pre‐process phase contains the depression filling, flow direction calculation, and flow accumulation calculation based on the six‐neighborhood relationship. Then, the flow arcs are connected, followed by estimating the flow direction. Finally, the connected paths are organized into a tree structure. To explore the effectiveness of hexagonal grids, comparative experiments are implemented against traditional DEMs with square grids using three sample regions. By analyzing the results between these two grid structures via visual and quantitative comparison, we conclude that the hexagonal grid structure has an outstanding ability in maintaining the location accuracy and bending characteristics of extracted valley networks. That is to say, the DEM‐derived VLs based on hexagonal grids have better spatial agreement with mapped river systems and lower shape diversion under the same resolution representation. Therefore, the DEMs with hexagonal grids can extract finer valley networks with the same data volume relative to traditional DEM.     

一种面向海量数字高程模型数据的洪水淹没区快速生成算法

常见种子点填充算法在实现DEM数据下的洪水淹没区生成时,具有难以处理大数据量以及过多的递归计算易导致算法效率较低等缺点。针对此问题,本文提出一种面向海量DEM数据的洪水淹没区生成算法分块压缩追踪法,该算法采用条带分块和实时栅格压缩存储技术,以解决海量地形数据下的淹没分析计算问题。最后,通过将本算法与常见种子点填充算法和分块种子点填充算法进行了对比测试,实验结果表明本算法不仅较好地解决了海量DEM数据下的洪水淹没区生成问题,与常规种子点填充算法和分块种子点填充算法相比亦具有较高的计算效率。     

Fast Image‐Space Silhouette Extraction for Non‐Photorealistic Landscape Rendering

Landscape illustration, a core visualization technique for field geologists and geomorphologists, employs the parsimonious use of linework to represent surface structure in a straightforward and intuitive manner. Under the rubric of non‐photorealistic rendering (NPR), automated procedures in this vein render silhouettes and creases to represent, respectively, view‐dependent and view‐independent landscape features. This article presents two algorithms and implementations for rendering silhouettes from adaptive tessellations of point‐normal (PN) triangles at speeds approaching those suitable for animation. PN triangles use cubic polynomial models to provide a surface that appears smooth at any required resolution. The first algorithm, drawing on standard silhouette detection techniques in surface meshes, builds object space facet adjacencies and image space pixel adjacencies in the graphics pipeline following adaptive tessellation. The second makes exclusive use of image space analysis without referencing the underlying scene world geometry. Other than initial pre‐processing operations, recent advances in the OpenGL API allow implementations for both algorithms to be hosted entirely on the graphics processing unit (GPU), eliminating slowdowns through data transfer across the system memory bus. We show that both algorithms provide viable paths to real‐time animation of pen and ink style landscape illustrations but that the second demonstrates superior performance over the first.     

基于水流扩展思想的网络空间Voronoi图生成

Voronoi图是地理空间设施分布特征提取的重要几何模型,基于不同的空间距离概念可建立不同的Voronoi图。本研究顾及城市网络空间中设施点的服务功能及相互联系发生于网络路径距离而非传统的欧式距离的事实,针对网络空间Voronoi图模型,建立一种网络空间Voronoi图生成的栅格扩展算法。首先对图结构的边目标剖分为细小的线性单元,称作网络空间的栅格化,引入水流扩展思想,将事件点发生源视为“水源”,以栅格单元长度为扩展步长,让水流方向沿着网络上的可通行路径同时向外蔓延,直至与其他水流相遇或者到达边的尽头。该算法可方便地加入网络图结构中的多种约束,如街道边的单向行驶、结点的限制性连接等实际空间限制条件。通过大规模实际数据的“数字城市”POI点服务范围的试验表明该算法的效率高。     

Improved Priority‐Flood method for depression filling by redundant calculation optimization in local micro‐relief areas

Depression filling is a critical step in distributed hydrological modeling using digital elevation models (DEMs). The traditional Priority‐Flood (PF) approach is widely used due to its relatively high efficiency when dealing with a small‐sized DEM. However, it seems inadequate and inefficient when dealing with large high‐resolution DEMs. In this work, we examined the relationship between the PF algorithm calculation process and the topographical characteristics of depressions, and found significant redundant calculations in the local micro‐relief areas in the conventional PF algorithm. As such calculations require more time when dealing with large DEMs, we thus propose a new variant of the PF algorithm, wherein redundant points and calculations are recognized and eliminated based on the local micro‐relief water‐flow characteristics of the depression‐filling process. In addition, depressions and flatlands were optimally processed by a quick queue to improve the efficiency of the process. The proposed method was applied and validated in eight case areas using the Shuttle Radar Topography Mission digital elevation model (SRTM‐DEM) with 1 arc‐second resolution. These selected areas have different data sizes. A comparative analysis among the proposed method, the Wang and Liu‐based PF, the improved Barnes‐based PF, the improved Zhou‐based PF, and the Planchon and Darboux (P&D) algorithms was conducted to evaluate the accuracy and efficiency of the proposed algorithm. The results showed that the proposed algorithm is 43.2% (maximum) faster than Wang and Liu's variant of the PF method, with an average of 31.8%. In addition, the proposed algorithm achieved similar performance to the improved Zhou‐based PF algorithm, though our algorithm has the advantage of being simpler. The optimal strategies using the proposed algorithm can be employed in various landforms with high efficiency. The proposed method can also achieve good depression filling, even with large amounts of DEM data.     

Comparison of Different Strategies for Determining Raster‐Based Least‐Cost Paths with a Minimum Amount of Distortion

The conventional raster‐based least‐cost path technique, in which the connectivity graph is constructed by treating each raster cell as a node and linking each node to its adjacent neighbors, has been widely used to determine optimum paths in space. Unfortunately, paths calculated with this method are subject to distortions that stem from the imposed node‐link structure. Due to the distortions, the calculated paths may be longer than the true optimum paths in continuous space, and because of this, they may also look highly unrealistic when displayed on a map. This study examines how the quality of the raster‐based paths can be improved by using larger connectivity patterns on the one hand, and placing nodes on the sides of the cells of a raster instead of at their centers, on the other. In addition, the utility of the quadtree structure is examined. The different methods are evaluated against three different datasets using the cost distance of the calculated paths and processing times as evaluation criteria. The results indicate that raster‐based paths can be improved by using the evaluated techniques, although the degree of improvement is also dependent on the properties of the underlying cost raster.     

Finding least-cost paths across a continuous raster surface with discrete vector networks

The problem of finding the least-cost path from a source point to a destination point can be dealt with by routing across a continuous surface or routing along a discrete network. The solutions within these two contexts are linked to the use of a raster- or a vector-based least-cost path algorithm. This study presents a technique which integrates raster- and vector-based least-cost path algorithms for determining the least-cost path across a continuous raster surface with discrete vector networks. The technique incorporates ancillary vector data sets that are required to examine the travel cost at each link, connections between nodes, and the representation of intersecting links in the discrete vector network into raster-based least-cost path analysis. The integrated technique presented here is applicable to all-terrain vehicle navigation where a continuous raster surface and discrete vector networks need to be considered simultaneously in order to find least-cost paths. This paper describes the concept behind, and details of, the integrated technique. Applications of the technique with synthetic and real-world data sets are also presented. They provide proof that the technique is effective in finding least-cost paths across a continuous raster surface with discrete vector networks.     

Efficient Priority-Flood depression filling in raster digital elevation models

Depressions in raster digital elevation models (DEM) present a challenge for extracting hydrological networks. They are commonly filled before subsequent algorithms are further applied. Among existing algorithms for filling depressions, the Priority-Flood algorithm runs the fastest. In this study, we propose an improved variant over the fastest existing sequential variant of the Priority-Flood algorithm for filling depressions in floating-point DEMs. The proposed variant introduces a series of improvements and greatly reduces the number of cells that need to be processed by the priority queue (PQ), the key data structure used in the algorithm. The proposed variant is evaluated based on statistics from 30 experiments. On average, our proposed variant reduces the number of cells processed by the PQ by around 70%. The speed-up ratios of our proposed variant over the existing fastest variant of the Priority-Flood algorithm range from 31% to 52%, with an average of 45%. The proposed variant can be used to fill depressions in large DEMs in much less time and in the parallel implementation of the Priority-Flood algorithm to further reduce the running time for processing huge DEMs that cannot be dealt with easily on single computers.     

基于DEM的地形曲率计算模型误差分析

地形曲率是地形表面几何形态和地学建模的基本变量之一。本文首先对曲率计算模型进行了归纳,然后通过数据独立的DEM误差分析方法和实际DEM的分析验证,对目前九种曲率计算的三类曲率计算模型进行了量化分析比较。研究结果表明,当DEM数据精度比较高时,高次曲面(四次曲面)能给出较高精度的曲率计算结果,而当DEM误差较大时,低次曲面(二次曲面)由于具有误差的平滑作用而能产生较高精度的曲率值。     

基于ArcGIS的流域水文特征分析方法研究

随着GIS技术的不断发展和DEM的广泛应用,基于DEM的流域水文特征分析研究受到越来越多的关注。目前,基于格网DEM的水流方向算法,会因为地形的局限,无法准确地进行模拟分流,水流方向也不符合实际流向。本文分析了几种基于DEM的水流方向算法,以格网点为中心建立3×3窗口的局部趋势面,计算出研究区内的曲率,分析区域内的水流聚合度和发散性随着曲率的变化情况,最后根据水流方向算法提取河网。     

一种新的基于矢量地图数据的地表纹理制作

主要阐述了基于矢量地图数据生成具有真实感3维地景纹理的思路和方法，详细论述了在Mapviewer和Photoshop环境下，地形背景纹理的制作，植被纹理的制作，水系纹理的制作以及其它要素纹理制作的方法，并给出了具体的实例。     

基于QTM的线状图形自动化简算法探讨

全球网格是由形成地球表面剖分的一系列区域所组成,八面体四分三角网(QTM)是其中一种具有层次性的网格。本文依据数据点在规则网格中的分布规律,提出了一种在QTM数据结构支持下的线状图形化简算法。该算法以经过每级QTM网格的数据点的平均值为标准,能自动地对比较平缓的线段进行较粗选点,而对相对复杂的线段进行较密选点。本文以及Dutton算法都能克服DouglasPeucker算法中难以客观和合理确定阈值的困难,但是本算法比Dutton算法简单,且具有更高的化简率,能更好地保留了线状图形的弯曲特征。     

Concurrent Drainage Network Rendering for Automated Pen‐and‐ink Style Landscape Illustration

Pen‐and‐ink style geomorphological illustrations render landscape elements critical to the understanding of surface processes within a viewshed and, at their highest levels of execution, represent works of art, being both practical and beautiful. The execution of a pen‐and‐ink composition, however, requires inordinate amounts of time and skill. This article will introduce an algorithm for rendering creases – linework representing visually significant morphological features – at animation speeds, made possible with recent advances in graphics processing unit (GPU) architectures and rendering APIs. Beginning with a preprocessed high‐resolution drainage network model, creases are rendered from selected stream segments if their weighted criteria (slope, flow accumulation, and surface illumination), attenuated by perspective distance from the viewpoint, exceed a threshold. The algorithm thus provides a methodology for crease representation at continuous levels of detail down to the highest resolution of the preprocessed drainage model over a range of surface orientation and illumination conditions. The article also presents an implementation of the crease algorithm with frame rates exceeding those necessary to support animation, supporting the proposition that parallel processing techniques exposed through modern GPU programming environments provide cartographers with a new and inexpensive toolkit for constructing alternative and attractive real‐time animated landscape visualizations for spatial analysis.