基于德劳内三角化和二分查找法的土地自动分配方法

梁其洋，吴保国，赵春江，潘瑜春，胡 萌，郝星耀



基于德劳内三角化和二分查找法的土地自动分配方法

梁其洋1，吴保国1※，赵春江2,3,4，潘瑜春2,3,4，胡 萌5，郝星耀2,3,4

（1. 北京林业大学信息学院，北京 100083；2. 国家农业信息化工程技术研究中心，北京 100097；3. 农业部农业信息技术重点实验室，北京 100097；4. 北京市农业物联网工程技术研究中心，北京 100097；5. 河南大学环境与规划学院，开封 475004）

为解决预分方案制定效率低的问题，该文提出一种基于德劳内三角化和二分查找法的地块分配算法。首先生成待分配地块的最小边界几何（minimum bounding geometry，MBG），对MBG进行三角剖分；其次在地块内通过累加三角形的面积执行查找，接近合同面积时采用二分查找法进行微调；最后遍历项目区内所有地块直至生成土地预分配方案。通过对算法进行编程实现，以试验区的土地整治项目为例对算法的可行性进行验证，并从分配效率、精度和形状指数3个方面对结果进行评价。结果表明：项目区内的地块划分仅需231 s，与仅用二分查找法相比，采用该文方法分割效率提高29.3%，精度提高28.2%，形状规则度提高18.2%；在减少农用道路占地面积的同时，分割后的地块具有良好的通达性。该方法可满足自动创建和动态调整土地分配方案的需求，为在一定约束条件下制定最优土地分配方案提供了技术支撑。

土地利用；算法；土地整治；土地分配；二分查找；德劳内三角化；地块分割

0 引 言

土地整治项目实施过程中需按照规划设计打破原有地块布局，同时优化配置农田水利及道路设施，从而导致原有的土地权属界线或标志物不复存在，而新的承包地块的划分将导致原有利益格局发生分化，涉及到土地所有者、使用者、他项权利人的权属调整[1]。目前大部分土地整治项目完工后只划分到大地块，没有对大地块进行详细划分，而是交给村委会由村委会主观划定，结果一般是保持各户地块位置和数量不变，未能改变耕地分散的现状、实现土地承包者的地块集中，不利于土地规模经营。

土地分配是将耕作地块分割为较小的子空间并最终获得由规则地块构成的土地分配方案的过程[2]，地块调整往往伴随着权属调整，而权属调整是一种利益敏感的行为，直接关系到土地权利人的根本利益[3]。因此，土地分配方案的制定是土地整治过程中最重要也是最耗时的步骤之一[4]。当前，这一规划和决策过程的自动化程度较低[5]。传统的分配方法是技术员利用裁剪、合并等地理工具的组合，对地块逐一进行操作，切分出相应面积的地块，再结合字段计算器求解出每个地块的面积[6]。该方法需频繁进行面积查询以及人工输入操作，不仅工作效率低，而且容易产生各种操作错误。当所涉及地块的质量差异较大时，这一过程还将面临周期长、操作成本高及利益相关者之间的利益冲突等问题[7]。

整治合并后的大地块的几何形状并非都很规则，限制了在分割过程中使用数学建模的方式计算分割线的位置和子地块的大小[8]。常用的自动化地块分割方法有步长法[6]、决策模型法[9-10]和遗传算法[11-12]等，虽然能够完成土地分配任务，但也存在诸多不足。步长法难以随土地经营承包权合同面积（以下简称合同面积）的改变动态地调整步长，无法兼顾精度和效率；决策模型法考虑的地块外部因素较多，如连片性因素、区位因素和行政因素等，更适合从宏观角度进行划定；基于遗传算法难以统一分割方向，无法保证地块通达性。考虑到这些模型或算法的效率和复杂性，当一个项目有大量地块时，这些方法难以快速制定出理想的土地预分配方案，存在分割精度和效率方面的不足。

针对以上问题，本文提出一种高效且满足实施标准的土地分配方案自动制定方法。该方法基于二分查找（binarysearch，BS）和德劳内三角化（Delaunaytriangulation，DT），可以自动确定不规则地块的分割起点，并快速计算出顾及地块等级、面积、形状和通达性的地块边界，输出子地块价值相等、利于实际耕作的土地分配方案。

1 方法与流程

1.1 基本原理

1.1.1 德劳内三角化

