Home
|
Main Page
|
Modules
|
Namespace List
|
Class Hierarchy
|
Alphabetical List
|
Data Structures
|
File List
|
Namespace Members
|
Data Fields
|
Globals
|
Related Pages
Components
Metrics
KNNGraphAlphaMutualInformation
KNN
ann_1.1
src
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
ANNbd_shrink::getStats
virtual void getStats(int dim, ANNkdStats &st, ANNorthRect &bnd_box)
ANNbd_shrink::ann_pri_search
virtual void ann_pri_search(ANNdist)
ANNkdStats
Definition:
ANNperf.h:48
ANNorthRect
Definition:
ANNx.h:93
kd_tree.h
ANNbd_shrink::n_bnds
int n_bnds
Definition:
bd_tree.h:63
ANNbd_shrink::ann_search
virtual void ann_search(ANNdist)
ANNbd_shrink::~ANNbd_shrink
~ANNbd_shrink()
Definition:
bd_tree.h:78
ANNbd_shrink::dump
virtual void dump(ostream &out)
ANN_IN
@ ANN_IN
Definition:
ANNx.h:47
ANNkd_node
Definition:
kd_tree.h:46
double
ANNbd_shrink
Definition:
bd_tree.h:62
ANNbd_shrink::ANNbd_shrink
ANNbd_shrink(int nb, ANNorthHSArray bds, ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL)
Definition:
bd_tree.h:67
KD_TRIVIAL
ANNkd_leaf * KD_TRIVIAL
ANN_OUT
@ ANN_OUT
Definition:
ANNx.h:47
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition:
bd_tree.h:65
ANNbd_shrink::ann_FR_search
virtual void ann_FR_search(ANNdist)
ANNbd_shrink::print
virtual void print(int level, ostream &out)
ANNorthHalfSpace
Definition:
ANNx.h:134
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition:
bd_tree.h:64
ANNx.h
Generated on OURCE_DATE_EPOCH for elastix by
1.8.18