A method for finding a least-cost wide path in raster space

Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values.     

An extension of GIS-based least-cost path modelling to the location of wide paths

The computation of least-cost paths over a cost surface is a well-known and widely used capability of raster geographic information systems (GISs). It consists in finding the path with the lowest accumulated cost between two locations in a raster model of a cost surface, which results in a string-like, thin and long sequence of cells. In this article, a new extension of raster-based least-cost path modelling is proposed. The new modelling approach allows the computation of paths or corridors with a fixed width, larger than one cell. These swaths are called wide paths and may be useful in circumstances where the detail level of the raster cost surfaces is higher than the width of the desired path or corridor. The wide path model presented in the article is independent of the choice of least-cost algorithms, because the transformation from regular to wide paths is applied to the construction of nodes and edges of an induced graph. The article gives the foundations and discusses the particularities of such paths, regardless of the imposed width, and explores the difference from the usual least-cost path model. Test cases were included, one hypothetical and the other with real data. The results are coherent and indicative of the applicability of wide paths.     

基于栅格数据和图论算法的生态廊道识别

利用图论中最短路算法思想和ArcGIS的空间分析功能,对生境中动物迁徙廊道的识别与构建进行研究。通过对具有不同空间自相关特征的模拟景观进行分析,发现该方法具有较好的适应性,能识别出不同类型模拟景观的廊道。在模拟景观分析的基础上,将该算法应用于长沙市大河西先导区,计算了先导区重要栖息地之间的廊道。研究表明该计算方法提取的生态廊道具有明显的冗余性,充分反映了物种在不同栖息地之间迁徙的需求,具有一定的生态学意义。同时廊道提取结果在一定程度上反映了城市发展对生态系统尤其是生态廊道的胁迫与挤占。通过对廊道空间结构的分析还发现生态廊道存在一定的瓶颈区域,对该区域的生态恢复与重建将对物种多样性的保持起到关键作用。该方法为区域土地管理以及生态环境保护规划提供一定的科学依据。     

An efficient method for single-facility location and path-connecting problems in a cell map

This article presents an efficient method for simultaneously finding both the Weber cell and optimal connective paths in a grid. As numerous barriers of arbitrary shape and weighted regions are distributed in the cell map of this research, the problem scenario is similar to working out a real-life facility location selection and path-routing problems in a geographical map. In this study, the Weber problem of finding a single-facility location from an accumulation cost table is generated by a grid wave propagation method (higher-geometry maze router). After finding the Weber point (cell), optimal connective paths with minimum total weighted cost are backtracked between the Weber location cell and the demand cells. This new computation algorithm with linear time and space complexity can be integrated as a spatial analytical function within GIS.     

A discrete square global grid system based on the parallels plane projection

We developed a direct partitioning method to construct a seamless discrete global grid system (DGGS) with any resolution based on a two‐dimensional projected plane and the earth ellipsoid. This DGGS is composed of congruent square grids over the projected plane and irregular ellipsoidal quadrilaterals on the ellipsoidal surface. A new equal area projection named the parallels plane (PP) projection derived from the expansion of the central meridian and parallels has been employed to perform the transformation between the planar squares and the corresponding ellipsoidal grids. The horizontal sides of the grids are parts of the parallel circles and the vertical sides are complex ellipsoidal curves, which can be obtained by the inverse expression of the PP projection. The partition strategies, transformation equations, geometric characteristics and distortions for this DGGS have been discussed. Our analysis proves that the DGGS is area‐preserving while length distortions only occur on the vertical sides off the central meridian. Angular and length distortions positively correlate to the increase in latitudes and the spanning of longitudes away from a chosen central meridian. This direct partition only generates a small number of broken grids that can be treated individually.     

邻域算法在景观分析中的应用

景观过渡带是景观空间异质性较高的地区,在分析中经常需要从中提取不同类型区的界线,确定相应的范围。提出一种基于邻域概念的简易算法,根据分界线两侧景观的显著差异,在非特定方向上对连续或者离散的景观单元进行类型判定,依据界线的位置特征和类型隶属上的双重属性设定临界值,在此基础上得到判定条件下的单元,消去孤立分布的单元后,经格式转换求出分界线。本文以首都圈景观为例,给出这种算法的明确步骤,解析出地貌分界线,检验了这种方法的准确程度,简要讨论这种方法的特点和适用性,并在其他景观分析中进行推广验证。这种算法能够确定两种复杂分布类型之间的界线,适用于划分农牧交错区,提取地貌分界线和谷缘线等分析。     

Quadrangle-grid velocity-stress finite-difference method for elastic-wave-propagation simulation

