基于搜索圆的离散点格网化建模

李 源 冯 贺

（安阳工学院 计算机科学与信息工程学院，河南 安阳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.