RTree源代码——C语言实现（下）

RTree源代码——C语言实现（下）2010-10-29 csdn 张亮
/*=============================================================================
                                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;
}