三角化是将给定地块剖分成不相交的三角形网格，这些三角形的顶点代表地块边界的节点，地块是三角形的集合。对地块进行三角剖分的目的是将目标的查找空间从整个多边形区域降至较小的三角形区域，再通过累加三角形的面积来接近目标面积值[13]。三角剖分的方法有很多[14]，由于德劳内三角化具有优越的特性，如大致全等三角形、最大化最小角和边的和最小，剖分出来的三角形网格均匀，从而保证了整体剖分质量最优[15]，所以本文选择德劳内三角化作为地块的剖分方法。

实践证明，形状不规则的地块直接利用边界上的节点进行德劳内三角化的结果过于复杂不便于遍历。本文采用了一种新的实现方式，即首先获得地块的最小边界几何（minimumboundinggeometry，MBG），将MBG短边上的节点剔除，在长边上按一定距离加密节点，将处理后的MBG进行德劳内三角化。遍历三角形进行面积累加时，取其与原始地块交集的面积作为基数。

图1为采用最小边界几何进行德劳内剖分的示例。剔除MBG短边上的节点后，按100 m的间隔加密长边节点，对MBG进行德劳内三角化，取原始地块与各三角形交集的面积作为三角形的面积，这样既能够通过控制节点间距获得合适的剖分效果，又保持了原始地块的完整，避免了原始地块剖分后再合并产生的开销。此外，MBG的4个顶点始终处于地块外部，有利于确定分割轴后根据顶点处的坐标极值动态地生成与地块完全相交的分割线。

注： xmax、xmin、ymax、ymin代表4个顶点的坐标极值。

1.1.2 二分查找法

利用BS法进行地块分割，即从地块的中间开始执行分割，如果目标值小于一半空间，则继续在下半部分查找；反之，则在上半部分查找。此过程循环进行，一次排除一半空间，并将目标值与剩余空间进行比较，直到找到目标值为止。在查找空间减少到一半大小的每次迭代中，算法的复杂度为O(log2)。由于BS法在确定分割线的位置时存在大量运算，当合同面积较小或待分割地块较多时会由于分割次数较多而影响计算效率，而将地块德劳内三角化可以减小BS的搜索空间。因此，本研究结合BS和DT进行地块分割，以达到土地分配所需的精度和效率。

1.2 土地分配流程

本研究的目标是通过对整治合并后的地块进行划分，得到地块满足价值、面积、形状规则度和通达性等约束的土地预分配方案。地块划分的基本工作流程可归纳为以下4步：1）输入合同面积，根据耕地价值指数确定子地块该划分的实际面积；2）确定待分割地块的分割轴和分割方向，并将其MBG德劳内三角化；3）基于三角形累加和二分查找法执行划分；4）地块划分方案输出。具体地，生成一个土地预分配方案的算法流程如图2所示。

图2 基于BS-DT的土地自动划分流程

1.3 地块划分实现方法

在地块划分过程中，为满足地块通达性约束，一般沿地块走向或路渠方向进行处理[17]。首先，提取地块的MBG及其4个端点，计算出各边中点，将对边中点连线形成、轴；比较2轴的长短，以代表地块走向的长轴作为分割轴。分割轴有2个用途：一是通过计算与2坐标轴的夹角判断分割方向及分割起点，当水平夹角大于竖直夹角时，地块沿竖直方向细分，反之沿水平向细分；二是沿垂直于分割轴的方向动态计算分割线。图3显示了分割一块面积为121 hm2地块的步骤。将长轴作为轴，短轴作为轴，由于轴与坐标轴的夹角大于与坐标轴的夹角，分割时在竖直方向上沿轴分割。三角剖分完成后，从轴2端点中坐标值较小的一端开始遍历，直到三角形的面积累加到接近合同面积（误差±5%）。三角形累加终止时，沿终止处的三角形的重心作轴的垂线作为分割线对原地块进行分割。

注： X、Y为候选分割轴，x、y为坐标轴。

由于大多数地块不可能仅通过一次分割就生成指定面积的地块，取终止处三角形的前一三角形的坐标最小值作为下限，后一三角形的坐标最大值作为上限，在该上下限组成的区间内运用BS法进行微调，通过更新这些最大值和最小值，迭代数次后完成微调。查找到符合容差范围的面积后，将原始地块中位于该面积范围内的所有多边形合并以完成本次分割。对剩余待分割部分合并后迭代执行这一过程即可完成整个地块的分割。对不足一个子块的剩余部分，可以合并到邻接的子地块中或者作为固定设施的预留用地。

