一种基于梯形剖分的多边形布尔运算方法  

Boolean Operations on Polygons by Using Trapezoidal Decomposition

作　　者：崔璨[1] 王结臣[1] 

机构地区：[1]南京大学地理信息科学系,江苏南京210093

出　　处：《测绘学报》2011年第1期104-110,共7页Acta Geodaetica et Cartographica Sinica

基　　金：国家基础科学人才培养基金(J0830518);国家自然科学基金(40601074)

摘　　要：借鉴计算几何学的理论方法,提出一种基于多边形梯形剖分思想的实现方法。首先利用扫描线技术将多边形分解为梯形面片集,以便将多边形的布尔运算转化为梯形面片间的布尔运算;这些梯形面片以扫描行为单元进行组织,梯形之间的布尔运算被限定在相同的扫描行内,可有效简化核心计算过程;在完成梯形单元布尔运算并得到结果梯形集后,通过边界追踪完成多边形重构。该方法可规避多数矢量算法中多边形各边之间复杂的空间关系判断,实现过程相对简单,具有较高的计算效率且易于理解。同时,借助简单的多属性条件提取,可实现GIS中的Union、Erase、Clip、Intersect等多种类型的空间操作,具有拓展性。A new algorithm for Boolean operations is presented,which incorporates trapezoidal decomposition.The involved polygons are decomposed into two sets of trapezoids by the sweep-line,therefore Boolean operations on polygons are transformed into the Boolean operations on the decomposed trapezoids.Since these trapezoids are organized and stored by row,thus the Boolean operations between them are confined within one row;in consequence,the computation efficiency could be improved.Once the resulting set of trapezoids is obtained by implementing Boolean operations on the two original sets of trapezoids,the resulting polygons need to be constructed by means of boundary tracing.The proposed method avoids the complex computation of spatial relationship between polygons＇ edges in most vector algorithms for Boolean operation,thus making the whole procedures more efficient and understandable.In addition,by adopting multi-attribute condition extraction,this method could realize various Boolean operations in a unified way,without the necessity of designing respective methods targeting at each operation.

关 键 词：梯形剖分 布尔运算 空间分析 地理信息系统 

分 类 号：P208[天文地球—地图制图学与地理信息工程]