#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){}