ID #5694

RTree源代码——C语言实现(下)

/*=============================================================================
                                Public functions:
 =============================================================================*/

int RTreeSetNodeMax(int new_max) { return set_max(&NODECARD, new_max); }
int RTreeSetLeafMax(int new_max) { return set_max(&LEAFCARD, new_max); }
int RTreeGetNodeMax(void) { return NODECARD; }
int RTreeGetLeafMax(void) { return LEAFCARD; }

/**
 * Initialize a rectangle to have all 0 coordinates.
 */
void RTreeInitRect( RTREEMBR *rc)
{
    int i;
    for (i=0; i<SIDES_NUMB; i++)
        rc->bound[i] = (REALTYPE) 0;
}


/**
 * Return a mbr whose first low side is higher than its opposite side -
 * interpreted as an undefined mbr.
 */
RTREEMBR RTreeNullRect(void)
{
    RTREEMBR rc;
    int i;

    rc.bound[0] = (REALTYPE) 1;
    rc.bound[DIMS_NUMB] = (REALTYPE)-1;
    for (i=1; i<DIMS_NUMB; i++)
        rc.bound[i] = rc.bound[i+DIMS_NUMB] = (REALTYPE) 0;
    return rc;
}

/**
 * Print out the data for a rectangle.
 */
void RTreePrintRect( RTREEMBR *rc, int depth)
{
    int i;

    _RTreeTabIn(depth);
    fprintf (stdout, "mbr: ");
    for (i = 0; i < DIMS_NUMB; i++)
    {
        _RTreeTabIn(depth+1);
        fprintf (stdout, "%f %f ", rc->bound[i], rc->bound[i + DIMS_NUMB]);
    }
}

/**
 * Calculate the 2-dimensional area of a rectangle
 */
REALTYPE RTreeRectArea( RTREEMBR *rc )
{
    if (INVALID_RECT(rc))
        return (REALTYPE) 0;

    return (rc->bound[DIMS_NUMB] - rc->bound[0]) * (rc->bound[DIMS_NUMB+1] - rc->bound[1]);
}


/**
 * Calculate the n-dimensional volume of a rectangle
 */
REALTYPE RTreeRectVolume( RTREEMBR *rc )
{
    int i;
    REALTYPE vol = (REALTYPE) 1;

    if (INVALID_RECT(rc))
        return (REALTYPE) 0;

    for(i=0; i<DIMS_NUMB; i++)
        vol *= (rc->bound[i+DIMS_NUMB] - rc->bound[i]);
    assert(vol >= 0.0);
    return vol;
}


/**
 * Precomputed volumes of the unit spheres for the first few dimensions
 */
const double UnitSphereVolumes[] = {
    0.000000,  /* dimension   0 */
    2.000000,  /* dimension   1 */
    3.141593,  /* dimension   2 */
    4.188790,  /* dimension   3 */
    4.934802,  /* dimension   4 */
    5.263789,  /* dimension   5 */
    5.167713,  /* dimension   6 */
    4.724766,  /* dimension   7 */
    4.058712,  /* dimension   8 */
    3.298509,  /* dimension   9 */
    2.550164,  /* dimension  10 */
    1.884104,  /* dimension  11 */
    1.335263,  /* dimension  12 */
    0.910629,  /* dimension  13 */
    0.599265,  /* dimension  14 */
    0.381443,  /* dimension  15 */
    0.235331,  /* dimension  16 */
    0.140981,  /* dimension  17 */
    0.082146,  /* dimension  18 */
    0.046622,  /* dimension  19 */
    0.025807,  /* dimension  20 */
};

#if DIMS_NUMB > 20
    #error "not enough precomputed sphere volumes"
#endif

#define UnitSphereVolume UnitSphereVolumes[DIMS_NUMB]

/**
 * 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 )
{
    int i;
    double sum_of_squares=0, radius;

    if (INVALID_RECT(rc))
        return (REALTYPE) 0;

    for (i=0; i<DIMS_NUMB; i++) {
        double half_extent = (rc->bound[i+DIMS_NUMB] - rc->bound[i]) / 2;
        sum_of_squares += half_extent * half_extent;
    }
    radius = sqrt(sum_of_squares);
    return (REALTYPE)(pow(radius, DIMS_NUMB) * UnitSphereVolume);
}


/**
 * Calculate the n-dimensional surface area of a rectangle
 */
