基于搜索圓的離散點格網(wǎng)化建模

李 源 馮 賀

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

0 引言

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

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

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

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

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

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

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

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

（1）離散點

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

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

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

struct grid ｛int row；int colum；｝；

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

3 算法步驟

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

4 算法分析

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

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