spatialSubdivision.h

Go to the documentation of this file.

/*******************************************************************************
** Copyright (c) 2004 MAK Technologies, Inc.
** All rights reserved.
*******************************************************************************/
/*******************************************************************************
** $RCSfile: spatialSubdivision.h,v $ $Revision: 1.29 $ $State: Exp $
*******************************************************************************/
#ifndef spatialSubdivision_H_
#define spatialSubdivision_H_

#include "geometry/point.h"
#include "geometry/extent.h"

#include <vlutil/vlConfig.h> 
#include <list>
#include <vector>
#include <assert.h>

#include <vlutil/vlPrint.h>

class DtGdbNode;

// class DtSpatialSubdivision:
//
// Instances of DtSpatialSubdivision represent a spatially sorted collection
// of cells, which contain the types specified at creation.  Each cell in the 
// rectangular area (or rectangular solid if 3D) will contain a container of 
// the items referenced in it.
//
// -------------------
// |\        \        \
// | \________\________\
// | |\        \        \
// | | \        \        \
// | |  \--------\--------\
// |\|   |       |        |
// | \   |       |        |
// | |\  |       |        |
// | | \ |       |        |
// | |  \--------\--------\
//  \|   |       |        |
//   \   |       |        |
//    \  |       |        |
//     \ |       |        |
//      \--------\--------\
//       A 2 x 2 x 2 Spatial Subdivision
//
// This class provides a minimal interface to make it easy for users to extend
// the types of elements contained within it by writing examination and modification
// classes outside of this one.  Thus no mechanism for examination or 
// modification, outside of points, is provided.  
// 
// This class is *not* threadsafe.
// 
// \b Class Invariant:
// A fully constructed spatial subdivision must always respect the following:
// - A positive cell size in any dimension where the number of cells is greater 
//   than one. 
// - The number of cells in each dimension must be greater than or equal to 1 at 
//   all times.  The smallest number of cells in any dimension is 1.  If a 
//   subdivision is created or resized with an extent that is either 
//   uninitialized or has an empty dimension, the number of cells in that 
//   dimension is still one, and the cell size will be zero.
// - The same number of cells in the container as equals the dimensions multiplied
//   together.
// 
template <typename T>
class DtSpatialSubdivision
{
public:
   // typedefs for the containers used to hold the contained elements
   typedef std::list<T> DtSpatialSubCellType;
   typedef typename DtSpatialSubCellType::iterator DtSpatialSubCellIter;
   typedef typename DtSpatialSubCellType::const_iterator DtSpatialSubCellConstIter;

   // As this is a 3D grid, cells can be addressed by indices as well.  
   typedef int DtSpatialSubCellIndex;
   
   // Iterators into the spatial subdivision's cells
   typedef typename std::vector< DtSpatialSubCellType >::iterator DtSpatialSubIter;
   typedef typename std::vector< DtSpatialSubCellType >::const_iterator DtSpatialSubConstIter;


   // Intended default constructor
   // \throws std::bad_alloc if there is not enough memory to allocate the object
   DtSpatialSubdivision(const DtPoint& origin, 
                        unsigned int cellCountX, 
                        unsigned int cellCountY, 
                        unsigned int cellCountZ,
                        double cellDx, 
                        double cellDy, 
                        double cellDz);

   // Cover this extent with the given number of cells.
   // \throws std::bad_alloc if there is not enough memory to allocate the object
   explicit DtSpatialSubdivision(DtExtent extent, 
                                 unsigned int cellCountX, 
                                 unsigned int cellCountY, 
                                 unsigned int cellCountZ = 1);

   // Cover this extent with the given cell sizes (in DB units)
   // \throws std::bad_alloc if there is not enough memory to allocate the object
   explicit DtSpatialSubdivision(DtExtent extent, 
                                 double cellDx, 
                                 double cellDy,
                                 double cellDz = -1.0);

   // Destructor
   virtual ~DtSpatialSubdivision();

public:

   // Resizes the spatial subdivision to fit the specified extent.  This function
   // clears the contents of the subdivision, and updates the cell sizes and origin
   // with the specified extent. 
   virtual void setExtent(DtExtent extent);

