tvrectangle.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: rectangle.C,v 1.2 1996/04/18 21:50:24 kilin Exp kilin $ 
#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 "TVutil.h"

TVRectangle::TVRectangle()
{
}

TVRectangle::TVRectangle(const TVector &v, float r, int d) 
{
   int dim = v.GetDim();
   nonsig = v.ProjectFront(dim - d);
   lower = v.ProjectBack(d) - r;
   upper = v.ProjectBack(d) + r;
} 

// TVRectangle with lower, upper corners with sigdim given 
// sigdim = 0 --> Maximum non-sigdim, sig dim possible
TVRectangle::TVRectangle(const TVector& low, const TVector& high, int sigdim)
{
   int dim = min(low.GetDim(), high.GetDim());
   int firstdiff = low.FirstDiffDim(high);

   if (firstdiff == -1)
      {
	nonsig = low;
      }
   else
      {
	sigdim = (sigdim > 0 ? min(sigdim, dim - firstdiff) : dim - firstdiff);
	nonsig = low.ProjectFront(firstdiff);
  	lower = low.ProjectMid(firstdiff, sigdim);
  	upper = high.ProjectMid(firstdiff, sigdim);
      }
}


// TVRectangle with non-sig portion and sig low/high corners
TVRectangle::TVRectangle(const TVector& nsig, const TVector &low, const TVector& high)
{
  nonsig = nsig;
  if (low.GetDim() != high.GetDim())
     { 
        int d1 = min(low.GetDim(), high.GetDim());
	lower = low.ProjectFront(d1);
	upper = high.ProjectFront(d1);
     }
  else
     { 
	lower = low;
	upper = high;
     }
}

TVRectangle::TVRectangle(const TVRectangle& rec)
{
   nonsig = rec.nonsig;
   lower = rec.lower;
   upper = rec.upper;
}



TVRectangle::~TVRectangle()
{
}

TVRectangle&  TVRectangle::operator=(const TVRectangle &rec)
{
   nonsig = rec.nonsig;
   lower = rec.lower;
   upper = rec.upper;
  return *this;
}

TVector TVRectangle::GetCenter() const
{
  return (nonsig  << ((lower + upper) / 2));
}

float TVRectangle::GetRadius() const
{
  return (upper - lower).MaxComponent();
}

int TVRectangle::GetSigDim() const
{
  return lower.GetDim();
}

int TVRectangle::GetNonSigDim() const
{
  return nonsig.GetDim();
}

int TVRectangle::GetCenterDim() const
{
  return nonsig.GetDim() + lower.GetDim();
}


TVector TVRectangle::GetSigCenter() const
{
  return (lower + upper) / 2;
}

TVector TVRectangle::GetNonSigCenter() const
{
  return nonsig;
}


int TVRectangle::Size() const
{
   return  nonsig.Size() + lower.Size() + upper.Size();
}


TVRectangle& TVRectangle::PutNonSig(const TVector& v)
{
  nonsig = v;
  return *this;
}
   
TVRectangle& TVRectangle::PutSig(const TVector& l, const TVector& h)
{
  lower = l;
  upper = h;
  return *this;
}

TVRectangle& TVRectangle::Put(const TVector& ns, const TVector& l, const TVector& h)
{
  nonsig = ns;
  lower = l;
  upper = h;
  return *this;
}

TVRectangle& TVRectangle::AppendSig(const TVector& l, const TVector& h)
{
  assert (l.GetDim() == h.GetDim());

  lower <<= l;
  upper <<= h;

  return *this;
}


TVRectangle TVRectangle::ProjectSigTVRectangle() const
{
  TVRectangle res;

  res.PutSig(lower, upper);

  return(res);
}

TVRectangle TVRectangle::ProjectFront(int dim) const
{
  assert(dim <= GetCenterDim());
  TVRectangle res;
  int sig = dim - nonsig.GetDim();

  if (sig <= 0)
     res.PutNonSig(nonsig.ProjectFront(dim));
  else
     res.Put(nonsig, lower.ProjectFront(sig), upper.ProjectFront(sig));

/*
cout << " res  : " << res;
cout << (dim - GetNonSigDim() > 0 ? dim - GetNonSigDim() : SIG_DIM) << '\n';
*/
  return(res);
}

