一种随机化递增的压缩四叉树形数据结构的构建算法

A Randemized Recursive Building Algorithm for Compact Quadtree Data Structure

介绍了一种压缩四叉树形数据结构的随机化增量构造算法。首先给出了压缩四叉树的定义,然后描述了算法实现步骤,通过将单位正方形不断分割为更小的正则正方形达到压缩的目的,使用平铺区域和冲突列表,采用随机化递增的算法构建出压缩四叉树,最后分析了算法正确性和运行时间。

We introduced a randomized recursive building algorithm for compact quadtree data structure in this article.At first we gave a definition for compressed quadtrees.Then we described the implementation steps of the algorithm.We compressed the quadtrees by splitting the unit square into smaller canonical square iteratively.We used tiles and conflict list,constructing the compressed quadtrees by randomized recursive algorithm.We analysis the correctness and the cost time of the algorithm at last.