Title: Pathfinding within a Hierarchical Navmesh Based on Geometry Analysis Author: Miroslav Chomut Department / Institute: Department of Software and Computer Science Education Supervisor of the master thesis: Mgr. Tomáš Plch, Media and Communications Office Abstract: Pathfinding is a common problem in the computer science dealing with navigation from a starting point to a destination point. Common algorithms today are mostly based on A* search on a graph representation of navigated world. Another common approach is creation of navigation structure of convex navigation meshes and navigating on them. Our goal is to propose pathfinding algorithm on hierarchical navigation meshes, based on the terrain geometry, which benefits from complexity of hierarchical search yet provides paths comparable in length to reference ones. This thesis analyses and describes our proposed approach of navigation including generation of the navigation structure. Keywords: navmesh, pathfinding, A*, hierarchy, terrain analysis, geometry

To aid in forest management, various approaches using Geographic Information Systems (GIS) have been used to identify the spatial distributions of relative slope instability. This study presents a systematic evaluation of three common slope instability modeling approaches applied in the Blue Ridge Mountains of Virginia. The modeling approaches include the Qualitative Map Combination, Bivariate Statistical Analysis, and the Shallow Landsliding Stability (SHALSTAB) model. Historically, the qualitative nature of the first model has led to the use of more quantitative statistical models and more deterministic physically-based models such as SHALSTAB. Although numerous studies have been performed utilizing each approach in various regions of the world, only a few comparisons of these approaches have been done in order to assess whether the quantitative and deterministic models result in better identification of instability. The goal of this study is to provide an assessment of relative model behavior and error potential in order to ascertain which model may be the most effective at identifying slope instability in a forest management context. The models are developed using both 10-meter and 30-meter elevation data and outputs are standardized and classified into instability classes (e.g. low instability to high instability). The outputs are compared with cross-tabulation tables based on the area (m²) assigned to each instability class and validated using known locations of debris flows. In addition, an assessment of the effects of varying source data (i.e. 10-meter vs. 30-meter) is performed. Among all models and using either resolution data, the Qualitative Map Combination correctly identifies the most debris flows. In addition, the Qualitative Map Combination is the best model in terms of correctly identifying debris flows while minimizing the classification of high instability in areas not affected by debris flows. The statistical model only performs well when using 10-meter data while SHALSTAB only performs well using 30-meter data. Overall, 30-meter elevation data predicts the location of debris flows better than 10-meter data due to the inclusion of more area into higher instability classes. Of the models, the statistical approach is the least sensitive to variations in source elevation data. / Master of Science

Understanding the hydrology of the riparian zone in a catchment can be an important prerequisite for determining solute loads and concentrations in streams. The riparian zone is the transition zone between surrounding landscape and an open water stream. This study focuses on the spatial and temporal variations of shallow groundwater levels in a forested headwater catchment in the Bergslagen area of central Sweden. Three snapshot campaigns were conducted during dry, humid and wet conditions to map the spatial variability of the groundwater levels. Piezometers giving the total hydraulic head were placed in the riparian zone along a stream network consisting of three first order streams and one second order stream. To asses temporal variations five groundwater wells were installed with automatic loggers to record continuous data during the wet period. Historical streamflow records from a permanent field station were collected and related to the groundwater levels in order to assess the relationship between groundwater levels and streamflow. Additionally a landscape analysis using GIS methods was conducted in order to identify potential drivers of spatial variation of groundwater levels in the riparian zone. The results showed that the slope could partially explain the observed spatial variability of riparian groundwater levels. The results from the spatially distributed piezometers and the continuously monitored groundwater wells with loggers were contradicting. Where the piezometers showed increasing depth to the groundwater table with increasing slope the loggers indicated the opposite. However, because the piezometers outnumbered the loggers the piezometer results can be considered more representative of the spatial variation of groundwater levels. There could be no general result concluded on the catchment scale but when looking at specific subcatchments it could be found that the variations in the riparian groundwater levels could be better explained where the stream had a more distinct channel. This indicates the importance to evaluate not only slope but the profile curvature as well for groundwater predictions.

