Disaggregation of polygons of surficial geology and soil maps using spatial modelling and legacy data

Examples from the Murray-Darling basin in Australia are used to illustrate different methods of disaggregation of reconnaissance-scale maps. One approach for disaggregation revolves around the de-convolution of the soil-landscape paradigm elaborated during a soil survey. The descriptions of soil ma units and block diagrams in a soil survey report detail soil-landscape relationships or soil toposequences that can be used to disaggregate map units into component landscape elements. Toposequences can be visualised on a computer by combining soil maps with digital elevation data. Expert knowledge or statistics can be used to implement the disaggregation. Use of a restructuring element and k-means clustering are illustrated. Another approach to disaggregation uses training areas to develop rules to extrapolate detailed mapping into other, larger areas where detailed mapping is unavailable. A two-level decision tree example is presented. At one level, the decision tree method is used to capture mapping rules from the training area; at another level, it is used to define the domain over which those rules can be extrapolated. (C) 2001 Elsevier Science B.V. All rights reserved.

An efficient algorithm for partitioning parameterized polygons into rectangles

In this paper, we propose an algorithm for partitioning parameterized orthogonal polygons into rectangles. The algorithm is based on the plane-sweep technique and can be used for partitioning polygons which contain holes. The input to the algorithm consists of the contour of a parameterized polygon to be partitioned and the constraints for those parameters which reside in the contour. The algorithm uses horizontal cuts only and generates a minimum number of rectangles whose union is the original orthogonal polygon. The proposed algorithm can be used as the basis to build corner stitching data structure for parameterized VLSI layouts and has been implemented in Java programming language. Copyright © 2010 ACM, Inc.

HIV heterogeneity and proximity of homestead to roads in rural South Africa: an exploration using a geographical information system

OBJECTIVE To describe heterogeneity of HIV prevalence among pregnant women in Hlabisa health district, South Africa and to correlate this with proximity of homestead to roads. METHODS HIV prevalence measured through anonymous surveillance among pregnant women and stratified by local village clinic. Polygons were created around each clinic, assuming women attend the clinic nearest their home. A geographical information system (GIS) calculated the mean distance from homesteads in each clinic catchment to nearest primary (1 degrees) and to nearest primary or secondary (2 degrees) road. RESULTS We found marked HIV heterogeneity by clinic catchment (range 19-31% (P < 0.001). A polygon plot demonstrated lower HIV prevalence in catchments remote from 1 degrees roads. Mean distance from homesteads to nearest 1 degrees or 2 degrees road varied by clinic catchment from 1623 to 7569 m. The mean distance from homesteads to a 1 degrees or 2 degrees road for each clinic catchment was strongly correlated with HIV prevalence (r = 0.66; P = 0.002). CONCLUSIONS The substantial HIV heterogeneity in this district is closely correlated with proximity to a 1 degrees or 2 degrees road. GIS is a powerful tool to demonstrate and to start to analyse this observation. Further research is needed to better understand this relationship both at ecological and individual levels, and to develop interventions to reduce the spread of HIV infection.

Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.