多边形分割算法在农村土地确权中的应用

刘苏，植江瑜

(1.广东瑞图万方科技股份有限公司广州分公司，广东 广州 510655； 2.环境保护部华南环境科学研究所，广东 广州 510655)

多边形分割算法在农村土地确权中的应用

刘苏1*，植江瑜2

(1.广东瑞图万方科技股份有限公司广州分公司，广东 广州 510655； 2.环境保护部华南环境科学研究所，广东 广州 510655)

针对农村土地确权工作中遇到的按比例划分地块的现实需求，提出了一种按照面积比例分割简单多边形的算法。该算法通过求取多边形最小外接矩形(MABR)判定多边形总体走势，据此生成初始分割直线，再根据目标子多边形面积与目标面积的差值调整分割线的位置，最终将多边形分割为两个边界合理的子多边形。利用该算法对实测农田地块进行一分为二的面积等分实验，实验结果表明：该算法适用于常见形状的农田地块，分割结果合理，效率高、误差小。

农村土地确权；面积比例；最小凸包；最小外接矩形；分割线调整

1 引 言

农村土地承包经营权确权，是根据法律规定和要求，将农民的土地承包经营权以法律文本、证书的形式进行登记，进一步巩固和完善农村土地承包关系，赋予农民更有保障的承包地财产权[1]。土地确权是农村土地产权制度建设中的基础一环，它提供的信息对公平、有效地进行土地管理十分必要，对科学制定相关政策、提高政策的针对性与有效性也大有助益。

当前，农村土地确权工作中常会遇到这样一个问题：一块耕地同时有多个承包经营者，而这些经营者通常是有血缘关系的，一般是兄弟。在这种情况下，若要进一步明确不同承包者对这一地块的具体经营权，则需根据实际情况，确定每个经营者所占的面积比例，再依据这一比例将地块分割成与经营者数目相同的若干子地块，从而确立每个经营者与每个子地块的一一对应关系。

实际工作中，面积比例的确定通常根据等分原则来进行：若N个经营者共同承包面积为S的地块，则将地块分割成N个面积为S/N的子地块，当然，有时也会遇到面积不等分的情况。若将地块视为平面多边形，则上述问题可抽象为基于目标面积的多边形分割问题，即已知多边形边界、需要分割的子多边形数目以及各子多边形的面积比例，确定分割线的精确位置的过程。

对此，目前农村土地确权工作者所采取的应对方式主要有两种：一是多次尝试，根据结果再进行手动调整，直到分割结果满意为止；二是直接忽略，不再进一步细分每个承包人的属地。前者效率低下，误差较大，且当数据量较大时无从应对；后者则不利于土地管理。而到目前为止，尚未有人就此提出更好的解决方法。

上述问题与基于目标面积修改多边形边界[2，3]的问题较为类似，不同的是前者不能改变原多边形边界，且要将多边形分成几份；后者则是通过修改多边部分顶点的位置，使多边形的面积达到目标面积[4]。本文受多边面积修改的算法思想启发[5]，提出了一种按面积比例分割简单多边形的全自动算法。

2 基本概念

为了下面叙述的方便，先给出几个相关的定义[6]。

定义1：设pi=(xi，yi)，i=1，2，3，…，n，pn+1=p1是给定多边形的n个顶点，若对任意i，j(i≠j)，i，j=1，2，3，…，n，线段pipi+1与pjpj+1或是相邻且相交于一端点或不相关，则称该多边形为简单多边形。

定义2：设p1，…，pn，pn+1=p1是一个简单多边形。若线段pi-1pi与线段pipi+1所成的内角(即由该多边形所围成有界区域内所形成的角)是一个不超过180°的角，则称pi顶点是凸的，否则称是pi凹的。

由此定义可知，对任意一个多边形，其每个顶点或是凸的，或是凹的。

定义3：设p1，…，pn，pn+1=p1是一个简单多边形。若沿p1→p2…pn→pn+1方向走，该简单多边形所围成的有界区域总在左边，则称该多边形的走向是逆时针的；反之，称其为顺时针的。

分割原则

