康建榮，李 新，劉翹楚

(1. 江蘇師范大學(xué) 測繪學(xué)院，江蘇 徐州 221116； 2. 無錫南洋職業(yè)技術(shù)學(xué)院，江蘇 無錫 214081；3. 連云港市國土資源局，江蘇 連云港 222001)

一、引 言

注記是地圖重要的組成部分,是計算機地圖制圖和地理信息系統(tǒng)的關(guān)鍵問題之一。在土地利用現(xiàn)狀圖中標(biāo)注圖斑號和土地類型時，標(biāo)注位置直接影響圖面的清晰和美觀。土地利用現(xiàn)狀圖的圖斑是多邊形，根據(jù)多邊形的幾何特點，分為凸多邊形和凹多邊形。本文基于土地利用現(xiàn)狀圖的信息注記對多邊形的最佳標(biāo)注位置進(jìn)行分析。

二、問題的提出

多邊形區(qū)域內(nèi)的注記一般是按多邊形重心來標(biāo)注的，如圖1(a)所示。但由于多邊形區(qū)域的復(fù)雜性，其重心位置可能位于邊界外部，如圖1(b)、(c)所示；也有的重心在邊界內(nèi)部，但距離邊界較近或者嚴(yán)重偏離，如圖1(d)所示。因此，僅靠重心來判斷標(biāo)注位置，不論在標(biāo)注質(zhì)量上還是美觀上都遠(yuǎn)遠(yuǎn)不能滿足注記要求。

MapGIS和ArcGIS是目前土地利用現(xiàn)狀圖制作較為常用的軟件，能夠方便快速地實現(xiàn)土地利用現(xiàn)狀圖斑的數(shù)字標(biāo)注功能。但針對某些特殊的圖斑其標(biāo)注位置也不是很好，需對個別位置進(jìn)行手工調(diào)整，如圖2所示。當(dāng)標(biāo)注位置不理想、偏離圖斑較大、處理的數(shù)據(jù)量較大時，僅依靠手工改動是很費時費力的。

由于標(biāo)注效果的缺陷以及數(shù)字注記的特殊性與復(fù)雜性，土地利用現(xiàn)狀圖斑自動數(shù)字注記還沒有完全適用于所有圖斑的算法，對于某些特殊的圖斑仍然會出現(xiàn)不理想的注記效果?？蒲泄ぷ髡咭恢敝铝τ谕恋乩矛F(xiàn)狀圖斑自動數(shù)字注記算法的研究，通過尋找相對完善的注記算法來提高圖斑數(shù)字注記的質(zhì)量和效率。本文從土地利用現(xiàn)狀圖斑的特點出發(fā)，提出基于最大內(nèi)接四邊形的圖斑自動數(shù)字注記方法。

圖1 不同規(guī)則形狀的圖斑重心位置

圖2 MapGIS和ArcGIS中不理想的標(biāo)注位置

三、注記位置的理論分析

根據(jù)多邊形的特點，不論形狀是簡單還是復(fù)雜，其內(nèi)部總存在一個面積最大的內(nèi)接四邊形，這個四邊形的重心就是最適合標(biāo)注的位置點。

設(shè)多邊形的頂點為A1(x1,y1)，A2(x2,y2)，…，An(xn,yn)，則其函數(shù)形式為

a∈(xi,xi+1),b∈(yi,yi+1)

上述多邊形函數(shù)形式可寫成

設(shè)B1(a1,b1)、B2(a2,b2)、B3(a3,b3)、B4(a4,b4)為多邊形邊界上任意4點，其組成的四邊形(頂點沿順時針方向排列)，面積為S，則有

為了得到S的最大值，做拉格朗日函數(shù)

φ=S+λ1·f(x,y)+λ2·f(x,y)+

λ3·f(x,y)+λ4·f(x,y)

分別對a1、a2、a3、a4和b1、b2、b3、b4求偏導(dǎo)數(shù)并令其等0，即有

經(jīng)化簡后得

要使等式成立，必然有

b2=b4，a2=a4，b1=b3，a1=a3

當(dāng)上述條件同時成立時，B1(a1,b1)和B3(a3,b3)為同一點，B2(a2,b2)和B4(a4,b4)為同一點，這時內(nèi)接四邊形退化成直線，從而確定出在多邊形內(nèi)的內(nèi)接四邊形最大面積產(chǎn)生的兩組條件為

條件1：a2=a4，b1=b3

條件2：a1=a3，b2=b4

這兩個條件實質(zhì)上可歸納為：相互垂直的兩直線與邊界交點組成的四邊形。這時針對第1個條件，其內(nèi)接四邊形的面積可寫成

式中，Δx=|a4-a2|；Δy=|b3-b1|。

