梁其洋，吳保國，趙春江，潘瑜春，胡 萌，郝星耀

?

基于德勞內(nèi)三角化和二分查找法的土地自動分配方法

梁其洋1，吳保國1※，趙春江2,3,4，潘瑜春2,3,4，胡 萌5，郝星耀2,3,4

（1. 北京林業(yè)大學信息學院，北京 100083；2. 國家農(nóng)業(yè)信息化工程技術研究中心，北京 100097；3. 農(nóng)業(yè)部農(nóng)業(yè)信息技術重點實驗室，北京 100097；4. 北京市農(nóng)業(yè)物聯(lián)網(wǎng)工程技術研究中心，北京 100097；5. 河南大學環(huán)境與規(guī)劃學院，開封 475004）

為解決預分方案制定效率低的問題，該文提出一種基于德勞內(nèi)三角化和二分查找法的地塊分配算法。首先生成待分配地塊的最小邊界幾何（minimum bounding geometry，MBG），對MBG進行三角剖分；其次在地塊內(nèi)通過累加三角形的面積執(zhí)行查找，接近合同面積時采用二分查找法進行微調(diào)；最后遍歷項目區(qū)內(nèi)所有地塊直至生成土地預分配方案。通過對算法進行編程實現(xiàn)，以試驗區(qū)的土地整治項目為例對算法的可行性進行驗證，并從分配效率、精度和形狀指數(shù)3個方面對結果進行評價。結果表明：項目區(qū)內(nèi)的地塊劃分僅需231 s，與僅用二分查找法相比，采用該文方法分割效率提高29.3%，精度提高28.2%，形狀規(guī)則度提高18.2%；在減少農(nóng)用道路占地面積的同時，分割后的地塊具有良好的通達性。該方法可滿足自動創(chuàng)建和動態(tài)調(diào)整土地分配方案的需求，為在一定約束條件下制定最優(yōu)土地分配方案提供了技術支撐。

土地利用；算法；土地整治；土地分配；二分查找；德勞內(nèi)三角化；地塊分割

0 引 言

土地整治項目實施過程中需按照規(guī)劃設計打破原有地塊布局，同時優(yōu)化配置農(nóng)田水利及道路設施，從而導致原有的土地權屬界線或標志物不復存在，而新的承包地塊的劃分將導致原有利益格局發(fā)生分化，涉及到土地所有者、使用者、他項權利人的權屬調(diào)整[1]。目前大部分土地整治項目完工后只劃分到大地塊，沒有對大地塊進行詳細劃分，而是交給村委會由村委會主觀劃定，結果一般是保持各戶地塊位置和數(shù)量不變，未能改變耕地分散的現(xiàn)狀、實現(xiàn)土地承包者的地塊集中，不利于土地規(guī)模經(jīng)營。

土地分配是將耕作地塊分割為較小的子空間并最終獲得由規(guī)則地塊構成的土地分配方案的過程[2]，地塊調(diào)整往往伴隨著權屬調(diào)整，而權屬調(diào)整是一種利益敏感的行為，直接關系到土地權利人的根本利益[3]。因此，土地分配方案的制定是土地整治過程中最重要也是最耗時的步驟之一[4]。當前，這一規(guī)劃和決策過程的自動化程度較低[5]。傳統(tǒng)的分配方法是技術員利用裁剪、合并等地理工具的組合，對地塊逐一進行操作，切分出相應面積的地塊，再結合字段計算器求解出每個地塊的面積[6]。該方法需頻繁進行面積查詢以及人工輸入操作，不僅工作效率低，而且容易產(chǎn)生各種操作錯誤。當所涉及地塊的質(zhì)量差異較大時，這一過程還將面臨周期長、操作成本高及利益相關者之間的利益沖突等問題[7]。

整治合并后的大地塊的幾何形狀并非都很規(guī)則，限制了在分割過程中使用數(shù)學建模的方式計算分割線的位置和子地塊的大小[8]。常用的自動化地塊分割方法有步長法[6]、決策模型法[9-10]和遺傳算法[11-12]等，雖然能夠完成土地分配任務，但也存在諸多不足。步長法難以隨土地經(jīng)營承包權合同面積（以下簡稱合同面積）的改變動態(tài)地調(diào)整步長，無法兼顧精度和效率；決策模型法考慮的地塊外部因素較多，如連片性因素、區(qū)位因素和行政因素等，更適合從宏觀角度進行劃定；基于遺傳算法難以統(tǒng)一分割方向，無法保證地塊通達性?？紤]到這些模型或算法的效率和復雜性，當一個項目有大量地塊時，這些方法難以快速制定出理想的土地預分配方案，存在分割精度和效率方面的不足。