实际工作表明，对地块进行分割时，需要分割的份数越多，遇到的概率就越小，因此，将地块一分为二的情况是最常见的。就算法实现的难度而言，当需要分割的数目越大，分割线求取的难度也就越大，因此将多边形一分为二的分割线的求取是最容易实现的。而实际上，将多边形分成N(N>2)份，可以转化成多次一分为二的运算，如要将一个多边形分割成面积相等的3个子多边形，可以先将多边形分成原来面积的1/3和2/3两份，再将2/3的部分平均分成两份。因此，本文提出的算法针对的是将多边形一分为二的情况。

根据既定的面积比例将多边形一分为二可以有无数种方案，而本文算法的目的是确定其中最合理且操作性最强的一种作为最终的解决方案。要从无数种方案中选出一种作为最终方案，则必须要有一定的准则可对不同的方案进行评价，因此，基于土地管理的实用性，文章提出了以下两大多边形分割的技术原则：

原则一：分割线上的控制点尽可能少；

原则二：分割线段尽可能短。

图1 将多边形一分为二的分割方案

由原则一可知，将多边形一分为二时，应采用直线分割法，因其只需要最基本的两个控制点即可，而折线或圆弧分割则需要较多的控制点，徒然增加实际工作量，因此上图中的方案a不可取；方案b、c、d均为直线分割法，控制点均只有2个，符合分割原则一，三者的区别在于分割线的长短，根据分割尽可能短的原则，方案d是最优的分割方案。分割线长短实质上反映了子多边形的面积紧凑度，在面积相同的情况下，周长越短，多边形面积越紧凑[7]，从土地利用的角度而言就具有更高的实用性。

上述例子中的目标多边形均为凸多边形，现实中会经常碰到形状为凹多边形的农田，对此类多边形进行一分为二的分割操作时，在确定采用直线分割法的前提下，还必须加上一个约束条件：直线分割操作能且只能将多边形分割成两个子多边形，以防出现如图2所示的将之边形分成了3个子多边形的情况。

图2 分割线将凹多边形分成3个子多边形

3 算法描述

算法的核心思想是绘制初始分割直线将多边形一分为二，选取其中一个子多边形作为计算对象，计算该子多边形与目标面积的差值(目标面积=对应面积比例*原多边形面积)，将面积差值除以分割线长度，得出分割线的调整位移，再根据调整位移作原分割线的平行线，得出新的分割直线，直到分割出来的子多边形的面积与目标面积的差值小于设定的误差限值为止，其运算过程如图3所示。

图3 算法简单图示

输入：多边形顶点序列；用户指定的其中一个子多边形的面积S目标(通过面积比例和原多边形面积求得)；用户根据分割原则绘制的分割直线。

输出：分割直线与多边形的两个交点的坐标。

步骤①根据分割原则绘制初始分割直线AB，如图3所示；

步骤②计算分割直线与多边形的交点A和B的坐标；

步骤③以图3为例，选择分割线左侧的子多边形(即图中阴影部分)作为调整对象，计算该子多边形的面积S子，多边形的面积计算公式为[8]：

步骤④计算子多边形的面积与目标面积的差值△S=S子-S目标；

步骤⑤若△S

步骤⑥计算分割线的调整位移offset=△S/|AB|；

步骤⑦将直线AB沿其垂线方向平移offset个单位，得到调整后分割直线CD；

步骤⑧计算调整后的分割线与多边形的新交点C和D的坐标，将C→A；D→B

重复步骤④到步骤⑧。

完整的算法流程如图4所示；算法运行的效果如图5所示，图5中黑色粗线为初始分割线，颜色各异的平行细线则是每次调整后的分割线，从其轨迹可以看出，算法通过多次迭代让分割线逐步趋近最终的精确位置。

图4算法流程图

图5 算法计算效果图

