C语言实现一个四叉树quadtree

C语言实现一个四叉树quadtree

cheungmine

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

头文件如下：

/*
*quadtree.h
*Quadtreestructure--forspatialquicksearching
*cheungmine
*Oct.5,2007.Allrightsreserved.
*/
#ifndefQUADTREE_H_INCLUDED
#defineQUADTREE_H_INCLUDED

#include"unistd.h"

#include"list.h"

#defineQUAD_SUBNODES4

#defineQBOX_OVERLAP_MAX0.4
#defineQBOX_OVERLAP_MIN0.02

#defineQTREE_DEPTH_MAX8
#defineQTREE_DEPTH_MIN4

#defineQUADRANT_BITS3

/*aquadrantdefinedbelow:

NW(1)|NE(0)
-----------|-----------
SW(2)|SE(3)
*/
typedefenum
{
NE=0,
NW=1,
SW=2,
SE=3
}QuadrantEnum;

/*aboxdefinedbelow:
_____max
|__|__|
|__|__|
min
*/
typedefstruct_quadbox_t
{
double_xmin,
_ymin,
_xmax,
_ymax;
}quadbox_t;

/*quadnode*/
typedefstruct_quadnode_t
{
quadbox_t_box;/*nodeboundbox*/
list_t*_lst;/*nodedatalist*/
struct_quadnode_t*_sub[QUAD_SUBNODES];/*pointertosubnodesofthisnode*/
}quadnode_t;

/*quadtree*/
typedefstruct_quadtree_t
{
quadnode_t*_root;
int_depth;/*maxdepthoftree:0-based*/
float_overlap;/*overlappedratioofquanbox*/
}quadtree_t;


/*=============================================================================
PublicFunctions
=============================================================================*/
/*createsaquadtreeandreturnsapointertoit*/
externquadtree_t*
quadtree_create(quadbox_tbox,
intdepth,/*4~8*/
floatoverlap/*0.02~0.4*/
);

/*destroysaquadtreeandfreeallmemory*/
externvoid
quadtree_destroy(INquadtree_t*qtree
);

/*insertsanodeidentifiedbynode_keyintoaquadtree,returnsthenodequadtreeencoding*/
externquadnode_t*
quadtree_insert(INquadtree_t*qtree,
INlongnode_key,
INquadbox_t*node_box
);

/*searchesnodesinsidesearch_box*/
externvoid
quadtree_search(INconstquadtree_t*qtree,
INquadbox_t*search_box,
OUTlist_t*results_list
);

#endif//QUADTREE_H_INCLUDED

实现文件如下：

/*
*quadtree.c
*Quadtreeimplementation--forspatialquicksearching
*cheungmine
*Oct.5,2007.Allrightsreserved.
*/
#include"quadtree.h"
#include<assert.h>

/*=============================================================================
PrivateFunctions
=============================================================================*/
staticBOOLquadbox_is_valid(quadbox_t*qb)
{
return(qb->_xmin<qb->_xmax&&qb->_ymin<qb->_ymax)?TRUE:FALSE;
}

staticdoublequadbox_width(constquadbox_t*qb)
{
return(qb->_xmax-qb->_xmin);
}

staticdoublequadbox_height(constquadbox_t*qb)
{
return(qb->_ymax-qb->_ymin);
}

staticvoidquadbox_init(quadbox_t*qb,
doublexmin,doubleymin,doublexmax,doubleymax)
{
qb->_xmin=xmin;qb->_ymin=ymin;qb->_xmax=xmax;qb->_ymax=ymax;
assert(quadbox_is_valid(qb));
}

staticvoidquadbox_inflate(quadbox_t*qb,doubledx,doubledy)
{
assert(dx>0&&dy>0);
qb->_xmin-=(dx/2);
qb->_xmax+=(dx/2);
qb->_ymin-=(dy/2);
qb->_ymax+=(dy/2);
}

/*splitsthequadrantsuchasbelow:
nw(0010)|ne(0001)
----------|----------
sw(0100)|se(1000)
*/
staticvoidquadbox_split(constquadbox_t*qb,
quadbox_t*ne,quadbox_t*nw,quadbox_t*se,quadbox_t*sw,
floatoverlap)
{
doubledx=quadbox_width(qb)*(1.0+overlap)/2;
doubledy=quadbox_height(qb)*(1.0+overlap)/2;

assert(overlap>=QBOX_OVERLAP_MIN-0.0001);
assert(overlap<=QBOX_OVERLAP_MAX+0.0001);

quadbox_init(ne,qb->_xmax-dx,qb->_ymax-dy,qb->_xmax,qb->_ymax);
quadbox_init(nw,qb->_xmin,qb->_ymax-dy,qb->_xmin+dx,qb->_ymax);
quadbox_init(sw,qb->_xmin,qb->_ymin,qb->_xmin+dx,qb->_ymin+dy);
quadbox_init(se,qb->_xmax-dx,qb->_ymin,qb->_xmax,qb->_ymin+dy);
}

/*returnsTRUEifthefirstisinsidethesenond*/
staticBOOLquadbox_is_inside(constquadbox_t*_first,constquadbox_t*_second)
{
return(_second->_xmin<_first->_xmin&&_second->_xmax>_first->_xmax&&
_second->_ymin<_first->_ymin&&_second->_ymax>_first->_ymax)?TRUE:FALSE;
}

/*returnsTRUEiftwoquad_boxisoverlapped*/
staticBOOLquadbox_is_overlapped(constquadbox_t*_first,constquadbox_t*_second)
{
return(_first->_xmin>_second->_xmax||_first->_xmax<_second->_xmin||
_first->_ymin>_second->_ymax||_first->_ymax<_second->_ymin)?FALSE:TRUE;
}

