一种平面散乱点集的自适应空间划分算法

An Algorithm for Self-adaptive Partition of Scattered Points in Planar Domain

  • 摘要: 针对平面散乱点集空间划分问题,提出了一种基于栅格统计的自适应空间划分算法。以栅格场为辅助手段为散乱点集建立空间索引,即判断各点与栅格的归属关系;统计各个栅格内包含点的数量;以栅格为基本统计单元对空间进行划分。划分过程中借助了二叉树结构,同时引入迭代次数作为划分终止的参数。该方法可灵活地将点集划分为数据量相对均衡的若干组,且各组的空间范围较合理。实验与分析表明,该算法具有较高的计算效率,也不需占用太多额外的存储空间。

     

    Abstract: This paper presents a method to partition the scattered points in planar domain based on grid-statistics and adaptive binary-partition.The basic idea of the method is as follows.First,build a grid field which can cover over all planar points to create the spatial index of the points.Then,figure out the position of every point in the grid field,such as the row and column place in the field,meanwhile,reserve the number of points in each grid.Finally,set the number of iterations as the parameter of terminating to partition the scattered points with proposed rules.This method can divide the data point-set into several groups flexibly and the result is relatively balanced.Besides,the computational efficient of the algorithm is relatively high and not too much extra storage space is needed.The method proposed in this paper can be used in the existing spatial analysis algorithms using partitioning-strategy and can be further applied to the related parallel algorithms.It also provides reference for adaptive partition of other types of spatial elements.

     

/

返回文章
返回