rtnode.cpp

此文件包含了在linux下实现tpr-tree索引的源代码

   if (Settings.GetTreeType() == RTsettings::tTPRtree && Settings.IsCTUnionMode()) 
      u->Sett1(CT);   

   u->Sett2(TPR_TS_INF);

   for (i = min; i < max; i++)
   {
      RTe = (RTentry*) (*this)[ix[i]].Ptr();

      if (Settings.GetTreeType() == RTsettings::tRtree) 
      {
         for (j = 0; j < to; j++)
         {
            c = RTe->Coordtp_br(j, 0, RTe->RefTS());
            if (first || c < u->Coord(j, 0)) u->SetCoord(c, j, 0);
            c = RTe->Coordtp_br(j, 0, RTe->t2()); 
            if (c < u->Coord(j, 0)) u->SetCoord(c, j, 0);
            c = RTe->Coordtp_br(j, 1, RTe->RefTS());
            if (first || c > u->Coord(j, 1)) u->SetCoord(c, j, 1);
            c = RTe->Coordtp_br(j, 1, RTe->t2());
            if (c > u->Coord(j, 1)) u->SetCoord(c, j, 1);
         }
         if (first || RTe->RefTS() < u->RefTS()) u->Sett1(RTe->RefTS());
         if (first || RTe->t2()    > u->t2())    u->Sett2(RTe->t2());
      }
      else if (Settings.GetTreeType() != RTsettings::tTPRtree || 
               Settings.GetUnionMode() == RTsettings::unInsRefT)         
         for (j = 0; j < to; j++)
         {
            if (first || RTe->Coord(j, 0) < u->Coord(j, 0))
               u->SetCoord(RTe->Coord(j, 0), j, 0);
            if (first || RTe->Coord(j, 1) > u->Coord(j, 1))
               u->SetCoord(RTe->Coord(j, 1), j, 1);
         }   
      else
         for (j = 0; j < Settings.GetDims(); j++)
         {
            c = RTe->CoordT_br(j, 0); 
            if (first || c < u->Coord(j, 0)) u->SetCoord(c, j, 0);
            c = RTe->CoordT_br(j, 1);
            if (first || c > u->Coord(j, 1)) u->SetCoord(c, j, 1);
            if (first || RTe->Speed(j, 0) < u->Speed(j, 0))
               u->SetSpeed(RTe->Speed(j, 0), j, 0);
            if (first || RTe->Speed(j, 1) > u->Speed(j, 1))
               u->SetSpeed(RTe->Speed(j, 1), j, 1);
         }
      first = false;
   }

   if (Settings.GetTreeType() != RTsettings::tTPRtree)   // static bounding rectangles
      for (j = 0; j < Settings.GetDims(); j++)
      {
         u->SetSpeed(0.0, j, 0);    
         u->SetSpeed(0.0, j, 1);
      }
   else 
      if (Settings.IsCTUnionMode()) u->SetRefTS_br(refts);

   return u;
}

//----------------------------------------------------
void RTnode::HeaderFromString(const char* buf)
{
   SetLevel(((short*) buf)[0]);
   SetNumEntries(((short*) buf)[1]);
//   memcpy(&refts, buf + 2*sizeof(short), sizeof(refts));
   refts = ((RT*) Tree())->GetRefTS(); 
}

//----------------------------------------------------
void RTnode::HeaderToString  (char* buf) const  
{
   ((short*) buf)[0] = (short) Level();
   ((short*) buf)[1] = (short) NumEntries();
//   memcpy(buf + 2*sizeof(short), &refts, sizeof(refts));
}

