基于單元復(fù)制的通用化離散格網(wǎng)系統(tǒng)生成算法

范帥博，童曉沖，雷 毅

（信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州 450000）

0 引 言

全球離散格網(wǎng)系統(tǒng)采用特定方法將地球均勻離散化，形成無縫無疊的多分辨率格網(wǎng)層次結(jié)構(gòu)，是一種新型的空間數(shù)據(jù)組織、管理與應(yīng)用模型[1-2]，其中基于正多面體剖分的離散格網(wǎng)是廣受關(guān)注的格網(wǎng)系統(tǒng)之一[3-4]，本文的研究也正是圍繞該類格網(wǎng)系統(tǒng)展開。近年來，針對不同類型的正多面體格網(wǎng)生產(chǎn)方法，國內(nèi)外諸多研究都給出了不同的方法，如針對三角形QTM格網(wǎng)的生成方法[5-6]；針對菱形剖分的層次格網(wǎng)生產(chǎn)算法[7-8]；六邊形格網(wǎng)的正多面體生成算法[8]。上述研究成果中，多面體格網(wǎng)的生成方式中關(guān)于不同層級格網(wǎng)單元的構(gòu)造，歸納起來主要有兩種思路：一種是采用逐層遞歸的方式進(jìn)行剖分[9]；另一種是采用分層逐單元排列的方式進(jìn)行生成。雖然這些方法可以生成各類不同的三角形、四邊形和六邊形格網(wǎng)，但是一般而言，在這些格網(wǎng)的生成過程中，存在下面兩類問題：

1）需要根據(jù)目標(biāo)網(wǎng)格的形態(tài)（三角形、四邊形、六邊形）、孔徑（3孔或4孔）[9]、剖分頻率[1]的質(zhì)因數(shù)、對偶性、對心偏心性等因素[8]定制相應(yīng)的格網(wǎng)生成算法；

2）在采用遞歸方法進(jìn)行格網(wǎng)生成的過程中，高層次格網(wǎng)的生成需要設(shè)計有效分布式算法，算法復(fù)雜度較高。

針對上述問題，通過對現(xiàn)有不同類型格網(wǎng)單元，以及不同層級格網(wǎng)的分析，本文提出了一種基于單元復(fù)制方法的通用化全球離散格網(wǎng)生成方法，該方法采用“簡單單元復(fù)制+有效區(qū)域限制”的方式，能夠解決不同形態(tài)格網(wǎng)、不同層級格網(wǎng)的統(tǒng)一化生成問題。為了說明問題，論文以正二十面體上六邊形格網(wǎng)剖分為例展開討論，其他類型的格網(wǎng)生成可以采用通用的方式。全球離散格網(wǎng)的生成方法采用文獻(xiàn)[10]中圖1中的方式，本文設(shè)計算法主要集中在多尺度格網(wǎng)系統(tǒng)的構(gòu)建這一過程中。

1 基本思想

由于正二十面體是中心對稱圖形，因此僅考慮一個三角面上格網(wǎng)剖分情況，我們定義為單一三角面格網(wǎng)系統(tǒng)，首先，固定網(wǎng)格的基本剖分形態(tài)，分析現(xiàn)有各種剖分類型的單一三角面格網(wǎng)系統(tǒng)，其本質(zhì)區(qū)別在于單一三角面格網(wǎng)系統(tǒng)中所包含的剖分網(wǎng)格的數(shù)目和其相對于三角面的位置姿態(tài)有所不同。因此，從另一角度而言，我們固定網(wǎng)格的基本剖分形態(tài)并將其擴(kuò)充至無限平面中使之無縫無疊，我們稱之為“基擴(kuò)充平面格網(wǎng)系統(tǒng)”。下面就算法的基本思想進(jìn)行介紹：