Terrain attributes computed from Digital Elevation Models (DEMs) are widely used in hydrology and hydrologic modeling. It is important to consider that the values of the attributes can be different depending on the resolution of the DEM from which they are derived. The question arises as to how much exactly the high-resolution DEMs created through LIDAR remote sensing techniques change the values of the terrain attributes when compared to lower resolution DEMs.In this thesis a LIDAR-derived DEM of 20 feet resolution was resampled using a nearest-neighbour algorithm to various coarser resolutions to examine and quantify the effect of DEM resolution upon a series of hydrologically significant terrain attributes including slope, surface curvature, topographic wetness index, stream power index and stream networks. Values for slope and surface curvature are found to be smaller when computed from lower resolution DEMs; values for the topographic wetness index and stream power index are found to increase as DEM cell size increases.The derived stream networks for each resolution were compared in terms of length per stream order, drainage density, bifurcation ratio, and overall accuracy indicating a loss of small detail, but only a modest change in the overall stream network morphometry. This research suggests that it is possible to establish relationships that quantify the effects of DEM resolution upon hydrologically significant terrain attributes, which can then be considered when processing DEMs from various resolutions for the purpose of parameterizing hydrologic models.

Digital soil mapping supervised and unsupervised classification methods were evaluated to aide soil survey of unmapped areas in the western United States. Supervised classification of landscape into mountains and basins preceded unsupervised classification of data chosen by iterative data reduction. Principal component data reduction, ISODATA classification, Linear combination of principal components, Zonal averaging of linear combination by ISODATA class, Segmentation of the image into polygons, and Attribution of polygons by majority ISODATA class (PILZSA process) comprised steps isolating unique soil-landscape units. Input data included ASTER satellite imagery and USGS 30-m elevation layers for environmental proxy variables representing soil forming factors. Results indicate that PILZSA captured general soil patterns when compared to an existing soil survey while also detecting fluvial soils sourced from different lithologies and unique mountain areas not delineated by the original survey. PILZSA demonstrates potential for soil pre-mapping, and sampling design efforts for soil survey and survey updates.

1st Topographical Survey Squadron, Royal Australian Engineers, provides deployable geospatial support to the Australian Defence Force. Part of this role is the production of products for use by commanders. These products provide commanders at all levels with mission specific and up to date knowledge of the terrain that he will encounter on the battlespace. Currently 1st Topographical Survey Squadron provides products that contain manmade features, hydrography, slope, surface configuration and vegetation as displayed on current mapping products. They do not provide an accurate portrayal of the effect that vegetation characteristics have on the battlespace. Introducing these types of features will give the commander a greater knowledge of the terrain and environment that he will encounter, and will greatly improve the planning and success of the campaign. This research explored to what extent the accuracy of the terrain analysis products currently produced by 1st Topographical Survey Squadron would increase by adding a more detailed portrayal of vegetation extracted from remote sensing data.

Trails are essential transportation infrastructure supporting access to protected natural areas and providing recreation to hikers, runners, cyclists, equestrians, motorists, and many more worldwide. This research presents spatial studies intended to improve understanding of the environmental, managerial, and use-related factors that influence management of and physical and experiential conditions on long-distance hiking trails. The first study investigates a dataset from the Appalachian Trail (AT) to examine methods for using high resolution digital elevation models to measure terrain steepness near trails and along trails or potential trail routes. This analysis supports trail planning and assessment efforts because these terrain metrics strongly influence physical trail sustainability and are useful to evaluate the difficulty of travel along trails. The second study analyzes long-distance use patterns on the Pacific Crest Trail (PCT) as depicted by a computer model developed from a survey administered to long-distance hikers, trail counters, observations, and registers. In addition to describing use patterns, the process is intended to inform the selection of methods for visitor use monitoring in response to the complexity and level of controversy of management needs. The third study examines the spatial relationships between the PCT, a national scenic trail, and other congressionally designated land areas including wilderness, wild and scenic rivers, and national monuments and how this complexity is manifested in camping management strategies and impacts along the trail corridor. This analysis supports managing for the multiple congressional mandates across the PCT landscape and improves understanding and management of interagency transboundary travel on the trail. / Doctor of Philosophy / Trails are essential transportation infrastructure supporting access to protected natural areas and providing recreation to hikers, runners, cyclists, equestrians, motorists, and many more worldwide. This research presents spatial studies intended to improve understanding of the environmental, managerial, and use-related factors that influence management and physical and experiential conditions on long-distance hiking trails. The first study investigates a dataset from the Appalachian Trail (AT) to examine methods for using high resolution digital elevation models to measure terrain steepness near trails and along trails or potential trail routes to improve digital trail assessment and planning. The second study analyzes long-distance use patterns on the PCT as depicted by a computer model developed from a survey administered to long-distance hikers, trail counters, observations, and registers. The third study examines the complexity of managing transboundary long distance trails by quantifying the spatial relationships between the Pacific Crest Trail (PCT), a national scenic trail, and other congressionally designated land areas, and by reviewing camping impacts at high use locations on the trail corridor.