   // Warning:  clears all contents!
   // Resets the cell counts of the spatial subdivision to the specified values,
   // reallocating the memory associated if necessary.
   //
   // \implementation As an optimization, it will not reallocate if the total 
   // cell count is the same as before, even if the resolutions are actually
   // different.  Thus if the previous resolutions were 10,15,1 and the new 
   // resolutions are 15,10,1, no reallocation will occur.  
   //
   // \note The minimum resolution is 1, which will be used if 0 is specified.
   virtual void setResolutions(unsigned int cellCountX, unsigned int cellCountY, 
      unsigned int cellCountZ = 1);

   // Resizes the spatial subdivision to fit the specified extent.  This function
   // clears the contents of the subdivision, and updates the cell sizes and origin
   // with the specified extent.  
   // This function will \b only reallocate the container of cells when the 
   // requested cell count total differs from the existing cell count total.  
   // 
   // \note Thus if a subdivision is resized from 10,10,1 to 10,1,10, the cells 
   // will only be cleared, not reallocated.  This is meant as a possible 
   // optimization when it is possible to reuse an existing container.
   virtual void resize(DtExtent extent, unsigned int cellCountX, 
                       unsigned int cellCountY, unsigned int cellCountZ);

   // Empties the entire spatial subdivision, removing all contents
   // \note Does not deallocate the container, just clears the contents
   // of the cells.
   virtual void clear();

   // Clears the cells referenced by the specified iterators.
   // \note The template type must support the clear() function, as
   // this function will call clear() on all cells at or between the 
   // specified iterators.
   virtual void clearCell(DtSpatialSubIter& cellIter);
   virtual void clearCell(DtSpatialSubIter& startIter, DtSpatialSubIter& endIter);

   // \return A boolean indicating whether or not anything is contained
   // in the subdivision
   virtual bool empty() const;

   // \return the total number of cells in the subdivision
   virtual unsigned int size() const;

   //
   // Accessors
   //
   // \return iterators to the first and last cells respectively.
   virtual DtSpatialSubIter begin();
   virtual DtSpatialSubConstIter begin() const;

   virtual DtSpatialSubIter end();
   virtual DtSpatialSubConstIter end() const;

   // \return an iterator to the spatial subdivision cell at the specified index, 
   // if the index is valid.
   // \note the results are undefined if the index is outside of the range of the
   // spatial subdivision's cells.  (technically, this just passes the index 
   // down to the std::vector at() call, so it will throw a range error exception.)
   // 
   virtual DtSpatialSubCellType& at(DtSpatialSubCellIndex index);
   virtual const DtSpatialSubCellType& at(DtSpatialSubCellIndex index) const;

   virtual DtSpatialSubCellType& at(DtSpatialSubCellIndex xIndex, 
      DtSpatialSubCellIndex yIndex, DtSpatialSubCellIndex zIndex);
   virtual const DtSpatialSubCellType& at(DtSpatialSubCellIndex xIndex, 
      DtSpatialSubCellIndex yIndex, DtSpatialSubCellIndex zIndex) const;

   // \return an iterator to the spatial subdivision cell at the specified index, 
   // \note Does \b not check if the index is valid or not.
   virtual DtSpatialSubCellType& operator[](DtSpatialSubCellIndex index);
   virtual const DtSpatialSubCellType& operator[](DtSpatialSubCellIndex index) const;


   // \return a reference (const or not) to the first or last spatial subdivision cell 
   // in the spatial subdivision.  
   // \note User \b must ensure the spatial subdivision is \b not empty before 
   // calling these functions.
   virtual DtSpatialSubCellType& front();
   virtual const DtSpatialSubCellType& front() const;

   virtual DtSpatialSubCellType& back();
   virtual const DtSpatialSubCellType& back() const;

   // Get/Set the origin of the spatial index (the point of lowest X, Y, Z)
   virtual const DtPoint& origin() const;
   virtual void setOrigin(const DtPoint& newOrigin);

   // \return the cell count in the specified dimension.
   virtual unsigned int cellCountX() const;
   virtual unsigned int cellCountY() const;
   virtual unsigned int cellCountZ() const;

