amr3t.cpp

Go to the documentation of this file.

/*
**
** File: martree.cpp
**
** Author: Mauricio Riguette Mediano
**
** Date: 28/03/1997
**
*/

#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>

#include "amr3t.h"

// -------------------------------------------
void PFS3Box::Dup(PFS3Box *B)
{
  Xmin = B->Xmin;
  Ymin = B->Ymin;
  Zmin = B->Zmin;
  Xmax = B->Xmax;
  Ymax = B->Ymax;
  Zmax = B->Zmax;
}
// -------------------------------------------
int PFS3Box::Equal(PFS3Box *B) 
{
  return( Xmin==B->Xmin&&Ymin==Ymin&&Zmin==Zmin&& 
          Xmax==B->Xmax&&Ymax==Ymax&&Zmax==Zmax);
}
// -------------------------------------------
int PFS3Box::Disjoint(PFS3Box *B) 
{
  if( Xmax<B->Xmin||Xmin>B->Xmax|| 
      Ymax<B->Ymin||Ymin>B->Ymax|| 
      Zmax<B->Zmin||Zmin>B->Zmax)
    return(1);
  return(0);
}
// -------------------------------------------
double PFS3Box::Volume() 
{
  return((Xmax-Xmin)*(Ymax-Ymin)*(Zmax-Zmin));
}
// -------------------------------------------
void PFS3Box::ExtendVolume(PFS3Box *B)
{
  Xmin = MIN(Xmin,B->Xmin);
  Ymin = MIN(Ymin,B->Ymin);
  Zmin = MIN(Zmin,B->Zmin);
  Xmax = MAX(Xmax,B->Xmax);
  Ymax = MAX(Ymax,B->Ymax);
  Zmax = MAX(Zmax,B->Zmax);
}
// --------------------------------------------------------
PFS3NodeBoxId::PFS3NodeBoxId(int Pmin, int Pmax) 
{ 
  if(Pmin>Pmax) exit(1);
  Min = Pmin;
  Max = Pmax;
  Num=0;
  Vet = new PFS3BoxId[Max+1];
  if(Vet==NULL) exit(1);
}
// --------------------------------------------------------
PFS3NodeBoxId::~PFS3NodeBoxId()
{
  delete[] Vet;
}
// --------------------------------------------------------
void PFS3NodeBoxId::Dup(PFS3NodeBoxId* Fromn)
{
  int i;
  Num=Fromn->Num;
  Max=Fromn->Max;
  Min=Fromn->Min;
  if (Vet!=NULL) delete[] Vet;
  if (Fromn->Vet==NULL) {
    Vet=NULL;
    return;
  };
  Vet = new PFS3BoxId[Max+1];
  if(Vet==NULL) exit(1);
  for(i=0;i<Num;i++)
    Vet[i]=Fromn->Vet[i];
};
// --------------------------------------------------------
void PFS3NodeBoxId::BBox(PFS3Box *B)
{
  if (Num==0) exit(1);
  *B = Vet[0];
  for(int cont=1;cont<Num;cont++)
    B->ExtendVolume(&Vet[cont]);
};
// --------------------------------------------------------
void PFS3NodeBoxId::MakeBoxId(PFS3BoxId *E)
{
  BBox(E);
  E->P=this;
}
// --------------------------------------------------------
void PFS3NodeBoxId::GetPos(PFS3BoxId *E,int i)
{
  if (Vet==NULL) exit(1);
  if (i > Num) exit(1);
  *E = Vet[i];
};
// --------------------------------------------------------
void PFS3NodeBoxId::PutPos(PFS3BoxId *E,int i)
{
  if(Vet==NULL) exit(1);
  if(i > Num) exit(1);
  Vet[i]=*E;
};
// --------------------------------------------------------
void PFS3NodeBoxId::Insert(PFS3BoxId *E,int Posit)
{
  if(Vet==NULL) exit(1);
  if(Posit>Num) exit(1);
  for(int cont=Num;cont>Posit;cont--)
    Vet[cont]=Vet[cont-1];
  Num++;
  Vet[Posit]=*E;
};
// --------------------------------------------------------
void PFS3NodeBoxId::Append(PFS3BoxId *E)
{
  if(Num > Max) exit(1);
  PutPos(E,Num);
  Num++;
};
// --------------------------------------------------------
void PFS3NodeBoxId::Remove(int i)
{
  if (Vet==NULL) exit(1);
  if (i > Num) exit(1);
  Num--;
  for(int cont=i;cont<Num;cont++)
    Vet[cont]=Vet[cont+1];
};
// --------------------------------------------------------
void PFS3NodeBoxId::Remove(PFS3BoxId *E,int Cont)
{
  GetPos(E,Cont);
  Remove(Cont);
};
// --------------------------------------------------------
void PFS3NodeBoxId::Remove(PFS3BoxId *E)
{
  GetPos(E,Num-1);
  Num--;
}
// --------------------------------------------------------
void PFS3NodeBoxId::ChooseBoxId(PFS3BoxId *Loc,PFS3BoxId *Out,int *Posit)
{
  PFS3BoxId eaux;
  double smallerarea,areabefore;

  if (Num==0) exit(1);
  *Posit=0;
  GetPos(&eaux,*Posit);
  *Out = eaux;
  areabefore = eaux.Volume()+Loc->Volume();
  eaux.ExtendVolume(Loc);
  smallerarea = eaux.Volume() - areabefore;
  for(int cont=1;cont<Number();cont++) {
    GetPos(&eaux,cont);
    areabefore = eaux.Volume()+Loc->Volume();
    eaux.ExtendVolume(Loc);
    if(eaux.Volume() - areabefore < smallerarea) {
      GetPos(Out,cont);
      *Posit = cont;
      smallerarea = eaux.Volume() - areabefore;
    }
  }
}
// --------------------------------------------------------
void PFS3NodeBoxId::UpdateBox(PFS3Box *B,int Posit)
{
  PFS3BoxId E;
  GetPos(&E,Posit);
  E.Dup(B);
  PutPos(&E,Posit);
}
// --------------------------------------------------------
int PFS3NodeBoxId::LocateBoxId(PFS3BoxId *In,int *Posit)
{
  for(int cont=0;cont<Number();cont++)
    if(Vet[cont].P==In->P) {
      *Posit=cont;
      return(0);
    }
  return(1);
}
// --------------------------------------------------------
void PFS3NodeBoxId::SplitNodeR3tree(PFS3NodeBoxId *Newnode)
{
  PFS3NodeBoxId auxnode(Min,Max);
  double extraarea;
  double areabefore;
  int imax, jmax;
  int i, j;
  PFS3BoxId ei, ej;
  PFS3BoxId eiaux,ejaux;

  imax=0;       //Inicializa entradas
  jmax=1;
  GetPos(&eiaux, 0); 
  GetPos(&ejaux, 1);
  areabefore = eiaux.Volume() + ejaux.Volume();
  eiaux.ExtendVolume(&ejaux);
  extraarea = eiaux.Volume() - areabefore;

  for(i=0;i<Number();i++) {  // Escolhe entradas iniciais.
    for(j=i+1;j<Number();j++) {
      GetPos(&eiaux, i);
      GetPos(&ejaux, j);
      areabefore = eiaux.Volume() + ejaux.Volume();
      eiaux.ExtendVolume(&ejaux);
      if(eiaux.Volume() - areabefore > extraarea) {
        imax = i;
        jmax = j;
        extraarea = eiaux.Volume() - areabefore;
      };
    } /* endfor */
  } /* endfor */

  if(imax>jmax) {
    Remove(&ei, imax);
    Remove(&ej, jmax);
  } else {
    Remove(&ej, jmax);
    Remove(&ei, imax);
  }

  while(Number()>0) {  // Move entradas para no' auxiliar.
    PFS3BoxId E;
    Remove(&E);
    auxnode.Append(&E);
  } /* endfor */

  Append(&ei);
  Newnode->Append(&ej);
  for(i=0;i<Min-1;i++) {  // Insere minimo por no'.
    PFS3BoxId E;
    int choose;
    auxnode.ChooseBoxId(&ei,&E,&choose);
    auxnode.Remove(&E, choose);
    ei.ExtendVolume(&E);
    Append(&E);
    auxnode.ChooseBoxId(&ej,&E,&choose);
    auxnode.Remove(&E, choose);
    ej.ExtendVolume(&E);
    Newnode->Append(&E);
  } /* endfor */

  GetPos(&ei,0);
  Newnode->GetPos(&ej,0);
  while(auxnode.Number()>0) {
    PFS3BoxId E;
    PFS3Box biaux,bjaux;
    auxnode.Remove(&E);
    biaux = ei;
    biaux.ExtendVolume(&E);
    bjaux = ej;
    bjaux.ExtendVolume(&E);
    if(biaux.Volume()-ei.Volume()<
       bjaux.Volume()-ej.Volume()){
      Append(&E);
      ei.ExtendVolume(&E);
    } else {
      Newnode->Append(&E);
      ej.ExtendVolume(&E);
    }
  } /* endfor */
}
// --------------------------------------------------------
PFS3Rtree::PFS3Rtree(int Nmin,int Nmax)
{
  Min=Nmin;
  Max=Nmax;
}
// --------------------------------------------------------
PFS3Rtree::~PFS3Rtree()
{
}
// --------------------------------------------------------
void PFS3Rtree::MergeRoot()
{
  PFS3BoxId enode;
  Root->GetPos(&enode,0);
  delete Root;
  Root=(PFS3NodeBoxId *)enode.P;
}
// --------------------------------------------------------
void PFS3Rtree::BBox(PFS3Box *B)
{
  Root->BBox(B);
}
// --------------------------------------------------------
int PFS3Rtree::Remove(PFS3BoxId *newentry)
{
  if (Remove(Root,newentry,Level)==2) return(2);
  if (Level>0 && Root->Number()==1){
    MergeRoot();
    Level--;
  }
  return(0);
};
// --------------------------------------------------------
int PFS3Rtree::Remove(PFS3NodeBoxId *Node,PFS3BoxId *In,int Lev)
{
  int posit;
  if (Lev==0) {
    if(Node->LocateBoxId(In,&posit)==0) {
      Node->Remove(posit);
      return(0);
    };
  } else {
    PFS3BoxId eson;
    PFS3NodeBoxId *son;
    for(posit=0;posit<Node->Number();posit++) {
      Node->GetPos(&eson,posit);
      if (In->Disjoint(&eson))
        continue;
      son=(PFS3NodeBoxId *)eson.P;
      if(Remove(son,In,Lev-1)==2) {
        continue;
      } else if(son->Number()<Min) {
        Merge(Node,son,posit);
      } else {
        son->MakeBoxId(&eson);
        Node->PutPos(&eson,posit);
      };
      return(0);
    }
  };
  return(2);
}
// --------------------------------------------------------
void PFS3Rtree::Insert(PFS3BoxId *newentry)
{
  PFS3BoxId out;
  if(Insert(Root,newentry,&out,Level)==2) {
    PFS3BoxId oldentry;
    PFS3NodeBoxId *newroot= new PFS3NodeBoxId(Min,Max);
    if (newroot==NULL) exit(1);
    Root->MakeBoxId(&oldentry);
    newroot->Append(&oldentry);
    newroot->Append(&out);
    Root=newroot;
    Level++;
  } /* endif */
}
// --------------------------------------------------------
void PFS3Rtree::SplitNodeR3tree(PFS3NodeBoxId *Node, PFS3BoxId *Out)
{
  PFS3NodeBoxId *newnode= new PFS3NodeBoxId(Min,Max);
  if (newnode==NULL) exit(1);
  Node->SplitNodeR3tree(newnode);
  newnode->MakeBoxId(Out);
};
// --------------------------------------------------------
int PFS3Rtree::Insert(PFS3NodeBoxId *Node,PFS3BoxId *In,PFS3BoxId *Out,int Lev)
{
  if (Lev==0) {
    Node->Append(In);
    if (Node->Number() > Max) {
      SplitNodeR3tree(Node,Out);
      return(2);
    }
  } else {
    int status,posit;
    PFS3BoxId eson;
    PFS3NodeBoxId *son;
    Node->ChooseBoxId(In,&eson,&posit);
    son=(PFS3NodeBoxId *)eson.P;
    status = Insert(son,In,Out,Lev-1);
    son->MakeBoxId(&eson);
    Node->PutPos(&eson,posit);
    if (status==2) {
      Node->Append(Out);
      if(Node->Number() > Max) {
        SplitNodeR3tree(Node,Out);
        return(2);
      }
    }
  }
  return(0);
}
// --------------------------------------------------------
void PFS3Rtree::Merge(PFS3NodeBoxId *Father,PFS3NodeBoxId *Node,short Posit)
{

//
// Alterar para procurar o no' mais proximo para 
// fazer o merge.
//

  int i;
  PFS3BoxId auxentry;
  PFS3NodeBoxId *auxnode;
  PFS3BoxId eaux;
  short auxposit;
  if(Posit + 1 < Father->Number()) auxposit = Posit + 1;
  else if(Posit > 0) auxposit = Posit - 1;
  Father->GetPos(&auxentry,auxposit);
  auxnode=(PFS3NodeBoxId *)auxentry.P;
  if(auxnode->Number() + Node->Number() <= Max) {
    for(i=0;i<Node->Number();i++) {
      Node->GetPos(&eaux,i);
      auxnode->Append(&eaux);
    }
    auxnode->MakeBoxId(&auxentry);
    Father->PutPos(&auxentry,auxposit);
    delete(Node);
    Father->Remove(Posit);
  } else {
    while(Node->Number() < Min) {
      auxnode->Remove(&eaux);
      Node->Append(&eaux);
    }
    auxnode->MakeBoxId(&auxentry);
    Father->PutPos(&auxentry,auxposit);
    Node->MakeBoxId(&auxentry);
    Father->PutPos(&auxentry,Posit);
  }
}
// --------------------------------------------------------
void PFS3Rtree::Create()
{
  Root=new PFS3NodeBoxId(Min,Max);
  if (Root==NULL) exit(1);
  Level=0;
}
// --------------------------------------------------------
void PFS3Rtree::Delete()
{
  if (Level>0)
    Delete(Root,Level);
  delete (Root);
};
// --------------------------------------------------------
void PFS3Rtree::Delete(PFS3NodeBoxId *Node,int Lev)
{
  if (Lev>0) {
    PFS3BoxId e;
    PFS3NodeBoxId *naux;
    while(Node->Number()>0) {
      Node->Remove(&e);
      naux=(PFS3NodeBoxId *)e.P;
      Delete(naux,Lev-1);
      delete(naux);
    }
  }
}
// --------------------------------------------------------
int PFS3Rtree::Number()
{
  int num=0;
  Number(Root,&num,Level);
  return(num);
};
// --------------------------------------------------------
void PFS3Rtree::Number(PFS3NodeBoxId *Node,int *Num,int Lev)
{
  PFS3BoxId e;
  if (Lev==0) { 
    *Num += Node->Number();
  } else {
    PFS3NodeBoxId *naux;
    while(Node->Number()>0) {
      Node->Remove(&e);
      naux=(PFS3NodeBoxId *)e.P;
      Number(naux,Num,Lev-1);
    }
  }
}
// --------------------------------------------------------
void PFS3Rtree::Print()
{
  int num=0;
  Print(Root,0,&num,Level);
  printf("Numero de elementos %d\n", num);
}
// --------------------------------------------------------
void PFS3Rtree::Print( PFS3NodeBoxId *Node, int ident, int *Num, int Lev)
{
  PFS3BoxId e;
  int i,j;
  PFS3Box* vet;
  vet = new PFS3Box[Max];
  if(vet==NULL) exit(1);
  for( i=0;i<ident;i++) {    
    printf( " ");
  }
  printf( "No #%d ->\n", Node->Number());
  for( i=0;i<Node->Number();i++) { 
    Node->GetPos(& e, i);
    e.Dup(&vet[i]);
    for( j=0;j<ident+2;j++) {    
      printf( " ");
    }
    printf("#%d %g %g %g %g %g %g\n",i, vet[i].Xmin, vet[i].Ymin, vet[i].Zmin,
                                        vet[i].Xmax, vet[i].Ymax, vet[i].Zmax);
  }
  if (Lev==0) {
    *Num+=Node->Number();
  } else {
    PFS3NodeBoxId *naux;
    for( i=0;i<Node->Number();i++) { 
      PFS3Box B;
      Node->GetPos(& e, i);
      naux=(PFS3NodeBoxId *)e.P;
      naux->BBox(&B);
      if(!B.Equal(&vet[i])) printf( "\nErro Box\n");
      Print(naux, ident+2, Num, Lev -1);
    }
  }
  delete[] vet;
}
// --------------------------------------------------------
void PFS3Rtree::Search(PFS3Box *B)
{
  Vnode[0]=Root;
  Vpos[0]=0;
  NumL=0;
  SearchVal=*B;
};
// --------------------------------------------------------
int PFS3Rtree::Result(PFS3BoxId *B)
{
  PFS3BoxId currkey;
  for(;;) {
    for (;Vpos[NumL]<Vnode[NumL]->Number();Vpos[NumL]++) {
      Vnode[NumL]->GetPos(&currkey,Vpos[NumL]);
      if (!currkey.Disjoint(&SearchVal))
          break;
    }
    if (Vpos[NumL]==Vnode[NumL]->Number()) {
      NumL--;
      if (NumL<0) break;
      else Vpos[NumL]++;
    } else {
      Vnode[NumL]->GetPos(&currkey,Vpos[NumL]);
      if (NumL==Level) break;
      NumL++;
      Vnode[NumL]=(PFS3NodeBoxId *)currkey.P;
      Vpos[NumL]=0;
    }
  }
  if (NumL==-1) return(1);
  *B=currkey;
  Vpos[NumL]++;
  return(0);
};
// --------------------------------------------------------
void PFS3Rtree::SearchAll()
{
  Vnode[0]=Root;
  Vpos[0]=0;
  NumL=0;
};
// --------------------------------------------------------
int PFS3Rtree::ResultAll(PFS3BoxId *B)
{
  PFS3BoxId currkey;
  for(;;) {
    Vnode[NumL]->GetPos(&currkey,Vpos[NumL]);
    if (Vpos[NumL]==Vnode[NumL]->Number()) {
      NumL--;
      if (NumL<0) break;
      else Vpos[NumL]++;
    } else {
      Vnode[NumL]->GetPos(&currkey,Vpos[NumL]);
      if (NumL==Level) break;
      NumL++;
      Vnode[NumL]=(PFS3NodeBoxId *)currkey.P;
      Vpos[NumL]=0;
    };
  };
  if (NumL==-1) return(1);
  *B=currkey;
  Vpos[NumL]++;
  return(0);
};
// --------------------------------------------------------

---