| 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 |