| 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 |