   // \return the size of each cell in the specified dimension.
   virtual double cellDx() const;
   virtual double cellDy() const;
   virtual double cellDz() const;

   // Get the cell that contains the given coordinate if the coordinate lies
   // within the spatial subdivision.
   // 
   // If the specified point lies within the spatial subdivision, the 
   // function sets the specified point to point to the cell and returns true.
   //
   // \return A boolean indicating whether or not the point lies within the 
   // spatial subdivision.  If it does not, the cell pointer is not set.
   virtual bool cell(double x, double y, double z, DtSpatialSubCellType*& cell);
   virtual bool cell(double x, double y, double z, const DtSpatialSubCellType*& cell) const;

   virtual bool cell(const DtPoint& containing, DtSpatialSubCellType*& cell);
   virtual bool cell(const DtPoint& containing, const DtSpatialSubCellType*& cell) const;

   // Given an offset vector (local coordinate - origin), return the cell
   // index values.  
   //
   // \param xIndex The index in X, of the specified point.  Set by the function.
   // \param yIndex The index in Y, of the specified point.  Set by the function.
   // \param zIndex The index in Z, of the specified point.  Set by the function.
   //
   // \note There is no guarantee that the resulting indices are inside the spatial 
   // subdivision.
   virtual void offsetToIndices(const DtPoint& offset, DtSpatialSubCellIndex& xIndex, 
                                DtSpatialSubCellIndex& yIndex, DtSpatialSubCellIndex& zIndex) const;

   // Check if the given index values are within the spatial subdivision
   // \return a boolean signifying whether or not the specified index/indices
   // are valid (refer to cells inside the spatial subdivision)
   virtual bool indexIsValid(DtSpatialSubCellIndex index) const;
   virtual bool indicesAreValid(DtSpatialSubCellIndex xIndex, 
      DtSpatialSubCellIndex yIndex, DtSpatialSubCellIndex zIndex) const;

   virtual int sizeInBytes() const;

protected:
   // Tests the class invariant.  Called at the beginning of every public 
   // member function and at the end of all non-const public member functions.
   bool testInvariant() const;

protected:
   // \return the inverse of the size of each cell in the specified dimension.
   // \note If the dimension is 0, then the function returns 0.0 as a default.
   // \note These should not be called when the dimension is 0, even though they
   // return 0.0 to be safe.
   double inverseCellDx() const;
   double inverseCellDy() const;
   double inverseCellDz() const;

   // Calculates the minimum and maximum sizes, in each dimension, of any offset 
   // that is to be translated into an index.  An offset that contains any 
   // dimension larger or smaller (negative) than these will result in rollover 
   // problems and the wrong index being calculated.  Since this is a function 
   // of std::limits<>max() and the cell delta in the appropriate dimension
   void calculateMinMaxOffsets();

   // Calculates the inverse of the cell deltas in each dimension.  Used every time
   // an index is calculated from an offset.
   void calculateInverseDeltas();

   DtPoint myOrigin;

   unsigned int myCellCountX;
   unsigned int myCellCountY;
   unsigned int myCellCountZ;

   double myCellDx;
   double myCellDy;
   double myCellDz;

   // These are used instead of dividing when calculating indexes from an offset
   double myInverseCellDx;
   double myInverseCellDy;
   double myInverseCellDz;

   // These are the maximum sizes, in each dimension, of any offset that is to 
   // be translated into and index.  An offset that contains any dimension larger
   // than these will result in rollover problems and the wrong index being 
   // calculated.
   double myMaxOffsetX;
   double myMaxOffsetY;
   double myMaxOffsetZ;

   double myMinOffsetX;
   double myMinOffsetY;
   double myMinOffsetZ;

   std::vector< DtSpatialSubCellType > myCells;
};


//------------------------------------------------------
//  INLINE METHODS
//------------------------------------------------------
// include the inline code
#define SPATIALSUBDIVISION_HEADER
#include "geometry/spatialSubdivision.inl"
#undef  SPATIALSUBDIVISION_HEADER

#endif