TVRectangle TVRectangle::ProjectMid(int start, int dim) const
{
  assert(start + dim <= GetCenterDim());
  TVRectangle res;
  int sig = dim + start - nonsig.GetDim();
  
  if (sig <= 0)
     res.PutNonSig(nonsig.ProjectMid(start, dim));
  else
     res.Put(nonsig.ProjectBack(nonsig.GetDim() - start + 1), lower.ProjectFront(sig), upper.ProjectFront(sig));
  
  return(res);
}

TVRectangle TVRectangle::ProjectBack(int dim) const
{
  assert(dim <= GetCenterDim());
  TVRectangle res;
  int nonsigdim = dim - lower.GetDim();

  if (dim < 0)
     res.PutSig(lower.ProjectBack(dim), upper.ProjectBack(dim));
  else 
     res.Put(nonsig.ProjectBack(nonsigdim), lower, upper);
  

  return(res);
}

TVector TVRectangle::ProjectFrontLow(int dim) const
{
   if (dim <= nonsig.GetDim())
     return nonsig.ProjectFront(dim);

   if (!nonsig.GetDim())
     return lower.ProjectFront(dim);

   return nonsig << lower.ProjectFront(dim - nonsig.GetDim());
}

TVector TVRectangle::ProjectFrontHigh(int dim) const
{
   if (dim <= nonsig.GetDim())
     return nonsig.ProjectFront(dim);

   if (!nonsig.GetDim())
     return lower.ProjectFront(dim);

   return nonsig << upper.ProjectFront(dim - nonsig.GetDim());
}

TVector TVRectangle::ProjectMidLow(int start, int dim) const
{
   if (start + dim <= nonsig.GetDim())  
     return nonsig.ProjectMid(start, dim);

   if (!nonsig.GetDim())
       return lower.ProjectMid(start, dim);

   return nonsig.ProjectBack(GetNonSigDim() - start) << lower.ProjectFront(dim - GetNonSigDim() + start);
}

TVector TVRectangle::ProjectMidHigh(int start, int dim) const
{
   if (start + dim <= nonsig.GetDim())  
     return nonsig.ProjectMid(start, dim);

   if (!nonsig.GetDim())
       return upper.ProjectMid(start, dim);

   return nonsig.ProjectBack(GetNonSigDim() - start) << upper.ProjectFront(dim - GetNonSigDim() + start);
}



int TVRectangle::Contain(const TVector& v) const
{
   int result = FALSE;
   
   if (v.GetDim() >= GetCenterDim())
      {
	  if (GetNonSigDim())
             result = (v.ProjectFront(GetNonSigDim()) == nonsig) &&  
		      (v.ProjectMid(GetNonSigDim(), GetSigDim()).Inrange(lower, upper));
          else
	     result = (v.ProjectFront(GetSigDim()).Inrange(lower, upper));
      }
   return result;
}

int TVRectangle::Contain(const TVRectangle &d) const
{
   int part1 = TRUE, part2 = TRUE, part3 = TRUE;

   if ((d.GetCenterDim() < GetCenterDim()) || (d.GetNonSigDim() < GetNonSigDim()))
      return FALSE;	// Inner rectangle must have more dimensions pinned down
			// Both in sig. and total dimensions
   else
      {
       //    Algorithm
       //
       //	     in  : |---------------------------|-----------------|
	//		         non-sig  |            |    sig
	//				  |            |
	//			          |            |
	//	     out : |--------------|---------------------|
	//		        non-sig                    sig
	//		       (1)           (2)         (3)

         // Check part (1)
	 if (GetNonSigDim())
	    part1 = (nonsig == d.nonsig.ProjectFront(GetNonSigDim()));

         // Check part (2)

	 int surplus_nonsigdim = min(d.GetNonSigDim() - GetNonSigDim(), GetSigDim());
         if (surplus_nonsigdim)
	    part2 = d.nonsig.ProjectMid(GetNonSigDim(), surplus_nonsigdim).Inrange(lower.ProjectFront(surplus_nonsigdim), upper.ProjectFront(surplus_nonsigdim));

         // Check part (3)

	 int part3dim = GetCenterDim() - d.GetNonSigDim();
         if (part3dim > 0)
	    {
	        TVector dlower = d.lower.ProjectFront(part3dim);
	        TVector dupper = d.upper.ProjectFront(part3dim);

 		TVector vlower = lower.ProjectMid(surplus_nonsigdim, part3dim);
 		TVector vupper = upper.ProjectMid(surplus_nonsigdim, part3dim);

                part3 = dlower.Inrange(vlower, vupper) && dupper.Inrange(vlower, vupper);
            }
        }

    return part1 && part2 && part3;
}