REALTYPE RTreeRectSurfaceArea( RTREEMBR *rc )
{
    int i, j;
    REALTYPE sum = (REALTYPE) 0;

    if (INVALID_RECT(rc))
        return (REALTYPE) 0;

    for (i=0; i<DIMS_NUMB; i++) {
        REALTYPE face_area = (REALTYPE)1;
        for (j=0; j<DIMS_NUMB; j++)
            /* exclude i extent from product in this dimension */
            if(i != j) {
                REALTYPE j_extent =    rc->bound[j+DIMS_NUMB] - rc->bound[j];
                face_area *= j_extent;
            }
            sum += face_area;
    }
    return 2 * sum;
}

/**
 * Combine two rectangles, make one that includes both.
 */
RTREEMBR RTreeCombineRect( RTREEMBR *rc1, RTREEMBR *rc2 )
{
    int i, j;
    RTREEMBR new_rect;

    assert(rc1 && rc2);

    if (INVALID_RECT(rc1))
        return *rc2;

    if (INVALID_RECT(rc2))
        return *rc1;

    for (i = 0; i < DIMS_NUMB; i++)
    {
        new_rect.bound[i] = MIN(rc1->bound[i], rc2->bound[i]);
        j = i + DIMS_NUMB;
        new_rect.bound[j] = MAX(rc1->bound[j], rc2->bound[j]);
    }
    return new_rect;
}


/**
 * Decide whether two rectangles overlap.
 */
int RTreeOverlap( RTREEMBR *rc1, RTREEMBR *rc2)
{
    int i, j;
    assert(rc1 && rc2);

    for (i=0; i<DIMS_NUMB; i++)
    {
        j = i + DIMS_NUMB;  /* index for high sides */

        if (rc1->bound[i] > rc2->bound[j] || rc2->bound[i] > rc1->bound[j])
            return FALSE;
    }
    return TRUE;
}


/**
 * Decide whether rectangle r is contained in rectangle s.
 */
int RTreeContained( RTREEMBR *r, RTREEMBR *s)
{
    int i, j, result;
    assert(r && s);

    /* undefined mbr is contained in any other */
    if (INVALID_RECT(r))
        return TRUE;

    /* no mbr (except an undefined one) is contained in an undef mbr */
    if (INVALID_RECT(s))
        return FALSE;

    result = TRUE;
    for (i = 0; i < DIMS_NUMB; i++)
    {
        j = i + DIMS_NUMB;  /* index for high sides */
        result = result    && r->bound[i] >= s->bound[i] && r->bound[j] <= s->bound[j];
    }
    return result;
}

/**
 * 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)
{
    RTREEPARTITION *p;
    int level;

    assert(node && br);

    /* load all the branches into a buffer, initialize old node */
    level = node->level;
    _RTreeGetBranches(node, br);

    /* find partition */
    p = &Partitions[0];

    /* Note: can't use MINFILL(n) below since node was cleared by GetBranches() */
    _RTreeMethodZero(p, level>0 ? MINNODEFILL : MINLEAFFILL);

    /* put branches from buffer into 2 nodes according to chosen partition    */
    *new_node = RTreeNewNode();
    (*new_node)->level = node->level = level;
    _RTreeLoadNodes(node, *new_node, p);

    assert(node->count+(*new_node)->count == p->total);
}


/**
 * Initialize a RTREENODE structure.
 */
void RTreeInitNode( RTREENODE *node )
{
    int i;
    node->count = 0;
    node->level = -1;
    for (i = 0; i < MAXCARD; i++)
        _RTreeInitBranch(&(node->branch[i]));
}

/**
 * Make a new node and initialize to have all branch cells empty.
 */
RTREENODE *RTreeNewNode(void)
{
    RTREENODE *node = (RTREENODE*) malloc(sizeof(RTREENODE));
    assert(node);
    RTreeInitNode(node);
    return node;
}

void RTreeFreeNode( RTREENODE *node )
{
    assert(node);
    free(node);
}


/**
 * Print out the data in a node.
 */
void RTreePrintNode( RTREENODE *node, int depth )
{
    int i;
    assert(node);

    _RTreeTabIn(depth);
    fprintf (stdout, "node");

    if (node->level == 0)
        fprintf (stdout, " LEAF");
    else if (node->level > 0)
        fprintf (stdout, " NONLEAF");
    else
        fprintf (stdout, " TYPE=?");

#pragma warning(push)    /* C4311 */
#pragma warning( disable : 4311 )
    fprintf (stdout, "  level=%d  count=%d  address=%o ", node->level, node->count, (unsigned int) node);
#pragma warning(pop)

    for (i=0; i<node->count; i++)
    {
        if(node->level == 0) {
            /* _RTreeTabIn(depth); */
            /* fprintf (stdout, " %d: data = %d ", i, n->branch[i].child); */
        }
        else {
            _RTreeTabIn(depth);
            fprintf (stdout, "branch %d ", i);
            _RTreePrintBranch(&node->branch[i], depth+1);
        }
    }
}

