用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