int TVRectangle::Intersect(const TVRectangle& d) const
{
   TVRectangle d1, d2;

   // ensure d1 has the shorter non-sigdim
   if (GetNonSigDim() < d.GetNonSigDim())
      {
	 d1 = *this;
	 d2 = d;
      }
   else
      {
	 d2 = *this;
	 d1 = d;
      }

   int part1 = TRUE, part2 = TRUE, part3 = TRUE;

   // Check part (1)
   if (d1.GetNonSigDim())
      part1 = (d1.nonsig == d2.nonsig.ProjectFront(d1.GetNonSigDim()));

   // Check part (2)

   int surplus_nonsigdim = min(d2.GetNonSigDim() - d1.GetNonSigDim(), d1.GetSigDim());
   if (surplus_nonsigdim)
      part2 = d2.nonsig.ProjectMid(d1.GetNonSigDim(), surplus_nonsigdim).Inrange(d1.lower.ProjectFront(surplus_nonsigdim), d1.upper.ProjectFront(surplus_nonsigdim));


   // Check part 3
   int restdim = min(d2.GetSigDim(), d1.GetSigDim() - surplus_nonsigdim);
   int restdimstart =  surplus_nonsigdim;
   if (restdim > 0)
      {
	int i = 0;
        for (; (i < restdim) && intersect((d1.lower)[restdimstart + i], 
                                          (d1.upper)[restdimstart + i], 
                                          (d2.lower)[i], 
                                          (d2.upper)[i]); i++)
            ;

        part3 = (i == restdim);
      }

// cout << *this << " Intersect " << d << " : " << (part1 && part2 && part3 ? "TRUE" : "FALSE") << endl;
   return part1 && part2 && part3;


}

int TVRectangle::NoIntersectDim(const TVRectangle& rect) const
{
   TVRectangle d1, d2;
   int result = 0;
   int curdim;

   // ensure d1 has the shorter non-sigdim
   if (GetNonSigDim() < rect.GetNonSigDim())
      {
	 d1 = *this;
	 d2 = rect;
      }
   else
      {
	 d2 = *this;
	 d1 = rect;
      }

   int shortnonsig = d1.GetNonSigDim(), longnonsig = d2.GetNonSigDim();
   for (curdim = 0; curdim < shortnonsig; curdim++)
      {
         result += (d1.nonsig[curdim] != d2.nonsig[curdim]);
      }

   for (; curdim < longnonsig; curdim++)
      result += ((d2.nonsig[curdim] < d1.lower[curdim - shortnonsig]) ||
		 (d2.nonsig[curdim] > d1.upper[curdim - shortnonsig]));

   int mdim = min(d1.GetCenterDim(), d2.GetCenterDim());
   for (; curdim < mdim; curdim++)
      result += !intersect(d1.lower[curdim - shortnonsig], d1.upper[curdim - shortnonsig],
			   d2.lower[curdim - longnonsig], d2.upper[curdim - longnonsig]);

   return result;
}

// Assume all parts are significiant
void NewSigRect(TVector &lower, TVector& upper, const TVector& oldlower, const TVector& oldupper, const TVector& v, int sigdim = 0)
{
   int dim = (sigdim ? min(oldlower.GetDim(), sigdim) : oldlower.GetDim());

   lower = oldlower.ProjectFront(dim).MinCompo(v.ProjectFront(dim));
   upper = oldupper.ProjectFront(dim).MaxCompo(v.ProjectFront(dim));

}


TVRectangle TVRectangle::InsertTVector(const TVector& v, int result_sig_dim)
{
  TVRectangle result;
  
  if (!Contain(v))