x_tree.cc

X-tree的C++源码

#include <math.h>


#ifdef S3
#include "s3.h"
#else
#include "x_tree.h"
#endif

#define CHECK_MBR

//////////////////////////////////////////////////////////////////////////////
// globals
//////////////////////////////////////////////////////////////////////////////
int XTDirNode__dimension;
void* XTDirNode__my_tree;
int XTDataNode__dimension;


//////////////////////////////////////////////////////////////////////////////
// C-functions
//////////////////////////////////////////////////////////////////////////////
float area(int dimension, float *mbr)
// berechnet Flaeche (Volumen) eines mbr der Dimension dimension
{
    int i;
    float sum;

    sum = 1.0;
    for (i = 0; i < dimension; i++)
	sum *= mbr[2*i+1] - mbr[2*i];

    return sum;
}

float margin(int dimension, float *mbr)
// berechnet Umfang eines mbr der Dimension dimension
{
    int i;
    float *ml, *mu, *m_last, sum;

    sum = 0.0;
    m_last = mbr + 2*dimension;
    ml = mbr;
    mu = ml + 1;
    while (mu < m_last)
    {
	sum += *mu - *ml;
	ml += 2;
	mu += 2;
    }

    return sum;
}

bool inside(float &p, float &lb, float &ub)
// ist ein Skalar in einem Intervall ?
{
    return (p >= lb && p <= ub);
}

bool inside(float *v, float *mbr, int dimension)
// ist ein Vektor in einer Box ?
{
    int i;

    for (i = 0; i < dimension; i++)
	if (!inside(v[i], mbr[2*i], mbr[2*i+1]))
	    return FALSE;

    return TRUE;
}


float overlap (int dim, float *q1, float *q2) {
   
   // Bestimmt den Schnittquader
   // zwischen q1 und q2
   
   float sum = 1.0;
   
   for (int i = 0; i < dim; i++) {
      sum *= min(q1[2*i+1],q2[2*i+1]) - max(q1[2*i],q2[2*i]);
      if (sum <= 0) {
	 sum = 0;
	 break;
      }
   }
   return sum;
}

/*
float overlap(int dimension, float *r1, float *r2)
// calcutales the overlapping area of r1 and r2
// calculate overlap in every dimension and multiplicate the values
{
    float sum;
    float *r1pos, *r2pos, *r1last, r1_lb, r1_ub, r2_lb, r2_ub;

    sum = 1.0;
    r1pos = r1; r2pos = r2;
    r1last = r1 + 2 * dimension;

    while (r1pos < r1last)
    {
	r1_lb = *(r1pos++);
	r1_ub = *(r1pos++);
	r2_lb = *(r2pos++);
	r2_ub = *(r2pos++);

        // calculate overlap in this dimension

        if (inside(r1_ub, r2_lb, r2_ub))
        // upper bound of r1 is inside r2 
	{
            if (inside(r1_lb, r2_lb, r2_ub))
            // and lower bound of r1 is inside
                sum *= (r1_ub - r1_lb);
            else
                sum *= (r1_ub - r2_lb);
	}
	else
	{
            if (inside(r1_lb, r2_lb, r2_ub))
	    // and lower bound of r1 is inside
		sum *= (r2_ub - r1_lb);
	    else 
	    {
		if (inside(r2_lb, r1_lb, r1_ub) &&
		    inside(r2_ub, r1_lb, r1_ub))
	        // r1 contains r2
		    sum *= (r2_ub - r2_lb);
		else
		// r1 and r2 do not overlap
		    sum = 0.0;
	    }
	}
    }

    return sum;
}
*/
 
void enlarge(int dimension, float **mbr, float *r1, float *r2)
// enlarge r in a way that it contains s
{
    int i;

    *mbr = new float[2*dimension];
    for (i = 0; i < 2*dimension; i += 2)
    {
	(*mbr)[i]   = min(r1[i],   r2[i]);

	(*mbr)[i+1] = max(r1[i+1], r2[i+1]);
    }
#ifdef CHECK_MBR
    check_mbr(dimension,*mbr);
#endif
}

bool section(int dimension, float *mbr1, float *mbr2)
{
    int i;

    for (i = 0; i < dimension; i++)
    {
	if (mbr1[2*i]     > mbr2[2*i + 1] ||
	    mbr1[2*i + 1] < mbr2[2*i]) 
	    return FALSE;
    }
    return TRUE;
}