在基擴(kuò)充平面格網(wǎng)系統(tǒng)中，建立適當(dāng)?shù)碾x散格網(wǎng)斜坐標(biāo)系，首先固定某一初始正三角形的頂點(diǎn)坐標(biāo)，稱該三角形為初始單一三角形；通過對初始單一三角形的邊界頂點(diǎn)坐標(biāo)進(jìn)行適當(dāng)?shù)男D(zhuǎn)、平移、縮放變換，使之與基擴(kuò)充平面格網(wǎng)系統(tǒng)中的部分剖分網(wǎng)格單元適當(dāng)?shù)亟M合起來，從而生成各種剖分類型任意層次的單一三角面格網(wǎng)系統(tǒng)，這樣不同組合變換參數(shù)與特定剖分類型和層次的單一三角面格網(wǎng)系統(tǒng)建立一一對應(yīng)的數(shù)學(xué)關(guān)系。通過改變網(wǎng)格的剖分形態(tài)和起算變換參數(shù)從而生成三角形、四邊形、六邊形任意剖分類型任意剖分層次的單一三角面格網(wǎng)系統(tǒng)。

結(jié)合上述的思路，算法分為下面幾個步驟：

1）建立基擴(kuò)充格網(wǎng)斜坐標(biāo)系；

2）確定待計算剖分格網(wǎng)系統(tǒng)的類型；

3）確定不同層級格網(wǎng)的有效控制邊界；

4）計算不同層級格網(wǎng)單元節(jié)點(diǎn)坐標(biāo)；

5）生成單一三角面格網(wǎng)系統(tǒng)坐標(biāo)；

6）建立不同層級單元節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系。

具體的算法技術(shù)路線圖，如圖1所示。

圖1 算法技術(shù)路線圖Fig.1 Algorithm technology roadmap

2 算法流程

2.1 建立基擴(kuò)充格網(wǎng)斜坐標(biāo)系

基擴(kuò)充格網(wǎng)坐標(biāo)系是建立在無限平面離散格網(wǎng)中的斜坐標(biāo)系，主要用于確定單一三角面格網(wǎng)系統(tǒng)中各種剖分形態(tài)、描述剖分類型規(guī)則排列的網(wǎng)格單元的中心位置，其坐標(biāo)值都是整數(shù)，下文統(tǒng)一稱格網(wǎng)坐標(biāo)。為了便于研究，本文以六邊形格網(wǎng)為例（后文中提到的格網(wǎng)皆指六邊形格網(wǎng)），定義坐標(biāo)原點(diǎn)位于無限平面離散格網(wǎng)中任一格網(wǎng)單元中心，水平相鄰格網(wǎng)中心連線作為坐標(biāo)系I軸，坐標(biāo)系J軸按照I軸逆時針方向旋轉(zhuǎn)120°方向得到。

另外，還需要建立輔助的空間直角坐標(biāo)系，該坐標(biāo)系的原點(diǎn)與X軸分別與基擴(kuò)充格網(wǎng)斜坐標(biāo)系的原點(diǎn)與I軸重合，Y軸按照X軸逆時針方向旋轉(zhuǎn)90°得到，Z軸遵循右手螺旋法則，下文統(tǒng)一稱直角坐標(biāo)。

在基擴(kuò)充格網(wǎng)斜坐標(biāo)系中，定義格網(wǎng)單元的半徑是R，初始單一三角形的頂點(diǎn)格網(wǎng)坐標(biāo)分別是A0(0,0)，B0(1,0)，C0(1,1)。對于格網(wǎng)坐標(biāo)(i,j)的任一單元的7個節(jié)點(diǎn)中，中心節(jié)點(diǎn)用O(i,j)標(biāo)識，6個邊界節(jié)點(diǎn)從右上角按逆時針方向依次用A(i,j)、B(i,j)、C(i,j)、D(i,j)、E(i,j)、F(i,j)標(biāo)識。具體情況如圖2所示。

圖2 基擴(kuò)充格網(wǎng)斜坐標(biāo)系和空間直角坐標(biāo)系的定義Fig.2 The def i nition of extended grid skew coordinate system and space cartesian coordinate system

通過基擴(kuò)充格網(wǎng)斜坐標(biāo)系和空間直角坐標(biāo)系之間的幾何變換關(guān)系，得出基擴(kuò)充格網(wǎng)斜坐標(biāo)系下格網(wǎng)坐標(biāo)是(i,j)的任意格網(wǎng)單元7個節(jié)點(diǎn)的空間直角坐標(biāo)分別如式（1）：

2.2 確定待計算剖分格網(wǎng)系統(tǒng)的類型

本文以六邊形格網(wǎng)系統(tǒng)為例，六邊形格網(wǎng)的情況比較復(fù)雜，目前常見的六邊形剖分有3孔剖分和4孔剖分，其中3孔剖分常見的有1種，4孔剖分常見有4種，具體剖分情況如圖3所示。

