AAKdTree.h

Go to the documentation of this file.

#ifndef __AAKDTREE_HEADER__
#define __AAKDTREE_HEADER__
 
#include <limits>
#include <list>
#include <vector>
 
#include <GfxTL/AACube.h>
#include <GfxTL/BaseTree.h>
#include <GfxTL/Intersect.h>
#include <GfxTL/NearestNeighbors.h>
#include <GfxTL/NullClass.h>
 
namespace GfxTL
{
    template <class Point, class Base>
    class AAKdCell : public Base
    {
    public:
        typedef Point PointType;
        typedef Base BaseType;
        typedef AAKdCell<Point, Base> ThisType;
        typedef typename Point::ScalarType ScalarType;
 
        enum
        {
            NChildren = 2
        };
 
        AAKdCell();
        AAKdCell(const AAKdCell<Point, Base>& cell);
        ~AAKdCell();
        const ThisType* operator[](unsigned int index) const;
        ThisType* operator[](unsigned int index);
        void Child(unsigned int index, ThisType* child);
        ScalarType Split() const;
        void Split(ScalarType split);
        unsigned int Axis() const;
        void Axis(unsigned int axis);
 
    private:
        unsigned int _axis;
        ScalarType _splitValue;
        ThisType* _children[2];
    };
 
    template <class Strategies>
    class AAKdTree :
        public Strategies::StrategyBase<
            BaseTree<AAKdCell<typename Strategies::PointType,
                              typename Strategies::CellData<typename Strategies::PointType>>>>
    {
    public:
        typedef AAKdCell<typename Strategies::PointType,
                         typename Strategies::CellData<typename Strategies::PointType>>
            CellType;
        typedef typename CellType::PointType PointType;
        typedef typename CellType::ScalarType ScalarType;
        typedef typename Strategies::StrategyBase<
            BaseTree<AAKdCell<typename Strategies::PointType,
                              typename Strategies::CellData<typename Strategies::PointType>>>>
            StrategyBaseType;
        typedef typename StrategyBaseType::HandleType HandleType;
        typedef ::GfxTL::NearestNeighbor<ScalarType> NN;
 
        enum
        {
            Dim = PointType::Dim
        };
 
        void Build();
        void PointsInSphere(const PointType& center,
                            ScalarType radius,
                            std::vector<size_t>* points) const;
        void PointsInAACube(const AACube<PointType>& cube, std::vector<size_t>* points) const;
        void PointsInAACube(const PointType& center,
                            ScalarType width,
                            std::vector<size_t>* points) const;
        void RefreshWithNewTreeData(const AACube<PointType>& bc);
        void NearestNeighbor(const PointType& p, size_t* neighbor, ScalarType* dist) const;
        void KNearestNeighbors(const PointType& p,
                               unsigned int k,
                               std::vector<NN>* neighbors,
                               ScalarType* dist) const;
 
    private:
        void NearestNeighbor(const CellType& cell,
                             const AABox<PointType>& box,
                             const PointType& p,
                             size_t* neighbor,
                             ScalarType* dist2) const;
        void KNearestNeighbors(const CellType& cell,
                               const AABox<PointType>& box,
                               const PointType& p,
                               unsigned int k,
                               std::vector<NN>* neighbors,
                               size_t* worstIdx,
                               ScalarType* dist2) const;
        void ReadjustData(CellType* cell);
        void PointsInSphere(const CellType* cell,
                            const PointType& center,
                            ScalarType radius,
                            std::vector<size_t>* points) const;
        void PointsInAACube(const CellType* cell,
                            const PointType& center,
                            ScalarType radius,
                            std::vector<HandleType>* points) const;
        bool ShouldSubdivide(const CellType* cell) const;
        void Subdivide(CellType* cell);
        ScalarType Absolute(ScalarType f) const;
    };
}; // namespace GfxTL
 
#include "AAKdTree.hpp"
 
#endif