MarlinUtil
1.12.1
Main Page
Related Pages
Namespaces
Classes
Files
File List
source
src
ann
bd_tree.h
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
Definition:
bd_tree.h:61
ANNkdStats
Definition:
ANNperf.h:45
ANNkd_node
Definition:
kd_tree.h:46
ANNorthHalfSpace
Definition:
ANNx.h:132
ANNorthRect
Definition:
ANNx.h:91
Generated on Fri Dec 2 2016 12:32:59 for MarlinUtil by
1.8.6