在多边形的形状和误差限值给定的前提下，初始分割线距目标位置越远，其初次迭代时调整位移offset的值就越大，但随着迭代次数的增加，该值会越来越小，最终固定在满足精度要求的目标位置上。而算法的精度只与设定的误差限值相关，与多边形的形状无关，只要运算结果的误差值小于设定误差就会终止迭代，其具体数值则与多边的形状有关，具有一定的随机性，但均会满足精度要求。如图5十边形面积等分结果与图6喇叭状多边形的面积等分结果均为误差限值设定为0.1个单位的运算结果，前者的实际误差值为0.093个单位，后者则为0.089个单位，就统计意义上而言，两者精度等级是一样的。理论上，设定的误差限值越小，运算结果的精度就越高，但迭代次数会明显增加，严重降低运算效率。

图6 喇叭状多边形面积等分运算结果

4 算法进阶

上述多边形分割算法只是半自动算法，用户仍需要手动输入分割直线，若分割线输入不符合最优化原则，得出的分割结果也会不理想，如图7所示。

图7 手动输入不合理分割线情况

用户在绘制分割线前，实际上还包含了多边形总体走势的判断，然后用户根据判断结果绘制其认为最合理的分割线。若多边形的边界十分复杂，人工判断多边形的总体走势较为准确，但当数据量较大时，依靠人工判断多边形总体走势然后据此画出分割线效率太低，不能进行批处理，若能将多边形走势判断及分割线绘制都交给计算机处理，则能应对数据量较大的情况。

实际工作中，农田地块大多是较为规则的四边形，或者总体呈四边形走势。进行多边形总体走势判断，在此可以归纳为多边形最小面积外接矩形(Minimum Area Bounding Rectangle，简称MABR)的求取。除MABR外，多边形还有一种常用的外接矩形，称为最小绑定矩形(Minimum Bounding Rectangle，简称MBR)，即以多边形顶点中最大、最小坐标确定的矩形，如图8所示；其计算非常简单[9]，在此不再赘述。

图8 多边形的MBR与MABR

本文采用文献[10]提出的MABR计算方法，其算法计算步骤如下：

第1步计算多边形最小凸包。计算多边形最小凸包的算法有很多，如Graham算法、卷包算法、分治算法等[11，12]。其中由于Graham算法的时间复杂性最低[13，14]，故此处选用该算法。多边形最小凸包计算涉及多边形的正反向判断[15]、多边形顶点的凹凸性判断等算法[6]，在此不再累赘。

第2步选取所得凸包中一条边作为起始边并对该凸包以选中边的左端点为中心旋转使平行坐标横轴，计算并保存其MBR的坐标、该边的编号、旋转角度及面积。

第3步按顺序选择其他边，并按照第2步的方法计算并保存其MBR的坐标、该边的编号、旋转角度及面积。

第4步比较所得的MBR的面积，其中面积最小者按其记录的旋转角度以该边的左端点为圆心逆向旋转即为所求的MABR。

根据上述算法求得多边形的MABR后，比较其MABR的两相邻边的长度，取较长对边的中点作为分割线的两个端点，然后执行上述步骤2到步骤9的计算过程，就完成了基于目标面积的多边形全自动分割，完整的算法流程图如图9所示。

图9全自动算法流程图

5 算例分析

为验证本文算法的实用性，取广东省某行政村XXX村的农田数据作为实算基础数据。如上文所述，项目组在对该村进行土地确权时，就碰到了十几例需要对农田地块进行等分切割的情况。为了更好地验证算法是否适用于各种形状的农田地块，现假设该村所有490个农田多边形均需要进行等面积分割，分割的误差限值设为 0.1 m2，分割前后的情况对比如图10所示。

图10 算例效果图

XXX村农田地块多边形信息统计 表1

算例运算信息统计 表2

图11 各多边形的分割误差

表1显示，XXX村的农田多为四边形，其占比接近50%，而随着顶点的增加，多边形的数量急剧下降，由此可见，该村农用地块多为形状较为规整的四边形。由图10的分割结果可以看出，本算法的多边形面分割算法结果合理；表2显示，算法分割误差要小于 0.1 m2，平均迭代次数不超过3次，而分割的平均误差则不到 0.03 m2。

6 结 论

