基于搜索圓的離散點格網化建模

李 源 馮 賀

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

0 引言

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

1 基于搜索圓離散點格網化原理

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

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

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

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

2 數據結構

為了實現基于搜索圓的離散點格網化，本文需要設計以下兩個數據結構：

（1）離散點

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

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

（2）規則格網

struct grid ｛int row；int colum；｝；

結構體struct grid 用于存儲規則格網信息， 其中row 為待插值格網的行數，colum 為格網的列數。

3 算法步驟

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

4 算法分析

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

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