x_tree.h

X-tree的C++源码

	if (v[i] < bounces[2*i] ||     // untere Grenze
	    v[i] > bounces[2*i + 1])   // obere Grenze
	    return FALSE;
    }

    return TRUE;
}

template <class DATA> 
SECTION DirEntry<DATA>::section(float *mbr)
// testet, ob mbr den Eintrag irgendwo ueberlappt
// Uberlappung kann nur dann nicht auf, wenn 
//
//    ttttt eeeee
//
//      oder
//
//    eeeee ttttt
//
// diese beiden Faelle werden fuer jede Dimension getestet
{
    bool inside;
    bool overlap;
    int i;

    overlap = TRUE;
    inside = TRUE;
    for (i = 0; i < dimension; i++)
    {
	if (mbr[2*i]     > bounces[2*i + 1] ||
	    mbr[2*i + 1] < bounces[2*i]) 
	    overlap = FALSE;
	if (mbr[2*i]     < bounces[2*i] ||
	    mbr[2*i + 1] > bounces[2*i + 1]) 
	    inside = FALSE;
    }
    if (inside)
	return INSIDE;
    else if (overlap)
	return OVERLAP;
    else
	return S_NONE;
}


template <class DATA> 
void DirEntry<DATA>::read_from_buffer(char *buffer)
{
    int i;

    i = 2*dimension*sizeof(float);
    memcpy(bounces, buffer, i);
    memcpy(&son, &buffer[i], sizeof(int));
    i += sizeof(int);
    memcpy(&num_of_data, &buffer[i], sizeof(int));
    i += sizeof(int);
    memcpy(&history, &buffer[i], sizeof(int));
}

template <class DATA> 
void DirEntry<DATA>::write_to_buffer(char *buffer)
{
    int i;

    i = 2*dimension*sizeof(float);
    memcpy(buffer, bounces, i);
    memcpy(&buffer[i], &son, sizeof(int));
    i += sizeof(int);
    memcpy(&buffer[i], &num_of_data, sizeof(int));
    i += sizeof(int);
    memcpy(&buffer[i], &history, sizeof(int));
}

template <class DATA> 
int DirEntry<DATA>::get_size()
{
    return 2*dimension * sizeof(float) + sizeof(int) + sizeof(int) + sizeof(int);
}

template <class DATA> 
XTNode<DATA>* DirEntry<DATA>::get_son()
{


    if (son_ptr == NULL)
    {
	if (son_is_data)
	    son_ptr = new XTDataNode<DATA>(my_tree, son);
	else
	    son_ptr = new XTDirNode<DATA>(my_tree, son);
    }
    return son_ptr;
}

template <class DATA>
bool DirEntry<DATA>::section_circle(DATA *center, float radius)
{
 float r2;

 r2 = radius * radius;

 if ( (r2 - MINDIST(center,bounces )) < 1.0e-8)
	return TRUE;
 else
	return FALSE;
}
 

//////////////////////////////////////////////////////////////////////////////
// XTNode
//////////////////////////////////////////////////////////////////////////////

template <class DATA> 
XTNode<DATA>::~XTNode()
{
}

template <class DATA> 
XTNode<DATA>::XTNode(XTree<DATA> *rt)
{
    my_tree = rt; 
    dimension = rt->dimension; 
    num_entries = 0; 

    block = -1;
}


