Delaunay三角网支持下的多边形化简与合并
摘 要
多边形的化简与合并运算是自动化制图综合中的重要算子,这类算子的设计要基于多边形几何特征,拓扑特征的分析,还需要一种有力的空间数据模型用于支持多边形各弯曲特征部位之间,多边形与多边形之间,多边形的各岛屿之间邻近关系探测,鉴于Delaunay三角网的“最大最小角规则”和“外接圆规则”,使得其成为空产邻近分析的一种强有力工具,因此在二维空间建立约束Delaunay三角网模型和形式检索机制的基础上,系统地讨论了多边形弯曲特征的化简,夸大,以及邻近多边形合并的方法,并将多边形化简分解为“岛屿”选取,凹部填充,狭长区域中轴化,保留凹部的夸大,以及凸部的弃除等几个步骤完成,又将多边形合并区分为吸刷式,包络式,分解式等3种情形,同时给出了这些算法的实验结果。
关键词
Simplification and Aggregation of Polygon Object Supported by Delaunay Triangulation Structure
() Abstract
Polygon simplification and aggregation play an important role in automatic cartographic generalization. Design of this kind of operator algorithm requires to consider geometric and topological characteristics, and needs to find a spatial data model to support extraction of interesting adjacent area, such as bend feature, gap region between polygons, neighbor area between islands within polygon. In this process, detection of neighbor relation is a key step. Delaunay triangulation structure is a powerful tool of spatial neighbor analysis due to its circumcircle principle and closest to equilateral properties. Applying Delaunay triangulation principles, this paper presents a spatial data model and constructs formal selection strategies. On the basis of constructed model, the study systematically investigates the problem of polygon bend simplification, exaggeration as well as neighbor polygon aggregation. The paper divides polygon simplification into steps: islands selection, concave part fill, shallow area skeletonizing, concave part exaggeration and convex part clip. As for polygon aggregation, it is classified as three cases: absorbing, enclosing and separating and three methods are discussed respectively. Some of operator algorithms are presented in the paper and corresponding experiment results are illustrated.
Keywords
|