使用BS法查找合同面积的地块时，事先对地块进行三角剖分可以减少BS法的查找空间。在对图4所给出的样地使用BS-DT法划分子块时，初步查找到的合同面积由三角形累加完成，不涉及复杂运算；微调区间由第一条分割线所在三角形及其前后2个三角形组成，在此区间内利用BS法查找5%左右的合同面积。

1.4 评价指标

为验证BS-DT法应用在土地分配上的可行性，依据耕作地块的几何特征和社会属性，按照重要性选取地块价值、面积相对误差和地块形状指数3个指标对土地划分结果进行评价。由于不同价值的地块可以通过耕地价值指数转换成同一价值，地块价值差异最终转换为面积差异[18]，故按照价值统一后的面积相对误差进行评价。

图4 BS法和BS-DT法的查找空间

1）面积相对误差Area。Area为计算面积与合同面积之差的绝对值占合同面积的百分比，取值介于0～1。面积精度是农业资源调查和承包地权属调查工作中的主要技术指标之一，《农村土地承包经营权调查规程》（NY/T 2537-2014）中明确提出，航测法、图解法测得的承包地块，其面积计算的相对误差不应超过5%[19]。以Area为评价指标的目标函数为

式中为子地块的编号；为子地块的数量。

2）地块形状指数（parcel shape index，PSI）。PSI是一个多参数指标，包括短边数、锐角数、优角数和折点数4个参数，各参数的测算方法如表1所示。对于耕作地块而言，过短的边长、过多的锐角、优角和折点会严重影响农业机械的使用[20]，为满足机械作业要求，必须使设计的地块至少具有一个直角且地块2个长边平行。因此，地块形状最好为内角为90°或接近90°的矩形。PSI的计算方法为

式中=1/ln。计算得到的各形状参数对应的权重系数如表1所示。

表1 形状指标的参数测算方法[23]

形状指数PSI的取值介于0～1。通常将PSI分为4类，PSI为0～0.50时认为形状是高度不规则的，PSI为0.51～0.70时是不规则的，PSI为0.71～0.90时是规则的或接近规则的，PSI≥0.91时是最优或接近最优的[23]。基于此，以偏离最优形状指数的累计误差作为评价依据，目标函数为

2 实例分析

2.1 研究区概况

本文以河北省顺平县的土地整治项目为案例进行研究。顺平县位于河北省保定市西郊，地理坐标为115°11′24″～115°15′25″E，38°47′28″～38°50′56″N。项目区涉及顺平县的2个镇12个村，区内耕地总面积1 838.92 hm2。项目区属于北方旱作区，地势较为平坦开阔，局部略有起伏，土层比较深厚，土壤母质绝大部分为黄土性黏土，主要作物为小麦和玉米。整治前项目区的耕地布局如图5所示，具体表现为小地块数量多，形状支离破碎，田间道路数量较多，每户农户承包的地块分散，以农业为主要工作的劳动力的人均耕地面积约0.02 hm2。

图5 项目区整治前地块分布

2.2 研究方法与实现

在土地整治方面国际上通用的土地权属调整方案有面积法和价值指数法2种[24]。面积法是根据土地整治前耕地的面积和位置，坚持“面积等量”的原则，确定土地权属调整后耕地的面积和位置的方法。耕地价值指数法是根据土地整治前后耕地质量等级的高低，运用耕地价值指数的比值作为面积折算系数确定划分地块的方法[25]。

面积法和价值指数法分别适用于不同的场合，面积法不需要考虑土地整治前后耕地价值的变化，使用比较简单方便，仅适用于权属调整前后土地利用条件差异不大的情况。价值指数法运用起来更复杂，但也更科学更具说服力，适用于调整前后土地利用条件差异较大、无法简单确定面积折算系数的情况[26]。土地权属调整的基本要求是土地承包者新承包耕地的价值总额与权属调整前相同或有所提高[27]。由于项目区的耕地经过整治后数量和质量等级发生了变化，鉴于土地权属调整过程的利益敏感性，价值指数法虽然比较复杂，但能综合体现权属调整中地块的价值，确保土地权属调整按等价值进行[28-29]，因此，本文采用价值指数法进行地块划分。

使用C#语言在Visual Studio 2015平台下开发针对BS和BS-DT 2种算法的土地自动分配原型系统，并利用研究区的数据进行测试分析。测试环境如下：Windows7操作系统、Inteli73.4 GHz4核处理器、8G内存，空间数据以文件形式储存。

