一种快速等面积分割平面简单多边形的算法  

A Fast Algorithm of Plane Simple Polygon Segmentation with Equal Areas

作　　者：吴建华[1,2] 张文朋 胡烈云 戴鹏 WU Jian-hua;ZH ANG Wen-peng;HU Lie-yun;DAI Peng(School of Geography and Environment,Jiangxi Normal University,Nanchang 330022;School of Geosciences and Info-physics,Central South University,Changsha 410012,China)

机构地区：[1]江西师范大学地理与环境学院,江西南昌330022 [2]中南大学地球科学与信息物理学院,湖南长沙410012

出　　处：《地理与地理信息科学》2020年第1期1-6,共6页Geography and Geo-Information Science

基　　金：国家自然科学基金项目(41561084、41201409);中国博士后科学基金项目(2018M632991);中南大学博士后科研启动金项目(189701)

摘　　要：针对平面简单多边形按相等面积划分问题,设计了一种顾及形态特征和面积精度的快速分割算法。首先计算出多边形的最小面积外包矩形(M ABR),确定其短轴方向为分割方向;然后根据MABR的长边距离与分块数计算出长边上的距离等分点,根据这些点构建初始分割线,并利用第一条分割线对多边形进行粗略分割;根据分割出的左多边形面积与目标分块面积差值转换成分割线的平移距离,沿长轴方向平移分割线,分割多边形,不断迭代,进行精细分割,直到满足面积精度要求;最后对分割出的右多边形按上述方法继续分割,直至完成分块。实验结果表明,相对于现有的两种算法,该算法的分割精度提升了1~2个数量级,处理性能分别提升了4127倍和7135倍。For the problem of dividing a plane simple polygon into equal-area blocks,this paper designs a fast segmentation algorithm considering morphological characteristics and accuracy of area.First,the minimum area bounding rectangle (MABR) of the polygon is calculated and its short axis direction is determined as the cutting direction.Then the equal-dividing points on the long side are calculated according to the long side distance of the MABR and the number of blocks.According to these points,the first dividing line is constructed,and the polygon is roughly divided by the first dividing line.Second,the deviation between the divided left polygon area and the target block area is converted into the translation distance of the dividing line and the dividing line is shifted along the long axis.Then the polygon is divided with the dividing line through continuous iteration for fine segmentation until it meets the area accuracy.Finally,the right polygon is further divided using the above-described method until the block dividing is completed.The experimental results showed that,compared with the existing two algorithms,the proposed algorithm improved the dividing accuracy by 1~2 orders of magnitude,and improved the processing performance by 4.27 and 7.35 times,respectively.

关 键 词：多边形分割 MABR 地类图斑 形状特征 GIS 

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