bd_tree.h
Go to the documentation of this file.
1 //----------------------------------------------------------------------
2 // File: bd_tree.h
3 // Programmer: David Mount
4 // Description: Declarations for standard bd-tree routines
5 // Last modified: 01/04/05 (Version 1.0)
6 //----------------------------------------------------------------------
7 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
8 // David Mount. All Rights Reserved.
9 //
10 // This software and related documentation is part of the Approximate
11 // Nearest Neighbor Library (ANN). This software is provided under
12 // the provisions of the Lesser GNU Public License (LGPL). See the
13 // file ../ReadMe.txt for further information.
14 //
15 // The University of Maryland (U.M.) and the authors make no
16 // representations about the suitability or fitness of this software for
17 // any purpose. It is provided "as is" without express or implied
18 // warranty.
19 //----------------------------------------------------------------------
20 // History:
21 // Revision 0.1 03/04/98
22 // Initial release
23 // Revision 1.0 04/01/05
24 // Changed IN, OUT to ANN_IN, ANN_OUT
25 //----------------------------------------------------------------------
26 
27 #ifndef ANN_bd_tree_H
28 #define ANN_bd_tree_H
29 
30 #include <ANN/ANNx.h> // all ANN includes
31 #include "kd_tree.h" // kd-tree includes
32 
33 //----------------------------------------------------------------------
34 // bd-tree shrinking node.
35 // The main addition in the bd-tree is the shrinking node, which
36 // is declared here.
37 //
38 // Shrinking nodes are defined by list of orthogonal halfspaces.
39 // These halfspaces define a (possibly unbounded) orthogonal
40 // rectangle. There are two children, in and out. Points that
41 // lie within this rectangle are stored in the in-child, and the
42 // other points are stored in the out-child.
43 //
44 // We use a list of orthogonal halfspaces rather than an
45 // orthogonal rectangle object because typically the number of
46 // sides of the shrinking box will be much smaller than the
47 // worst case bound of 2*dim.
48 //
49 // BEWARE: Note that constructor just copies the pointer to the
50 // bounding array, but the destructor deallocates it. This is
51 // rather poor practice, but happens to be convenient. The list
52 // is allocated in the bd-tree building procedure rbd_tree() just
53 // prior to construction, and is used for no other purposes.
54 //
55 // WARNING: In the near neighbor searching code it is assumed that
56 // the list of bounding halfspaces is irredundant, meaning that there
57 // are no two distinct halfspaces in the list with the same outward
58 // pointing normals.
59 //----------------------------------------------------------------------
60 
61 class ANNbd_shrink : public ANNkd_node // splitting node of a kd-tree
62 {
63  int n_bnds; // number of bounding halfspaces
64  ANNorthHSArray bnds; // list of bounding halfspaces
65  ANNkd_ptr child[2]; // in and out children
66 public:
67  ANNbd_shrink( // constructor
68  int nb, // number of bounding halfspaces
69  ANNorthHSArray bds, // list of bounding halfspaces
70  ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL) // children
71  {
72  n_bnds = nb; // cutting dimension
73  bnds = bds; // assign bounds
74  child[ANN_IN] = ic; // set children
75  child[ANN_OUT] = oc;
76  }
77 
78  ~ANNbd_shrink() // destructor
79  {
80  if (child[ANN_IN]!= NULL && child[ANN_IN]!= KD_TRIVIAL)
81  delete child[ANN_IN];
82  if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL)
83  delete child[ANN_OUT];
84  if (bnds != NULL)
85  delete [] bnds; // delete bounds
86  }
87 
88  virtual void getStats( // get tree statistics
89  int dim, // dimension of space
90  ANNkdStats &st, // statistics
91  ANNorthRect &bnd_box); // bounding box
92  virtual void print(int level, ostream &out);// print node
93  virtual void dump(ostream &out); // dump node
94 
95  virtual void ann_search(ANNdist); // standard search
96  virtual void ann_pri_search(ANNdist); // priority search
97  virtual void ann_FR_search(ANNdist); // fixed-radius search
98 };
99 
100 #endif
virtual void ann_pri_search(ANNdist)
ANNkd_leaf * KD_TRIVIAL
Definition: kd_tree.cpp:50
virtual void ann_search(ANNdist)
Definition: bd_search.cpp:39
int n_bnds
Definition: bd_tree.h:63
Definition: ANNx.h:46
~ANNbd_shrink()
Definition: bd_tree.h:78
virtual void getStats(int dim, ANNkdStats &st, ANNorthRect &bnd_box)
Definition: bd_tree.cpp:71
int dim
Definition: ann2fig.cpp:81
ANNbd_shrink(int nb, ANNorthHSArray bds, ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL)
Definition: bd_tree.h:67
virtual void dump(ostream &out)
Definition: kd_dump.cpp:159
ANNkd_ptr child[2]
Definition: bd_tree.h:65
virtual void print(int level, ostream &out)
Definition: bd_tree.cpp:41
Definition: ANNx.h:46
virtual void ann_FR_search(ANNdist)
double ANNdist
Definition: ANN.h:159
ANNorthHSArray bnds
Definition: bd_tree.h:64


addwa_local_planner
Author(s): Xie Fusheng
autogenerated on Mon Jun 10 2019 15:52:59