← Back to branch summary

~ubuntu-branches/debian/sid/3depict/sid

« back to all changes in this revision

Viewing changes to src/K3DTree.h

  • Committer: Bazaar Package Importer
  • Author(s): D Haley
  • Date: 2010-08-09 21:23:50 UTC
  • Revision ID: james.westby@ubuntu.com-20100809212350-cg6yumndhwi3bqws
Tags: upstream-0.0.1
Import upstream version 0.0.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/K3DTree.h
 
1
/*
 
2
 * $Id: K3DTree.h 86 2010-01-23 00:32:22Z daniel $
 
3
 */
 
4
 
 
5
//As this program relies on GNU GPL(v3) components, this program is GPLv3
 
6
/* rdf-kd : Calculates radial distribution functions
 
7
 * Copyright (C) 2008  Daniel Haley
 
8
 * 
 
9
 * This program is free software: you can redistribute it and/or modify
 
10
 * it under the terms of the GNU General Public License as published by
 
11
 * the Free Software Foundation, either version 3 of the License, or
 
12
 * (at your option) any later version.
 
13
 * 
 
14
 * This program is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 * GNU General Public License for more details.
 
18
 * 
 
19
 * You should have received a copy of the GNU General Public License
 
20
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
21
 */
 
22
#ifndef K3DTree_H
 
23
#define K3DTree_H
 
24
 
 
25
 
 
26
#include <algorithm>
 
27
#include <stack>
 
28
#include <vector>
 
29
#include <deque>
 
30
#include <cmath>
 
31
#include <iostream>
 
32
 
 
33
//TODO: eliminate the using directives from this header
 
34
using std::vector;
 
35
using std::copy;
 
36
using std::sort;
 
37
using std::deque;
 
38
#include "basics.h"
 
39
 
 
40
 
 
41
class K3DNode;
 
42
class AxisCompare;
 
43
class K3DTree;
 
44
 
 
45
struct CubeStruct;
 
46
 
 
47
 
 
48
 
 
49
//!Functor allowing for sorting of points in 3D
 
50
/*! Used by KD Tree to sort points based around which splitting axis is being used
 
51
 * once the axis is set, points will be ranked based upon their relative value in
 
52
 * that axis only
 
53
 */ 
 
54
class AxisCompare
 
55
{
 
56
        private:
 
57
                unsigned int axis;
 
58
        public:
 
59
                AxisCompare();
 
60
                void setAxis(unsigned int Axis);
 
61
                inline bool operator() (const Point3D &p1,const Point3D &p2)
 
62
                {return p1[axis]<p2[axis];};
 
63
};
 
64
 
 
65
//!Node Class for storing point
 
66
class K3DNode
 
67
{
 
68
        private:
 
69
                K3DNode *childLeft;
 
70
                K3DNode *childRight;
 
71
                Point3D loc;
 
72
                //!The axis being stored here is redundant, but the original idea was to speed up acces times in K3DTree::findNearest
 
73
                unsigned int axis;
 
74
        public:
 
75
                //K3DNode();
 
76
                //get and sets.
 
77
                
 
78
                //!Return the point data from the ndoe
 
79
                Point3D getLoc() const;
 
80
                //!Return a pointer to the point from the node
 
81
                inline const Point3D *getLocRef() const { return &loc;};
 
82
                //!Set the left child node
 
83
                inline void setLeft(K3DNode *node) {childLeft= node;};
 
84
                //!Set the right child node
 
85
                inline void setRight(K3DNode *node) {childRight=node;};
 
86
 
 
87
                //!Set the point data associated with this node
 
88
                void setLoc(const Point3D &);
 
89
                //!Set the axis that this node operates on
 
90
                inline void setAxis(unsigned int newAxis) {axis=newAxis;};
 
91
                //!Retrieve the axis that this node operates on
 
92
                inline unsigned int getAxis() const{ return axis;};
 
93
                //!retrieve the value associated with this axis
 
94
                inline float getAxisVal() const { return loc.getValue(axis);};
 
95
                inline float getLocVal(unsigned int pos) const {return loc.getValue(pos);};     
 
96
                inline float sqrDist(const Point3D &pt) const {return loc.sqrDist(pt);};        
 
97
                //TODO: make this return const pointer?
 
98
                inline K3DNode *left() const {return childLeft;};
 
99
                inline K3DNode *right() const {return childRight;};
 
100
 
 
101
                //!Recursively delete this node and all children
 
102
                void deleteChildren();
 
103
                //!print the node data out to a given stream
 
104
                void dump(std::ostream &, unsigned int) const;
 
105
};
 