2.3 结果与分析

根据《农用地定级规程》（GB/T 28405-2012）得到的整治后土地质量分等定级图如图6所示。项目区的土地基于BS-DT法和价值指数法划分的结果如图7所示。在合同面积不变的前提下，运用BS-DT法进行多次重复划分子地块的形状和空间位置不发生改变，说明该算法具有较强的稳定性。划分得到的地块需要满足3个约束条件：面积精度、形状规则度和通达性[30]。其中，地块通达性是必须满足的硬性约束，面积精度和形状规则度是允许有一定误差的弹性约束。下面采用定性分析和定量分析相结合的方法对2种算法的划分效果进行对比分析。

土地整治过程中归并了不必要的路渠，农用道路和沟渠占地面积由52.7 hm2减少到35.8 hm2，增加了有效耕地面积。本文的地块布设与分配方法充分结合了整治后的道路、河渠，将代表地块走向的长边方向与路渠方向保持一致，地块划分时均沿垂直于路渠的方向进行，从而保证了划分出的每个子块都至少与一条道路或河渠相通达。

注： ~表示整治后地块的编号。

图7 基于BS-DT的土地划分结果

本文从分割耗时、面积精度和形状指数3个方面对2种算法的划分结果进行量化分析。为避免系统误差，分别采用2种算法对各地块重复划分10次，并统计耗时的平均值。图8给出了合同面积为6.67 hm2的约束下各地块分别采用2种方法划分的耗时比较。

图8 BS法和BS-DT法耗时比较

由于耗时只与地块被分割的次数相关，因此将图8横坐标按子地块数目升序排列后，纵坐标上耗时总体上能够反映随分割次数递增的趋势，证明了算法的有效性。随着分割次数的增加，2种算法的耗时相对差距逐渐增大。由于BS-DT法能够缩小所有地块的查找空间，因而比BS法效率更高，在本案例中，BS-DT和BS法生成土地预分配方案的时间为分别为231和327 s，前者总体效率高出29.3%。

分地块统计子地块的累计面积相对误差和累计形状指数误差如表2所示。从表2可以看出，2种方法生成的各子块的面积相对误差均满足5%的约束。其中，仅采用BS法各子块的面积平均误差为2.16%，而BS-DT法的面积平均误差为1.55%，提高了28.2%。采用BS-DT法，单个地块中除地块10和12的Area比仅用BS法稍大，其他地块的面积精度均高于仅用BS法。地块10和12的形状复杂度较高，限制了BS-DT对面积误差的减少。

划分结果中形状规则的地块（PSI≥0.71）占73.3%，不规则地块占26.7%。这部分不规则地块通常位于分割轴两端，是由第一次或最后一次切分产生，不能保证至少有两条边平行，因而形状不规则度较高。由于本文划分地块时以面积精度作为主要约束，2种方法均不针对地块形状做过多的调整，地块形状指数的差别不能显著得反映在每个地块的上，但表2中的结果显示BS-DT法具有一定优势，总体规则度提高18.2%。

表2 2种算法下的面积相对误差和形状指数误差比较

从试验结果总体来看，在同样满足面积精度、形状规则度、通达性约束的前提下，BS-DT法在效率、精度和形状规则度方面均优于BS法。由于项目区内以农业为主要工作的劳动力的人均耕地面积约0.02 hm2，每个子地块还需进一步细分，随着待分割地块数量的增加，采用BS-DT法的优势将更加明显。

4 结 论

1）本文以快速制定土地整治项目所需的土地预分方案为目标，针对不规则地块的等价值分割问题，设计了基于BS-DT的土地分配方法，该方法具有参数设置简便、人工干预少和易于进行系统化实现的优势，制定土地预分配方案仅需231 s，且新划分地块均具有良好的通达性，规则地块占比为73.3%。在保证土地分配作业过程公平公正的基础上，能够缓解地块分散破碎和分配不均的问题，最大程度地提高农户的满意度和耕作的便利度，具有较好的应用推广价值。