//----------------------------------------------------
void RTnode::RstarSplit(RTindexArray& group1, RTindexArray& group2)
{
   // The R*-tree split algorithm (time-parameterized) 

   int i, j, ifrom, ito, splitindex;
   int chosen_axis = 0, chosen_axis2 = 0;         // for observer
   int candidates, to = Settings.GetTreeType() == RTsettings::tTPRtree ? 
                        Settings.GetDims()*4 : Settings.GetDims()*2;
   edgeix *lvec, *hvec;

   double sumAxis, sumMin = -1.0;
   double minxtion, minarea, tmpxtion, tmparea;
   int    m = (int)((double)NumEntries()*Tree()->m() + 0.5);
   RTentry     *tmpe1, *tmpe2;
   RTentry     *tmpentry;
   RTindexArray* theArray, *theArray1, *theArray2;
   RTindexArray* candidateArrays[TPR_MAX_DIMS*4 + 2];

   lvec = new edgeix[NumEntries()];
   hvec = new edgeix[NumEntries()];

   for (candidates = 0; candidates < to; candidates++)
   {
      if (Settings.GetTreeType() == RTsettings::tTPRtree && 
          candidates < Settings.GetDims()*2 && Settings.IsCTUnionMode())
         for (i = 0; i < NumEntries(); i++)
         {
            tmpentry = (RTentry*)((*this)[i].Ptr());
            lvec[i].ix   = i;
            lvec[i].edge = tmpentry->CoordT(candidates / 2, 0);
            hvec[i].ix   = i;
            hvec[i].edge = tmpentry->CoordT(candidates / 2, 1);
         }
      else 
         for (i = 0; i < NumEntries(); i++)
         {
            tmpentry = (RTentry*)((*this)[i].Ptr());
            lvec[i].ix   = i;
            lvec[i].edge = tmpentry->Coord(candidates / 2, 0);
            hvec[i].ix   = i;
            hvec[i].edge = tmpentry->Coord(candidates / 2, 1);
         }

      qsort(lvec, NumEntries(), sizeof(edgeix), RTcmp);
      qsort(hvec, NumEntries(), sizeof(edgeix), RTcmp);

      candidateArrays[candidates] = new RTindexArray(NumEntries());
      for (i = 0; i < NumEntries(); i++)
         (*candidateArrays[candidates])[i] = lvec[i].ix;
      candidateArrays[++candidates] = new RTindexArray(NumEntries());
      for (i = 0; i < NumEntries(); i++)
         (*candidateArrays[candidates])[i] = hvec[i].ix;
   }

   if (Settings.GetTreeType() == RTsettings::tRtree)
   { 
      for (i = 0; i < NumEntries(); i++)
      {
         tmpentry = (RTentry*)((*this)[i].Ptr());
         lvec[i].ix   = i;
         lvec[i].edge = tmpentry->RefTS();
         hvec[i].ix   = i;
         hvec[i].edge = tmpentry->t2();
      }

      qsort(lvec, NumEntries(), sizeof(edgeix), RTcmp);
      qsort(hvec, NumEntries(), sizeof(edgeix), RTcmp);

      candidateArrays[candidates] = new RTindexArray(NumEntries());
      for (i = 0; i < NumEntries(); i++)
         (*candidateArrays[candidates])[i] = lvec[i].ix;
      candidateArrays[++candidates] = new RTindexArray(NumEntries());
      for (i = 0; i < NumEntries(); i++)
         (*candidateArrays[candidates])[i] = hvec[i].ix;  
      candidates++;   
   }

   // ChooseSplitAxis:
   // sort entries by xl, by xh
   // by yl, by yh, etc.
   // for distributions of each axis, compute S, the sum of the
   // margin-value (margin[bb(first-group)] + margin[bb(second-group)]).
   // Axis with min S is the split axis.
   for (j = 0; j < candidates; j += 2)
   {
      for(sumAxis = 0, i = m; i <= NumEntries() - m; i++)
      {
         // compute bounding boxes of 0 to (i-1), i to (NumEntries()-1)
         // inclusively; take sum of margins
         tmpentry = UnionEntries(*candidateArrays[j], 0, i);
         sumAxis += tmpentry->bbox().margin_n1(((RT*) Tree())->GetParam());
         delete tmpentry;
         tmpentry = UnionEntries(*candidateArrays[j], i, NumEntries());
         sumAxis += tmpentry->bbox().margin_n1(((RT*) Tree())->GetParam());
         delete tmpentry;
         tmpentry = UnionEntries(*candidateArrays[j+1], 0, i);
         sumAxis += tmpentry->bbox().margin_n1(((RT*) Tree())->GetParam());
         delete tmpentry;
         tmpentry = UnionEntries(*candidateArrays[j+1], i, NumEntries());
         sumAxis += tmpentry->bbox().margin_n1(((RT*) Tree())->GetParam());
         delete tmpentry;
      }
      if (sumMin == -1.0 || sumAxis < sumMin)
      {
         sumMin = sumAxis;
         chosen_axis = j;
         theArray1   = candidateArrays[j];
         theArray2   = candidateArrays[j+1];
      }
   }
   for (j = 0; j < candidates; j++)
      if (candidateArrays[j] != theArray1 &&
          candidateArrays[j] != theArray2)
             delete candidateArrays[j];
   candidateArrays[0] = theArray1;
   candidateArrays[1] = theArray2;
   candidates = 2;

   delete lvec;
   delete hvec;

   // ChooseSplitIndex:
   // Compute minimum overlap-value
   // for each distribution (area[bb(first) intersect bb(second)]).
   // Along the chosen split axis, choose the distribution with the
   // minimum overlap-value. Resolve ties by choosing the distribution with
   // minimum area-value.

   theArray     = candidateArrays[0];

   for (int j = 0; j < candidates; j++)
   {
      // The following two loops are neccessary to avoid producing underfull nodes,
      // when entries have varying lengths 
      ifrom = m;
      ito   = NumEntries() - m;
      while (IsUnderFull(*Tree()->Store(), candidateArrays[j]->GetArrayPointer(), ifrom))
         ifrom++;
      if (ifrom > ito) ito = ifrom;
      while (IsUnderFull(*Tree()->Store(), 
                         candidateArrays[j]->GetArrayPointer() + ito, NumEntries() - ito))
         ito--;
      if (ito < ifrom) ifrom = ito;
      for(i = ifrom; i <= ito; i++)
      {
         tmpe1    = UnionEntries(*candidateArrays[j], 0, i);
         tmpe2    = UnionEntries(*candidateArrays[j], i, NumEntries());
         tmpxtion = Settings.GetSplitAlg() == RTsettings::saNoOverlap  ? 0 :
                    tmpe1->bbox().intersectArea_n1(tmpe2->bbox(), 
                                                   ((RT*) Tree())->GetParam());
         tmparea  = tmpe1->bbox().area_n1(((RT*) Tree())->GetParam()) +
                    tmpe2->bbox().area_n1(((RT*) Tree())->GetParam());
         if (i == ifrom && !j)
         {
            splitindex  = ifrom;
            minxtion    = tmpxtion;
            minarea     = tmparea;
         }
         else if (tmpxtion < minxtion ||
                  tmpxtion == minxtion && tmparea < minarea)
              {
                 minxtion   = tmpxtion;
                 minarea    = tmparea;
                 splitindex = i;
                 theArray   = candidateArrays[j];
                 chosen_axis2 = chosen_axis + j;
              }
         delete tmpe1;
         delete tmpe2;
      }
   }

   for (i = 0; i < splitindex; i++)
      group1.Add((*theArray)[i]);
   for (i = splitindex; i < NumEntries(); i++)
      group2.Add((*theArray)[i]);

   if (Tree()->Observer())
      ((RTobserver*)Tree()->Observer())->Inform(ON_SOFT_SPLIT,
                                                chosen_axis2, splitindex);

   for (j = 0; j < candidates; j++) delete candidateArrays[j];
}