R-TREE的实现及应用

R树在数据库等领域做出的功绩是非常显著的，它很好的解决了在高维空间搜索等问题，该资料为其简单的实现和应用哦。

/****************************************************************************
* RTree.C
*
* 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
*****************************************************************************/

#include 
#include 
#include 
#include 
#include 

#include “rtree.h“

#define        METHODS        1

/* variables for finding a partition */
typedef struct _RTREEPARTITION
{
    int            partition[MAXCARD+1];
    int            total;
    int            minfill;
    int            taken[MAXCARD+1];
    int            count[2];
    RTREEMBR    cover[2];
    REALTYPE    area[2];
} RTREEPARTITION;

RTREEBRANCH        BranchBuf[MAXCARD+1];
int                BranchCount;
RTREEMBR        CoverSplit;
REALTYPE        CoverSplitArea;
RTREEPARTITION    Partitions[METHODS];


#define BIG_NUM （FLT_MAX/4.0）

#define INVALID_RECT（x） （（x）->bound[0] > （x）->bound[DIMS_NUMB]）
#define MIN（a b） （（a） < （b） ? （a） : （b））
#define MAX（a b） （（a） > （b） ? （a） : （b））

int NODECARD = MAXCARD;
int LEAFCARD = MAXCARD;

/* balance criteria for node splitting */
/* NOTE: can be changed if needed. */
#define MINNODEFILL （NODECARD / 2）
#define MINLEAFFILL （LEAFCARD / 2）

#define MAXKIDS（n） （（n）->level > 0 ? NODECARD : LEAFCARD）
#define MINFILL（n） （（n）->level > 0 ? MINNODEFILL : MINLEAFFILL）

static int set_max（int *which int new_max）
{
    if（2 > new_max || new_max > MAXCARD）
        return 0;
    *which = new_max;
    return 1;
}


/**
 * Load branch buffer with branches from full node plus the extra branch.
 */
static void _RTreeGetBranches（ RTREENODE *node RTREEBRANCH *br）
{
    int i;

    assert（node && br）;
    
    /* load the branch buffer */
    for （i=0; i    {
        assert（node->branch[i].child）; /* n should have every entry full */
        BranchBuf[i] = node->branch[i];
    }

    BranchBuf[MAXKIDS（node）] = *br;
    BranchCount = MAXKIDS（node） + 1;

    /* calculate mbr containing all in the set */
    CoverSplit = BranchBuf[0].mbr;

    for （i=1; i    {
        CoverSplit = RTreeCombineRect（&CoverSplit &BranchBuf[i].mbr）;
    }

    CoverSplitArea = RTreeRectSphericalVolume（&CoverSplit）;
    RTreeInitNode（node）;
}



/**
 * Put a branch in one of the groups.
 */
static void _RTreeClassify（int i 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件    4601517  2014-08-17 21:39  Rtree\Data10.asc

     文件     186227  2014-08-17 21:39  Rtree\Data20.asc

     文件     118272  2014-11-11 17:29  Rtree\Debug\Rtree.exe

     文件     738308  2014-11-11 17:29  Rtree\Debug\Rtree.ilk

     文件    1018880  2014-11-11 17:29  Rtree\Debug\Rtree.pdb

     文件    6017162  2014-08-07 09:58  Rtree\NoiseModel1.asc

     文件    4745286  2014-11-11 17:30  Rtree\Rtree\Data1.asc

     文件    5036878  2014-08-19 12:26  Rtree\Rtree\Data10.asc

     文件     430664  2014-11-11 17:30  Rtree\Rtree\Data2.asc

     文件     139072  2014-08-19 12:26  Rtree\Rtree\Data20.asc

     文件     620098  2014-11-11 17:30  Rtree\Rtree\Data3.asc

     文件     307646  2014-08-20 14:35  Rtree\Rtree\Data3_14_8.asc

     文件     337550  2014-08-20 14:19  Rtree\Rtree\Data3_18_8.asc

     文件    4555852  2014-11-11 17:30  Rtree\Rtree\Data4.asc

     文件    4868304  2014-08-20 14:35  Rtree\Rtree\Data4_14_8.asc

     文件    4838400  2014-08-20 14:19  Rtree\Rtree\Data4_18_8.asc

     文件       8810  2014-11-11 17:29  Rtree\Rtree\Debug\BuildLog.htm

     文件         65  2014-11-11 17:29  Rtree\Rtree\Debug\mt.dep

     文件        663  2014-08-19 12:21  Rtree\Rtree\Debug\Rtree.exe.embed.manifest

     文件        728  2014-08-19 12:21  Rtree\Rtree\Debug\Rtree.exe.embed.manifest.res

     文件        621  2014-11-11 17:29  Rtree\Rtree\Debug\Rtree.exe.intermediate.manifest

     文件      73681  2014-08-20 15:12  Rtree\Rtree\Debug\RTree.obj

     文件     312242  2014-11-11 17:29  Rtree\Rtree\Debug\TestNoise.obj

     文件     265216  2014-11-11 17:29  Rtree\Rtree\Debug\vc90.idb

     文件     266240  2014-11-11 17:29  Rtree\Rtree\Debug\vc90.pdb

     文件     170005  2014-11-11 17:30  Rtree\Rtree\density

     文件     469458  2014-08-19 12:26  Rtree\Rtree\density0

     文件      30244  2014-08-06 19:54  Rtree\Rtree\RTree.cpp

     文件       6594  2014-08-20 15:12  Rtree\Rtree\RTree.h

     文件       4037  2014-08-07 21:32  Rtree\Rtree\Rtree.vcproj

............此处省略14个文件信息