I present a 2-D numerical-modelling algorithm based on a first-order velocity-stress hyperbolic system and a non-rectangular-grid finite-difference operator. In this method the velocity and stress are defined at different nodes for a staggered grid. The scheme uses non-orthogonal grids, thereby surface topography and curved interfaces can be easily modelled in the seismic-wave-propagation stimulation. The free-surface conditions of complex geometry are achieved by using integral equilibrium equations on the surface, and the stability of the free-surface conditions is improved by introducing local filter modification. The method incorporates desirable qualities of the finite-element method and the staggered-grid finite-difference scheme, which is of high accuracy and low computational cost.     

Surface modeling of DEMs based on a sequential adjustment method

A sequential adjustment (SA) method is employed to decrease the computational cost of high-accuracy surface modeling (HASM), and the SA of HASM (HASM-SA) is being developed. A mathematical surface was used to comparatively analyze the computing speed of SA and the classical iterative solvers provided by MATLAB 7.7 for solving the system of linear equations of HASM. Results indicate that SA is much faster than the classical iterative solvers. The computing time of HASM-SA is determined by not only the total number of grid cells but also the number of sampling points in the computational domain. A real-world example of surface modeling of digital elevation models (DEMs) with various resolutions shows that HASM-SA is averagely more accurate and much faster than the commonly used interpolation methods, such as inverse distance weighting (IDW), kriging, and three versions of spline, namely regularized spline (RSpline), thin-plate spline (TPS), and ANUDEM in terms of root mean square error (RMSE), mean absolute error (MAE), and mean error (ME). In particular, the ME of HASM-SA at different spatial resolutions is averagely smaller than those of IDW, kriging, RSpline, TPS, and ANUDEM by 85%, 83%, 83%, 53%, and 19%, respectively. The high speed and high accuracy of HASM-SA can be due to the absence of matrix inversion computation, combined with the perfect fundamental theorem of HASM.     

Geomorphometry on the surface of a triaxial ellipsoid: towards the solution of the problem

Existing algorithms of geomorphometry can be applied to digital elevation models (DEMs) given with plane square grids or spheroidal equal angular grids on the surface of an ellipsoid of revolution or a sphere. Computations on spheroidal equal angular grids are trivial for modelling of the Earth, Mars, the Moon, Venus, and Mercury. This is because: (a) forms of these celestial bodies can be described by an ellipsoid of revolution or a sphere and (b) for these surfaces, there are well-developed theory and algorithms to solve the inverse geodetic problem as well as to determine spheroidal trapezoidal areas. It is advisable to apply a triaxial ellipsoid for describing the forms of small moons and asteroids. However, there are no geomorphometric algorithms intended for such a surface. In this article, first, we formulate the problem of geomorphometric modelling on a triaxial ellipsoid surface. Then, we recall definitions and formulae for coordinate systems of a triaxial ellipsoid and their transformation. Next, we present analytical and computational solutions, which provide the basis for geomorphometric modelling on the surface of a triaxial ellipsoid. The Jacobi solution for the inverse geodetic problem has a fundamental mathematical character. The Bespalov solutions for determination of the length of meridian/parallel arcs and the spheroidal trapezoidal areas are computationally efficient. Finally, we describe easy-to-code algorithms for derivation of local and non-local morphometric variables from DEMs based on a spheroidal equal angular grid of a triaxial ellipsoid.     

单一景观类型时空变化分析方法——以酒泉盆地绿洲化为例

受单一土地利用动态度模型的启发, 本文提出了格网化单一景观类型变化率模型, 较好地反映了单一景观类型在研究时段内的变化情况。在此基础上又提出累积变化率和时空变化指数模型, 用于描述单一景观类型在长时间序列中的空间变化, 并以中国西部酒泉盆地1963-2009 年间的绿洲化过程为例对模型进行了检验。结果表明:①格网化单一景观类型变化率模型, 可以很好地反映期初和期末单一景观类型的局部细微变化, 包括变化速度和空间分布情况;②累积变化率综合了中间各期数据的影响, 可以较好地刻画较长时间序列中单一景观类型的变化幅度及其空间分布情况;③时空变化指数能够反映单一景观类型的变化模式, 进一步描述了变化过程的特点和趋势;④3 个模型的综合运用, 可对单一景观类型的时空变化过程及其特征做出比较全面的描述和刻画。     

2.5-dimensional crosshole acoustic response: a variable density approach