由此可得到結(jié)論：對于一個任意多邊形而言，其面積最大的內(nèi)接四邊形是存在的，最大橫向截距和最大縱向截距組成的四邊形即為面積最大內(nèi)接四邊形。

四、實現(xiàn)方法

1. 最大內(nèi)接四邊形查找方法

根據(jù)上述分析，多邊形內(nèi)存在的面積最大的內(nèi)接四邊形是由相互垂直的兩條直線與多邊形邊界交點組成的四邊形，為了找到最大橫向截距和最大縱向截距，本文提出了一種基于規(guī)則網(wǎng)格的四邊形查找方法，即將圖斑劃分為若干網(wǎng)格，以網(wǎng)格點為四邊形對角線的交點，網(wǎng)格橫向、縱向掃描線與圖斑邊界的上下左右4個交點為四邊形的4個頂點。

所構(gòu)網(wǎng)格點如圖3所示，將圖斑以一定的網(wǎng)格間距劃分，由于外部網(wǎng)格點不參與計算，故可先查詢并記錄圖斑內(nèi)部網(wǎng)格點。

圖3 圖斑網(wǎng)格示意圖

由于圖斑邊界的復(fù)雜性，對于每條橫向網(wǎng)格掃描線而言，所求的交點個數(shù)常多于兩個，為方便對每個網(wǎng)格點交點信息的獲取，可對交點作以下判斷：若所求交點不是圖斑邊界線段的端點，記錄此交點；若所求交點是圖斑邊界線段的端點，則判斷該點前后兩點的位置關(guān)系，若這兩點在此端點的異側(cè)，記錄此交點(注意：起點和終點只記錄一次)，反之，不記錄。

經(jīng)上述判斷后所求的交點個數(shù)始終為偶數(shù)，將交點兩兩配對：1號交點與2號交點配對、3號交點與4號交點配對、……，交點兩兩配對的線段必定為圖斑內(nèi)部線段，減少了對兩交點之間線段的判斷。對位于兩交點之間的網(wǎng)格點，可直接將這兩個交點納入其網(wǎng)格點的left、right點索引信息中。同樣，對于縱向網(wǎng)格掃描線也是如此。

建立網(wǎng)格點索引后，對于每一個網(wǎng)格點都有一個與其相對應(yīng)的四邊形，排除與圖斑邊界相交的四邊形即為符合要求的四邊形，如圖4所示，四邊形ABCD、EFGH即為該圖斑內(nèi)的任意內(nèi)接四邊形。

圖4 圖斑內(nèi)的任意內(nèi)接四邊形

有一種特殊情況的四邊形需考慮，如圖5所示，四邊形雖然與圖斑邊界沒有端點以外的交點，但此四邊形并不是圖斑的內(nèi)接四邊形，其重心位置也不符合該圖斑的注記要求，該情況可通過四邊形邊的中點來判斷排除。

圖5 與邊界無多余交點的特殊四邊形

2. 形狀因子分析

由于圖斑邊界的復(fù)雜性，面積最大的內(nèi)接四邊形的重心位置不一定是最佳的數(shù)字標(biāo)注位置。因此，為確保標(biāo)注位置的良好性，本文又綜合考慮了四邊形的形狀因子，排除形狀不好的內(nèi)接四邊形。

四邊形ABCD的兩條對角線為AC和BD，O為兩條對角線交點，如圖6所示。

形狀因子K的計算公式為

為確保K≤1，上式中可限定AO

圖6 形狀因子示意圖

可設(shè)定一定的閾值來限定需要進(jìn)行形狀因子比較的內(nèi)接四邊形，本文選取了與最大內(nèi)接四邊形面積差小于十分之一的四邊形進(jìn)行形狀因子計算，意在找到面積最大且形狀因子較好的內(nèi)接四邊形。對于圖7所示的圖斑而言，找到的面積最大且形狀因子較好的四邊形如圖7(c)所示。

3. 網(wǎng)格密度對標(biāo)注位置的影響

從圖7(a)的標(biāo)注情況來看，標(biāo)注位置大體合適，但標(biāo)注效果仍然不是十分理想。這主要是由尋找四邊形時所劃分的網(wǎng)格決定的。顯然網(wǎng)格的密度稀疏程度對面積最大內(nèi)接四邊形的獲取有著很大的影響，并直接影響其標(biāo)注效果。若網(wǎng)格密度太稀疏，標(biāo)注位置效果不理想；反之，若網(wǎng)格密度太密，則必會造成算法時間長且效率降低。

