Debian Codegraph @

src/kd_util.h

raw
1 //----------------------------------------------------------------------
2 // File: kd_util.h
3 // Programmer: Sunil Arya and David Mount
4 // Description: Common utilities for kd- trees
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 //----------------------------------------------------------------------
24
25 #ifndef ANN_kd_util_H
26 #define ANN_kd_util_H
27
28 #include "kd_tree.h" // kd-tree declarations
29
30 //----------------------------------------------------------------------
31 // externally accessible functions
32 //----------------------------------------------------------------------
33
34 double annAspectRatio( // compute aspect ratio of box
35 int dim, // dimension
36 const ANNorthRect &bnd_box); // bounding cube
37
38 void annEnclRect( // compute smallest enclosing rectangle
39 ANNpointArray pa, // point array
40 ANNidxArray pidx, // point indices
41 int n, // number of points
42 int dim, // dimension
43 ANNorthRect &bnds); // bounding cube (returned)
44
45 void annEnclCube( // compute smallest enclosing cube
46 ANNpointArray pa, // point array
47 ANNidxArray pidx, // point indices
48 int n, // number of points
49 int dim, // dimension
50 ANNorthRect &bnds); // bounding cube (returned)
51
52 ANNdist annBoxDistance( // compute distance from point to box
53 const ANNpoint q, // the point
54 const ANNpoint lo, // low point of box
55 const ANNpoint hi, // high point of box
56 int dim); // dimension of space
57
58 ANNcoord annSpread( // compute point spread along dimension
59 ANNpointArray pa, // point array
60 ANNidxArray pidx, // point indices
61 int n, // number of points
62 int d); // dimension to check
63
64 void annMinMax( // compute min and max coordinates along dim
65 ANNpointArray pa, // point array
66 ANNidxArray pidx, // point indices
67 int n, // number of points
68 int d, // dimension to check
69 ANNcoord& min, // minimum value (returned)
70 ANNcoord& max); // maximum value (returned)
71
72 int annMaxSpread( // compute dimension of max spread
73 ANNpointArray pa, // point array
74 ANNidxArray pidx, // point indices
75 int n, // number of points
76 int dim); // dimension of space
77
78 void annMedianSplit( // split points along median value
79 ANNpointArray pa, // points to split
80 ANNidxArray pidx, // point indices
81 int n, // number of points
82 int d, // dimension along which to split
83 ANNcoord &cv, // cutting value
84 int n_lo); // split into n_lo and n-n_lo
85
86 void annPlaneSplit( // split points by a plane
87 ANNpointArray pa, // points to split
88 ANNidxArray pidx, // point indices
89 int n, // number of points
90 int d, // dimension along which to split
91 ANNcoord cv, // cutting value
92 int &br1, // first break (values < cv)
93 int &br2); // second break (values == cv)
94
95 void annBoxSplit( // split points by a box
96 ANNpointArray pa, // points to split
97 ANNidxArray pidx, // point indices
98 int n, // number of points
99 int dim, // dimension of space
100 ANNorthRect &box, // the box
101 int &n_in); // number of points inside (returned)
102
103 int annSplitBalance( // determine balance factor of a split
104 ANNpointArray pa, // points to split
105 ANNidxArray pidx, // point indices
106 int n, // number of points
107 int d, // dimension along which to split
108 ANNcoord cv); // cutting value
109
110 void annBox2Bnds( // convert inner box to bounds
111 const ANNorthRect &inner_box, // inner box
112 const ANNorthRect &bnd_box, // enclosing box
113 int dim, // dimension of space
114 int &n_bnds, // number of bounds (returned)
115 ANNorthHSArray &bnds); // bounds array (returned)
116
117 void annBnds2Box( // convert bounds to inner box
118 const ANNorthRect &bnd_box, // enclosing box
119 int dim, // dimension of space
120 int n_bnds, // number of bounds
121 ANNorthHSArray bnds, // bounds array
122 ANNorthRect &inner_box); // inner box (returned)
123
124 #endif