李 源 馮 賀

（安陽(yáng)工學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河南 安陽(yáng)455000）

0 引言

基于格網(wǎng)模型的等值線生成，首先要把離散點(diǎn)網(wǎng)格化，以建立格網(wǎng)模型。 在建立格網(wǎng)模型的過(guò)程中，需要以格網(wǎng)點(diǎn)周圍離散點(diǎn)的高程值內(nèi)插格網(wǎng)點(diǎn)高程值，因此格網(wǎng)點(diǎn)周圍離散點(diǎn)的選取不同對(duì)內(nèi)插得到的格網(wǎng)點(diǎn)高程值的影響很大，內(nèi)插格網(wǎng)點(diǎn)高程值最理想的結(jié)果是所研究的區(qū)域內(nèi)全部離散點(diǎn)都參與某一格網(wǎng)點(diǎn)高程值的內(nèi)插計(jì)算，但這一方法由于參與運(yùn)算的數(shù)據(jù)量非常大，效率低而不可取。 因此在離散點(diǎn)格網(wǎng)化的過(guò)程中，所采取的方法要兼顧插值結(jié)果的準(zhǔn)確性及運(yùn)行效率的高效性。

1 基于搜索圓離散點(diǎn)格網(wǎng)化原理

公式1：r=（7*A／N／Pj）1/2

為了提高Pj 的準(zhǔn)確性及格網(wǎng)化效率， 一般預(yù)先設(shè)定落在r 為半徑的圓內(nèi)離散點(diǎn)數(shù)目K 的范圍為［Nmin，Nmax］，若落在搜索圓內(nèi)的離散點(diǎn)個(gè)數(shù)大于Nmax或小于Nmin則搜索圓的半徑r 做相應(yīng)的縮小或擴(kuò)大調(diào)整。

由上述原理及離散點(diǎn)分布的無(wú)規(guī)律性可知， 每個(gè)插值點(diǎn)Pj 的搜索圓半徑r 都是不相同的， 那么就需要重復(fù)計(jì)算以確定搜索圓的半徑。 經(jīng)典方法是首先求出所有離散點(diǎn)與待插值點(diǎn)Pj之間的距離，然后把離散點(diǎn)按距離為關(guān)鍵字進(jìn)行排序，以找到nj個(gè)落在r 為半徑的圓內(nèi)的離散點(diǎn)。設(shè)集合P 的元素個(gè)數(shù)為M，計(jì)算距離的復(fù)雜度為O（M*N），N 個(gè)點(diǎn)按距離排序的最優(yōu)時(shí)間復(fù)雜度是O（NlogN），因?yàn)橛?jì)算距離及排序的時(shí)間復(fù)雜度為O（MN（1＋logN）），該時(shí)間復(fù)雜度也是經(jīng)典方法內(nèi)插格網(wǎng)點(diǎn)的時(shí)間復(fù)雜度。 本章介紹的方法，首先對(duì)離散點(diǎn)按X 軸排序，然后再動(dòng)態(tài)確定搜索圓半徑。

根據(jù)公式4、公式5 可得到集合D′，再由D′中的元素與Pj的距離可得到集合D″。 D″中的元素就是所求得的參與格網(wǎng)點(diǎn)Pj內(nèi)插計(jì)算并且落入搜索圓中的離散點(diǎn)。調(diào)整搜索圓的半徑，使D″中元素個(gè)數(shù)K 滿足條件Nmin≤K≤Nmax。

2 數(shù)據(jù)結(jié)構(gòu)

為了實(shí)現(xiàn)基于搜索圓的離散點(diǎn)格網(wǎng)化，本文需要設(shè)計(jì)以下兩個(gè)數(shù)據(jù)結(jié)構(gòu)：

（1）離散點(diǎn)

struct point ｛int no；float x，y，z；float s｝；

結(jié)構(gòu)體struct point 用于存儲(chǔ)離散點(diǎn)坐標(biāo)信息， 其中no 為離散點(diǎn)索引號(hào)，x，y，z 為離散點(diǎn)的三維坐標(biāo)，s 為離散點(diǎn)到插值點(diǎn)的距離。

（2）規(guī)則格網(wǎng)

struct grid ｛int row；int colum；｝；

結(jié)構(gòu)體struct grid 用于存儲(chǔ)規(guī)則格網(wǎng)信息， 其中row 為待插值格網(wǎng)的行數(shù)，colum 為格網(wǎng)的列數(shù)。

3 算法步驟

根據(jù)上述原理，確定搜索圓半徑內(nèi)離散點(diǎn)的步驟如下：

4 算法分析

由上述對(duì)基于搜索圓的格網(wǎng)建模算法描述可知，在同一次建立格網(wǎng)模型時(shí)，需要對(duì)離散點(diǎn)進(jìn)行按X 軸排序，使用快速排序算法對(duì)離散點(diǎn)排序的時(shí)間復(fù)雜度為O（NlogN），在對(duì)含有N 個(gè)關(guān)鍵字從小到大排序的線性表進(jìn)行折半查找，查找的時(shí)間復(fù)雜度為O（logN），對(duì)有M 個(gè)格網(wǎng)點(diǎn)高程值需要進(jìn)行內(nèi)插計(jì)算，所以全部格網(wǎng)點(diǎn)內(nèi)插計(jì)算的時(shí)間復(fù)雜度為O（MlogN），因此離散點(diǎn)格網(wǎng)建?？偟臅r(shí)間復(fù)雜度為O（NlogN）+O（MlogN）=O（（M+N）logN）。

［1］孫科峰，孫根正，李潔.一種新的矩形網(wǎng)格生成等值線算法[J].東華大學(xué)學(xué)報(bào)：自然科學(xué)版，2005(31)4：66－69.