00001 //---------------------------------------------------------------------- 00002 // File: kd_util.h 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Common utilities for kd- trees 00005 // Last modified: 01/04/05 (Version 1.0) 00006 //---------------------------------------------------------------------- 00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00008 // David Mount. All Rights Reserved. 00009 // 00010 // This software and related documentation is part of the Approximate 00011 // Nearest Neighbor Library (ANN). This software is provided under 00012 // the provisions of the Lesser GNU Public License (LGPL). See the 00013 // file ../ReadMe.txt for further information. 00014 // 00015 // The University of Maryland (U.M.) and the authors make no 00016 // representations about the suitability or fitness of this software for 00017 // any purpose. It is provided "as is" without express or implied 00018 // warranty. 00019 //---------------------------------------------------------------------- 00020 // History: 00021 // Revision 0.1 03/04/98 00022 // Initial release 00023 //---------------------------------------------------------------------- 00024 00025 #ifndef ANN_kd_util_H 00026 #define ANN_kd_util_H 00027 00028 #include "kd_tree.h" // kd-tree declarations 00029 00030 //---------------------------------------------------------------------- 00031 // externally accessible functions 00032 //---------------------------------------------------------------------- 00033 00034 double annAspectRatio( // compute aspect ratio of box 00035 int dim, // dimension 00036 const ANNorthRect &bnd_box); // bounding cube 00037 00038 void annEnclRect( // compute smallest enclosing rectangle 00039 ANNpointArray pa, // point array 00040 ANNidxArray pidx, // point indices 00041 int n, // number of points 00042 int dim, // dimension 00043 ANNorthRect &bnds); // bounding cube (returned) 00044 00045 void annEnclCube( // compute smallest enclosing cube 00046 ANNpointArray pa, // point array 00047 ANNidxArray pidx, // point indices 00048 int n, // number of points 00049 int dim, // dimension 00050 ANNorthRect &bnds); // bounding cube (returned) 00051 00052 ANNdist annBoxDistance( // compute distance from point to box 00053 const ANNpoint q, // the point 00054 const ANNpoint lo, // low point of box 00055 const ANNpoint hi, // high point of box 00056 int dim); // dimension of space 00057 00058 ANNcoord annSpread( // compute point spread along dimension 00059 ANNpointArray pa, // point array 00060 ANNidxArray pidx, // point indices 00061 int n, // number of points 00062 int d); // dimension to check 00063 00064 void annMinMax( // compute min and max coordinates along dim 00065 ANNpointArray pa, // point array 00066 ANNidxArray pidx, // point indices 00067 int n, // number of points 00068 int d, // dimension to check 00069 ANNcoord& min, // minimum value (returned) 00070 ANNcoord& max); // maximum value (returned) 00071 00072 int annMaxSpread( // compute dimension of max spread 00073 ANNpointArray pa, // point array 00074 ANNidxArray pidx, // point indices 00075 int n, // number of points 00076 int dim); // dimension of space 00077 00078 void annMedianSplit( // split points along median value 00079 ANNpointArray pa, // points to split 00080 ANNidxArray pidx, // point indices 00081 int n, // number of points 00082 int d, // dimension along which to split 00083 ANNcoord &cv, // cutting value 00084 int n_lo); // split into n_lo and n-n_lo 00085 00086 void annPlaneSplit( // split points by a plane 00087 ANNpointArray pa, // points to split 00088 ANNidxArray pidx, // point indices 00089 int n, // number of points 00090 int d, // dimension along which to split 00091 ANNcoord cv, // cutting value 00092 int &br1, // first break (values < cv) 00093 int &br2); // second break (values == cv) 00094 00095 void annBoxSplit( // split points by a box 00096 ANNpointArray pa, // points to split 00097 ANNidxArray pidx, // point indices 00098 int n, // number of points 00099 int dim, // dimension of space 00100 ANNorthRect &box, // the box 00101 int &n_in); // number of points inside (returned) 00102 00103 int annSplitBalance( // determine balance factor of a split 00104 ANNpointArray pa, // points to split 00105 ANNidxArray pidx, // point indices 00106 int n, // number of points 00107 int d, // dimension along which to split 00108 ANNcoord cv); // cutting value 00109 00110 void annBox2Bnds( // convert inner box to bounds 00111 const ANNorthRect &inner_box, // inner box 00112 const ANNorthRect &bnd_box, // enclosing box 00113 int dim, // dimension of space 00114 int &n_bnds, // number of bounds (returned) 00115 ANNorthHSArray &bnds); // bounds array (returned) 00116 00117 void annBnds2Box( // convert bounds to inner box 00118 const ANNorthRect &bnd_box, // enclosing box 00119 int dim, // dimension of space 00120 int n_bnds, // number of bounds 00121 ANNorthHSArray bnds, // bounds array 00122 ANNorthRect &inner_box); // inner box (returned) 00123 00124 #endif
1.6.1