RTree源代码——C语言实现（上）2010-10-29 csdn 张亮一、什么是RTree“R树是B树向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。当更新一个关系并且在这个关系上正在做扫描时，如果更新影响到了扫描操作的任何一个页，我们需要检查扫描并且修复它。”其实上面的话，你也不用多做研究。理解RTree是范围树，适合做空间索引（快速查找）。更多的关于RTree的知识我也没时间写在这里，我只知道原理，然后提供了下面的代码（经过我修改，看起来更顺眼些）。一定要用它。感谢算法的原作者和发明的人。“帝国大厦的建立，人才更在资本之上”啊！二、RTree的实现代码本文的代码来源于GRASS，我根据自己的习惯，作了适当的修改，把原来多个文件合成了2个文件（rtree.h和rtree.c）。本文提供了完整的rtree实现代码和一个简单的测试代码（test.c）。如果你发现什么问题，请及时提交评论，以利改正。RTree.h文件：/**************************************************************************** * RTree.H * * MODULE: R-Tree library * * AUTHOR（S）: Antonin Guttman - original code * Daniel Green （green@superliminal.com） - major clean-up * and implementation of bounding spheres * * PURPOSE: Multi Dimensional Index * * COPYRIGHT: （C） 2001 by the GRASS Development Team * * This program is free software under the GNU General Public * License （>=v2）. Read the file COPYING that comes with GRASS * for details. * * LAST MODIFY: ZhangLiang （cheungmine@gmail.com） - 2007-11 *****************************************************************************/ #ifndef RTREE_H_INCLUDED #define RTREE_H_INCLUDED
/* PAGE_SIZE is normally the natural page size of the machine */ #define PAGE_SIZE 512 #define DIMS_NUMB 3 /* number of dimensions */ #define SIDES_NUMB 2*DIMS_NUMB
/* * If passed to a tree search, this callback function will be called * with the ID of each data mbr that overlaps the search mbr * plus whatever user specific pointer was passed to the search. * It can terminate the search early by returning 0 in which case * the search will return the number of hits found up to that point. */ typedef int （*pfnSearchHitCallback）（int id, void* pfnParam）;
int RTreeSetNodeMax（int new_max）;
int RTreeSetLeafMax（int new_max）;
int RTreeGetNodeMax（void）;
int RTreeGetLeafMax（void）;
/** * Initialize a rectangle to have all 0 coordinates. */ void RTreeInitRect（ RTREEMBR *rc）;
/** * Return a mbr whose first low side is higher than its opposite side - * interpreted as an undefined mbr. */ RTREEMBR RTreeNullRect（void）;
/** * Print out the data for a rectangle. */ void RTreePrintRect（ RTREEMBR *rc, int depth ）;
/** * Calculate the 2-dimensional area of a rectangle */ REALTYPE RTreeRectArea（ RTREEMBR *rc ）;
/** * Calculate the n-dimensional volume of a rectangle */ REALTYPE RTreeRectVolume（ RTREEMBR *rc ）;
/** * Calculate the n-dimensional volume of the bounding sphere of a rectangle * The exact volume of the bounding sphere for the given RTREEMBR. */ REALTYPE RTreeRectSphericalVolume（ RTREEMBR *rc ）;
/** * Calculate the n-dimensional surface area of a rectangle */ REALTYPE RTreeRectSurfaceArea（ RTREEMBR *rc ）;
/** * Combine two rectangles, make one that includes both. */ RTREEMBR RTreeCombineRect（ RTREEMBR *rc1, RTREEMBR *rc2 ）;
/** * Decide whether two rectangles overlap. */ int RTreeOverlap（ RTREEMBR *rc1, RTREEMBR *rc2）;
/** * Decide whether rectangle r is contained in rectangle s. */ int RTreeContained（ RTREEMBR *r, RTREEMBR *s）;
/** * Split a node. * Divides the nodes branches and the extra one between two nodes. * Old node is one of the new ones, and one really new one is created. * Tries more than one method for choosing a partition, uses best result. */ void RTreeSplitNode（ RTREENODE *node, RTREEBRANCH *br, RTREENODE **new_node）;
/** * Make a new node and initialize to have all branch cells empty. */ RTREENODE *RTreeNewNode（void）;
void RTreeFreeNode（ RTREENODE *node ）;
/** * Print out the data in a node. */ void RTreePrintNode（ RTREENODE *node, int depth ）;
/** * Find the smallest rectangle that includes all rectangles in branches of a node. */ RTREEMBR RTreeNodeCover（ RTREENODE *node ）;
/** * Pick a branch. Pick the one that will need the smallest increase * in area to accomodate the new rectangle. This will result in the * least total area for the covering rectangles in the current node. * In case of a tie, pick the one which was smaller before, to get * the best resolution when searching. */ int RTreePickBranch（ RTREEMBR *rc, RTREENODE *node）;
/** * Add a branch to a node. Split the node if necessary. * Returns 0 if node not split. Old node updated. * Returns 1 if node split, sets *new_node to address of new node. * Old node updated, becomes one of two. */ int RTreeAddBranch（ RTREEBRANCH *br, RTREENODE *node, RTREENODE **new_node）;
/** * Disconnect a dependent node. */ void RTreeDisconnectBranch（ RTREENODE *node, int i ）;
/** * Create a new rtree index, empty. Consists of a single node. */ RTREENODE * RTreeCreate（void）;
/** * Destroy a rtree root must be a root of rtree. Free all memory. */ void RTreeDestroy（RTREENODE *root）;
/** * Search in an index tree or subtree for all data rectangles that overlap the argument rectangle. * Return the number of qualifying data rects. */ int RTreeSearch（ RTREENODE *node, RTREEMBR *rc, pfnSearchHitCallback pfnSHCB, void* pfnParam）;
/** * Insert a data rectangle into an index structure. * RTreeInsertRect provides for splitting the root; * returns 1 if root was split, 0 if it was not. * The level argument specifies the number of steps up from the leaf * level to insert; e.g. a data rectangle goes in at level = 0. * _RTreeInsertRect does the recursion. */ int RTreeInsertRect（ RTREEMBR *rc, int tid, RTREENODE **root, int level）;
/** * Delete a data rectangle from an index structure. * Pass in a pointer to a RTREEMBR, the tid of the record, ptr to ptr to root node. * Returns 1 if record not found, 0 if success. * RTreeDeleteRect provides for eliminating the root. */ int RTreeDeleteRect（ RTREEMBR *rc, int tid, RTREENODE **root）;
易网时代-编程资源站