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

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

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

Abstract: Producing land partitioning plans 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. The BS-DT algorithm and BS algorithm (used as a control) were realized based on ArcEngine, and 4 criteria of BS-DT (efficiency, area error, parcel shape index, and land access) were compared with the BS method. The result of the experimental study showed that an ideal land partitioning 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.