針對以上問題，本文提出一種高效且滿足實施標準的土地分配方案自動制定方法。該方法基于二分查找（binarysearch，BS）和德勞內(nèi)三角化（Delaunaytriangulation，DT），可以自動確定不規(guī)則地塊的分割起點，并快速計算出顧及地塊等級、面積、形狀和通達性的地塊邊界，輸出子地塊價值相等、利于實際耕作的土地分配方案。

1 方法與流程

1.1 基本原理

1.1.1 德勞內(nèi)三角化

三角化是將給定地塊剖分成不相交的三角形網(wǎng)格，這些三角形的頂點代表地塊邊界的節(jié)點，地塊是三角形的集合。對地塊進行三角剖分的目的是將目標的查找空間從整個多邊形區(qū)域降至較小的三角形區(qū)域，再通過累加三角形的面積來接近目標面積值[13]。三角剖分的方法有很多[14]，由于德勞內(nèi)三角化具有優(yōu)越的特性，如大致全等三角形、最大化最小角和邊的和最小，剖分出來的三角形網(wǎng)格均勻，從而保證了整體剖分質(zhì)量最優(yōu)[15]，所以本文選擇德勞內(nèi)三角化作為地塊的剖分方法。

實踐證明，形狀不規(guī)則的地塊直接利用邊界上的節(jié)點進行德勞內(nèi)三角化的結果過于復雜不便于遍歷。本文采用了一種新的實現(xiàn)方式，即首先獲得地塊的最小邊界幾何（minimumboundinggeometry，MBG），將MBG短邊上的節(jié)點剔除，在長邊上按一定距離加密節(jié)點，將處理后的MBG進行德勞內(nèi)三角化。遍歷三角形進行面積累加時，取其與原始地塊交集的面積作為基數(shù)。

圖1為采用最小邊界幾何進行德勞內(nèi)剖分的示例。剔除MBG短邊上的節(jié)點后，按100 m的間隔加密長邊節(jié)點，對MBG進行德勞內(nèi)三角化，取原始地塊與各三角形交集的面積作為三角形的面積，這樣既能夠通過控制節(jié)點間距獲得合適的剖分效果，又保持了原始地塊的完整，避免了原始地塊剖分后再合并產(chǎn)生的開銷。此外，MBG的4個頂點始終處于地塊外部，有利于確定分割軸后根據(jù)頂點處的坐標極值動態(tài)地生成與地塊完全相交的分割線。

注： xmax、xmin、ymax、ymin代表4個頂點的坐標極值。

1.1.2 二分查找法

利用BS法進行地塊分割，即從地塊的中間開始執(zhí)行分割，如果目標值小于一半空間，則繼續(xù)在下半部分查找；反之，則在上半部分查找。此過程循環(huán)進行，一次排除一半空間，并將目標值與剩余空間進行比較，直到找到目標值為止。在查找空間減少到一半大小的每次迭代中，算法的復雜度為O(log2)。由于BS法在確定分割線的位置時存在大量運算，當合同面積較小或待分割地塊較多時會由于分割次數(shù)較多而影響計算效率，而將地塊德勞內(nèi)三角化可以減小BS的搜索空間。因此，本研究結合BS和DT進行地塊分割，以達到土地分配所需的精度和效率。

1.2 土地分配流程

本研究的目標是通過對整治合并后的地塊進行劃分，得到地塊滿足價值、面積、形狀規(guī)則度和通達性等約束的土地預分配方案。地塊劃分的基本工作流程可歸納為以下4步：1）輸入合同面積，根據(jù)耕地價值指數(shù)確定子地塊該劃分的實際面積；2）確定待分割地塊的分割軸和分割方向，并將其MBG德勞內(nèi)三角化；3）基于三角形累加和二分查找法執(zhí)行劃分；4）地塊劃分方案輸出。具體地，生成一個土地預分配方案的算法流程如圖2所示。

圖2 基于BS-DT的土地自動劃分流程