106
 
 
107
//!3D specific KD tree
 
108
class K3DTree
 
109
{
 
110
        private:
 
111
                //!Total points in tree
 
112
                unsigned int treeSize;
 
113
                //!The maximum depth of the tree
 
114
                unsigned int maxDepth;
 
115
                
 
116
                //!Root node of tree
 
117
                K3DNode *root;
 
118
                //!Build tree recursively
 
119
                K3DNode *buildRecurse(vector<Point3D>::iterator pts_start,
 
120
                                vector<Point3D>::iterator pts_end, unsigned int depth );
 
121
                //TODO: Why is deadDist here?
 
122
                float deadDistSqr;
 
123
                mutable deque<float> bestDistsSqr;
 
124
        public:
 
125
        
 
126
                //KD Tree constructor
 
127
                K3DTree();
 
128
 
 
129
                //!Cleans up tree, deallocates nodes
 
130
                ~K3DTree();
 
131
                
 
132
                /*! Builds a balanced KD tree from a list of points
 
133
                 * This call is being passed by copy in order to prevent
 
134
                 * re-ordering of the points. It may be worth having two calls
 
135
                 * a pass by ref version where the points get scrambled and this one
 
136
                 * which preserves input point ordering (due to the copy) 
 
137
                 */     
 
138
                void build(vector<Point3D> pts);
 
139
 
 
140
                /*! Builds a balanced KD tree from a list of points
 
141
                 *  This uses a pass by ref where the points get scrambled (sorted). 
 
142
                 *  Resultant tree should be identical to that generated by build() 
 
143
                 */     
 
144
                void buildByRef(vector<Point3D> &pts);
 
145
        
 
146
 
 
147
                //Tree walker that counts the number of nodes
 
148
                void verify();
 
149
                void verifyChildren(K3DNode *curNode);
 
150
 
 
151
                //! Clean the tree
 
152
                void kill();
 
153
                
 
154
                //!Find the nearest point to a given P that lies outsid some dead zone
 
155
                /*!deadDistSqr can be used ot disallow exact matching on NN searching
 
156
                 * simply pass epsilon =std::numeric_limits<float>::epsilon() 
 
157
                 * (#include <limits>)  
 
158
                 * Boundcube is the bounding box around the entire dataset
 
159
                 */
 
160
                const Point3D *findNearest(const Point3D &, const BoundCube &,
 
161
                
 
162
                                float deadDistSqr) const;
 
163
 
 
164
                //!Find the nearest N points 
 
165
                /*!Finds the nearest N points, that lie outside a 
 
166
                 * dead distance of deadDistSqr. k is the number to find
 
167
                 */
 
168
                void findKNearest(const Point3D & sourcePoint, const BoundCube& treeDomain, 
 
169
                                        unsigned int numNNs, vector<const Point3D *> &results,
 
170
                                        float deadDistSqr=0.0f) const;
 
171
 
 
172
                //!Textual output of tree. tabs are used to separate different levels of the tree
 
173
                /*!The output from this function can be quite large for even modest trees. 
 
174
                 * Recommended for debugging only*/
 
175
                void dump(std::ostream &) const;
 
176
                
 
177
                //!Print the number of nodes stored in the tree
 
178
                inline unsigned int nodeCount() const{return treeSize;};
 
179
};
 
180
 
 
181
        
 
182
 
 
183
#endif