As estradas rurais não pavimentadas são importantes geradoras de crescimento em países subdesenvolvidos, desempenhando papel essencial na produção e comercialização de produtos primários e no acesso a bens e serviços. Cerca de 78,6% do sistema de transporte brasileiro é composto por estradas não pavimentadas, sem contabilizar as estradas de uso privado de propriedades rurais. No âmbito florestal as estradas não pavimentadas tem sido o principal foco de estudos relacionados à erosão, pois são os agentes que mais contribuem para o escoamento superficial e geração de sedimentos. A aceleração dos processos erosivos proporcionada pelas estradas está vinculada às mudanças dos processos hidrológicos. A interceptação direta da chuva e do escoamento superficial e subsuperficial, a divergência e a concentração do fluxo d\'água nas estruturas das estradas são as principais mudanças ocorridas. Entre os danos ambientais causados pela introdução das estradas se destacam a redução da qualidade da água e o assoreamento dos cursos d\'água. Diante a necessidade de se entender as funções atribuídas às estradas nas relações entre o manejo florestal e a água, as estradas não pavimentadas da Estação Experimental de Ciências Florestais de Itatinga (EECFI) foram submetidas a duas análises. O trabalho foi dividido em duas partes, a primeira identificou os trechos de estradas suscetíveis à erosão (análise qualitativa) e a segunda parte estimou as taxas de produção de sedimentos e volume de enxurrada nas superfícies das estradas (análise quantitativa). Toda a malha viária da EECFI foi mapeada e digitalizada em plataformas de Sistema de Informações Geográficas (SIG). A partir do modelo digital do terreno e dos mapas de tipo e cobertura de solo foram calculados os quatro indicadores (hidrológicos e topográficos) utilizados na identificação dos trechos com maiores riscos de erosão. Por meio de métodos estatísticos multivariados, todos os indicadores de cada trecho de estrada, simultaneamente, foram divididos em grupos com características similares. A identificação dos grupos de trechos suscetíveis à erosão foi realizada pela interpretação da análise de variância (One Way ANOVA). Para a estimativa proposta na segunda parte do trabalho, foram instaladas 16 parcelas com diferentes declividades, com e sem realização de manutenção nas superfícies das estradas. As taxas de produção de sedimentos e de volume de enxurrada foram analisadas pela análise de covariância, sendo que os efeitos das variáveis e covariáveis foram analisados pelo modelo linear generalizado misto. Os resultados mostraram que tanto os indicadores quanto o método utilizado para a separação foram capazes de identificar dois grupos de trechos com características distintas quanto à suscetibilidade à erosão. Essas características foram proporcionadas pelo posicionamento das estradas em relação às curvas de nível do terreno. A declividade e a manutenção das superfícies das estradas aumentaram significativamente a produção de sedimentos, com maior destaque para as declividades. No que diz respeito ao aumento do volume de enxurrada, somente a realização da manutenção apresentou efeito significativo. A adequação das técnicas de manutenção, assim como a adoção de técnicas complementares em trechos de estradas considerados mais suscetíveis, reduzirão a perda de solo e água e os danos ambientais decorrentes. / Unpaved rural roads generate important growth in developing countries, they play an essential role in the production and marketing of primary products and access to goods and services. Approximately 78.6% of Brazil\'s transport system consists of unpaved roads, not counting the roads of private use of rural properties. In the forest sector the unpaved roads have been the main focus of studies related to erosion, as are the agents that contribute most to the runoff and sediment production. The erosion acceleration provided by roads are linked to changes in hydrological processes. The main changes are rainfall and surface and subsurface flow interception, and the divergence and the concentration of water flow on the roads\' structures. Among the environmental damage caused by the introduction of roads it\'s possible to emphasize the reduction of water quality and stream aggradation. In view of the need to understand the functions of roads in the relations between forest management and water, the unpaved roads of the Experimental Station of Forest Sciences Itatinga (EECFI) were subjected to two analyzes. The study was divided into two parts, the first identified road segments susceptible to erosion (qualitative analysis) and the second part estimated the sediments production rates and volume runoff on road surfaces (quantitative analysis). The entire road network of EECFI was mapped and digitalized using System Geographic Information (GIS) platforms. From the digital elevation model (DEM) and the soil type and land cover maps were calculated four indicators (hydrological and topographical) used in the identification of segments with greater erosion risks. Through multivariate statistical methods, all indicators of each road segment, simultaneously, were divided into groups with similar characteristics. The identification of segments groups susceptible to erosion was performed by the interpretation of the analysis of variance (one way ANOVA). For the estimative proposed in the second part, 16 plots were installed with different slopes, with and without carrying out maintenance on the surfaces of the roads. The sediment production rates and runoff volume were analyzed by analysis of covariance, and the effects of the variables and covariates were analyzed using generalized linear mixed model. The results showed that both the indicators and the method used for the separation were able to identify two segments groups with different characteristics for susceptibility to erosion. These characteristics were provided by the positioning of roads in relation to the terrain contour lines. The slope and the maintenance of road surfaces significantly increased the production of sediments, most notably the slopes. Regarding the increase of the runoff volume, only maintenance activities showed significant effect. The adjustment of maintenance techniques, as well as the adoption of complementary techniques in segments roads considered more susceptible, will reduce the soil and water losses and resulting environmental damages.