圖3 孔徑為3和4的六邊形剖分格網(wǎng)Fig.3 Hexagonal grid with 3 and 4 apertures

對當(dāng)前常見六邊形剖分的各類單一三角面格網(wǎng)系統(tǒng)的形態(tài)進(jìn)行分析，發(fā)現(xiàn)其本質(zhì)是：剖分網(wǎng)格的幾何形態(tài)是一致的，唯一不同的是三角面內(nèi)所包含的剖分網(wǎng)格的數(shù)目和這些網(wǎng)格相對于三角面的位置姿態(tài)有所不同，并且不同層級的網(wǎng)格，不同剖分類型的網(wǎng)格，具體情況都是類似的。因此，單一三角面格網(wǎng)系統(tǒng)的形態(tài)在基擴(kuò)充格網(wǎng)斜坐標(biāo)系中主要由起始點(diǎn)位置S=（i0,j0）、起始邊長度LN、起始邊與I軸正向夾角θ3個因素共同決定。

其中起始點(diǎn)位置僅有兩種情況：起始于格網(wǎng)中心節(jié)點(diǎn)和格網(wǎng)邊界節(jié)點(diǎn)。起始邊長度LN的不同取值可以生成不同尺度的格網(wǎng)系統(tǒng)。起始邊與X軸正向夾角θ有3種情況：0°、30°、60°。六邊形格網(wǎng)在基擴(kuò)充格網(wǎng)斜坐標(biāo)系中的具體剖分情況如圖4所示。

圖4 六邊形格網(wǎng)的各種剖分類型Fig.4 Various partition types of Hexagonal grid

通過對圖3和圖4剖分類型的對比分析，以三角形邊界處的格網(wǎng)形態(tài)為（具體情況已在圖3灰色區(qū)域中標(biāo)注）依據(jù)，可以得到這樣的結(jié)論：圖4a中的剖分方法對應(yīng)常見的4孔1類剖分，4孔2類剖分，3孔偶數(shù)層剖分；圖4b中的剖分方法對應(yīng)常見的4孔3類剖分，3孔奇數(shù)層剖分；圖4c中的剖分方法對應(yīng)常見的4孔4類剖分；圖4d中的剖分方法由于三角形邊界處的格網(wǎng)形態(tài)與格網(wǎng)單元間不具有明顯的幾何對稱關(guān)系，導(dǎo)致相鄰三角面間跨面單元的歸屬問題[11]變的異常復(fù)雜，因此文章對此種剖分方法不做過多研究。

2.3 確定多尺度格網(wǎng)有效控制邊界

為便于說明問題，本文以圖4a中的剖分方法為例，通過對基擴(kuò)充格網(wǎng)斜坐標(biāo)系下該類剖分的單一三角面格網(wǎng)系統(tǒng)進(jìn)行分析，發(fā)現(xiàn)多尺度格網(wǎng)生成的關(guān)鍵因素取決于起始邊長LN。換言之，取不同的起始邊長LN可以生產(chǎn)該剖分方法下不同層級的格網(wǎng)系統(tǒng)，因此研究起始邊長LN的不同取值與格網(wǎng)層級間的數(shù)學(xué)關(guān)系是十分必要的。

正二十面體上的20個頂點(diǎn)間具有對稱性、平等性、自反性。因此在固定剖分方法下，任一三角形邊界頂點(diǎn)處的格網(wǎng)形態(tài)必然是一致的，本文以此為依據(jù)研究發(fā)現(xiàn)起算邊長LN的取值可以表示為：LN=M×，公式中M∈Z+，R是六邊形格網(wǎng)單元的半徑。

為了體現(xiàn)格網(wǎng)系統(tǒng)不同層次間的關(guān)系，通過對該類剖分層級格網(wǎng)的研究，起算邊長LN的具體取值與格網(wǎng)層級的關(guān)系表示為：當(dāng)LN=3×2N-1×?xí)r，取適當(dāng)?shù)腘值，對應(yīng)該類剖分的第N層格網(wǎng)邊界長度。