從圖7的標(biāo)注效果來看，50 m網(wǎng)格間距太稀疏，注記位置嚴(yán)重偏離了該圖斑中心區(qū)域，網(wǎng)格密度加倍后，25 m相對于50 m的網(wǎng)格，標(biāo)注效果得到了很大的改善，繼續(xù)加密網(wǎng)格，標(biāo)注位置變化不明顯。因此，如何做到時間與效果的完美結(jié)合是關(guān)鍵，表1是本文針對不同圖斑經(jīng)過多次測試得到的一組較為合適的網(wǎng)格密度的經(jīng)驗值。

表1 不同圖斑網(wǎng)格密度選取測試結(jié)果

續(xù)表1

表1中

α=圖斑面積/圖斑最大最小值組成矩形面積

β=圖斑周長-圖斑最大最小值組成矩形周長

式中，α表明了圖斑的飽滿程度，其值越大，圖斑的形狀越好且凸性越強；β表明了圖斑的凹凸復(fù)雜性。β>0，表示圖斑形狀復(fù)雜，凹凸拐點較多；β<0，表示圖斑比較狹長。

由表1可以看出， 不同形狀的圖斑標(biāo)注所需要的網(wǎng)格密度雖然不一樣，但相差不是很大，當(dāng)min(Δx,Δy)處于0～400 m之間時，網(wǎng)格密度的選取在20～30 m之間，當(dāng)min(Δx,Δy)處于400～1600 m之間時，網(wǎng)格密度的選取在30～40 m之間，且同一范圍內(nèi)，α因子較大的圖斑網(wǎng)格密度選取較大，β因子絕對值越大，網(wǎng)格密度選取也較大?？筛鶕?jù)情況選取該范圍內(nèi)對所有圖斑較為合適的一個網(wǎng)格密度。

五、結(jié)束語

本文針對土地利用現(xiàn)狀圖標(biāo)注過程中某些特殊圖斑的標(biāo)注缺陷問題，提出了一種基于面積最大內(nèi)接四邊形的標(biāo)注方法。通過理論推導(dǎo)，得到了圖斑內(nèi)面積最大內(nèi)接四邊形存在的條件，即找到具有最大橫向截距和最大縱向截距組成的四邊形，由此提出了基于一定密度規(guī)則格網(wǎng)的最大內(nèi)接四邊形的查找方法，結(jié)合形狀因子找到最理想注記位置的面積最大的內(nèi)接四邊形，由該四邊形的重心位置確定圖斑標(biāo)注位置。試驗證明，面積最大且形狀因子較好的四邊形具有最佳標(biāo)注位置。針對不同形狀的圖斑，分析了查找最大內(nèi)接四邊形的網(wǎng)格密度經(jīng)驗值，從而為編制程序提供了依據(jù)。

參考文獻(xiàn)：

[1] 朱正國，柳榮其.地圖中面狀要素標(biāo)注算法的設(shè)計與改進(jìn)[J].西華大學(xué)學(xué)報：自然科學(xué)版，2009,28(2)：38-42.

[2] 焦明勇，蘇鴻根.一套多邊形內(nèi)專業(yè)注記的定位方法及其應(yīng)用[J].計算機工程與科學(xué)，2008，30(6)：44-47.

[3] 吳長彬，閭國年，劉昱君.基于規(guī)則庫和網(wǎng)格算法的土地利用現(xiàn)狀圖自動數(shù)字注記[J].測繪學(xué)報，2008，37(2)：250-255.

[4] 余代俊， 耿留勇.基于Delaunay三角形實現(xiàn)面狀要素自動注記[J].測繪通報，2006(11):26-28.

[5] 杜世宏，杜道生，樊紅.面狀地物自動注記方法探討[J].測繪信息與工程，2000(4)：6-8.

[5] 樊紅,張祖勛,杜道生.地圖線狀要素自動注記的算法設(shè)計與實現(xiàn)[J].測繪學(xué)報，1999，28(1)：86-89.

[6] 賀彪，李霖，朱海紅.數(shù)字制圖中面狀注記自動配置的研究[J].測繪信息與工程，2007，32(6)：12-14.

[7] 高輝，劉金義，盧英，等.利用近似骨架線進(jìn)行面狀要素注記算法及實現(xiàn)[J].計算機與數(shù)字工程，2006，34(9)：115-116.

[8] 耿留勇，余代俊.中心陣列法實現(xiàn)面狀地圖要素的自動注記[J].測繪科學(xué)，2007，32(2)：36-37，63.

[9] 姜永發(fā)，張書亮，蘭小機，等.長對角線法實現(xiàn)GIS中矢量地圖面狀地物漢字注記的自動配置[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2005，30(6)：544-548.

[10] 杜世宏，王橋，杜道生，等.地名注記自動配置的關(guān)鍵技術(shù)研究[J].地理與地理信息科學(xué)，2003，19(1)：20-24.

[11] 杜世宏，王橋，杜道生，等.地名注記自動配置研究[J].地理學(xué)與國土研究，2002，18(4)：14-18.