用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　　E *qtree,
　　　　　　/　　　　　　　　　　 IN　 quadbox_t　　　t　　　　　　　 *search_box,
　　　　　　　　　　　　　　　　 OUT list_t　　　　　　　　　　　　　　　 *results_list
　　　　　　　　　　　　　　　　 );

#endif // QUADTREE_H_INCLUDED