范帥博，童曉沖，雷 毅

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

0 引 言

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

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

2）在采用遞歸方法進行格網生成的過程中，高層次格網的生成需要設計有效分布式算法，算法復雜度較高。

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

1 基本思想

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

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

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

1）建立基擴充格網斜坐標系；

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

3）確定不同層級格網的有效控制邊界；

4）計算不同層級格網單元節(jié)點坐標；

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

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

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

圖1 算法技術路線圖Fig.1 Algorithm technology roadmap

2 算法流程

2.1 建立基擴充格網斜坐標系

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

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

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

圖2 基擴充格網斜坐標系和空間直角坐標系的定義Fig.2 The def i nition of extended grid skew coordinate system and space cartesian coordinate system

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

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

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

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

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

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

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

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

2.3 確定多尺度格網有效控制邊界

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

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

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

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

2.4 計算多尺度格網單元格網坐標

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

圖5 基擴充格網斜坐標系中第N層多尺度格網邊界Fig.5 Multi-scale grid boundary in the N-th Layer in extended grid skew coordinate system

2.5 計算單一三角面格網系統(tǒng)單元的節(jié)點坐標

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

通過多尺度格網和初始單一三角形的邊界頂點在空間直角坐標中的幾何關系，給出如下的坐標變換關系：

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

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

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

本文針對上述剖分方法，研究表明，給定起算變換參數(shù)F=(S,LN,θ)=((i0,j0),3×2N-1×60°))，通過相似縮放變換，其中，得出在基擴充格網斜坐標系下，與第N層多尺度格網中滿足公式(3)的格網坐標為(i,j)的格網單元相應的單一三角面格網系統(tǒng)中單元的7個節(jié)點的空間直角坐標(定義為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é)點的關聯(lián)關系

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

圖2所示的基擴充格網斜坐標系中，定義單一三角面格網系統(tǒng)的第N層格網單元中，格網坐標是(I,J)單元的7個節(jié)點位置分別用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é)點間的位置排序遵循前述原則。通過對相鄰層次格網的子單元、父單元的幾何位置關系分析，得出如下結論：

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

3 結果與分析

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

表1 各類剖分格網起算參數(shù)、有效控制邊界、單元節(jié)點空間直角坐標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é)點的空間直角坐標和中心節(jié)點O的情況類似，只需要用字母A，B，C，D，E，F(xiàn)分別替換上述公式中格網坐標是(i，j)單元的節(jié)點字母O即可。

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

本文以4孔1類剖分為例，進行了下面的實驗，具體實驗結果如圖6所示。

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

4 結束語

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