staticquadnode_t*quadnode_create(constquadbox_t*box)
{
quadnode_t*node=(quadnode_t*)calloc(1,sizeof(quadnode_t));
if(node)
memcpy(&(node->_box),box,sizeof(quadbox_t));
returnnode;
}

staticvoidquadnode_destroy(quadnode_t*node)
{
if(node->_sub[NE]!=0){
quadnode_destroy(node->_sub[NE]);
quadnode_destroy(node->_sub[NW]);
quadnode_destroy(node->_sub[SE]);
quadnode_destroy(node->_sub[SW]);
}

if(node->_lst)
list_destroy(node->_lst,NULL);

free(node);
}

staticvoidquadnode_create_child(quadnode_t*node,floatoverlap,intdepth)
{
quadbox_tne,nw,se,sw;

assert(node);
quadbox_split(&(node->_box),&ne,&nw,&se,&sw,overlap);

node->_sub[NE]=quadnode_create(&ne);
node->_sub[NW]=quadnode_create(&nw);
node->_sub[SW]=quadnode_create(&sw);
node->_sub[SE]=quadnode_create(&se);
}

staticBOOLquadnode_has_child(constquadnode_t*node)
{
return(node->_sub[NE]!=0);
}

staticBOOLquadnode_has_data(constquadnode_t*node)
{
return(node->_lst&&node->_lst->size>0)?TRUE:FALSE;
}

staticvoidquadnode_add_data(quadnode_t*node,longnode_key)
{
assert(node);
if(!node->_lst)node->_lst=list_create();
assert(node->_lst);
list_append_node(node->_lst,list_key_create(node_key));
}

/*insertsanodetoparentnodeoftree.returnspointertonode*/
staticquadnode_t*quadtree_insert_node(quadtree_t*tree,
quadnode_t*parent,
longnode_key,
quadbox_t*node_box,
int*depth
)
{
if(quadbox_is_inside(node_box,&(parent->_box)))
{
if(++(*depth)<tree->_depth)
{
if(!quadnode_has_child(parent))
quadnode_create_child(parent,tree->_overlap,(*depth));

if(quadbox_is_inside(node_box,&(parent->_sub[NE]->_box)))
returnquadtree_insert_node(tree,parent->_sub[NE],node_key,node_box,depth);

if(quadbox_is_inside(node_box,&(parent->_sub[NW]->_box)))
returnquadtree_insert_node(tree,parent->_sub[NW],node_key,node_box,depth);

if(quadbox_is_inside(node_box,&(parent->_sub[SW]->_box)))
returnquadtree_insert_node(tree,parent->_sub[SW],node_key,node_box,depth);

if(quadbox_is_inside(node_box,&(parent->_sub[SE]->_box)))
returnquadtree_insert_node(tree,parent->_sub[SE],node_key,node_box,depth);
}

/*insertsintothisnodesinceitcanNOTbeincludedinanysubnodes*/
quadnode_add_data(parent,node_key);
returnparent;
}

returnNULL;
}


/*searchedtreenodes*/
staticvoidquadtree_search_nodes(quadnode_t*current_node,
quadbox_t*search_box,
list_t*results_list
)
{
if(quadbox_is_overlapped(&(current_node->_box),search_box))
{
if(quadnode_has_data(current_node))
list_append_node(results_list,list_node_create(current_node));

if(quadnode_has_child(current_node))
{
quadtree_search_nodes(current_node->_sub[NE],search_box,results_list);
quadtree_search_nodes(current_node->_sub[NW],search_box,results_list);
quadtree_search_nodes(current_node->_sub[SW],search_box,results_list);
quadtree_search_nodes(current_node->_sub[SE],search_box,results_list);
}
}
}


/*=============================================================================
PublicFunctions
=============================================================================*/
quadtree_t*
quadtree_create(quadbox_tbox,
intdepth,/*4~8*/
floatoverlap/*0.02~0.4*/
)
{
quadtree_t*qt=NULL;

assert(depth>=QTREE_DEPTH_MIN-0.0001&&depth<=QTREE_DEPTH_MAX+0.0001);
assert(overlap>=QBOX_OVERLAP_MIN-0.0001&&overlap<=QBOX_OVERLAP_MAX+0.0001);

qt=(quadtree_t*)calloc(1,sizeof(quadtree_t));

if(qt)
{
qt->_depth=depth;
qt->_overlap=overlap;

quadbox_inflate(&box,quadbox_width(&box)*overlap,quadbox_height(&box)*overlap);

qt->_root=quadnode_create(&box);
assert(qt->_root);
if(!qt->_root)
{
free(qt);
qt=NULL;
}
}

assert(qt);
returnqt;
}

/*destroysaquadtree*/
void
quadtree_destroy(INquadtree_t*qtree)
{
assert(qtree&&qtree->_root);
quadnode_destroy(qtree->_root);
free(qtree);
}

/*insertsanodeintoquadtreeandreturnpointertonewnode*/
quadnode_t*
quadtree_insert(INquadtree_t*qtree,
INlongnode_key,
INquadbox_t*node_box
)
{
intdepth=-1;
returnquadtree_insert_node(qtree,qtree->_root,node_key,node_box,&depth);
}

/*searchesnodesinsidesearch_box*/
void
quadtree_search(INconstquadtree_t*qtree,
INquadbox_t*search_box,
OUTlist_t*results_list
)
{
quadtree_search_nodes(qtree->_root,search_box,results_list);
}

其中用到的文件（list.h，list.c，unistd.h）参考我的另一篇文章：

C语言实现一个简单的单向链表list