/
kd_util.h
124 lines (107 loc) · 4.64 KB
/
kd_util.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//----------------------------------------------------------------------
// File: kd_util.h
// Programmer: Sunil Arya and David Mount
// Description: Common utilities for kd- trees
// Last modified: 01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount. All Rights Reserved.
//
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN). This software is provided under
// the provisions of the Lesser GNU Public License (LGPL). See the
// file ../ReadMe.txt for further information.
//
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose. It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
// Revision 0.1 03/04/98
// Initial release
//----------------------------------------------------------------------
#ifndef ANN_kd_util_H
#define ANN_kd_util_H
#include "kd_tree.h" // kd-tree declarations
//----------------------------------------------------------------------
// externally accessible functions
//----------------------------------------------------------------------
double annAspectRatio( // compute aspect ratio of box
int dim, // dimension
const ANNorthRect &bnd_box); // bounding cube
void annEnclRect( // compute smallest enclosing rectangle
ANNpointArray pa, // point array
ANNidxArray pidx, // point indices
int n, // number of points
int dim, // dimension
ANNorthRect &bnds); // bounding cube (returned)
void annEnclCube( // compute smallest enclosing cube
ANNpointArray pa, // point array
ANNidxArray pidx, // point indices
int n, // number of points
int dim, // dimension
ANNorthRect &bnds); // bounding cube (returned)
ANNdist annBoxDistance( // compute distance from point to box
const ANNpoint q, // the point
const ANNpoint lo, // low point of box
const ANNpoint hi, // high point of box
int dim); // dimension of space
ANNcoord annSpread( // compute point spread along dimension
ANNpointArray pa, // point array
ANNidxArray pidx, // point indices
int n, // number of points
int d); // dimension to check
void annMinMax( // compute min and max coordinates along dim
ANNpointArray pa, // point array
ANNidxArray pidx, // point indices
int n, // number of points
int d, // dimension to check
ANNcoord& min, // minimum value (returned)
ANNcoord& max); // maximum value (returned)
int annMaxSpread( // compute dimension of max spread
ANNpointArray pa, // point array
ANNidxArray pidx, // point indices
int n, // number of points
int dim); // dimension of space
void annMedianSplit( // split points along median value
ANNpointArray pa, // points to split
ANNidxArray pidx, // point indices
int n, // number of points
int d, // dimension along which to split
ANNcoord &cv, // cutting value
int n_lo); // split into n_lo and n-n_lo
void annPlaneSplit( // split points by a plane
ANNpointArray pa, // points to split
ANNidxArray pidx, // point indices
int n, // number of points
int d, // dimension along which to split
ANNcoord cv, // cutting value
int &br1, // first break (values < cv)
int &br2); // second break (values == cv)
void annBoxSplit( // split points by a box
ANNpointArray pa, // points to split
ANNidxArray pidx, // point indices
int n, // number of points
int dim, // dimension of space
ANNorthRect &box, // the box
int &n_in); // number of points inside (returned)
int annSplitBalance( // determine balance factor of a split
ANNpointArray pa, // points to split
ANNidxArray pidx, // point indices
int n, // number of points
int d, // dimension along which to split
ANNcoord cv); // cutting value
void annBox2Bnds( // convert inner box to bounds
const ANNorthRect &inner_box, // inner box
const ANNorthRect &bnd_box, // enclosing box
int dim, // dimension of space
int &n_bnds, // number of bounds (returned)
ANNorthHSArray &bnds); // bounds array (returned)
void annBnds2Box( // convert bounds to inner box
const ANNorthRect &bnd_box, // enclosing box
int dim, // dimension of space
int n_bnds, // number of bounds
ANNorthHSArray bnds, // bounds array
ANNorthRect &inner_box); // inner box (returned)
#endif