染雾
用C语言实现一个2维四叉树quadtree，具有一定的实际意义，
C语言实现一个四叉树(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
实现文件如下：
/*
* quadtree.c
* Quad tree implementation -- for spatial quick searching
* cheungmine
* Oct. 5, 2007. All rights reserved.
*/
#include "quadtree.h"
#include
/*=============================================================================
Private Functions
=============================================================================*/
static BOOL quadbox_is
{
return (qb->_xmin < qb->_xmax && qb->_ymin < qb->_ymax)? TRUE : FALSE;
}
static double quadbox_width (const quadbox_t* qb)
{
return (qb->_xmax - qb->_xmin);
}
static double quadbox_height (const quadbox_t* qb)
{
return (qb->_ymax - qb->_ymin);
}
static void quadbox_init (quadbox_t *qb,
double xmin, double ymin, double xmax, double ymax)