This paper presents the development of a 2.5-D simulation technique for acoustic wave propagation in media with variable density and velocity. A comparative study of the 2-D and 2.5-D responses of a model reveals the spatially and temporally damped nature of the 2.5-D acoustic wave equations. The simulated results for constant and variable density models show that the density variation affects only the reflectivity of the layer. The computational cost for variable density models is 2.17 and 2.26 times that for constant density models for the 2.5-D and 2-D cases, respectively. Furthermore, the 2.5-D computational cost in the time domain is only about 10–15 per cent more than that for two dimensions, so this modest increase in computational cost can avoid the exorbitant 3-D computational cost.
Snapshots for a crosshole geometry were computed at various times in order to study the effect of heterogeneity on the amplitude and shape of the wave front. Extensive analysis of an oil-bearing reservoir with and without the inclusion of a gas zone was performed using a point source as well as multiple sources. In addition, the effects of the thickness of a low-velocity layer (oil-bearing) and of the location of the source have been studied. It is concluded from the numerical response that the waveguide action of the low-velocity layer depends on its thickness in terms of the dominant wavelength. Trapping of waves was not observed when the source was outside the low-velocity layer. Furthermore, the presence of heterogeneity in the low-velocity layer contributes considerably to the leakage of energy in the adjacent layers due to scattering/diffraction. It was found that, in the 2.5-D numerical simulation, the stability condition and the requirement of the number of grid points per wavelength to avoid grid dispersion are the same as for the 2-D case.     

西安市城市景观的正负生态系统服务测算及空间格局

综合测评城市景观的复合（正负）生态系统服务功能和评价不同城市景观类型的生态系统服务贡献,对优化、调控在城市化影响下的景观转换和城市生态环境建设等具有重要的科学意义。运用景观生态学理论与生态系统服务理论,基于研究区的TM遥感影像和Erdas、ArcGIS 10.1软件对西安市建成区2013年城市景观的复合生态系统服务进行测算和空间分析。结果表明：① 西安城市景观产生的负向生态系统服务价值远高于正向生态系统服务价值,净生态系统服务达-12.71×10⁸元;在城市化过程中,随着自然景观向半人工景观、人工景观的转变,导致景观生态系统服务的价值急剧下降,负向生态系统服务占主导,87.81%的土地复合生态系统服务为负值,仅有12.19%的土地复合生态系统服务为正值,以建筑用地为主体的城市景观体系必然会导致生态系统服务的下降。② 西安市城市景观的总正向生态系统服务空间分布差异明显,整体呈现为研究区中心值低于四周,沿行道绿地、公园绿地等景观形成格网状、斑块状分布的高值区;总负向生态系统服务整体上呈现中心值高于四周,高值区较集聚,自然景观和半人工景观是维系城市正向生态系统服务的主要景观类型。③ 城市景观的空间分布基本上决定了复合生态系统服务的空间大格局,西安市各城市景观类型的空间组合与镶嵌状况,使得生态系统服务正负值呈斑块状、棋盘状交错分布的格局。愈向城市外围,复合生态系统服务价值越高;城中林地、绿地和水域分布的地方是复合生态系统服务价值网状高值区。     

Unsupervised regionalization of the United States into landscape pattern types

We present a pattern-based regionalization of the conterminous US – a partitioning of the country into a number of mutually exclusive and exhaustive regions that maximizes the intra-region stationarity of land cover patterns and inter-region disparity between those patterns. The result is a discretization of the land surface into a number of landscape pattern types (LPTs) – spatial units each containing a unique quasi-stationary pattern of land cover classes. To achieve this goal, we use a recently developed method which utilizes machine vision techniques. First, the entire National Land Cover Dataset (NLCD) is partitioned into a grid of square-size blocks of cells, called motifels. The size of a motifel defines the spatial scale of a local landscape. The land cover classes of cells within a motifel form a local landscape pattern which is mathematically represented by a histogram of co-occurrence features. Using the Jensen–Shannon divergence as a dissimilarity function between patterns we group the motifels into several LPTs. The grouping procedure consists of two phases. First, the grid of motifels is partitioned spatially using a region-growing segmentation algorithm. Then, the resulting segments of this grid, each represented by its medoid, are clustered using a hierarchical algorithm with Ward’s linkage. The broad-extent maps of progressively more generalized LPTs resulting from this procedure are shown and discussed. Our delineated LPTs agree well with the perceptual patterns seen in the NLCD map.     

一种启发式A*算法和网格划分的空间可达性计算方法

本文提出了一个适用于研究城市内部的个体或商业区位的微观可达性计算方法,该方法的核心是将研究区域进行等距的网格划分,通过计算每个网格的可达性指标,来研究整个区域的可达性的空间分布特点。在可达性计算中,利用网格内的道路密度和土地利用状态这两个因素来模拟计算每个网格的交通成本,引入了启发式A ^*空间搜索算法来计算网格间路径的交通成本,并且加入适当的启发信息,提高了搜索效率,使搜索结果更符合实际需求。最后,基于本文提出的方法,利用GIS二次开发工具ArcEngine开发了计算程序,收集了多源数据,以广州市商务区的可达性作为计算对象,进行了商务区的可达性和易达性案例计算。     

广州市生态系统服务价值空间异质性变化

