K3DTree-exact.h

Go to the documentation of this file.

/* 
 * K3DTreeExact.h  - Precise KD tree implementation
 * Copyright (C) 2014  D. 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_EXACT_H
#define ATOMPROBE_K3DTREE_EXACT_H

//This is the second revision of my KD tree implementation
//The goals here are, as compared to the first
//  - Improved build performance by minimising memory allocation calls
//    and avoiding recursive implementations
//  - index based construction for smaller in-tree storage


#include <vector>
#include <cstdlib>

#include "atomprobe/primitives/ionHit.h"


//Note that many functions in the tree are parallelised using openmp
namespace AtomProbe
{


class K3DNodeExact
{
    public:
        //Index of left child in parent tree array. -1 if no child
        size_t childLeft;
        //Index of right child in parent tree array. -1 if no child
        size_t childRight;

        //Has this point been marked by an external algorithm?
        bool tagged;
};

class K3DTreeExact
{
    private:
        size_t maxDepth;

        //Second is original array index upon build
        std::vector<std::pair<Point3D,size_t> > indexedPoints;

        std::vector<K3DNodeExact> nodes;

        size_t treeRoot;

        BoundCube treeBounds;
        
        //Callback for progress reporting
        bool (*callback)(void);

        unsigned int *progress; //Progress counter pointer. Storage must be assigned

    public:

        K3DTreeExact();

        ~K3DTreeExact(){};

        void resetPts(std::vector<Point3D> &pts, bool clear=true);
        void resetPts(std::vector<IonHit> &pts, bool clear=true);


        bool build();

        void getBoundCube(BoundCube &b); 


        void dump(std::ostream &,size_t depth=0, size_t offset=-1) const;



        size_t findNearestUntagged(const Point3D &queryPt,
                        const BoundCube &b, bool tag=true);


        void findUntaggedInRadius(const Point3D &queryPt, const BoundCube &b, 
                    float radius, std::vector<size_t> &result);

        //Find the indices of all points that lie within  the
        // sphere (pts < radius) of given radius, centered upon
        // this origin. Tags are not considered in this algorithm,
        // and must be checked by the end 
        void ptsInSphere(const Point3D &origin, float radius,
            std::vector<size_t> &pts) const;


        //Obtain a point from its internal index
        const Point3D *getPt(size_t index) const ;
        //Obtain a point from its internal index
        const Point3D &getPtRef(size_t index) const ;

        //reset the specified "tags" in the tree
        void clearTags(std::vector<size_t> &tagsToClear);

        //Convert the "tree index" (the position in the tree) into the original point offset in the input array
        size_t getOrigIndex(size_t treeIndex) const ;
        
        //Set the callback routine for progress reporting. If
        // callback returns false during build process, build is
        // aborted. Progress is also updated (0->100) during build
        void setCallback(bool (*cb)(void)) {callback = cb;}
        
        //Set a pointer that can be used to write the current progress
        void setProgressPointer(unsigned int *p) { progress=p;};

        //Erase tree contents
        void clear() { nodes.clear(); indexedPoints.clear();};

        //mark a point as "tagged" (or untagged,if tagVal=false) via its tree index.
        void tag(size_t treeIndex,bool tagVal=true); 
        //mark a vector of points as "tagged" (or untagged,if tagVal=false) via its tree index.
        void tag(const std::vector<size_t> &treeIndicies,bool tagVal=true); 

        //obtain the tag status for a given point, using the tree index
        bool getTag(size_t treeIndex) const ;

        //obtain the number of points in the tree
        size_t size() const; 
        
        //Find the position of the root node in the tree
        size_t rootIdx() const { return treeRoot;}

        //Find the number of tagged items in the tree
        size_t tagCount() const;

        //reset all tagged points to untagged
        void clearAllTags();

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

}
#endif