Logo Search packages:      
Sourcecode: 3depict version File versions  Download package


 * $Id: K3DTree.h 86 2010-01-23 00:32:22Z daniel $

//As this program relies on GNU GPL(v3) components, this program is GPLv3
/* rdf-kd : Calculates radial distribution functions
 * Copyright (C) 2008  Daniel Haley
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
#ifndef K3DTree_H
#define K3DTree_H

#include <algorithm>
#include <stack>
#include <vector>
#include <deque>
#include <cmath>
#include <iostream>

//TODO: eliminate the using directives from this header
using std::vector;
using std::copy;
using std::sort;
using std::deque;
#include "basics.h"

class K3DNode;
class AxisCompare;
class K3DTree;

struct CubeStruct;

//!Functor allowing for sorting of points in 3D
/*! Used by KD Tree to sort points based around which splitting axis is being used
 * once the axis is set, points will be ranked based upon their relative value in
 * that axis only
00054 class AxisCompare
            unsigned int axis;
            void setAxis(unsigned int Axis);
            inline bool operator() (const Point3D &p1,const Point3D &p2)
            {return p1[axis]<p2[axis];};

//!Node Class for storing point
00066 class K3DNode
            K3DNode *childLeft;
            K3DNode *childRight;
            Point3D loc;
            //!The axis being stored here is redundant, but the original idea was to speed up acces times in K3DTree::findNearest
00073             unsigned int axis;
            //get and sets.
            //!Return the point data from the ndoe
            Point3D getLoc() const;
            //!Return a pointer to the point from the node
00081             inline const Point3D *getLocRef() const { return &loc;};
            //!Set the left child node
00083             inline void setLeft(K3DNode *node) {childLeft= node;};
            //!Set the right child node
00085             inline void setRight(K3DNode *node) {childRight=node;};

            //!Set the point data associated with this node
            void setLoc(const Point3D &);
            //!Set the axis that this node operates on
00090             inline void setAxis(unsigned int newAxis) {axis=newAxis;};
            //!Retrieve the axis that this node operates on
00092             inline unsigned int getAxis() const{ return axis;};
            //!retrieve the value associated with this axis
00094             inline float getAxisVal() const { return loc.getValue(axis);};
            inline float getLocVal(unsigned int pos) const {return loc.getValue(pos);};   
            inline float sqrDist(const Point3D &pt) const {return loc.sqrDist(pt);};      
            //TODO: make this return const pointer?
            inline K3DNode *left() const {return childLeft;};
            inline K3DNode *right() const {return childRight;};

            //!Recursively delete this node and all children
            void deleteChildren();
            //!print the node data out to a given stream
            void dump(std::ostream &, unsigned int) const;

//!3D specific KD tree
00108 class K3DTree
            //!Total points in tree
00112             unsigned int treeSize;
            //!The maximum depth of the tree
00114             unsigned int maxDepth;
            //!Root node of tree
00117             K3DNode *root;
            //!Build tree recursively
            K3DNode *buildRecurse(vector<Point3D>::iterator pts_start,
                              vector<Point3D>::iterator pts_end, unsigned int depth );
            //TODO: Why is deadDist here?
            float deadDistSqr;
            mutable deque<float> bestDistsSqr;
            //KD Tree constructor

            //!Cleans up tree, deallocates nodes
            /*! Builds a balanced KD tree from a list of points
             * This call is being passed by copy in order to prevent
             * re-ordering of the points. It may be worth having two calls
             * a pass by ref version where the points get scrambled and this one
             * which preserves input point ordering (due to the copy) 
            void build(vector<Point3D> pts);

            /*! Builds a balanced KD tree from a list of points
             *  This uses a pass by ref where the points get scrambled (sorted). 
             *  Resultant tree should be identical to that generated by build() 
            void buildByRef(vector<Point3D> &pts);

            //Tree walker that counts the number of nodes
            void verify();
            void verifyChildren(K3DNode *curNode);

            //! Clean the tree
            void kill();
            //!Find the nearest point to a given P that lies outsid some dead zone
            /*!deadDistSqr can be used ot disallow exact matching on NN searching
             * simply pass epsilon =std::numeric_limits<float>::epsilon() 
             * (#include <limits>)  
             * Boundcube is the bounding box around the entire dataset
            const Point3D *findNearest(const Point3D &, const BoundCube &,
                        float deadDistSqr) const;

            //!Find the nearest N points 
            /*!Finds the nearest N points, that lie outside a 
             * dead distance of deadDistSqr. k is the number to find
            void findKNearest(const Point3D & sourcePoint, const BoundCube& treeDomain, 
                              unsigned int numNNs, vector<const Point3D *> &results,
                              float deadDistSqr=0.0f) const;

            //!Textual output of tree. tabs are used to separate different levels of the tree
            /*!The output from this function can be quite large for even modest trees. 
             * Recommended for debugging only*/
            void dump(std::ostream &) const;
            //!Print the number of nodes stored in the tree
00178             inline unsigned int nodeCount() const{return treeSize;};



Generated by  Doxygen 1.6.0   Back to index