[37] | 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 |
---|