Using an Energy Minimization Technique for Polygon Generalization

Snakes are iterative energy-minimizing splines controlled by both internal constraint forces (internal energy) and external forces (external energy). This paper investigates the use of snakes for the resolution of conflicts in polygonal subdivisions (i.e., polygon maps or polygon mosaics) resulting from the violation of metric constraints which exist if a polygonal object is too small, too narrow, or too close to another polygon. Such metric conflicts are denoted as size and proximity conflicts. In the generalization of polygonal subdivisions, internal energy reflects the resistance of an object to deformation and external energy describes the need for generalization. This paper suggests the usage of a snakes-based algorithm which is triggered in such a way that it achieves the translation, a local and global increase (or decrease) of polygons, or an arbitrary combination of these transformations, depending on the conflicts encountered. Hence, size and proximity conflicts within a group of polygons can be solved simultaneously and holistically. Furthermore, snakes support the propagation of a change of a polygon's geometry to all adjacent neighbors. The proposed algorithm has been implemented in a prototype system that also supports a variety of other polygon generalization algorithms. The main difficulties identified are the intricate setup and fine-tuning of the snakes parameters and the computer resources required by the algorithm. However, the experiments showed that the proposed algorithm is a valuable method for the automated generalization of polygonal subdivisions.     

Tile‐based polygon overlay of vector data in a virtual globe

The demand for analysis of large‐scale data has increased with increased access to spatial vector data. Polygon overlay of vector data in a virtual globe requires proprietary data structures and proprietary analysis algorithms. A vector data structure is designed for rapid polygon overlay in a virtual globe by recording the metadata of the triangles (TriMeta) that constitute polygons. A polygon overlay algorithm is proposed based on this data structure. The overlay of two complex GIS polygons is transformed into the intersection computation of their 3D triangular presentations. The intersection computation of two sets of triangles is reduced considerably by utilizing TriMeta to filter out the disjoint triangle pairs and rapidly identify the contained triangle. The new method improves the overlay efficiency in a virtual globe because the amount of computation required to calculate the intersections of two large polygons and drape the intersections onto a terrain surface is reduced.     

基于南方cass的土地利用图斑绘制改进方法研究

第二次全国土地调查中土地利用图斑绘制是十分重要的环节.依据城镇土地利用数据建库的新绘制要求,研究在南方cass下传统的基于面的图斑绘制方法的不足,并提出一种改进的基于线的图斑绘制方法.采用该方法,很快完成了某县城镇17 kmz的土地利用图斑绘制工作.实践证明该方法可以大大提高土地利用图斑绘制的工作效率,确保土地利用数据...     

Area‐preservation Simplification of Polygonal Boundaries by the Use of the Structured Total Least Squares Method with Constraints

This article presents an area‐preservation approach for polygonal boundary simplification by the use of structured total least squares adjustment with constraints (STLSC), with the aim being to maintain the area of the original polygons after the simplification. Traditionally, a simplified line is represented by critical points selected from the original one. However, this study focuses on maintaining the areas of the polygons in the process of simplification of polygonal boundaries. Therefore, the proposed method in this article is a supplement to the existing line simplification methods, and it improves the quality of the simplification of polygonal boundaries in terms of positional and area errors. Based on the sub‐divisions of the original polyline, using the critical points detected from the polyline by the use of line simplification methods, the framework of the proposed method includes three main components, as follows: (1) establishment of the straight‐line‐segment fitting model based on both the critical and intermediate points on the sub‐polyline; (2) introduction of both area and end‐point constraints to reduce the geometric distortions due to the line simplification; and (3) derivation of the solution of boundary simplification by the use of STLSC. An empirical example was conducted to test the applicability of the proposed method. The results showed that: (1) by imposing the linear fitting model on both the critical and intermediate points on the sub‐polylines in the proposed STLSC method, the positional differences between the original points and the simplified line are approximately in a normal distribution; and (2) by introducing both end‐point and area constraints in the proposed STLSC method, the areas of the simplified polygons are the same as those of the original ones at different scales, and the two neighboring fitted lines are connected to each other at the optimized position.     

