tvpickbranch.c

TV-tree的c实现源码

/* 
 
                  COPYRIGHT NOTICE
 
This material was developed by Christos Faloutsos and King-Ip Lin
at the University of Maryland, College Park, Department of Computer Science.
Permission is granted to copy this software, to redistribute it
on a nonprofit basis, and to use it for any purpose, subject to
the following restrictions and understandings.
 
1. Any copy made of this software must include this copyright notice
in full.
 
2. All materials developed as a consequence of the use of this
software shall duly acknowledge such use, in accordance with the usual
standards of acknowledging credit in academic research.
 
3. The authors have made no warranty or representation that the
operation of this software will be error-free or suitable for any
application, and they are under under no obligation to provide any
services, by way of maintenance, update, or otherwise.  The software
is an experimental prototype offered on an as-is basis.
 
4. Redistribution for profit requires the express, written permission
of the authors.
 
*/

// Author : $Author$
// Date : $Date$
// Id : $Id$
// $Id: pickbranch.C,v 1.2 1996/04/18 21:50:24 kilin Exp kilin $ 
// Please change sig_dim to active_dim

#include <iostream.h>
#include <assert.h>
#include <stdlib.h>
#include <fstream.h>
#include "TVdefine.h"
#include "TVconstants.h"
#include "TVvector.h"
#include "TVrectangle.h"
//#include "TVrectangle.h"
#include "TVelement.h"
#include "TVsimbuf.h"
#include "TVnode.h"
#include "TVutil.h"

PickTVBranchCompare::PickTVBranchCompare()
{
  contained = FALSE;
  increase = 0.0;
  dim = 0;
  unfold_dim = 0;
  dist_from_center = 0.0;
  intersect_count = 0;
}

// Smaller is better
int PickTVBranchCompare::operator<(const PickTVBranchCompare&  pbc) const
{
   int result = FALSE;

   if (contained && !pbc.contained)
      result = TRUE;
   else
     {
     if (!contained && pbc.contained)
        result = FALSE;
     else
	{
	     if (intersect_count < pbc.intersect_count) 
		result = TRUE;
	     else 
		{
		  if (intersect_count == pbc.intersect_count)
		     {
		       if (unfold_dim > pbc.unfold_dim)  
			  result = TRUE;
		       else
			  {
			     if (unfold_dim == pbc.unfold_dim)  
			       {
				  if (increase < pbc.increase)
				     result = TRUE;
				  else
				     {
					if ((increase < pbc.increase + PRECISION) && (dist_from_center < pbc.dist_from_center))
					   result = TRUE;
				     }

			       }
			  }
		     }
		  
		}
        }
     }
   return result;
}

int PickTVBranchCompare::operator==(const PickTVBranchCompare&  pbc) const
{
   return (contained == pbc.contained) && 
           (increase == pbc.increase) &&
	  (dim == pbc.dim) &&
	  (unfold_dim == pbc.unfold_dim) &&
	  (dist_from_center == pbc.dist_from_center) &&
	  (intersect_count == pbc.intersect_count);
}

PickTVBranchCompare Internal_TVNode::PickTVBranchCal(Leaf_Element& le, int ent, VCOM_TYPE (*gfeat)(int, char *), int checkintersectcount, int sig_dim)
{
   PickTVBranchCompare res;

   TVRectangle d = entry[ent].GetBound();
   TVector v = le.GetTVector(d.GetCenterDim(), gfeat);
   TVRectangle d1; // the new rectangle formed by adding d0 to d
  
   res.contained = d.Contain(v);
   res.increase =  (d1 =  d.InsertTVector(v, sig_dim)).GetRadius() - d.GetRadius();
   res.dim = d1.GetCenterDim();
   res.unfold_dim = res.dim - d.GetCenter().GetDim();
   int rdim = min(v.GetDim(), res.dim);
   res.dist_from_center = v.ProjectFront(rdim).Distance(d1.GetCenter().ProjectFront(rdim));

   // calculate the intersection count
   int lowstart, highend;
   if (ent < checkintersectcount / 2)
      {
	 lowstart = 0;
	 highend = checkintersectcount;

      }
   else
      if ((count - ent - 1) < checkintersectcount - checkintersectcount / 2)
      {
	 lowstart = count - checkintersectcount - 1;
	 highend = count - 1;
      }
      else
      {
	 lowstart = ent - checkintersectcount/2;
	 highend = ent + checkintersectcount - checkintersectcount / 2;
      }

   int k;
   for (k = lowstart; k < ent; k++)
       {
	  if ( (d1.Intersect(entry[k].GetBound())) && (!(d.Intersect(entry[k].GetBound()))
) )
	      res.intersect_count++;
       }
   for (k = ent+1; k <= highend; k++)
       {
	  if ( (d1.Intersect(entry[k].GetBound())) && (!(d.Intersect(entry[k].GetBound()))
) )
	      res.intersect_count++;
       }
  return res;

}