1.3 地塊劃分實現(xiàn)方法

在地塊劃分過程中，為滿足地塊通達性約束，一般沿地塊走向或路渠方向進行處理[17]。首先，提取地塊的MBG及其4個端點，計算出各邊中點，將對邊中點連線形成、軸；比較2軸的長短，以代表地塊走向的長軸作為分割軸。分割軸有2個用途：一是通過計算與2坐標軸的夾角判斷分割方向及分割起點，當水平夾角大于豎直夾角時，地塊沿豎直方向細分，反之沿水平向細分；二是沿垂直于分割軸的方向動態(tài)計算分割線。圖3顯示了分割一塊面積為121 hm2地塊的步驟。將長軸作為軸，短軸作為軸，由于軸與坐標軸的夾角大于與坐標軸的夾角，分割時在豎直方向上沿軸分割。三角剖分完成后，從軸2端點中坐標值較小的一端開始遍歷，直到三角形的面積累加到接近合同面積（誤差±5%）。三角形累加終止時，沿終止處的三角形的重心作軸的垂線作為分割線對原地塊進行分割。

注： X、Y為候選分割軸，x、y為坐標軸。

由于大多數(shù)地塊不可能僅通過一次分割就生成指定面積的地塊，取終止處三角形的前一三角形的坐標最小值作為下限，后一三角形的坐標最大值作為上限，在該上下限組成的區(qū)間內(nèi)運用BS法進行微調(diào)，通過更新這些最大值和最小值，迭代數(shù)次后完成微調(diào)。查找到符合容差范圍的面積后，將原始地塊中位于該面積范圍內(nèi)的所有多邊形合并以完成本次分割。對剩余待分割部分合并后迭代執(zhí)行這一過程即可完成整個地塊的分割。對不足一個子塊的剩余部分，可以合并到鄰接的子地塊中或者作為固定設施的預留用地。

使用BS法查找合同面積的地塊時，事先對地塊進行三角剖分可以減少BS法的查找空間。在對圖4所給出的樣地使用BS-DT法劃分子塊時，初步查找到的合同面積由三角形累加完成，不涉及復雜運算；微調(diào)區(qū)間由第一條分割線所在三角形及其前后2個三角形組成，在此區(qū)間內(nèi)利用BS法查找5%左右的合同面積。

1.4 評價指標

為驗證BS-DT法應用在土地分配上的可行性，依據(jù)耕作地塊的幾何特征和社會屬性，按照重要性選取地塊價值、面積相對誤差和地塊形狀指數(shù)3個指標對土地劃分結果進行評價。由于不同價值的地塊可以通過耕地價值指數(shù)轉換成同一價值，地塊價值差異最終轉換為面積差異[18]，故按照價值統(tǒng)一后的面積相對誤差進行評價。

圖4 BS法和BS-DT法的查找空間

1）面積相對誤差Area。Area為計算面積與合同面積之差的絕對值占合同面積的百分比，取值介于0～1。面積精度是農(nóng)業(yè)資源調(diào)查和承包地權屬調(diào)查工作中的主要技術指標之一，《農(nóng)村土地承包經(jīng)營權調(diào)查規(guī)程》（NY/T 2537-2014）中明確提出，航測法、圖解法測得的承包地塊，其面積計算的相對誤差不應超過5%[19]。以Area為評價指標的目標函數(shù)為

式中為子地塊的編號；為子地塊的數(shù)量。

2）地塊形狀指數(shù)（parcel shape index，PSI）。PSI是一個多參數(shù)指標，包括短邊數(shù)、銳角數(shù)、優(yōu)角數(shù)和折點數(shù)4個參數(shù)，各參數(shù)的測算方法如表1所示。對于耕作地塊而言，過短的邊長、過多的銳角、優(yōu)角和折點會嚴重影響農(nóng)業(yè)機械的使用[20]，為滿足機械作業(yè)要求，必須使設計的地塊至少具有一個直角且地塊2個長邊平行。因此，地塊形狀最好為內(nèi)角為90°或接近90°的矩形。PSI的計算方法為

式中=1/ln。計算得到的各形狀參數(shù)對應的權重系數(shù)如表1所示。

表1 形狀指標的參數(shù)測算方法[23]