bool section_c(int dimension, float *mbr1, const void *center, float radius)
{
	float r2;

	r2 = radius * radius;

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

int sort_lower_mbr(const void *d1, const void *d2)
// Vergleichsfunktion fuer qsort, sortiert nach unterem Wert der mbr bzgl.
// der angegebenen Dimension
{
    SortMbr *s1, *s2;
    float erg;
    int dimension;

    s1 = (SortMbr *) d1;
    s2 = (SortMbr *) d2;
    dimension = s1->dimension;
    erg = s1->mbr[2*dimension] - s2->mbr[2*dimension];
    if (erg < 0.0)
	return -1;
    else if (erg == 0.0)
	return 0;
    else 
	return 1;
}

int sort_upper_mbr(const void *d1, const void *d2)
// Vergleichsfunktion fuer qsort, sortiert nach oberem Wert der mbr bzgl.
// der angegebenen Dimension
{
    SortMbr *s1, *s2;
    float erg;
    int dimension;

    s1 = (SortMbr *) d1;
    s2 = (SortMbr *) d2;
    dimension = s1->dimension;
    erg = s1->mbr[2*dimension+1] - s2->mbr[2*dimension+1];
    if (erg < 0.0)
	return -1;
    else if (erg == 0.0)
	return 0;
    else 
	return 1;
}

int sort_center_mbr(const void *d1, const void *d2)
// Vergleichsfunktion fuer qsort, sortiert nach center of mbr 
{
    SortMbr *s1, *s2;
    int i, dimension;
    float d, e1, e2;

    s1 = (SortMbr *) d1;
    s2 = (SortMbr *) d2;
    dimension = s1->dimension;

    e1 = e2 = 0.0;
    for (i = 0; i < dimension; i++)
    {
        d = ((s1->mbr[2*i] + s1->mbr[2*i+1]) / 2.0) - s1->center[i];
        e1 += d*d;
        d = ((s2->mbr[2*i] + s2->mbr[2*i+1]) / 2.0) - s2->center[i];
        e2 += d*d;
    }

    if (e1 < e2)
	return -1;
    else if (e1 == e2)
	return 0;
    else 
	return 1;
}


float OBJECT_DIST(const void  *Point1, const void  *Point2)
{

    //
    // Berechnet das Quadrat der euklid'schen Metrik.
    // (Der tatsaechliche Abstand ist uninteressant, weil
    // die anderen Metriken (MINDIST und MINMAXDIST fuer
    // die NearestNarborQuery nur relativ nie absolut 
    // gebraucht werden; nur Aussagen "<" oder ">" sind
    // relevant.
    //

    DataStruct *d1,*d2;
    float summe = 0;
    int i;
    
    d1 = (DataStruct *) Point1;
    d2 = (DataStruct *) Point2;

    for( i = 0; i < d1->dimension; i++)
	summe += pow(    d1->Data[i] - d2->Data[i], 2 );

    //return( sqrt(summe) );
    return(summe);
}

float MINDIST(const void *Point, float *bounces)
{
    //
    // Berechne die kuerzeste Entfernung zwischen einem Punkt Point
    // und einem MBR bounces (Lotrecht!)
    //

    DataStruct *p;
    float summe = 0.0;
    float r;
    int i;

    p = (DataStruct *) Point;

    
    for(i = 0; i < p->dimension; i++)
    {
	if (p->Data[i] < bounces[2*i])
	    r = bounces[2*i];
	else
	{
	    if (p->Data[i] > bounces[2*i +1])
		r = bounces[2*i+1];
	    else 
		r = p->Data[i];
	}    

	summe += pow( p->Data[i] - r , 2);
    }
    return(summe);
    
}

float MINMAXDIST(const void *Point, float *bounces)
{

    // Berechne den kleinsten maximalen Abstand von einem Punkt Point
    // zu einem MBR bounces.
    // Wird benutzt zur Abschaetzung von Abstaenden bei NearestNarborQuery.
    // Kann als Supremum fuer die aktuell kuerzeste Distanz: 
    // Alle Punkte mit einem Abstand > MINMAXDIST sind keine Kandidaten mehr
    // fuer den NearestNarbor
    // vgl. Literatur: 
    // Nearest Narbor Query v. Roussopoulos, Kelley und Vincent, 
    // University of Maryland
    
    DataStruct *p;
    
    float summe = 0;
    float minimum = 1.0e20;
    float S = 0;

    float rmk, rMi;
    int k,i,j;

    p = (DataStruct *) Point;

    

    for( i = 0; i < p->dimension; i++) 
    { 
	rMi = (	p->Data[i] >= (bounces[2*i]+bounces[2*i+1])/2 )
	    ? bounces[2*i] : bounces[2*i+1];
	S += pow( p->Data[i] - rMi , 2 );
    }

    for( k = 0; k < p->dimension; k++)
    {  
	
	rmk = ( p->Data[k] <=  (bounces[2*k]+bounces[2*k+1]) / 2 ) ? 
	    bounces[2*k] : bounces[2*k+1];

	summe = pow( p->Data[k] - rmk , 2 );	
	
	rMi = (	p->Data[k] >= (bounces[2*k]+bounces[2*k+1]) / 2 )
	    ? bounces[2*k] : bounces[2*k+1];

	summe += S - pow( p->Data[k] - rMi , 2 );
	
	minimum = min( minimum,summe);
    }

    return(minimum);
    

}




int sort_min_dist(const void *element1, const void *element2)
{
    //
    // Vergleichsfunktion fuer die Sortierung der BranchList bei der
    // NearestNarborQuery (Sort, Branch and Prune)
    //

    BranchList *e1,*e2;

    e1 = (BranchList *) element1;
    e2 = (BranchList *) element2;
    
    if (e1->mindist < e2->mindist) 
	return(-1);
    else if (e1->mindist > e2->mindist)
	return(1);
    else
	return(0);

}


int prune_branch_list(float *nearest_distanz, const void *activebrunchList, 
		    int n)
{

    // Schneidet im Array BranchList alle Eintraege ab, deren Distanz groesser
    // ist als die aktuell naeheste Distanz
    //

    BranchList *bl; 
    
    int i,j,k, aktlast;
    
    bl = (BranchList *) activebrunchList;
    
    // 1. Strategie:
    // 
    // Ist MINDIST(P,M1) > MINMAXDIST(P,M2), so kann der 
    // NearestNeighbor auf keinen Fall mehr in M1 liegen!
    //


    aktlast = n;
    

    for( i = 0; i < aktlast ; i++ )
    {
	if (bl[i].minmaxdist < bl[aktlast-1].mindist)
	    for( j = 0; (j < aktlast) ; j++ )
		if ((i!=j) && (bl[j].mindist>bl[i].minmaxdist))
		{
		    aktlast = j;
		    break;
		}
	
    }

    

    // 2. Strategie:
    //
    // nearest_distanz > MINMAXDIST(P,M)
    // -> nearest_distanz = MIMMAXDIST(P,M)
    //


    for( i = 0; i < aktlast; i++)
	if (*nearest_distanz > bl[i].minmaxdist)
	    *nearest_distanz = bl[i].minmaxdist;

    
    // 3. Strategie:
    // 
    // nearest_distanz < MINDIST(P,M)
    //
    // in M kann der Nearest-Narbor sicher nicht mehr liegen.
    //

    for( i = 0; (i < aktlast) && (*nearest_distanz >= bl[i].mindist) ; i++);
    
    aktlast = i;

    // printf("n: %d aktlast: %d \n",n,aktlast);   

    return (aktlast);


    
}


int testBrunchList(const void *abL, const void *sL,
		   int n, int last)
{

    // Schneidet im Array BranchList alle Eintr"age ab, deren Distanz gr"o"ser
	// ist als die aktuell naeheste Distanz
	//

	BranchList *activebrunchList, *sectionList; 
	
	int i,number, aktlast;
	
	activebrunchList = (BranchList *) abL;
	sectionList      = (BranchList *) sL;

	aktlast = last; 

	for(i = last; i < n ; i++)
	{
	    number = activebrunchList[i].entry_number;  
	    if (sectionList[number].section)
	    {
		// obwohl vom Abstand her dieser Eintrag gecanceld werden
		// m"usste, wird hier der Eintrag in die ABL wieder
		    // aufgenommen, da evtl. ein Treffer der range-Query zu erwarten ist!
		    //
		    // An der letzten Stelle der Liste kommt der aktuelle Eintrag!
		    aktlast++;
		    activebrunchList[aktlast].entry_number = activebrunchList[i].entry_number;
		    activebrunchList[aktlast].mindist = activebrunchList[i].mindist;
		    activebrunchList[aktlast].minmaxdist = activebrunchList[i].minmaxdist;		     }      	 
	    
	}
	
	return (aktlast);

    }


void check_mbr(int dimension, float *mbr)
{
}