Geo‐questionnaire: A Method and Tool for Public Preference Elicitation in Land Use Planning

Geo‐questionnaire involves an integration of sketchable maps with questions, aimed at eliciting public preferences and attitudes about land allocation and services. Respondents can link their answers with corresponding locations on a map by marking points or sketching polygon features. Geo‐questionnaires have been used to learn about perceptions and preferences of city residents for specific types of land use, place‐based services, and development projects. This article reports on results of an empirical study, in which an online geo‐questionnaire was designed and implemented to elicit preferences of residents in guiding an urban development plan. Preferences collected in the form of polygon sketches were processed using GIS operations and mapped for visual interpretation. The article focuses on aggregation and analysis of respondent preferences including the analysis of positional and attribute uncertainty. Results of the study show that geo‐questionnaire is a scalable method for eliciting public preferences with a potential for meaningfully informing land use planning.     

第三次国土调查的图斑自动综合方法

从第三次国土调查数据库快速缩编派生出多尺度数据库,是地图制图的重要任务。本文针对大量图斑,首先通过研究图斑栅格综合,减少碎图斑数量;然后构建图斑语义邻近度模型、空间几何拓扑模型,分析了顾及拓扑和地区地理特征约束下的地类图斑制图综合方法;最后形成了自动化图斑缩编生产工艺流程。基于上述方法,采用计算机编程技术研发国土三调缩编系统,并应用于四川省某县23万图斑量的三调数据并试验验证。试验结果表明,通过本文方法的成果符合专题制图要求,极大地提高了三调图斑的自动综合效率。     

Cartographic Design Matters – A Comparison of Thematic Polygon Design

The number of web services providing cartographic data is increasing. A main challenge is to enable a user to combine these services, not only from a technical perspective, but also from a cartographic one. One common use case for these services is to create mashups based on thematic polygons on top of background maps. In this study we compare four cartographic designs of thematic polygons: only boundaries, transparencies, hatches and icons. The aim of the comparison is to investigate whether the designs are good for identifying the extent of the polygons and if the design disturbs the reading of the background map. The comparison is based on an eye-tracking study, where 24 participants performed polygon identification tasks as well as background search tasks. The study revealed that hatches were more efficient than the other designs for polygon identification. Hatches had significantly shorter total fixation times as well as scanpath lengths, possibly since the participants were able to identify the extent of the polygon solely based on the interior (i.e. the hatches), while for the other designs the participants were extensively reliant on the boundaries. However, the results also indicate that the hatches design disturbs the reading of the background map more than the other designs; hatches also appear visually unpleasant for many users. Since each design had its strengths and weaknesses, we recommend producers of services for thematic data to provide several designs so users can select an appropriate design for their own use cases.     

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。     

A web‐based visualization tool for exploring stakeholder conflicts in land‐use planning

This article describes an open source web‐based visualization tool for exploring stakeholder conflicts in land‐use planning. It implements a multi‐criteria, decision‐analytic framework which solves a conflict‐constrained knapsack problem in order to find Pareto efficient combinations of actions which maximize public value, given the conflict constraint. The user interface is centered around an interactive map in which geographical subareas are color‐shaded in proportion to the mean strength of preference for a particular chosen action within the population in the selected area. The aim of this work is to investigate the use of web technologies and formal problem‐solving methods for improving public participation in land‐use planning and support local governments in the pursuit of improved decision‐making. The tool was developed using the free statistical programming language R and the web application framework Shiny. Its usefulness is demonstrated through a case study in Upplands Väsby municipality in Stockholm County, Sweden. The article ends with a summary together with some ideas for future research and development.     

Small‐area patch‐merging method accounting for both local constraints and the overall area balance