形狀指數(shù)PSI的取值介于0～1。通常將PSI分為4類，PSI為0～0.50時認為形狀是高度不規(guī)則的，PSI為0.51～0.70時是不規(guī)則的，PSI為0.71～0.90時是規(guī)則的或接近規(guī)則的，PSI≥0.91時是最優(yōu)或接近最優(yōu)的[23]?；诖耍云x最優(yōu)形狀指數(shù)的累計誤差作為評價依據(jù)，目標函數(shù)為

2 實例分析

2.1 研究區(qū)概況

本文以河北省順平縣的土地整治項目為案例進行研究。順平縣位于河北省保定市西郊，地理坐標為115°11′24″～115°15′25″E，38°47′28″～38°50′56″N。項目區(qū)涉及順平縣的2個鎮(zhèn)12個村，區(qū)內(nèi)耕地總面積1 838.92 hm2。項目區(qū)屬于北方旱作區(qū)，地勢較為平坦開闊，局部略有起伏，土層比較深厚，土壤母質(zhì)絕大部分為黃土性黏土，主要作物為小麥和玉米。整治前項目區(qū)的耕地布局如圖5所示，具體表現(xiàn)為小地塊數(shù)量多，形狀支離破碎，田間道路數(shù)量較多，每戶農(nóng)戶承包的地塊分散，以農(nóng)業(yè)為主要工作的勞動力的人均耕地面積約0.02 hm2。

圖5 項目區(qū)整治前地塊分布

2.2 研究方法與實現(xiàn)

在土地整治方面國際上通用的土地權屬調(diào)整方案有面積法和價值指數(shù)法2種[24]。面積法是根據(jù)土地整治前耕地的面積和位置，堅持“面積等量”的原則，確定土地權屬調(diào)整后耕地的面積和位置的方法。耕地價值指數(shù)法是根據(jù)土地整治前后耕地質(zhì)量等級的高低，運用耕地價值指數(shù)的比值作為面積折算系數(shù)確定劃分地塊的方法[25]。

面積法和價值指數(shù)法分別適用于不同的場合，面積法不需要考慮土地整治前后耕地價值的變化，使用比較簡單方便，僅適用于權屬調(diào)整前后土地利用條件差異不大的情況。價值指數(shù)法運用起來更復雜，但也更科學更具說服力，適用于調(diào)整前后土地利用條件差異較大、無法簡單確定面積折算系數(shù)的情況[26]。土地權屬調(diào)整的基本要求是土地承包者新承包耕地的價值總額與權屬調(diào)整前相同或有所提高[27]。由于項目區(qū)的耕地經(jīng)過整治后數(shù)量和質(zhì)量等級發(fā)生了變化，鑒于土地權屬調(diào)整過程的利益敏感性，價值指數(shù)法雖然比較復雜，但能綜合體現(xiàn)權屬調(diào)整中地塊的價值，確保土地權屬調(diào)整按等價值進行[28-29]，因此，本文采用價值指數(shù)法進行地塊劃分。

使用C#語言在Visual Studio 2015平臺下開發(fā)針對BS和BS-DT 2種算法的土地自動分配原型系統(tǒng)，并利用研究區(qū)的數(shù)據(jù)進行測試分析。測試環(huán)境如下：Windows7操作系統(tǒng)、Inteli73.4 GHz4核處理器、8G內(nèi)存，空間數(shù)據(jù)以文件形式儲存。

2.3 結果與分析

根據(jù)《農(nóng)用地定級規(guī)程》（GB/T 28405-2012）得到的整治后土地質(zhì)量分等定級圖如圖6所示。項目區(qū)的土地基于BS-DT法和價值指數(shù)法劃分的結果如圖7所示。在合同面積不變的前提下，運用BS-DT法進行多次重復劃分子地塊的形狀和空間位置不發(fā)生改變，說明該算法具有較強的穩(wěn)定性。劃分得到的地塊需要滿足3個約束條件：面積精度、形狀規(guī)則度和通達性[30]。其中，地塊通達性是必須滿足的硬性約束，面積精度和形狀規(guī)則度是允許有一定誤差的彈性約束。下面采用定性分析和定量分析相結合的方法對2種算法的劃分效果進行對比分析。