因此，定義邊長起始節(jié)點(diǎn)所在格網(wǎng)單元為S=(i0,j0)，改變起算變換參數(shù)F=(S,LN,θ)=[(i0,j0)，3×2N-1×，60°]，得到該剖分方法下第N層剖分三角形的3個頂點(diǎn)格網(wǎng)坐標(biāo)分別為AN(i0,j0)，BN(i0+3×2N-1,j0)，CN(i0+3×2N-1),j0+3×2N-1)。然后通過公式(1)可以快速確定多尺度格網(wǎng)邊界頂點(diǎn)在空間直角坐標(biāo)系下的坐標(biāo)。具體結(jié)果如公式（2）：

2.4 計算多尺度格網(wǎng)單元格網(wǎng)坐標(biāo)

通過上述研究發(fā)現(xiàn)，在給定任意起始節(jié)點(diǎn)所在格網(wǎng)單元格網(wǎng)坐標(biāo)S=(i0,j0)和格網(wǎng)剖分層次N，在基擴(kuò)充格網(wǎng)斜坐標(biāo)系中，可以快速確定該層次剖分中任一格網(wǎng)單元的格網(wǎng)坐標(biāo)(i,j)，其中格網(wǎng)坐標(biāo)具體取值如公式（3）。第N層多尺度格網(wǎng)邊界在基擴(kuò)充格網(wǎng)斜坐標(biāo)系中具體情況如下圖5所示。因此，該層次剖分中的任一格網(wǎng)單元的7個節(jié)點(diǎn)的空間直角坐標(biāo)皆可通過公式（1）求得。

圖5 基擴(kuò)充格網(wǎng)斜坐標(biāo)系中第N層多尺度格網(wǎng)邊界Fig.5 Multi-scale grid boundary in the N-th Layer in extended grid skew coordinate system

2.5 計算單一三角面格網(wǎng)系統(tǒng)單元的節(jié)點(diǎn)坐標(biāo)

定義在第N層多尺度格網(wǎng)中，滿足公式(3)的格網(wǎng)坐標(biāo)為(i,j)的任意格網(wǎng)單元其7個節(jié)點(diǎn)中，設(shè)中心節(jié)點(diǎn)在空間直角坐標(biāo)系中X軸Y軸Z軸上的分量分別表示為。從右上角按逆時針方向定義的6個邊界節(jié)點(diǎn)在空間直角坐標(biāo)系中X軸Y軸Z軸上的分量依次表示為：

通過多尺度格網(wǎng)和初始單一三角形的邊界頂點(diǎn)在空間直角坐標(biāo)中的幾何關(guān)系，給出如下的坐標(biāo)變換關(guān)系：

在公式（4）中，K表示縮放系數(shù)，H表示旋轉(zhuǎn)矩陣，[x0y0z0]T表示平移向量，[x y z]T和[X Y Z]T分別表示變換前后的坐標(biāo)值。具體有以下兩類情況：

1）當(dāng)Z=0時，僅考慮單一三角面格網(wǎng)系統(tǒng)單元（平面），其中，H是二維旋轉(zhuǎn)矩陣；

2）當(dāng)Z≠0時，考慮直接從初始單一三角面（平面）到空間三角面的變換，通過該方法直接生成二十面體表面的格網(wǎng)。

