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

摘要

针对平面简单多边形按相等面积划分问题,设计了一种顾及形态特征和面积精度的快速分割算法。首先计算出多边形的最小面积外包矩形(M ABR),确定其短轴方向为分割方向;然后根据MABR的长边距离与分块数计算出长边上的距离等分点,根据这些点构建初始分割线,并利用第一条分割线对多边形进行粗略分割;根据分割出的左多边形面积与目标分块面积差值转换成分割线的平移距离,沿长轴方向平移分割线,分割多边形,不断迭代,进行精细分割,直到满足面积精度要求;最后对分割出的右多边形按上述方法继续分割,直至完成分块。实验结果表明,相对于现有的两种算法,该算法的分割精度提升了1~2个数量级,处理性能分别提升了4127倍和7135倍。