土地整治過程中歸并了不必要的路渠，農(nóng)用道路和溝渠占地面積由52.7 hm2減少到35.8 hm2，增加了有效耕地面積。本文的地塊布設與分配方法充分結合了整治后的道路、河渠，將代表地塊走向的長邊方向與路渠方向保持一致，地塊劃分時均沿垂直于路渠的方向進行，從而保證了劃分出的每個子塊都至少與一條道路或河渠相通達。

注： ~表示整治后地塊的編號。

圖7 基于BS-DT的土地劃分結果

本文從分割耗時、面積精度和形狀指數(shù)3個方面對2種算法的劃分結果進行量化分析。為避免系統(tǒng)誤差，分別采用2種算法對各地塊重復劃分10次，并統(tǒng)計耗時的平均值。圖8給出了合同面積為6.67 hm2的約束下各地塊分別采用2種方法劃分的耗時比較。

圖8 BS法和BS-DT法耗時比較

由于耗時只與地塊被分割的次數(shù)相關，因此將圖8橫坐標按子地塊數(shù)目升序排列后，縱坐標上耗時總體上能夠反映隨分割次數(shù)遞增的趨勢，證明了算法的有效性。隨著分割次數(shù)的增加，2種算法的耗時相對差距逐漸增大。由于BS-DT法能夠縮小所有地塊的查找空間，因而比BS法效率更高，在本案例中，BS-DT和BS法生成土地預分配方案的時間為分別為231和327 s，前者總體效率高出29.3%。

分地塊統(tǒng)計子地塊的累計面積相對誤差和累計形狀指數(shù)誤差如表2所示。從表2可以看出，2種方法生成的各子塊的面積相對誤差均滿足5%的約束。其中，僅采用BS法各子塊的面積平均誤差為2.16%，而BS-DT法的面積平均誤差為1.55%，提高了28.2%。采用BS-DT法，單個地塊中除地塊10和12的Area比僅用BS法稍大，其他地塊的面積精度均高于僅用BS法。地塊10和12的形狀復雜度較高，限制了BS-DT對面積誤差的減少。

劃分結果中形狀規(guī)則的地塊（PSI≥0.71）占73.3%，不規(guī)則地塊占26.7%。這部分不規(guī)則地塊通常位于分割軸兩端，是由第一次或最后一次切分產(chǎn)生，不能保證至少有兩條邊平行，因而形狀不規(guī)則度較高。由于本文劃分地塊時以面積精度作為主要約束，2種方法均不針對地塊形狀做過多的調(diào)整，地塊形狀指數(shù)的差別不能顯著得反映在每個地塊的上，但表2中的結果顯示BS-DT法具有一定優(yōu)勢，總體規(guī)則度提高18.2%。

表2 2種算法下的面積相對誤差和形狀指數(shù)誤差比較

從試驗結果總體來看，在同樣滿足面積精度、形狀規(guī)則度、通達性約束的前提下，BS-DT法在效率、精度和形狀規(guī)則度方面均優(yōu)于BS法。由于項目區(qū)內(nèi)以農(nóng)業(yè)為主要工作的勞動力的人均耕地面積約0.02 hm2，每個子地塊還需進一步細分，隨著待分割地塊數(shù)量的增加，采用BS-DT法的優(yōu)勢將更加明顯。

4 結 論

1）本文以快速制定土地整治項目所需的土地預分方案為目標，針對不規(guī)則地塊的等價值分割問題，設計了基于BS-DT的土地分配方法，該方法具有參數(shù)設置簡便、人工干預少和易于進行系統(tǒng)化實現(xiàn)的優(yōu)勢，制定土地預分配方案僅需231 s，且新劃分地塊均具有良好的通達性，規(guī)則地塊占比為73.3%。在保證土地分配作業(yè)過程公平公正的基礎上，能夠緩解地塊分散破碎和分配不均的問題，最大程度地提高農(nóng)戶的滿意度和耕作的便利度，具有較好的應用推廣價值。