Several studies in high-latitude catchments have demonstrated the importance of near-stream riparian zones as hydrogeochemical hotspots with a substantial influence on stream chemistry. An adequate representation of the spatial variability of riparian-zone processes and characteristics is the key for modeling spatio-temporal variations of stream-water quality. This thesis contributes to current knowledge by refining landscape-analysis techniques to describe riparian zones and by introducing a conceptual framework to quantify solute exports from riparian zones. The utility of the suggested concepts is evaluated based on an extensive set of hydrometric and chemical data comprising measurements of streamflow, groundwater levels, soil-water chemistry and stream chemistry. Standard routines to analyze digital elevation models that are offered by current geographical information systems have been of very limited use for deriving hydrologically meaningful terrain indices for riparian zones. A model-based approach for hydrological landscape analysis is outlined, which, by explicitly simulating groundwater levels, allows better predictions of saturated areas compared to standard routines. Moreover, a novel algorithm is presented for distinguishing between left and right stream sides, which is a fundamental prerequisite for characterizing riparian zones through landscape analysis. The new algorithm was used to derive terrain indices from a high-resolution LiDAR digital elevation model. By combining these terrain indices with detailed hydrogeochemical measurements from a riparian observatory, it was possible to upscale the measured attributes and to subsequently characterize the variation of total organic-carbon exports from riparian zones in a boreal catchment in Northern Sweden. Riparian zones were recognized as highly heterogeneous landscape elements. Organic-rich riparian zones were found to be hotspots influencing temporal trends in stream-water organic carbon while spatial variations of organic carbon in streams were attributed to the arrangement of organic-poor and organic-rich riparian zones along the streams. These insights were integrated into a parsimonious modeling approach. An analytical solution of the model equations is presented, which provides a physical basis for commonly used power-law streamflow-load relations. / At the time of doctoral defense, the following papers were unpublished and had a status as follows: Paper 2: In press; Paper 4: Manuscript. / Swedish Research Council (VR, grant no. 2005-4289)

