VRS - The Virtual Rendering System

version 3.3

quadtree.h

Go to the documentation of this file.

/******************************************************************************
 * VRS - The Virtual Rendering System
 * Copyright (C) 2002 Computer Graphics Systems Group at the 
 * Hasso-Plattner-Institute (HPI), Potsdam, Germany.
 *
 * This  library  is  free  software; you can redistribute it and/or  modify it
 * under the terms of the GNU Lesser General Public  License  as  published  by
 * the  Free  Software  Foundation;  either  version 2.1 of the License, or (at
 * your option) any later version. This library  is  distributed  in  the  hope
 * that  it will be useful, but  WITHOUT ANY WARRANTY; without even the implied
 * warranty of  MERCHANTABILITY or FITNESS FOR A PARTICULAR  PURPOSE.  See  the
 * GNU Lesser General Public License for more details. You should have received
 * a copy of the GNU Lesser+ General Public License along with this library; if
 * not, write to the FreeSoftware Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA, 02111-1307, USA.
 ******************************************************************************/

// $Id: quadtree.h 4479 2004-11-09 15:07:24Z kirsch $
// $Date: 2004-11-09 16:07:24 +0100 (Tue, 09 Nov 2004) $
// $Revision: 4479 $
// $State$
// $Author: kirsch $
//
// $Log$
// Revision 1.5  2004/11/09 15:07:24  kirsch
// further changes to class comments due to doxygen
//
// Revision 1.4  2004/03/12 16:28:39  baumann
// macros VRS_NAMESPACE_BEGIN/_END expanded and removed
//
// Revision 1.3  2003/11/07 14:19:24  kirsch
// removed leading underscore from include guards
//
// Revision 1.2  2003/01/29 07:55:55  kirsch
// fixed comment
//
// Revision 1.1  2003/01/27 18:14:39  buchholz
// spacetree derivates for the 2 and 3 dimensional case.
//

#ifndef VRS_CONTAINER_QUADTREE_H_
#define VRS_CONTAINER_QUADTREE_H_


#include <vrs/matrix.h>
#include "spacetree.h"

namespace VRS {

struct QuadtreeCell {
    Vector min;
    Vector max;
};

template<typename CONTENT> class DynamicQuadtree : public DynamicSpaceTree<CONTENT, 2> {

public:

    typedef SpaceTreePath<2> Path;
    typedef typename DynamicSpaceTree<CONTENT, 2>::NodePointer NodePointer;


    DynamicQuadtree(const Vector& p1, const Vector& p2, 
        const Vector& xAxis = Vector(1,0,0), 
        const Vector& yAxis = Vector(0,1,0));
    // spatial search
    SpaceTreePath<2> findContainingNode(const Vector& point, 
                                                                                UINT level,
                                        bool mustExist = true);
    Iterator<SpaceTreePath<2> >* findBoundsIntersectingNodes(
                                                                                                        const Bounds& bounds, 
                                                                                                        UINT level,
                                                                                                        bool mustExist = true);
    SpaceTreePath<2> findSmallestBoundsEnclosingNode(const Bounds& bounds, 
                                                                                UINT maxLevel = 16,
                                        bool mustExist = true);

    virtual QuadtreeCell getQuadtreeCell(const Path& path);
    virtual QuadtreeCell getQuadtreeCell(const NodePointer& np);
    const Matrix& getTransform();
    const Matrix& getInverseTransform();
    
private:

    Matrix transform_;
    Matrix inverse_;
};

template<typename CONTENT> class StaticQuadtree : public StaticSpaceTree<CONTENT, 2> {

public:

    typedef SpaceTreePath<2> Path;
    typedef typename StaticSpaceTree<CONTENT, 2>::NodePointer NodePointer;

    StaticQuadtree(const Vector& p1, const Vector& p2, UINT depth,
        const Vector& xAxis = Vector(1,0,0), 
        const Vector& yAxis = Vector(0,1,0));


    SpaceTreePath<2> findContainingNode(const Vector& point, 
                                                                                UINT level,
                                        bool mustExist = true);
    Iterator<SpaceTreePath<2> >* findBoundsIntersectingNodes(
                                                                                                        const Bounds& bounds, 
                                                                                                        UINT level,
                                                                                                        bool mustExist = true);
    SpaceTreePath<2> findSmallestBoundsEnclosingNode(const Bounds& bounds, 
                                                                                UINT maxLevel = 16,
                                        bool mustExist = true);

    virtual QuadtreeCell getQuadtreeCell(const Path& path);
    virtual QuadtreeCell getQuadtreeCell(const NodePointer& np);
    
    const Matrix& getTransform();
    const Matrix& getInverseTransform();
    
private:

    Matrix transform_;
    Matrix inverse_;
};

} // namespace VRS

#include "quadtree.tli"

#endif // VRS_CONTAINER_QUADTREE_H_

---

Generated on Wed May 23 06:00:13 2012 by Doxygen 1.5.6

© 2001-2010 Hasso-Plattner-Institut | Impressum | Contact