将基于分等成果的区域耕地质量等级转换为价值指数，以价值指数的比值作为面积折算系数使地块按等价值进行划分，有利于维护农户的利益。为使本文方法更具针对性，耕地价值指数的确定需要进一步研究，应充分考虑区域内耕地的自然属性、经济属性和生态属性，选取主要影响指标，通过对价值影响因素的综合评价确定适合该区域的耕地价值指数。接下来还应结合农户对承包地块调整的意愿，在坚持自愿原则的基础上，实现程序化地块调整与农户自主择地意愿的耦合。对于不适合应用耕地价值指数的情况，如地块上有固定设施（温室，灌溉井等），由于该地块在其所有者心目中远比一般地块重要，进行土地权属调整时，应优先将该地块划分给原所有者或者采取其他补偿措施。

通过扩展以价值、面积、通达性和规则度为主的评价指标，本文方法可满足不同场景的应用需求，如以耕地质量、耕作距离和耕作可达性等为约束指标可以自动划分出耕地保护分区。随着农村土地适度规模化经营成为趋势，现代农业生产中没必要每个成员都有明确的地块界限，只需在理论上明确在区域耕地上占有的产权份额，但本文方法可推广应用到耕地保护分区、农用地自动分等定级及田块规划设计等领域。

[1] 王长江. 农村土地整治权属调整与管理模式研究[D]. 北京：中国矿业大学，2011.

Wang Changjiang. Study on Property Adjustment and Management Models of Rural Land Reclamation[D]. Beijing: China University of Mining and Technology, 2011. (in Chinese with English abstract)

[2] Uyan M, Cay T, Akcakaya O. A spatial decision support system design for land reallocation: A case study in Turkey[J]. Computers & Electronics in Agriculture, 2013, 98(98): 8－16.

[3] 关江华. 土地整理权属调整研究[D]. 武汉：华中农业大学，2008.

Guan Jianghua. Study on the Readjustments of Land Property Rights in Land Consolidation[D]. Wuhan: Huazhong Agricultural University, 2008. (in Chinese with English abstract)

[4] Demetriou D, See L, Stillwell J. A spatial multi-criteria model for the evaluation of land redistribution plans[J]. ISPRS International Journal of Geo-Information, 2012, 1(3): 272－293.

[5] Demetriou D, Stillwell J, Seel L. Landspaces: A spatial expert system for land consolidation[C]//Advancing Geoinformation Science for A Changing World. DBLP, 2011: 249－274.

[6] 杨林波，刘欧，谢飞，等. 基于ArcMap的地块分割插件设计与实现[J]. 地理空间信息，2016，14(10)：80－81.

[7] Demetriou D, Stillwell J, See L. Laconiss: A Planning Support System for Land Consolidation[M]// Planning Support Systems for Sustainable Urban Development. Springer Berlin Heidelberg, 2013: 73－90.

[8] Theodor J S, Ron J. A multiobjective GIS-based land use planning algorithm[J]. Computers Environment & Urban Systems, 2014, 46(7): 25－34.

[9] 石英，程锋，朱德举. 基本农田保护区划定自动化成图中图斑分割决策模型研究[J]. 地理与地理信息科学，2003，19(5)：39－42.

ShiYing, ChengFeng, ZhuDeju. Studyondecision-makingmodelsofpolygonpartitionduringthemappingautomaticallyofprimefarmlandprotectionplanning[J]. GeographyandGeographicInformationScience, 2003, 19(5): 39－42. (in Chinese with English abstract)

[10] Ayranci Y. Re-allocation aspects in land consolidation: A new model and its application[J]. 2007, 6(2): 270－277.

[11] Demetriou D. LACONISS: A land consolidation integrated support system for planning and decision making[J]. Zfv Journal of Geodesy, Geoinformation und Land Management, 2013, 138(2): 119－131.

[12] Demetriou D, See L, Stillwell J. Integrating GIS and genetic algorithms for automating land partitioning[C]// International Conference on Remote Sensing and Geoinformation of the Environment, 2014: 2391－2409.

[13] Haklı H, Uğuz H, Çay T. A new approach for automating land partitioning using binary search and Delaunay triangulation[J]. Computers & Electronics in Agriculture, 2016, 125: 129－136.

[14] 蒋恒恒. 自适应三角剖分算法及其关键技术研究[D]. 重庆：重庆大学，2012.

Jiang Hengheng. Research on Adaptive Triangulation Algorithm and Key Techniques[D]. Chongqing: Chongqing University, 2012. (in Chinese with English abstract)

[15] 张卫正，徐武峰，裘正军，等. 基于多视角图像的植物叶片建模与曲面面积测量[J]. 农业机械学报，2013，44(7)：229－234.