基于广州市2004―2016年土地利用分类成果,通过CA-Markov模型模拟预测2020年土地利用状况,结合格网分析法构建广州市2004―2020年的生态系统服务价值（Ecosystem Services Value,ESV）密度格网,并展开Getis-Ord热点区分析和圈层分析评估,分析广州市快速城市化进程土地利用变化对ESV变化过程和影响的空间异质性。结果表明：1）广州市快速城市化进程中,建设用地扩张占用了大量生态用地,建设用地面积从2004年的1 320 km2扩张到2016年约2 000 km2,预计2020年将达到2 263.63 km2,生态用地斑块日趋破碎化;2）2004―2016年间,广州市ESV总值累计减少了92.41亿元,年均减少约8.4亿元,预计2016―2020年其继续减少但减速会放缓;3）ESV高值区域的格网数量净减少近18%,低值区域的格网数量净增加约46%,局部区域生态系统服务功能的改善难以抵消快速城市化造成的ESV损失;4）广州市ESV变化呈现局部空间自相关现象,高冷区常年集聚分布在花都区和番禺―南沙一带,高热区从集聚分布于东北部逐渐变成为零星分布;5）ESV圈层格局从中心城区向外围区（核心区、近郊区、边缘区和外围区）呈“低―低―中―高”向“低―低―低―高”的结构特征演变,地处城市边缘的近郊区域和边缘区域逐渐形成空间异质性最突出的城乡交错带。     

分布式水文模拟汇流方法及应用

对于必须考虑汇流过程的分布式水文模型而言 ,其汇流模型可以分解为三个层次来讨论 :第一个层次是单元划分 ;第二个层次为汇流路径 ;第三个层次则是基于该汇流路径的汇流演算模型。基于栅格的分级运动波汇流模型是根据栅格DEM的网格单元水流流向来划分栅格等级 (汇流带 ) ,然后应用运动波模型进行逐级汇流演算。文中从可操作性的角度对栅格分级方法和运动波汇流模型进行了分析讨论 ,最后根据潮白河流域 1 981～ 1 990年资料进行了日径流过程模拟分析 ,说明该方法在理论上是合理的 ,并在应用中取得良好的模拟效果。     

A new algorithm to find raster-based least-cost paths using cut and fill operations

We developed a least-cost path analysis algorithm that satisfies a slope threshold condition in hilly terrain. The new algorithm uses an expanding moving-window to explore a combination of cells that satisfy an elevation threshold condition and then supplements this by executing cut and fill operations when there are obstacle cells between source and destination cells. Cut and fill factors regarding the difference in the actual elevation and revised elevation are considered and a least-cost path is analyzed after calculating the accumulated travel cost to the destination point. After applying the developed algorithm to synthetic and real-world data, the least accumulated travel cost from the source point can then be calculated for all cells on the raster surface by considering various slope thresholds, moving-window sizes and raster data resolutions. This algorithm can be implemented as a useful tool in GIS software as well as engineering design software utilized in the construction and mining industries.     

石羊河上游林区景观空间邻接特征及生态安全分析

在干旱区山地,荒地斑块特征可反映植被的破碎化及退化状况,农田斑块特征可反映自然植被景观受农田开垦的威胁程度,而其它景观类型与这两种类型斑块的邻接特征可间接反映这些类型潜在的植被退化风险大小或受农田开垦的威胁程度。以Landsat/TM及林相图作为数据源,在桌面GIS下解译出石羊河上游的哈溪林区各景观类型,计算了各景观类型与荒地和农田的空间邻接长度和数目比例,并利用缓冲区分析方法计算了荒地和农田对各景观的影响面积。在此基础上通过计算各类型植被退化风险大小和受农田开垦的威胁程度,定量分析了研究区各景观类型的生态安全性。结果表明：灌丛和草地与荒地的邻接边长和数目较大,由放牧活动引起的植被破碎化和退化的风险较大,而乔木林种与农田的邻接长度、数目较大,受农田开垦的威胁较为严重;景观整体植被退化的风险（0.28）高于受农田威胁程度（0.11）;各类型植被退化风险值的差别不明显,但灌丛草地相对较高,而各乔木林种受农田开垦的威胁程度明显高于灌丛和草地;基于景观类型空间邻接的生态安全评价分析可以初步反映干旱区山地景观受人类活动影响的威胁程度。     

A step towards an objective procedure for land classification and mapping

This paper outlines a method for explicitly classifying landscape using 4 km² grid cells, a set of attributes derived from topographic and geologic maps and an agglomerative numerical taxonomic procedure which can accommodate mixed data. The method was used to classify the landscapes of the Hunter Valley, NSW (22 000 km²) and the landscape classes generated are briefly described. These classes are compared with the land systems of the Hunter which were developed by traditional integrated survey procedure. It is concluded that the method could provide a more satisfactory starting-point for integrated land survey than air photo pattern analysis.