Statistics
| Branch: | Revision:

root / rgbdslam / gicp / ann_1.1.1 / src / bd_tree.h @ 9240aaa3

History | View | Annotate | Download (3.87 KB)

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