UT/UT_RTree.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:
 *      Michiel Hagedoorn
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_RTreeGeneric.h (UT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __UT_RTreeGeneric__
#define __UT_RTreeGeneric__

#include <SYS/SYS_Types.h>
#include <vector>
#include <limits>
#include "UT_API.h"
#include "UT_Math.h"

// UT_BoxT represents either an axis-aligned box or the empty set.
// UT_BoxT is closed as a set; all operations assume that 
// the boundary is included.
template< typename T >
class UT_BoxT
{
public:
    typedef T Scalar;

    // Default construct: the empty set
    UT_BoxT();

    // Construct box containing a single point position,
    // which is represented by its array of three coordinates.
    explicit UT_BoxT(const T p[3]);

    // Return whether this represents the empty set
    bool isEmpty() const;

    // Get minimum coordinate for given standard axis
    // Assumes this is not empty!
    T getMin(const int c) const;

    // Get maximum coordinate for given standard axis
    // Assumes this is not empty!
    T getMax(const int c) const;

    // Make a box that's a single point
    void assignPoint(const T*const p);

    // Expand the box just enough so that it contains a point p
    void absorbPoint(const T*const p);

    // Expand the box just enough so that it contains a box b
    void absorbBox(const UT_BoxT<T>& b);

    // Expand in the directions of the axes:
    // In case this is the empty set, the result is still the empty set
    // This is equivalent to making *this the union of all cubes with
    // radius l placed at points of the original set.
    void expandDistance(const T l);

    // Return whether a point is contained in the closed set
    bool contains(const T*const p) const;

    // Return whether the closed set *this intersects the closed set b
    bool intersects(const UT_BoxT<T>& b) const;

    // Return the axis in which the box is the widest.
    // For the empty set, this always returns axis 0
    int getLargestAxis() const;

private:
    // This represents set of all points x
    // with myMin[c] <= x[c] <= myMax[c] for each c = 0, 1, 2
    T myMin[3];
    T myMax[3];
};

template< int ORDER >
class UT_RTreeGeneric;

// This is an assigment of a box to each item stored in the R-tree.
// It is passed an argument to queries on the R-tree.
// This way, an R-tree can be re-used efficiently if the item boxes change.
// This will only remain efficient as long as the configuration of boxes
// doesn't change dramatically.
template< typename T >
class UT_RTreeBoxAssignmentT
{
public:
    UT_RTreeBoxAssignmentT() {}
    ~UT_RTreeBoxAssignmentT() {}

private:
    typedef UT_BoxT<T> Box;
    std::vector<Box> myBoxesForSharedNodes;

    template< int ORDER >
    friend class UT_RTreeGeneric;
};

template< int ORDER >
class UT_RNode;

// The order of the R-Tree is the number of children that each
// internal node in the tree has. Picking a higher value of
// ORDER will reduce the height of the R-tree.
// R-tree stores a containment structure for the boxes that are
// passed to its contructor, but doesn't store any actual boxes.
// That's why UT_RTreeGeneric doesn't take the number type T as a template parameter.
template< int ORDER >
class UT_RTreeGeneric
{
public:
    // Construct R-tree that contains the range of items [0, size),
    // During the construction, item_boxes[i] is used as the bounding box
    // for item #i. These boxes determine the initial structure of the R-tree.
    // However, the box positions and dimensions are not stored in the R-tree.
    template< typename T >
    UT_RTreeGeneric(const UT_BoxT<T> item_boxes[], const int size);

    ~UT_RTreeGeneric();

    // The number of items stored in the tree
    int getNumItems() const;

    // Create an assignment of a box to each item in the tree.
    // That is, item i is assigned box item_boxes[i].
    // This box assignment can be used in intersection queries.
    template< typename T >
    void createBoxAssignment(
        UT_RTreeBoxAssignmentT<T>& assignment, 
        const UT_BoxT<T> item_boxes[]
    ) const;

    // Return all items i for which item_boxes[i] intersects query_box.
    // The resulting items will be stored in the range [items_begin, items_end),
    // where items_end is the return value.
    // It is assumed that the array starting at items_begin is large enough
    // to contain the results (at most the total number of items).
    template< typename T >
    int* getIntersectingItems(
        const UT_BoxT<T>& box, 
        const UT_RTreeBoxAssignmentT<T>& assignment,
        int*const items_begin
    ) const;

private:
    typedef UT_RNode<ORDER> Node;

    int mySharedNodesCapacity;
    Node* mySharedNodes;
    Node* myRoot;
    int myNumItems;

    // Disallow
    UT_RTreeGeneric();
    UT_RTreeGeneric(const UT_RTreeGeneric&);
    UT_RTreeGeneric& operator=(const UT_RTreeGeneric&);
};

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

// R-tree boxes for various float types
typedef UT_BoxT<fpreal32> UT_BoxF;
typedef UT_BoxT<fpreal64> UT_BoxD;
typedef UT_BoxT<fpreal64> UT_Box;

// R-tree box assignments for various float types
typedef UT_RTreeBoxAssignmentT<fpreal32> UT_RTreeBoxAssignmentF;
typedef UT_RTreeBoxAssignmentT<fpreal64> UT_RTreeBoxAssignmentD;
typedef UT_RTreeBoxAssignmentT<fpreal64> UT_RTreeBoxAssignment;

// Tree of various orders
typedef UT_RTreeGeneric<2> UT_RTree2;
typedef UT_RTreeGeneric<16> UT_RTree16;
typedef UT_RTreeGeneric<2> UT_RTree;

#endif

---