qtree.h

Go to the documentation of this file.

/**
 * \file qtree.h <mi32/qtree.h>
 * \brief Spatial searching functions
 *
 * \if NODOC
 * $Id: qtree.h_v 1.16 2004/02/19 22:01:38 scowan Exp $
 *
 * $Log: qtree.h_v $
 * Revision 1.16  2004/02/19 22:01:38  scowan
 * Added another method.
 *
 * Revision 1.15  2004/02/12 21:37:58  scowan
 * Replaced function version with class version.
 *
 * Revision 1.14  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.13  2000/07/11 19:06:42  sparsons
 * Genitor documentation.
 *
 * Revision 1.12  2000/07/10 20:20:01  mju
 * Compile in isolation.
 *
 * Revision 1.11  1999/05/07 21:21:00  mju
 * Header restruct.
 *
 * Revision 1.10  1999/04/08  16:00:48  mju
 * Add inclusion guard.
 *
 * \endif
**/

#ifndef  INC_MI32_QTREE_H
#define  INC_MI32_QTREE_H

#ifndef  INC_MI32_SIMPLEAR_H
#include <mi32/simplear.h>
#endif

#ifdef GEOMDLL
   #define GEOMLIBEXPORT MI_DLLEXPORT
   #define GEOMLIBCLASSEXPORT MI_DLLCLASSEXPORT
#else
   #define GEOMLIBEXPORT MI_DLLIMPORT
   #define GEOMLIBCLASSEXPORT MI_DLLCLASSIMPORT
#endif

#ifndef GENERATING_DOXYGEN_OUTPUT
//! Forward declarations
struct DRECT2D;
class BITSET_DEQUE;
#endif // GENERATING_DOXYGEN_OUTPUT

//! Quad search tree implementation
class GEOMLIBCLASSEXPORT QUADTREE {
   public:
      enum INITFLAGS {
         INITFLAG_None =         0x0000,
         INITFLAG_StoreExtents = 0x0001,     //!< Ignored if INITFLAG_PointOnly is specified, stores DRECT2D passed to Add() according to ItemID
         INITFLAG_PointOnly =    0x0002,     //!< Creates optimized version for point only searches
         INITFLAG_FastAdd =      0x0004      //!< Performs no validation check for adding an ItemID multiple times
         };

      //! Default constructor 
      QUADTREE (
         );
   
      //! Copy constructor 
      QUADTREE (
         const QUADTREE& rhs
         );
   
      //! Destructor 
      ~QUADTREE (
         );
         
      //! Assignment operator
      QUADTREE& operator= (
         const QUADTREE& rhs
         );
   
      //! Add an element to the quad tree
      ERRVALUE Add (
         INT32 ItemID,
         const DRECT2D& Extents
         );
         
      //! Clear the quad tree of all elements, reverts back to the Initialize() state
      void Clear (
         );
   
      //! Delete an item from the quad tree
      //! Only valid if INITFLAG_StoreExtents is specified in Initialize()
      ERRVALUE Delete (
         INT32 ItemID
         );
         
      //! Delete an item from the quad tree
      ERRVALUE Delete (
         INT32 ItemID,
         const DRECT2D& Extents
         );
         
      //! Free the memory used by the quad tree
      void Free (
         );
   
      //! Get the extents of the item specified
      //! Only valid if INITFLAG_StoreExtents is specified in Initialize()
      ERRVALUE GetItemExtents (
         INT32 ItemID,
         DRECT2D& Extents
         ) const;
         
      //! Initialize the quad tree for a specific extents and number of elements
      ERRVALUE Initialize (
         const DRECT2D& Extents,
         INT32 NumItems,
         INITFLAGS InitFlags = INITFLAG_None
         );

      //! Determine if the quad tree is initialized
      bool IsInitialized (
         ) const;
         
      //! Search for the ItemID's that fall within the DRECT2D specified
      //! If INITFLAG_StoreExtents is not specified in Initialize(), some of the elements might fall outside the extents specified
      ERRVALUE Search (
         const DRECT2D& rect,
         SIMPLE_ARRAY<INT32>& ItemList
         ) const;
   
      //! Search for the ItemID's that fall within the DRECT2D specified
      //! If INITFLAG_StoreExtents is not specified in Initialize(), some of the elements might fall outside the extents specified
      ERRVALUE Search (
         const DRECT2D& rect,
         BITSET_DEQUE& Deque
         ) const;

      //! Sort the item list using the item extents stored in the quad tree
      //! The list is sorted from smallest extents to largest extents item
      //! Only valid if INITFLAG_StoreExtents is specified in Initialize()
      ERRVALUE SortItemListByExtents (
         SIMPLE_ARRAY<INT32>& ItemList
         ) const;
      
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      class PRIV;
      PRIV* m_Priv;
      #endif // GENERATING_DOXYGEN_OUTPUT
   };

DEFINE_ENUM_OP_BITWISE(QUADTREE::INITFLAGS);

#endif   //!<  INC_MI32_QTREE_H 

---