KdTree.h
Go to the documentation of this file.
1 // ****************************************************************************
2 // This file is part of the Integrating Vision Toolkit (IVT).
3 //
4 // The IVT is maintained by the Karlsruhe Institute of Technology (KIT)
5 // (www.kit.edu) in cooperation with the company Keyetech (www.keyetech.de).
6 //
7 // Copyright (C) 2014 Karlsruhe Institute of Technology (KIT).
8 // All rights reserved.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are met:
12 //
13 // 1. Redistributions of source code must retain the above copyright
14 // notice, this list of conditions and the following disclaimer.
15 //
16 // 2. Redistributions in binary form must reproduce the above copyright
17 // notice, this list of conditions and the following disclaimer in the
18 // documentation and/or other materials provided with the distribution.
19 //
20 // 3. Neither the name of the KIT nor the names of its contributors may be
21 // used to endorse or promote products derived from this software
22 // without specific prior written permission.
23 //
24 // THIS SOFTWARE IS PROVIDED BY THE KIT AND CONTRIBUTORS “AS IS” AND ANY
25 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 // DISCLAIMED. IN NO EVENT SHALL THE KIT OR CONTRIBUTORS BE LIABLE FOR ANY
28 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 // ****************************************************************************
35 // ****************************************************************************
36 // Filename: KdTree.h
37 // Author: Kai Welke
38 // Date: 14.04.2005
39 // ****************************************************************************
40 
41 
42 #ifndef _KD_TREE_H_
43 #define _KD_TREE_H_
44 
45 
46 // ****************************************************************************
47 // Necessary includes
48 // ****************************************************************************
49 
50 #include "KdStructs.h"
51 
52 
53 // ****************************************************************************
54 // Forward declarations
55 // ****************************************************************************
56 
57 class CKdPriorityQueue;
58 
59 
60 // ****************************************************************************
61 // CKdTreeNode
62 // ****************************************************************************
63 
65 {
66 public:
68  {
69  m_pLeftChild = 0;
70  m_pRightChild = 0;
71  m_nCutDimension = 0;
72  m_bIsLeaf = 0;
73  m_Bounding.fLow = 0;
74  m_Bounding.fHigh = 0;
75  m_nSize = 0;
76  m_pValues = 0;
77  }
78 
80  {
81  if (m_pValues)
82  delete [] m_pValues;
83  }
84 
85 
86  // public methods
88 
90 
92 
93  int m_bIsLeaf;
95 
96  int m_nSize;
97  float *m_pValues;
98 };
99 
100 
101 
102 // ****************************************************************************
103 // CKdTree
104 // ****************************************************************************
105 
106 class CKdTree
107 {
108 public:
109  // constructor
110  CKdTree(int nMaximumNumberOfNodes = 10000);
111 
112  // destructor
113  ~CKdTree();
114 
115 
116  // build a kd-tree
117  // Use userdata to attach metadata to the
118  // values. Only the dimensions of the vectors
119  // are used to build tree and search.
120  // In the NN results, you get the full vector, with
121  // the userdata in the upper elements of the vector.
122  // Casting of float values to the appropriate type
123  // has to be handled by user.
124  void Build(float **ppfValues, int nLow, int nHigh, int nBucketSize, int nDimensions, int nUserDataSize);
125 
126  // nearest neighbor only
127  void NearestNeighbor(const float *pQuery, float &fError, float*& pfNN, int nMaximumLeavesToVisit = -1);
128  void NearestNeighborBBF(const float *pfQuery, float &fError, float *&pfNN, int nMaximumLeavesToVisit = -1); // with best bin first strategy
129 
130  // nearest neighbor with list of best elements
131  void NearestNeighbor(const float *pQuery, float &fError, CKdPriorityQueue *&pNNList, int nMaximumLeavesToVisit = -1);
132  void NearestNeighborBBF(const float *pQuery, float &fError, CKdPriorityQueue *&pNNList, int nMaximumLeavesToVisit = -1); // with best bin first strategy
133 
134 
135 private:
136  // private methods
137  void Dispose();
138  CKdTreeNode* BuildRecursive(float** ppfValues,int nLow, int nHigh, KdBoundingBox* pCurrentBoundingBox, int nCurrentDepth);
139  void DisposeRecursive(CKdTreeNode *pNode);
140  void NearestNeighborRecursive(CKdTreeNode* pNode, const float *pQuery);
141  void NearestNeighborRecursiveBBF(CKdTreeNode* pNode, const float *pQuery, float fDistanceBB);
142 
143 
144  // root node
146  // maximum bucket size in tree
148  // number of dimensions of vectors
150  // size of userdata in vectors
152  // m_nDimensions + m_nUserDataSize
154  // number of leaves
156  // bounding box of whole tree (calculated in build process)
158 
159  // used for query recursion
162  // used when a maximum number of nodes to visit is provided
164  // queue to enable second closest element
167  // needed for BBF
169 };
170 
171 
172 
173 #endif // _KD_TREE_H_
int m_nMaximumLeavesToVisit
Definition: KdTree.h:163
float fHigh
Definition: KdStructs.h:53
int m_nDimensions
Definition: KdTree.h:149
CKdTreeNode * m_pRightChild
Definition: KdTree.h:87
CKdPriorityQueue * m_pNodeListBBF
Definition: KdTree.h:168
float m_fMedianValue
Definition: KdTree.h:89
int m_nUserDataSize
Definition: KdTree.h:151
~CKdTreeNode()
Definition: KdTree.h:79
CKdPriorityQueue * m_pNearestNeighborList_
Definition: KdTree.h:166
float * m_pValues
Definition: KdTree.h:97
int m_nTotalVectorSize
Definition: KdTree.h:153
CKdPriorityQueue * m_pNearestNeighborList
Definition: KdTree.h:165
CKdTreeNode * m_pRoot
Definition: KdTree.h:145
int m_nLeaves
Definition: KdTree.h:155
int m_bIsLeaf
Definition: KdTree.h:93
KdBounding m_Bounding
Definition: KdTree.h:91
CKdTreeNode * m_pLeftChild
Definition: KdTree.h:87
int m_nBucketSize
Definition: KdTree.h:147
float * m_pNearestNeighbor
Definition: KdTree.h:161
CKdTreeNode()
Definition: KdTree.h:67
KdBoundingBox m_EnclosingBox
Definition: KdTree.h:157
int m_nCutDimension
Definition: KdTree.h:94
float m_fCurrentMinDistance
Definition: KdTree.h:160
int m_nSize
Definition: KdTree.h:96
float fLow
Definition: KdStructs.h:51


asr_ivt
Author(s): Allgeyer Tobias, Hutmacher Robin, Kleinert Daniel, Meißner Pascal, Scholz Jonas, Stöckle Patrick
autogenerated on Mon Dec 2 2019 03:47:28