UT/UT_HashGrid.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Jeff Chadwick
 *      Side Effects Software Inc.
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        Utility Library (C++)
 *
 * COMMENTS:
 *      This class implements a grid-based data structure for
 *      storing spacial data (ie. points) with a fixed radius of
 *      influence.  It can be used to quickly determine the set
 *      of elements affecting a given point in space.
 *
 */

#ifndef __UT_HashGrid_h__
#define __UT_HashGrid_h__

#ifdef WIN32
    #pragma warning(disable:4251)
    #pragma warning(disable:4275)
#endif

#include "UT_HashTable.h"
#include "UT_IntArray.h"
#include "UT_PtrArray.h"
#include "UT_RefArray.h"
#include "UT_Vector3.h"
#include "UT_Vector3Array.h"

/// A class that defines a cubic grid cell.
template <typename utPtr>
class UT_HashGridCell {
    public:
        UT_HashGridCell() {}
        UT_HashGridCell(int i, int j, int k, int index)
                : myElements(15), myIndices(15), myXindex(i), myYindex(j),
                  myZindex(k), myIndex(index), myNumEntries(0)
        {
            if (i > 1)
            {
                myIL = i + 2;
                myIR = i - 2;
            }
            else if (i == 1)
            {
                myIL = 0;
                myIR = 3;
            }
            else // i == 0
            {
                myIL = 2;
                myIR = 1;
            }

            if (j > 1)
            {
                myJL = j + 2;
                myJR = j - 2;
            }
            else if (j == 1)
            {
                myJL = 0;
                myJR = 3;
            }
            else // j == 0
            {
                myJL = 2;
                myJR = 1;
            }

            if (k > 1)
            {
                myKL = k + 2;
                myKR = k - 2;
            }
            else if (k == 1)
            {
                myKL = 0;
                myKR = 3;
            }
            else // k == 0
            {
                myKL = 2;
                myKR = 1;
            }
        }

        virtual ~UT_HashGridCell() {}

        UT_PtrArray<utPtr>       myElements;
        UT_IntArray              myIndices;

        int                      myXindex;
        int                      myYindex;
        int                      myZindex;

        int                      myIL, myIR;
        int                      myJL, myJR;
        int                      myKL, myKR;

        int                      myIndex;

        int                      myNumEntries;
};

template <typename utPtr>
class UT_HashGrid {

public:
    /// Constructor takes a floating point value to indicate
    /// the size of each grid cell to be stored by the, and
    /// optionally takes a size parameter to determine the
    /// initial size of the grid cell array.  The constructor
    /// also requires an origin about which the point set will
    /// be roughly centred.  fullinit determines whether or
    /// not a point is associated with all surrounding grid
    /// cells immediately upon addition, or if a point should
    /// only ever be associated with one grid cell.  In the
    /// second case, each query requires that 27 grid cells be
    /// checked instead of 1.  This is essentially a trade off
    /// between the cost of building the data structure and the
    /// cost of making point queries.  If the number of point
    /// queries is likely to outnumber the number of points
    /// added to the tree, then fullinit = true is recommended.
    /// NOTE: Any points added to the grid after
    /// it is constructed must be within 1000000 grid units of
    /// the origin.
    UT_HashGrid(fpreal cellsize, const UT_Vector3 &origin,
                        bool fullinit, unsigned int sz = 0);

    /// Trivial destructor
    virtual ~UT_HashGrid();

    /// Inserts a new element in to the set using the given
    /// point to determine that element's location in the grid.
    /// Returns true if successful.
    bool                         insert(const UT_Vector3 &p, utPtr t);

    /// Finds all elements close to the given point and returns
    /// a list of those elements.
    inline void                  findCloseElements(const UT_Vector3 &p,
                                    UT_PtrArray<utPtr> &list);

    /// Resets the structure by clearing all elements from it
    /// and optionally reinitializing the cell array to the
    /// given size.
    void                         reset(unsigned int sz = 0);

    /// Additional reset function that also changes the cell
    /// width and origin for the structure.
    void                         reset(fpreal cellsize,
                                    const UT_Vector3 &origin,
                                    bool fullinit,
                                    unsigned int sz = 0);

protected:
    typedef UT_RefArray<UT_HashGridCell<utPtr> > ut_CellArray;

    /// Helper functions used to get a grid cell from the
    /// hash table, or generate a new one if necessary.
    UT_HashGridCell<utPtr>      *getCell(const UT_Vector3 &p,
                                        bool create = false);
    UT_HashGridCell<utPtr>      *getCell(int i, int j, int k,
                                        bool create = false);

private:
    UT_Vector3                   myOrigin;
    fpreal                       myCellWidth;
    fpreal                       myCellWidth2;

    int                          myMaxElements;

    UT_HashTable                 myGridSet;
    ut_CellArray                 myCellArray;

    bool                         myFullInit;

    UT_Vector3Array              myPositions;

};

#if defined( WIN32 ) || defined( LINUX ) || defined(MBSD) || defined(GAMEOS)
    #include "UT_HashGrid.C"
#endif

#endif

---