template <class DATA> 
int XTNode<DATA>::topological_split(float **mbr, int **distribution, int *dim)
// teilt ein Array von mbrs in zwei Haelften und liefert in distribution
// zurueck, welche *m Eintraege in die neue Seite verschoben werden muessen
// hierfuer wird der R*-Baum Split Algorithmus benutzt
{
#ifdef SHOWMBR
	split_000++;
#endif

    bool lu;
    int i, j, k, l, s, n, m1, dist, split_axis;
    SortMbr *sml, *smu;
    float minmarg, marg, minover, mindead, dead, over, 
	*rxmbr, *rymbr;

    // how many nodes are used?
    n = get_num();

    // nodes have to be filled at least 40%
    m1 = (int) ((float)n * 0.40); 

    // sort by lower value of their rectangles
    // Indexarray aufbauen und initialisieren
    sml = new SortMbr[n];    
    smu = new SortMbr[n];    
    rxmbr = new float[2*dimension];
    rymbr = new float[2*dimension];

    // choose split axis
    minmarg = MAXREAL;
    for (i = 0; i < dimension; i++)
    // for each axis
    {
        for (j = 0; j < n; j++)
        {
            sml[j].index = smu[j].index = j;
            sml[j].dimension = smu[j].dimension = i;
            sml[j].mbr = smu[j].mbr = mbr[j];
        }

        // Sort by lower and upper value perpendicular axis_i
      	qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);
        qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);

        marg = 0.0;
        // for all possible distributions of sml
        for (k = 0; k < n - 2*m1 + 1; k++)
        {
            // now calculate margin of R1
	    // initialize mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =    MAXREAL;
		rxmbr[s+1] = -MAXREAL;
	    }
            for (l = 0; l < m1+k; l++)
            {
                // calculate mbr of R1 
		for (s = 0; s < 2*dimension; s += 2)
	        {
	            rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);
	            rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);
                }
            }
	    marg += margin(dimension, rxmbr); 

            // now calculate margin of R2
	    // initialize mbr of R2 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =    MAXREAL;
		rxmbr[s+1] = -MAXREAL;
	    }
            for ( ; l < n; l++)
            {
                // calculate mbr of R1 
		for (s = 0; s < 2*dimension; s += 2)
	        {
	            rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);
	            rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);
                }
            }
	    marg += margin(dimension, rxmbr); 
        }

        // for all possible distributions of smu
       	for (k = 0; k < n - 2*m1 + 1; k++)
        {
            // now calculate margin of R1
	    // initialize mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =    MAXREAL;
		rxmbr[s+1] = -MAXREAL;
	    }
            for (l = 0; l < m1+k; l++)
            {
                // calculate mbr of R1 
		for (s = 0; s < 2*dimension; s += 2)
	        {
	            rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);
	            rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);
                }
            }
	    marg += margin(dimension, rxmbr); 

            // now calculate margin of R2
	    // initialize mbr of R2 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =    MAXREAL;
		rxmbr[s+1] = -MAXREAL;
	    }
            for ( ; l < n; l++)
            {
                // calculate mbr of R1 
		for (s = 0; s < 2*dimension; s += 2)
	        {
	            rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);
	            rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);
                }
            }
	    marg += margin(dimension, rxmbr); 
        }

        // actual margin better than optimum?
        if (marg < minmarg)
        {
            split_axis = i;
            minmarg = marg;
        }

    }

    /* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
    *dim = split_axis;

    
    // choose best distribution for split axis
    for (j = 0; j < n; j++)
    {
	sml[j].index = smu[j].index = j;
	sml[j].dimension = smu[j].dimension = split_axis;
	sml[j].mbr = smu[j].mbr = mbr[j];
    }
	       
    // Sort by lower and upper value perpendicular split axis
    qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);
    qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);
    
    minover = MAXREAL;
    mindead = MAXREAL;
    // for all possible distributions of sml and snu
    for (k = 0; k < n - 2*m1 + 1; k++)
    {
        // lower sort
	// now calculate margin of R1
	// initialize mbr of R1 
        dead = 0.0;
	for (s = 0; s < 2*dimension; s += 2)
	{
	    rxmbr[s] =    MAXREAL;
	    rxmbr[s+1] = -MAXREAL;
	}
	for (l = 0; l < m1+k; l++)
	{
	    // calculate mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);
		rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);
	    }
            dead -= area(dimension, sml[l].mbr);
	}
        dead += area(dimension, rxmbr);
	
	// now calculate margin of R2
	// initialize mbr of R2 
	for (s = 0; s < 2*dimension; s += 2)
	{
	    rymbr[s] =    MAXREAL;
       	    rymbr[s+1] = -MAXREAL;
	}
	for ( ; l < n; l++)
	{
	    // calculate mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rymbr[s] =   min(rymbr[s],   sml[l].mbr[s]);
		rymbr[s+1] = max(rymbr[s+1], sml[l].mbr[s+1]);
	    }
            dead -= area(dimension, sml[l].mbr);
	}
        dead += area(dimension, rymbr);
	over = overlap(dimension, rxmbr, rymbr); 

        if ((over < minover) ||
	    (over == minover) && dead < mindead)
        {
            minover = over;
            mindead = dead;
            dist = m1+k;
            lu = TRUE;
        }

        // upper sort
	// now calculate margin of R1
	// initialize mbr of R1 
        dead = 0.0;
	for (s = 0; s < 2*dimension; s += 2)
	{
	    rxmbr[s] =    MAXREAL;
	    rxmbr[s+1] = -MAXREAL;
	}
	for (l = 0; l < m1+k; l++)
	{
	    // calculate mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);
		rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);
	    }
            dead -= area(dimension, smu[l].mbr);
	}
        dead += area(dimension, rxmbr);
	
	// now calculate margin of R2
	// initialize mbr of R2 
	for (s = 0; s < 2*dimension; s += 2)
	{
	    rymbr[s] =    MAXREAL;
	    rymbr[s+1] = -MAXREAL;
	}
	for ( ; l < n; l++)
	{
	    // calculate mbr of R1 
	    for (s = 0; s < 2*dimension; s += 2)
	    {
		rymbr[s] =   min(rymbr[s],   smu[l].mbr[s]);
		rymbr[s+1] = max(rymbr[s+1], smu[l].mbr[s+1]);
	    }
            dead -= area(dimension, smu[l].mbr);
	}
        dead += area(dimension, rxmbr);
	over = overlap(dimension, rxmbr, rymbr); 

        if ((over < minover) ||
	    (over == minover) && dead < mindead)
        {
            minover = over;
            mindead = dead;
            dist = m1+k;
            lu = FALSE;
        }
    }

    // calculate best distribution
    *distribution = new int[n];    
    for (i = 0; i < n; i++)
    {
        if (lu)
            (*distribution)[i] = sml[i].index;
        else
            (*distribution)[i] = smu[i].index;
    }

    delete [] sml;
    delete [] smu;
    delete [] rxmbr;
    delete [] rymbr;


    return dist;
}


template <class DATA> 
int XTNode<DATA>::overlap_free_split(float **mbr, int *split_history, int **distribution, int *dim)
// teilt ein Array von mbrs in zwei Haelften und liefert in distribution
// zurueck, welche *m Eintraege in die neue Seite verschoben werden muessen
// hierfuer wird der X-Baum Split Algorithmus benutzt
{
#ifdef SHOWMBR
	split_000++;
#endif

    bool lu;
    int i, j, k, l, s, n, m1, dist, split_axis;
    int split_vector, num_axis, a;
    int axis[dimension];
    SortMbr *sml, *smu;
    float minmarg, marg, minover, mindead, dead, over, 
	*rxmbr, *rymbr;

    // how many nodes are used?
    n = get_num();

    // check split-history
    split_vector = split_history[0];
    for (i = 1; i < n; i++)
        split_vector = split_vector & split_history[i];

    if (split_vector == 0)
       return 0;


    // nodes have to be filled with at least one entry
    m1 = 1; 

    // sort by lower value of their rectangles
    // Indexarray aufbauen und initialisieren
    sml = new SortMbr[n];    
    smu = new SortMbr[n];    
    rxmbr = new float[2*dimension];
    rymbr = new float[2*dimension];

    
    num_axis = 0;
    for (i = 0; i < dimension; i++)
    {
        if ((split_vector & 1) == 1) {
            axis[num_axis] = i;
            num_axis++;
        }
        split_vector = split_vector >> 1;
    }

    // choose split axis from the above pre-selection
    minmarg = MAXREAL;
    for (a = 0; a < num_axis; a++)
    // for each axis
    {
        i = axis[a];

        for (j = 0; j < n; j++)
        {
            sml[j].index = smu[j].index = j;
            sml[j].dimension = smu[j].dimension = i;
            sml[j].mbr = smu[j].mbr = mbr[j];
        }

        // Sort by lower and upper value perpendicular axis_i
      	qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);
        qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);

        marg = 0.0;
        // for all possible distributions of sml
        for (k = 0; k < n - 2*m1 + 1; k++)
        {
            // now calculate margin of R1