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.