As estradas rurais não pavimentadas são importantes geradoras de crescimento em países subdesenvolvidos, desempenhando papel essencial na produção e comercialização de produtos primários e no acesso a bens e serviços. Cerca de 78,6% do sistema de transporte brasileiro é composto por estradas não pavimentadas, sem contabilizar as estradas de uso privado de propriedades rurais. No âmbito florestal as estradas não pavimentadas tem sido o principal foco de estudos relacionados à erosão, pois são os agentes que mais contribuem para o escoamento superficial e geração de sedimentos. A aceleração dos processos erosivos proporcionada pelas estradas está vinculada às mudanças dos processos hidrológicos. A interceptação direta da chuva e do escoamento superficial e subsuperficial, a divergência e a concentração do fluxo d\'água nas estruturas das estradas são as principais mudanças ocorridas. Entre os danos ambientais causados pela introdução das estradas se destacam a redução da qualidade da água e o assoreamento dos cursos d\'água. Diante a necessidade de se entender as funções atribuídas às estradas nas relações entre o manejo florestal e a água, as estradas não pavimentadas da Estação Experimental de Ciências Florestais de Itatinga (EECFI) foram submetidas a duas análises. O trabalho foi dividido em duas partes, a primeira identificou os trechos de estradas suscetíveis à erosão (análise qualitativa) e a segunda parte estimou as taxas de produção de sedimentos e volume de enxurrada nas superfícies das estradas (análise quantitativa). Toda a malha viária da EECFI foi mapeada e digitalizada em plataformas de Sistema de Informações Geográficas (SIG). A partir do modelo digital do terreno e dos mapas de tipo e cobertura de solo foram calculados os quatro indicadores (hidrológicos e topográficos) utilizados na identificação dos trechos com maiores riscos de erosão. Por meio de métodos estatísticos multivariados, todos os indicadores de cada trecho de estrada, simultaneamente, foram divididos em grupos com características similares. A identificação dos grupos de trechos suscetíveis à erosão foi realizada pela interpretação da análise de variância (One Way ANOVA). Para a estimativa proposta na segunda parte do trabalho, foram instaladas 16 parcelas com diferentes declividades, com e sem realização de manutenção nas superfícies das estradas. As taxas de produção de sedimentos e de volume de enxurrada foram analisadas pela análise de covariância, sendo que os efeitos das variáveis e covariáveis foram analisados pelo modelo linear generalizado misto. Os resultados mostraram que tanto os indicadores quanto o método utilizado para a separação foram capazes de identificar dois grupos de trechos com características distintas quanto à suscetibilidade à erosão. Essas características foram proporcionadas pelo posicionamento das estradas em relação às curvas de nível do terreno. A declividade e a manutenção das superfícies das estradas aumentaram significativamente a produção de sedimentos, com maior destaque para as declividades. No que diz respeito ao aumento do volume de enxurrada, somente a realização da manutenção apresentou efeito significativo. A adequação das técnicas de manutenção, assim como a adoção de técnicas complementares em trechos de estradas considerados mais suscetíveis, reduzirão a perda de solo e água e os danos ambientais decorrentes. / Unpaved rural roads generate important growth in developing countries, they play an essential role in the production and marketing of primary products and access to goods and services. Approximately 78.6% of Brazil\'s transport system consists of unpaved roads, not counting the roads of private use of rural properties. In the forest sector the unpaved roads have been the main focus of studies related to erosion, as are the agents that contribute most to the runoff and sediment production. The erosion acceleration provided by roads are linked to changes in hydrological processes. The main changes are rainfall and surface and subsurface flow interception, and the divergence and the concentration of water flow on the roads\' structures. Among the environmental damage caused by the introduction of roads it\'s possible to emphasize the reduction of water quality and stream aggradation. In view of the need to understand the functions of roads in the relations between forest management and water, the unpaved roads of the Experimental Station of Forest Sciences Itatinga (EECFI) were subjected to two analyzes. The study was divided into two parts, the first identified road segments susceptible to erosion (qualitative analysis) and the second part estimated the sediments production rates and volume runoff on road surfaces (quantitative analysis). The entire road network of EECFI was mapped and digitalized using System Geographic Information (GIS) platforms. From the digital elevation model (DEM) and the soil type and land cover maps were calculated four indicators (hydrological and topographical) used in the identification of segments with greater erosion risks. Through multivariate statistical methods, all indicators of each road segment, simultaneously, were divided into groups with similar characteristics. The identification of segments groups susceptible to erosion was performed by the interpretation of the analysis of variance (one way ANOVA). For the estimative proposed in the second part, 16 plots were installed with different slopes, with and without carrying out maintenance on the surfaces of the roads. The sediment production rates and runoff volume were analyzed by analysis of covariance, and the effects of the variables and covariates were analyzed using generalized linear mixed model. The results showed that both the indicators and the method used for the separation were able to identify two segments groups with different characteristics for susceptibility to erosion. These characteristics were provided by the positioning of roads in relation to the terrain contour lines. The slope and the maintenance of road surfaces significantly increased the production of sediments, most notably the slopes. Regarding the increase of the runoff volume, only maintenance activities showed significant effect. The adjustment of maintenance techniques, as well as the adoption of complementary techniques in segments roads considered more susceptible, will reduce the soil and water losses and resulting environmental damages.