int Internal_TVNode::PickTVBranch(Leaf_Element& d0,  VCOM_TYPE (*gfeat)(int, char*), int pbcc, int sig_dim)
{

/*
cout <<"\n-----------\n";
cout << "Element : " << d0.GetTVector() << endl;
cout << *this << endl;
*/

   int checkintersectcount = min(pbcc, count - 1);   // number of intersections to count

   PickTVBranchCompare curbest = PickTVBranchCal(d0, 0, gfeat, checkintersectcount, sig_dim);

   int min_index = 0;
 
   // Check for the rest of the branches 

   for (int i = 1; i < count; i++)
     {
	   PickTVBranchCompare cur = PickTVBranchCal(d0, i, gfeat, checkintersectcount, sig_dim);

           // Compare and see if new branch the best 

           if (cur < curbest)
              {
		 curbest = cur;
                 min_index = i;
              }
     }

// cout << "Picked : " << min_index << endl;

  return(min_index);
}

PickTVBranchCompare Internal_TVNode::PickTVBranchCal(const TVRectangle& d0, int ent, int checkintersectcount, int sig_dim)
{
   PickTVBranchCompare res;

   TVRectangle d = entry[ent].GetBound();
   TVRectangle d1; // the new rectangle formed by adding d0 to d
   res.increase =  (d1 =  d.Combine(d0, sig_dim)).GetRadius() - d.GetRadius();
   res.dim = d1.GetCenterDim();
   res.unfold_dim = res.dim - d.GetCenter().GetDim();
   int rdim = min(d0.GetCenterDim(), res.dim);
   res.dist_from_center = d0.GetCenter().ProjectFront(rdim).Distance(d1.GetCenter().ProjectFront(rdim));

   // calculate the intersection count
   int lowstart, highend;
   if (ent < checkintersectcount / 2)
      {
	 lowstart = 0;
	 highend = checkintersectcount;

      }
   else
      if ((count - ent - 1) < checkintersectcount - checkintersectcount / 2)
      {
	 lowstart = count - checkintersectcount - 1;
	 highend = count - 1;
      }
      else
      {
	 lowstart = ent - checkintersectcount/2;
	 highend = ent + checkintersectcount - checkintersectcount / 2;
      }

   int k;
   for (k = lowstart; k < ent; k++)
       {
	  if ( (d1.Intersect(entry[k].GetBound())) && (!(d.Intersect(entry[k].GetBound()))
) )
	      res.intersect_count++;
       }
   for (k = ent+1; k <= highend; k++)
       {
	  if ( (d1.Intersect(entry[k].GetBound())) && (!(d.Intersect(entry[k].GetBound()))
) )
	      res.intersect_count++;
       }
  return res;

}


int Internal_TVNode::PickTVBranch(const TVRectangle& d0, int pbcc, int sig_dim)
{
   int checkintersectcount = min(count-1, pbcc);   // number of intersections to count

   PickTVBranchCompare curbest = PickTVBranchCal(d0, 0, checkintersectcount, sig_dim);

   int min_index = 0;
 
   // Check for the rest of the branches 

   for (int i = 1; i < count; i++)
     {
	   PickTVBranchCompare cur = PickTVBranchCal(d0, i, checkintersectcount, sig_dim);

           // Compare and see if new branch the best 

           if (cur < curbest)
              {
		 curbest = cur;
                 min_index = i;
              }
     }

  return(min_index);
}