Zhang Weizheng, Xu Wufeng, Qiu Zhengjun, et al. Plant leaf modeling and surface area measuring based on multi-view images[J].Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(7): 229－234. (in Chinese with English abstract)

[16] 王海涛，朱洪. 改进的二分法查找[J]. 计算机工程，2006，32(10)：60－62，118. Wang Haitao, Zhu Hong. Modified binary search[J]. Computer Engineering, 2006, 32(10): 60－62, 118. (in Chinese with English abstract)

[17] 赵虎，裴志远. 农村土地承包经营权调查中面积精度问题分析[J]. 农业工程学报，2016，32(18)：241－246.

Zhao Hu, Pei Zhiyuan. Area accuracy analysis for investigation of rural land contractual management right[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2016, 32(18): 241－246. (in Chinese with English abstract)

[18] 于雷，周勇，郧文聚，等. 基于农用地分等成果的耕地占补平衡按等折算[J]. 农业工程学报，2009，25(1)：244－248.

Yu Lei, Zhou Yong, Yun Wenju, et al. Cultivated land requisition-compensation balance by class conversion based on outcome of farm land classification[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2009, 25(1): 244－248. (in Chinese with English abstract)

[19] 农业部农村经济体制与经营管理司. NY/T 2537-2014 农村土地承包经营权调查规程[S]. 北京：中国农业出版社，2014.

[20] 邓瑶. 基于坡度和耕作田块空间格局的土地整理决策支持系统[D]. 重庆：西南大学，2016.

Deng Yao. Decision Support System for Land Consolidation Based on Slope and Spatial Pattern of Field[D]. Chongqing: Southwest University, 2016. (in Chinese with English abstract)

[21] 信桂新，杨朝现，杨庆媛，等. 用熵权法和改进TOPSIS模型评价高标准基本农田建设后效应[J]. 农业工程学报，2017，33(1)：238－249.

Xin Guixin, Yang Chaoxian, Yang Qingyuan, et al. Post-evaluation of well-facilitied capital farmland construction based on entropy weight method and improved TOPSIS model[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2017, 33(1): 238－249. (in Chinese with English abstract)

[22] 曾凡伟. 基于层次—熵权法的地质公园综合评价[D]. 成都：成都理工大学，2014.Zeng Fanwei. Geopark’s Comprehensive Evaluation Based on Hierarchy-Entropy Weight Method[D]. Chengdu: Chengdu University of Technology, 2014. (in Chinese with English abstract)

[23] Demetriou D, See L, Stillwell J. A parcel shape index for use in land consolidation planning[J]. Transactions in GIS, 2013, 17(6): 861－882.

[24] 刘雪冉. 土地整治中承包田块的调整研究[D]. 北京：中国矿业大学，2013.

Liu Xueran. Study on the Adjustment of Contracted Farmland in Land Reclamation[D]. Beijing: China University of Mining and Technology, 2013. (in Chinese with English abstract)

[25] 王瑷玲，赵瑞茂，高明秀. 土地整理农地承包经营权调整调查[J]. 中国土地科学，2008，22(8)：60－64.

Wang Ailing, Zhao Ruimao, Gao Mingxiu. Investigation in adjustment on contractual operation right of farmland in land reconsolidation[J]. China Land Sciences, 2008, 22(8): 60－64. (in Chinese with English abstract)

[26] 连子康. 江汉平原土地整理权属调整研究[D]. 武汉：华中农业大学，2007.

Lian Zikang. The Study on Landownership Adjusting of Land Adjustment in Jianghan Plain[D]. Wuhan: Huazhong Agricultural University, 2007. (in Chinese with English abstract)

[27] 胡昱东，吴次芳. 我国农村土地整理中土地权属调整问题研究[J]. 西北农林科技大学学报：社会科学版，2009，9(1)：6－10.

Hu Yudong, Wu Cifang. Study on land ownership adjustment in rural land consolidation in China[J]. Journal of Northwest A&F University: Social Science Edition, 2009, 9(1): 6－10. (in Chinese with English abstract)

[28] 苗利梅，范树印，郧文聚. 农用地分等定级估价成果在土地开发整理中的应用[J]. 资源与产业，2007，9(6)：78－81.

Miao Limei, Fan Shuyin, Yun Wenju. Application of classification-gradation assessment of farmlands on land development and consolidation[J]. Resources and Industries, 2007, 9(6): 78－81. (in Chinese with English abstract)

[29] 靳取货. 基于耕地等级提升的土地整理规划设计研究[D].北京：中国地质大学，2010.

Jin Quhuo. Land Consolidation Planning and Design Based on Land Classification and Graduation Enhancement[D]. Beijing: China University of Geosciences, 2010. (in Chinese with English abstract)

[30] Cay T, Uyan M. Evaluation of reallocation criteria in land consolidation studies using the analytic hierarchy process (AHP)[J]. Land Use Policy, 2013, 30(1): 541－548.

Approach for automating land reallocation based on Delaunay triangulation and binary search

LiangQiyang1, WuBaoguo1※, ZhaoChunjiang2,3,4, PanYuchun2,3,4, Hu Meng5, HaoXingyao2,3,4

(1.,,100083,; 2.,100097,; 3.,100097,; 4.,100097,; 5.,475004,)

Producinglandpartitioningplans is one of the most difficult and time-consuming stages of land consolidation. To carry out land adjustment efficiently, it is necessary to quickly develop a reasonable pre-plan of land distribution in the late stage of land consolidation project. Due to the non-uniform geometric shapes of most blocks, blocks cannot be divided according to a certain mathematical model. With the goal of obtaining a land partitioning plan with regularly-shaped parcels which all have access to at least one road/ditch, a land partition algorithm based on Delaunay triangulation (DT) and binary search (BS) was put forward. The DT process was applied to each block to reduce the size of the search space. In the automatic land partitioning, one block was processed at a time and the blocks were processed in the order of their sequence numbers. First, after the minimum bounding geometry (MBG) of a block was generated, the subdivision axis was determined by connecting the midpoints of the 2 short sides of the MBG, and subdivision direction was determined according to the angle between the subdivision axis and horizontal axis to avoid beginning the land partition from a random point; then the nodes of the long edges of the MBG were densified and the nodes of the short edges were removed and the MBG was triangulated. Second, after calculating the real area according to the land quality grade map and the input desired area, each triangle was intersected with the block and the intersection area was set as the triangle’s area; going through the triangles according to the subdivision direction, the area of the triangles was added one by one until the accumulated area was close to the desired area (with an error less than 5%), and then the BS method was adopted to further decrease the area error. Last, the progress was iterated to the rest part of blocks until all blocks were partitioned and the land pre-distribution plan was generated. TheBS-DT algorithm and BS algorithm (used as a control)wererealizedbasedonArcEngine, and 4 criteriaofBS-DT (efficiency, area error, parcel shape index,andlandaccess)werecompared with the BS method. The result of the experimental study showed that an ideal landpartitioning plan was created in 231 s by applying the BS-DT method. Compared with the BS method, the time consumption of the BS-DT approach decreased by 29.3%, while the area accuracy improved by 28.2% and the shape regularity improved by 18.2%. In order to decrease area of road and ditch, redundant roads and ditches were merged into adjacent block, and each sub block still kept good accessibility to at least one road/ditch due to the algorithm’s control of the division direction. The result verified the feasibility of the proposed algorithm in land partitioning. Thus, the proposed BS-DT approach can meet the demand of developing a land allocation plan that is closest to the optimum under certain constraints, which provides a new way for automatically creating and dynamically adjusting land allocation scheme.

land use; algorithms; land consolidation; land reallocation; binary search; Delaunay triangulation; land partitioning

2017-09-14

2018-01-09

国家自然科学基金资助项目（41401193）

梁其洋，博士生，主要从事空间信息技术研究。Email：liangqiyang@bjfu.edu.cn

吴保国，教授，博士生导师，主要从事林业信息化与林业信息技术研究。Email：wubg@ bjfu.edu.cn

10.11975/j.issn.1002-6819.2018.04.032

S126; TP391.72

A

1002-6819(2018)-04-0261-08

梁其洋，吴保国，赵春江，潘瑜春，胡 萌，郝星耀. 基于德劳内三角化和二分查找法的土地自动分配方法[J]. 农业工程学报，2018，34(4)：261－268.doi：10.11975/j.issn.1002-6819.2018.04.032 http://www.tcsae.org

Liang Qiyang, Wu Baoguo, Zhao Chunjiang, Pan Yuchun, Hu Meng, Hao Xingyao. Approach for automating land reallocation based on Delaunay triangulation and binary search[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2018, 34(4): 261－268. (in Chinese with English abstract) doi：10.11975/j.issn.1002-6819.2018.04.032 http://www.tcsae.org