/**
 * Find the smallest rectangle that includes all rectangles in branches of a node.
 */
RTREEMBR RTreeNodeCover( RTREENODE *node )
{
    int i, first_time=1;
    RTREEMBR rc;
    assert(node);

    RTreeInitRect(&rc);

    for (i = 0; i < MAXKIDS(node); i++)
    {
        if (node->branch[i].child)
        {
            if (first_time)
            {
                rc = node->branch[i].mbr;
                first_time = 0;
            }
            else
                rc = RTreeCombineRect(&rc, &(node->branch[i].mbr));
        }
    }
    return rc;
}

/**
 * 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)
{
    RTREEMBR *r;
    int i, first_time = 1;
    REALTYPE increase, bestIncr=(REALTYPE)-1, area, bestArea=0;
    int best=0;
    RTREEMBR tmp_rect;
    assert(rc && node);

    for (i=0; i<MAXKIDS(node); i++)
    {
        if (node->branch[i].child)
        {
            r = &node->branch[i].mbr;
            area = RTreeRectSphericalVolume(r);
            tmp_rect = RTreeCombineRect(rc, r);
            increase = RTreeRectSphericalVolume(&tmp_rect) - area;
            if (increase < bestIncr || first_time)
            {
                best = i;
                bestArea = area;
                bestIncr = increase;
                first_time = 0;
            }
            else if (increase == bestIncr && area < bestArea)
            {
                best = i;
                bestArea = area;
                bestIncr = increase;
            }
        }
    }
    return best;
}

/**
 * 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)
{
    int i;
    assert(br && node);

    if (node->count < MAXKIDS(node))  /* split won't be necessary */
    {
        for (i = 0; i < MAXKIDS(node); i++)  /* find empty branch */
        {
            if (node->branch[i].child == NULL)
            {
                node->branch[i] = *br;
                node->count++;
                break;
            }
        }

        return 0;
    }

    assert(new_node);
    RTreeSplitNode(node, br, new_node);

    return 1;
}

/**
 * Disconnect a dependent node.
 */
void RTreeDisconnectBranch( RTREENODE *node, int i )
{
    assert(node && i>=0 && i<MAXKIDS(node));
    assert(node->branch[i].child);

    _RTreeInitBranch(&(node->branch[i]));
    node->count--;
}

/**
 * Destroy (free) node recursively.
 */
void RTreeDestroyNode ( RTREENODE *node )
{
    int i;

    if (node->level > 0)
    {
        /* it is not leaf -> destroy childs */
        for ( i = 0; i < NODECARD; i++)
        {
            if ( node->branch[i].child )
                RTreeDestroyNode ( node->branch[i].child );
        }
    }

    /* Free this node */
    RTreeFreeNode( node );
}


/**
 * Create a new rtree index, empty. Consists of a single node.
 */
RTREENODE * RTreeCreate(void)
{
    RTREENODE * root = RTreeNewNode();
    root->level = 0; /* leaf */
    return root;
}

/**
 * Destroy a rtree root must be a root of rtree. Free all memory.
 */
void RTreeDestroy(RTREENODE *root)
{
    RTreeDestroyNode (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)
{
    /* Fix not yet tested. */
    int hitCount = 0;
    int i;

    assert(node && rc);
    assert(node->level >= 0);

    if (node->level > 0) /* this is an internal node in the tree */
    {
        for (i=0; i<NODECARD; i++){
            if (node->branch[i].child && RTreeOverlap(rc, &node->branch[i].mbr))
                hitCount += RTreeSearch(node->branch[i].child, rc, pfnSHCB, pfnParam);
        }
    }
    else /* this is a leaf node */
    {
#pragma warning(push)    /* C4311 */
#pragma warning( disable : 4311 )
        for (i=0; i<LEAFCARD; i++)
        {
            if (node->branch[i].child && RTreeOverlap(rc, &node->branch[i].mbr))
            {
                hitCount++;

                /* call the user-provided callback and return if callback wants to terminate search early */
                if(pfnSHCB && ! pfnSHCB((int)node->branch[i].child, pfnParam) )
                    return hitCount;

            }
        }
#pragma warning(pop)
    }
    return hitCount;
}

/**
 * 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)
{
#ifdef _DEBUG
    int i;
#endif

    RTREENODE    *newroot;
    RTREENODE    *newnode;
    RTREEBRANCH b;

    assert(rc && root);
    assert(level >= 0 && level <= (*root)->level);

#ifdef _DEBUG
    for (i=0; i<DIMS_NUMB; i++)
        assert(rc->bound[i] <= rc->bound[DIMS_NUMB+i]);
#endif

    /* root split */
    if (_RTreeInsertRect(rc, tid, *root, &newnode, level))
    {
        newroot = RTreeNewNode();  /* grow a new root, & tree taller */
        newroot->level = (*root)->level + 1;
        b.mbr = RTreeNodeCover(*root);
        b.child = *root;
        RTreeAddBranch(&b, newroot, NULL);
        b.mbr = RTreeNodeCover(newnode);
        b.child = newnode;
        RTreeAddBranch(&b, newroot, NULL);
        *root = newroot;

        return 1;
    }

    return 0;
}