本文針對上述剖分方法，研究表明，給定起算變換參數(shù)F=(S,LN,θ)=((i0,j0),3×2N-1×60°))，通過相似縮放變換，其中，得出在基擴(kuò)充格網(wǎng)斜坐標(biāo)系下，與第N層多尺度格網(wǎng)中滿足公式(3)的格網(wǎng)坐標(biāo)為(i,j)的格網(wǎng)單元相應(yīng)的單一三角面格網(wǎng)系統(tǒng)中單元的7個節(jié)點(diǎn)的空間直角坐標(biāo)(定義為A'(i,j)，B'(i,j)，C'(i,j)，D'(i,j)，E'(i,j)，F(xiàn)'(i,j)，O'(i,j))分別表示如下：

2.6 建立不同層級單元節(jié)點(diǎn)的關(guān)聯(lián)關(guān)系

建立不同層級格網(wǎng)單元節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系，有助于空間數(shù)據(jù)的快速檢索和應(yīng)用分析的高效計算[12]。這里的關(guān)聯(lián)關(guān)系指的是不同層級格網(wǎng)之間節(jié)點(diǎn)之間的對應(yīng)關(guān)系，目標(biāo)是為了建立層級節(jié)點(diǎn)之間的聯(lián)系，即計算第N層格網(wǎng)坐標(biāo)(I,J)的格網(wǎng)單元中，其7個節(jié)點(diǎn)在第N+1層格網(wǎng)中的具體格網(wǎng)坐標(biāo)與節(jié)點(diǎn)位置。

圖2所示的基擴(kuò)充格網(wǎng)斜坐標(biāo)系中，定義單一三角面格網(wǎng)系統(tǒng)的第N層格網(wǎng)單元中，格網(wǎng)坐標(biāo)是(I,J)單元的7個節(jié)點(diǎn)位置分別用A(N,I,J)，B(N,I,J)，C(N,I,J)，D(N,I,J)，E(N,I,J)，F(xiàn)(N,I,J)，O(N,I,J)表示。7個節(jié)點(diǎn)間的位置排序遵循前述原則。通過對相鄰層次格網(wǎng)的子單元、父單元的幾何位置關(guān)系分析，得出如下結(jié)論：

公式（6）中，A(N,I,J)～B(N+1,2I+1,2J)表示第N層中格網(wǎng)坐標(biāo)是(I,J)單元的邊界節(jié)點(diǎn)A與第N+1層中格網(wǎng)坐標(biāo)是(2I+1，2J)單元的邊界節(jié)點(diǎn)B對應(yīng)，公式（6）中其他情況類同。

3 結(jié)果與分析

根據(jù)前文的算法，本節(jié)針對平面單一三角面格網(wǎng)系統(tǒng)，計算得到其中各類參數(shù)，即3.1～3.6中的關(guān)鍵參數(shù)，見表1。

表1 各類剖分格網(wǎng)起算參數(shù)、有效控制邊界、單元節(jié)點(diǎn)空間直角坐標(biāo)Tab.1 Initial parameters of various partition grid types, eあective control of the boundary, unit node space cartesian coordinates

說明：表格中公式（5）見2.5，表格中公式（7）、（8）、（9）、（10）、（11）如下。

在公式（9），（10），（11）中，其他6個邊界節(jié)點(diǎn)的空間直角坐標(biāo)和中心節(jié)點(diǎn)O的情況類似，只需要用字母A，B，C，D，E，F(xiàn)分別替換上述公式中格網(wǎng)坐標(biāo)是(i，j)單元的節(jié)點(diǎn)字母O即可。

另外，本論文還給出通過本方法直接轉(zhuǎn)換到二十面體表面格網(wǎng)的情況，只需要令式（4）中的Z≠0，然后結(jié)合正二十面體的幾何屬性信息，建立合適的數(shù)學(xué)變換關(guān)系，可以完成從初始單一三角面（平面）到空間三角面的變換，即而從基擴(kuò)充平面格網(wǎng)系統(tǒng)直接生成正二十面體表面的格網(wǎng)。

本文以4孔1類剖分為例，進(jìn)行了下面的實(shí)驗，具體實(shí)驗結(jié)果如圖6所示。

圖6 正二十面體上4孔1類剖分第4、5、6、7層格網(wǎng)系統(tǒng)Fig.6 Divide the 4th, 5th, 6th, 7th grid system based on class 1 with 4-apertures on the icosahedron

4 結(jié)束語

本文提出了一種基于單元復(fù)制的通用化格網(wǎng)系統(tǒng)生成新算法，并以六邊形離散格網(wǎng)為例開展了驗證，實(shí)驗證明該方法具有很好的通用性，適合多種類型格網(wǎng)生成過程的復(fù)用。該算法的核心是“簡單單元復(fù)制+有效區(qū)域控制”，可以通過改變起算變換參數(shù)，生成任意形態(tài)任意類型的多尺度格網(wǎng)，避免了傳統(tǒng)定制算法的局限性，實(shí)現(xiàn)了統(tǒng)一化生成各類球面格網(wǎng)系統(tǒng)的目標(biāo)。相對于遞歸剖分方法而言，本算法在高層次格網(wǎng)生成中，進(jìn)一步降低了算法的復(fù)雜度，并且為不同剖分類型全球離散格網(wǎng)系統(tǒng)間互操作性[13-14]問題研究提供了一種解決思路。