Small‐area patch merging is a common operation in land use data generalization. However, existing research on small‐area patch merging has mainly focused on local compatibility measures, which often lead to area imbalances among land use types from a global perspective. To address the shortcomings of previous studies by resolving local and global concerns simultaneously, this article proposes a merging method that considers both local constraints and the overall area balance. First, a local optimization model that considers three constraints—namely, the areas of neighboring patches, the lengths of shared arcs, and semantic similarity—is established. The areas of small patches are first pre‐allocated. Subsequently, in accordance with an area change threshold for individual land use types, land use types with area changes that exceed this threshold are identified. The patches corresponding to these land use types are subjected to iterative adjustments while considering the overall area balance. Based on their area splitting abilities, the split lines for small‐area patches are determined, and small‐area patches are merged. Finally, actual data from Guangdong Province are used for validation. The experimental results demonstrate that the proposed method is capable of preserving the local compatibility of patches while balancing the overall area associated with each land use type.     

基于栅格化思想的矢量电子地图几何变化检测

在检测不同版本矢量电子地图的变化时,通常采用要素遍历、坐标比较的方法,这种方法计算速度慢、效率较低。针对这一不足,提出一种基于栅格化思想的矢量电子地图几何变化统计比较检测方法(SCAG),即利用矢量电子地图进行栅格化处理时构造的统计数据对点、线、面等形状地物的几何变化进行变化统计分析和要素快速检测,其计算量比遍历的方法显著减少,效率提高。最后通过实验验证了SCAG检测方法的可行性、合理性和高效性。     

Using Pattern‐oriented Modeling (POM) to Cope with Uncertainty in Multi‐scale Agent‐based Models of Land Change

Local land‐use and ‐cover changes (LUCCs) are the result of both the decisions and actions of individual land‐users, and the larger global and regional economic, political, cultural, and environmental contexts in which land‐use systems are embedded. However, the dearth of detailed empirical data and knowledge of the influences of global/regional forces on local land‐use decisions is a substantial challenge to formulating multi‐scale agent‐based models (ABMs) of land change. Pattern‐oriented modeling (POM) is a means to cope with such process and parameter uncertainty, and to design process‐based land change models despite a lack of detailed process knowledge or empirical data. POM was applied to a simplified agent‐based model of LUCC to design and test model relationships linking global market influence to agents’ land‐use decisions within an example test site. Results demonstrated that evaluating alternative model parameterizations based on their ability to simultaneously reproduce target patterns led to more realistic land‐use outcomes. This framework is promising as an agent‐based virtual laboratory to test hypotheses of how and under what conditions driving forces of land change differ from a generalized model representation depending on the particular land‐use system and location.     

土地利用数据库中大比例尺面状道路数据缩编研究

根据建立大比例尺多级土地利用数据库的需要,在进行面状道路数据综合时,对道路进行分类,保留需保持面状的道路面,将不符合要求的道路从网络状道路面中分离出来,并根据需要予以转线或删除,形成新的小比例尺的线面混合道路数据。同时,将删除的道路面分割并归并进相邻图斑,以保证土地数据面状连续的特点。     

A multi‐label cellular automata model for land change simulation

The use of cellular automata (CA) has for some time been considered among the most appropriate approaches for modeling land‐use changes. Each cell in a traditional CA model has a state that evolves according to transition rules, taking into consideration its own and its neighbors’ states and characteristics. Here, we present a multi‐label CA model in which a cell may simultaneously have more than one state. The model uses a multi‐label learning method—a multi‐label support vector machine, Rank‐SVM—to define the transition rules. The model was used with a multi‐label land‐use dataset for Luxembourg, built from vector‐based land‐use data using a method presented here. The proposed multi‐label CA model showed promising performance in terms of its ability to capture and model the details and complexities of changes in land‐use patterns. Applied to historical land use data, the proposed model estimated the land use change with an accuracy of 87.2% exact matching and 98.84% when including cells with a misclassification of a single label, which is comparably better than a classical multi‐class model that achieved 83.6%. The multi‐label cellular automata outperformed a model combining CA and artificial neural networks. All model goodness‐of‐fit comparisons were quantified using various performance metrics for predictive models.     

矢量化多边形优化方法