本文针对农村土地确权中普遍存在的“一地多承包人”的问题，提出了根据面积比例分割多边形的算法，该算法综合了多边形最小凸包计算、多边形最小外接矩形计算、分割直线调整等子算法，实现了全自动分割多边形的功能。利用本文算法对实测农田地块数据进行了面积等分实验，结果表明，对常见形状的农用地块，算法适用性强、分割结果合理、误差较小、效率较高：完成490个多边形的分割时间只需29ms，能胜任多数情况下农田多边形分割运算，具备较强的批处理功能，能切实提高实际工作中解决此类问题的精度及效率。

[1] 李秀川. 山西省农村土地承包经营权确权技术模式与推进措施研究[D]. 西安：西北农林科技大学，2012.

[2] DAVID A，DAVID P. Equal-area locus-based convex polygon decomposition[C]. Structrual Information and Communication Complexity，2008：141～155.

[3] SIVAKHOLUNDU K M，PRABAHARAN N. A program to compute the area of an irregular polygon on a spheroidal surface[J]. Computers & Geosciences，1998，24(8)：823～826.

[4] Mark K J，TZVETALIN S V. Algorithm for optimal area triangulations of a convex polygon[J]. Computational Geometry；Theory and Applications，2006，25(3)：173～187.

[5] 方雷，张华鑫，姚申君. 一种基于面积修改简单多边形的算法[J]. 华东师范大学学报·自然科学版，2011，2：77～88.

[6] 刘润涛. 任意多边形顶点凸、凹性判别的简捷算法[J]. 软件学报，2002，13(7)：1309～1312.

[7] 毛亮，李满春，刘永学等. 一种基于面积紧凑度的二维空间形状指数及其应用[J]. 地理与地理信息科学，2005，21(5)：11～14.

[8] 罗志强，钟尔杰. 任意多边形面积公式的推导及其应用[J]. 大学数学，2005，21(1).

[9] 闫浩文. 空间方向关系理论研究[M]. 成都：成都地图出版社，2003：23～24.

[10] 程鹏飞，闫浩文，韩振辉. 一个求解多边形最小面积外接矩形的算法[J]. 工程图学学报，2008，1：122～126.

[11] 吴文周，李利番，王结臣. 平面点集凸包Graham算法的改进[J]. 测绘科学，2010，35(6)：123～125.

[12] 周培德，卢开澄. 计算几何——算法分析与设计[M]. 北京：清华大学出版社，1999： 57～58.

[13] Graham R L. An Efficient Algorithm for Determine the Convex Hull of a Finite Planar Set[J]. Information Processing Letters，1972，1(1).

[14] Chand D R，Kaqur S S. An Algorithm for Convex Polytopes[J]. JACM，1970，17(1).

[15] Yao A C. A Lower Bound to Finding Convex Hulls[J]. JACM，1981，28(4).

ApplicationofAlgorithmforDividingPolygoninConfirmationofRuralLand

Liu Su1，Zhi Jiangyu2
(1.Guangdong Ruituwanfang Technology Co.，Ltd，Guangzhou 510655，China；2.South China Institute of Environmental Science.MEP，Guangzhou 510655，China)

In the confirmation of rural land contractual operation right，it often occurs that more than one person share a single piece of land，which asks a demand for a useful method of dividing a piece of land at specific area ratio. Aiming at this requirement，a new algorithm for dividing simple polygon according to target area was proposed in the paper. First，the algorithm identified the general trend of polygon by calculating its minimum area bounding rectangle (MABR)，then generated the initial dividing line based on its MABR. After that，it adjusted the position of dividing line according to the difference between the area of the divided sub-polygon and the target area until the value of area difference descended to zero. Finally，we got two sub-polygons with target area as well as reasonable borders. For testing the practicality of this method，an experiment was taken. The results show that the algorithm is efficient，accurate and practical.

rural land contractual operation right；area ratio；minimum convex hull；minimum area bounding rectangle；dividing line adjustment

1672-8262(2017)06-146-06

P209

B

2017—02—21

刘苏(1989—)，女，硕士，工程师，现主要从事测绘地理信息相关工作。

植江瑜(1987—)，男，硕士，工程师，现主要从事环境信息系统方向研究。