/**
 * 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)
{
    int        i;
    RTREENODE        *tmp_nptr = NULL;
    RTREELISTNODE    *reInsertList = NULL;
    RTREELISTNODE    *e;

    assert(rc && root);
    assert(*root);
    assert(tid >= 0);

    if (!_RTreeDeleteRect(rc, tid, *root, &reInsertList))
    {
        /* found and deleted a data item */

        /* reinsert any branches from eliminated nodes */
        while (reInsertList)
        {
            tmp_nptr = reInsertList->node;

#pragma warning(push)    /* C4311 */
#pragma warning( disable : 4311 )
            for (i = 0; i < MAXKIDS(tmp_nptr); i++)
            {
                if (tmp_nptr->branch[i].child)
                {
                    RTreeInsertRect(&(tmp_nptr->branch[i].mbr), (int)tmp_nptr->branch[i].child, root, tmp_nptr->level);
                }
            }
#pragma warning(pop)

            e = reInsertList;
            reInsertList = reInsertList->next;
            RTreeFreeNode(e->node);
            _RTreeFreeListNode(e);
        }

        /* check for redundant root (not leaf, 1 child) and eliminate */
        if ((*root)->count == 1 && (*root)->level > 0)
        {
            for (i = 0; i < NODECARD; i++)
            {
                tmp_nptr = (*root)->branch[i].child;
                if(tmp_nptr)
                    break;
            }
            assert(tmp_nptr);
            RTreeFreeNode(*root);
            *root = tmp_nptr;
        }

        return 0;
    }

    return 1;
}

测试文件test.c:

/**
    rtree lib usage example app.
 */
#include <stdio.h>
#include "rtree.h"

RTREEMBR rects[] = {
    { {0, 0, 0, 2, 2, 0} },  /* xmin, ymin, zmin, xmax, ymax, zmax (for 3 dimensional RTree) */
    { {5, 5, 0, 7, 7, 0} },
    { {8, 5, 0, 9, 6, 0} },
    { {7, 1, 0, 9, 2, 0} }
};


int nrects = sizeof(rects) / sizeof(rects[0]);
RTREEMBR search_rect = {
    {6, 4, 0, 10, 6, 0}   /* search will find above rects that this one overlaps */
};

int MySearchCallback(int id, void* arg)
{
    /* Note: -1 to make up for the +1 when data was inserted */
    fprintf (stdout, "Hit data mbr %d ", id-1);
    return 1; /* keep going */
}

int main()
{
    RTREENODE* root = RTreeCreate();

    int i, nhits;

    fprintf (stdout, "nrects = %d ", nrects);

    /* Insert all the testing data rects */
    for(i=0; i<nrects; i++){
        RTreeInsertRect(&rects[i],  /* the mbr being inserted */
                        i+10,        /* i+1 is mbr ID. ID MUST NEVER BE ZERO */
                        &root,        /* the address of rtree's root since root can change undernieth*/
                        0            /* always zero which means to add from the root */
                    );
    }

    nhits = RTreeSearch(root, &search_rect, MySearchCallback, 0);

    fprintf (stdout, "Search resulted in %d hits ", nhits);

    RTreeDestroy (root);

    return 0;
}

使用VS2005,新建一个Console项目test,选为空项目。然后把这3个文件加入进来,就可以使用了。必要的话,把RTree.h和RTree.C建立成连接库,就更方便了。


2011-07-01 18:28
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

用C语言描述数据结构

汉诺塔的C语言实现以及冒泡排序

点在多边形内算法的C语言实现

约瑟夫环问题求解算法C语言源代码

linux下的c语言的随机数算法代码