从地理空间数据不确定性理论出发,提出了矢量化多边形的优化方法。该方法通过对矢量多边形进行"磨角插值"和基于可接受域限定的自适应滤波平滑处理,以此来削弱由空间数据表示不确定性造成的误差,使矢量化多边形最大限度地逼近地理实体真实轮廓。采用基于全局阈值的DP算法进行压缩处理,消除了数据冗余。从压缩比、位置误差及处理效率3个方面进行对比实验,验证了所提方法的有效性。     

Assessing polygon edge integrity

Geographic entities are represented in vector GIS as geometric objects with definite position and sharp, zero or one-dimensional, boundaries. This representation ignores, and may in fact misrepresent, the underlying properties of many geographic features. This paper considers a binary classification scheme for ill-defined edges recently suggested by Couclelis (1996). Three initial perspectives of edge indeterminacy are considered for woodland polygons, namely functionally defined, using Hamming distances of the indeterminacy properties, and using the weighted trace of the connectivity matrix that defines the simplicial complex created from the indeterminacy relationships among the woodland polygons and their adjacent polygons. Finally, an analysis of the relationships created by the binary coding is carried out by examining more closely the connectivity structure of the simplicial complexes. The usefulness of the approach is discussed in the context of woodland habitat. Received: 20 March 1999/Accepted: 7 September 1999     

Polygon-to-Polygon Spatial Accessibility Using Different Aggregation Approaches: A Case Study of National Forests in the US Mountain West Region

Spatial accessibility is an enduring topic of spatial analysis that is intimately tied to issues of spatial representation and scale. A variety of methods to measure accessibility have been developed with most research focusing on metropolitan‐sized spatial extents using census‐defined aggregation units and relying on vector point representation to calculate Euclidean or network distances as key ingredients in measure formulations. Less research considers broader scales where both origin and destination points are treated as polygons. This research develops alternative gravity‐based measures of polygon‐to‐polygon accessibility for a case study of county‐level accessibility to national forests in the western US. Different methods of county and forest representation are implemented using census block centroids and a lattice approach for disaggregation and re‐aggregation. Other characteristics that are analyzed include origin‐destination linkage definitions, population weighting, and distance thresholds. Correlation analysis is used to assess relationships of alternative measures with a simple percentage measure and with each other. Low correlations would suggest that measures capture different aspects of accessibility that are related to their qualitative characteristics. Results show the alternative measures to be dissimilar from the percentage measure; however, high correlations among alternative measures suggest that there is little to differentiate certain disaggregated measures in spite of their richer qualitative interpretation.     

Delaunay三角网在图斑与点群目标综合中的应用

土地资源调查利用的土地类型数据多为不同比例尺电子矢量地图,以此数据为研究基础,详细介绍了Delaunay三角网及其Voronoi多边形的特性,以及在土地数据类型中的图斑综合与点群目标综合中的算法应用,具体描述了两种算法的实现过程和试验结果,并对几种点群目标算法进行了简要分析和比对,详细介绍了实现过程;重点阐述了图斑综合算法的思想和算法的具体实现.最后以"土地利用数据库智能化自动综合系统"为例验证了算法方案的合理性和可行性.     

利用骨架线端点匹配进行面状要素渐变变换

面向空间数据连续地图综合问题,提出了一种基于骨架线端点匹配的面状要素渐变方法,通过在两个关键表达之间进行尺度内插,实时、动态地派生任意中间比例尺地图数据。首先,对面状要素在大小比例尺下的两重表达分别进行约束Delaunay三角网剖分并提取各自的骨架线特征;然后,使用最优子序双射优化技术对骨架端点进行匹配获得多边形边界上相对应的特征点序列;最后,在剖分边界的基础上进行分段常规线性内插,获得面状要素介于始末尺度之间的多尺度表达。实验结果表明,该算法充分顾及了空间数据弯曲结构特征,对于光滑边界面状要素的渐变变换具有良好的渐变效果,可用于空间数据的连续地图综合和多尺度表达。