C语言实现一个四叉树（quadtree）

C语言实现一个四叉树（quadtree）2010-10-10 csdn 张亮用C语言实现一个2维四叉树quadtree，具有一定的实际意义。你可以把几何图形的索引（用long型的id标识）放到这个树中（根据最小边界矩形）。quadtree可以用来快速区域查找图形，虽然不是那么精确，但是毕竟没有漏掉的。虽然quadtree的效率不如RTree？但是RTree的实现毕竟复杂了些，我会尽快收集整理出RTree的代码。RTree确实比QuadTree好的多？（起码RTree很时髦啊！）

头文件如下：

/*
 * quadtree.h
 *        Quad tree structure -- for spatial quick searching
 *        cheungmine
 *      Oct. 5, 2007.  All rights reserved.
 */
#ifndef QUADTREE_H_INCLUDED
#define QUADTREE_H_INCLUDED

#include "unistd.h"

#include "list.h"

#define QUAD_SUBNODES 4

#define QBOX_OVERLAP_MAX 0.4
#define QBOX_OVERLAP_MIN 0.02

#define QTREE_DEPTH_MAX 8
#define QTREE_DEPTH_MIN 4

#define QUADRANT_BITS  3

/* a quadrant defined below:

        NW（1）   |    NE（0）
        -----------|-----------
        SW（2）   |    SE（3）
*/
typedef enum
{
    NE = 0,
    NW = 1,
    SW = 2,
    SE = 3
}QuadrantEnum;

/* a box defined below:
           _____max
          |__|__|
          |__|__|
   min
*/
typedef struct _quadbox_t
{   
    double _xmin,
        _ymin,
        _xmax,
        _ymax;
}quadbox_t;

/* quad node */
typedef struct _quadnode_t
{
    quadbox_t  _box;  /* node bound box */
    list_t   *_lst;  /* node data list */
    struct _quadnode_t  *_sub[QUAD_SUBNODES];  /* pointer to subnodes of this node */
}quadnode_t;

/* quad tree */
typedef struct _quadtree_t
{
    quadnode_t *_root;
    int    _depth;  /* max depth of tree: 0-based */
    float   _overlap;  /* overlapped ratio of quanbox */
}quadtree_t;


/*=============================================================================
                        Public Functions
=============================================================================*/
/* creates a quadtree and returns a pointer to it */
extern  quadtree_t*
quadtree_create （quadbox_t    box,
                 int  depth,  /* 4~8 */
                 float overlap /* 0.02 ~ 0.4 */
                 ）;

/* destroys a quad tree and free all memory */
extern  void
quadtree_destroy （IN  quadtree_t  *qtree
                  ）;

/* inserts a node identified by node_key into a quadtree, returns the node quadtree encoding */
extern  quadnode_t *
quadtree_insert （IN  quadtree_t            *qtree,
                 IN  long                 node_key,
                 IN  quadbox_t            *node_box
                 ）;

/* searches nodes inside search_box */
extern  void
quadtree_search （IN  const quadtree_t    *qtree,
                  IN  quadbox_t            *search_box,
                 OUT list_t                *results_list
                 ）;

#endif // QUADTREE_H_INCLUDED