MarlinUtil  1.12.1
kd_util.h
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
ANNorthHalfSpace
Definition: ANNx.h:132
ANNorthRect
Definition: ANNx.h:91
Generated on Fri Dec 2 2016 12:32:59 for MarlinUtil by   doxygen 1.8.6