K3DTree-approx.h

Go to the documentation of this file.

/* K3Dtree-approx.h: KD tree class for approximate calculations
 * Copyright (C) 2014  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
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * 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 ATOMPROBE_K3DTREE_H
#define ATOMPROBE_K3DTREE_H


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


#include "atomprobe/primitives/point3D.h"
#include "atomprobe/primitives/boundcube.h"

namespace AtomProbe
{



class AxisCompare
{
    private:
        unsigned int axis;
    public:
        AxisCompare();
        void setAxis(unsigned int Axis);
        inline bool operator()(const Point3D &p1,const Point3D &p2) const
        {return p1[axis]<p2[axis];};
};

class K3DNodeApprox
{
    private:
        K3DNodeApprox *childLeft;
        K3DNodeApprox *childRight;
        Point3D loc;
        unsigned int axis;
    public:
        //K3DNodeApprox();
        //get and sets.
        
        Point3D getLoc() const;
        inline const Point3D *getLocRef() const { return &loc;};
        inline void setLeft(K3DNodeApprox *node) {childLeft= node;};
        inline void setRight(K3DNodeApprox *node) {childRight=node;};

        void setLoc(const Point3D &);
        inline void setAxis(unsigned int newAxis) {axis=newAxis;};
        inline unsigned int getAxis() const{ return axis;};
        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);};    
        inline K3DNodeApprox *left() const {return childLeft;};
        inline K3DNodeApprox *right() const {return childRight;};

        void deleteChildren();
        void dump(std::ostream &, unsigned int) const;
};

class K3DTreeApprox
{
    private:
        unsigned int treeSize;
        unsigned int maxDepth;
        
        K3DNodeApprox *root;
        K3DNodeApprox *buildRecurse(std::vector<Point3D>::iterator pts_start, std::vector<Point3D>::iterator pts_end, unsigned int depth );
    public:
    
        //KD Tree constructor
        K3DTreeApprox();

        ~K3DTreeApprox();
        

        void build(const std::vector<Point3D> &pts);


        void buildByRef(std::vector<Point3D> &pts);
    

        void kill();
        

        const Point3D *findNearest(const Point3D &, const BoundCube &,
        
                float deadDistSqr) const;


        void findKNearest(const Point3D & sourcePoint, const BoundCube& treeDomain, 
                    unsigned int numNNs, std::vector<const Point3D *> &results,
                    float deadDistSqr=0.0f) const;


        void dump(std::ostream &) const;
        
        inline unsigned int nodeCount() const{return treeSize;};

#ifdef DEBUG
    static bool test();
#endif
};

}   

#endif