將基于分等成果的區(qū)域耕地質(zhì)量等級轉換為價值指數(shù)，以價值指數(shù)的比值作為面積折算系數(shù)使地塊按等價值進行劃分，有利于維護農(nóng)戶的利益。為使本文方法更具針對性，耕地價值指數(shù)的確定需要進一步研究，應充分考慮區(qū)域內(nèi)耕地的自然屬性、經(jīng)濟屬性和生態(tài)屬性，選取主要影響指標，通過對價值影響因素的綜合評價確定適合該區(qū)域的耕地價值指數(shù)。接下來還應結合農(nóng)戶對承包地塊調(diào)整的意愿，在堅持自愿原則的基礎上，實現(xiàn)程序化地塊調(diào)整與農(nóng)戶自主擇地意愿的耦合。對于不適合應用耕地價值指數(shù)的情況，如地塊上有固定設施（溫室，灌溉井等），由于該地塊在其所有者心目中遠比一般地塊重要，進行土地權屬調(diào)整時，應優(yōu)先將該地塊劃分給原所有者或者采取其他補償措施。

通過擴展以價值、面積、通達性和規(guī)則度為主的評價指標，本文方法可滿足不同場景的應用需求，如以耕地質(zhì)量、耕作距離和耕作可達性等為約束指標可以自動劃分出耕地保護分區(qū)。隨著農(nóng)村土地適度規(guī)?；?jīng)營成為趨勢，現(xiàn)代農(nóng)業(yè)生產(chǎn)中沒必要每個成員都有明確的地塊界限，只需在理論上明確在區(qū)域耕地上占有的產(chǎn)權份額，但本文方法可推廣應用到耕地保護分區(qū)、農(nóng)用地自動分等定級及田塊規(guī)劃設計等領域。

[1] 王長江. 農(nóng)村土地整治權屬調(diào)整與管理模式研究[D]. 北京：中國礦業(yè)大學，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] 關江華. 土地整理權屬調(diào)整研究[D]. 武漢：華中農(nóng)業(yè)大學，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的地塊分割插件設計與實現(xiàn)[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] 石英，程鋒，朱德舉. 基本農(nóng)田保護區(qū)劃定自動化成圖中圖斑分割決策模型研究[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] 張衛(wèi)正，徐武峰，裘正軍，等. 基于多視角圖像的植物葉片建模與曲面面積測量[J]. 農(nóng)業(yè)機械學報，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] 趙虎，裴志遠. 農(nóng)村土地承包經(jīng)營權調(diào)查中面積精度問題分析[J]. 農(nóng)業(yè)工程學報，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] 于雷，周勇，鄖文聚，等. 基于農(nóng)用地分等成果的耕地占補平衡按等折算[J]. 農(nóng)業(yè)工程學報，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] 農(nóng)業(yè)部農(nóng)村經(jīng)濟體制與經(jīng)營管理司. NY/T 2537-2014 農(nóng)村土地承包經(jīng)營權調(diào)查規(guī)程[S]. 北京：中國農(nóng)業(yè)出版社，2014.

[20] 鄧瑤. 基于坡度和耕作田塊空間格局的土地整理決策支持系統(tǒng)[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] 信桂新，楊朝現(xiàn)，楊慶媛，等. 用熵權法和改進TOPSIS模型評價高標準基本農(nóng)田建設后效應[J]. 農(nóng)業(yè)工程學報，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] 曾凡偉. 基于層次—熵權法的地質(zhì)公園綜合評價[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] 劉雪冉. 土地整治中承包田塊的調(diào)整研究[D]. 北京：中國礦業(yè)大學，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] 王璦玲，趙瑞茂，高明秀. 土地整理農(nóng)地承包經(jīng)營權調(diào)整調(diào)查[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] 連子康. 江漢平原土地整理權屬調(diào)整研究[D]. 武漢：華中農(nóng)業(yè)大學，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] 胡昱東，吳次芳. 我國農(nóng)村土地整理中土地權屬調(diào)整問題研究[J]. 西北農(nóng)林科技大學學報：社會科學版，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] 苗利梅，范樹印，鄖文聚. 農(nóng)用地分等定級估價成果在土地開發(fā)整理中的應用[J]. 資源與產(chǎn)業(yè)，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] 靳取貨. 基于耕地等級提升的土地整理規(guī)劃設計研究[D].北京：中國地質(zhì)大學，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

吳保國，教授，博士生導師，主要從事林業(yè)信息化與林業(yè)信息技術研究。Email：wubg@ bjfu.edu.cn

10.11975/j.issn.1002-6819.2018.04.032

S126; TP391.72

A

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

梁其洋，吳保國，趙春江，潘瑜春，胡 萌，郝星耀. 基于德勞內(nèi)三角化和二分查找法的土地自動分配方法[J]. 農(nóng)業(yè)工程學報，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