李 源 馮 賀

（安陽工學院 計算機科學與信息工程學院，河南 安陽455000）

0 引言

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

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

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

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

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

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

2 數(shù)據(jù)結構

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

（1）離散點

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

結構體struct point 用于存儲離散點坐標信息， 其中no 為離散點索引號，x，y，z 為離散點的三維坐標，s 為離散點到插值點的距離。

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

struct grid ｛int row；int colum；｝；

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

3 算法步驟

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

4 算法分析

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

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