Debian Codegraph @

include/ANN/ANNx.h

raw
1 //----------------------------------------------------------------------
2 // File: ANNx.h
3 // Programmer: Sunil Arya and David Mount
4 // Description: Internal include file for ANN
5 // Last modified: 01/27/10 (Version 1.1.2)
6 //
7 // These declarations are of use in manipulating some of
8 // the internal data objects appearing in ANN, but are not
9 // needed for applications just using the nearest neighbor
10 // search.
11 //
12 // Typical users of ANN should not need to access this file.
13 //----------------------------------------------------------------------
14 // Copyright (c) 1997-2010 University of Maryland and Sunil Arya and
15 // David Mount. All Rights Reserved.
16 //
17 // This software and related documentation is part of the Approximate
18 // Nearest Neighbor Library (ANN). This software is provided under
19 // the provisions of the Lesser GNU Public License (LGPL). See the
20 // file ../ReadMe.txt for further information.
21 //
22 // The University of Maryland (U.M.) and the authors make no
23 // representations about the suitability or fitness of this software for
24 // any purpose. It is provided "as is" without express or implied
25 // warranty.
26 //----------------------------------------------------------------------
27 // History:
28 // Revision 0.1 03/04/98
29 // Initial release
30 // Revision 1.0 04/01/05
31 // Changed LO, HI, IN, OUT to ANN_LO, ANN_HI, etc.
32 // Revision 1.1.2 01/27/10
33 // Fixed minor compilation bugs for new versions of gcc
34 //----------------------------------------------------------------------
35
36 #ifndef ANNx_H
37 #define ANNx_H
38
39 #include <iomanip> // I/O manipulators
40 #include <ANN/ANN.h> // ANN includes
41
42 //----------------------------------------------------------------------
43 // Global constants and types
44 //----------------------------------------------------------------------
45 enum {ANN_LO=0, ANN_HI=1}; // splitting indices
46 enum {ANN_IN=0, ANN_OUT=1}; // shrinking indices
47 // what to do in case of error
48 enum ANNerr {ANNwarn = 0, ANNabort = 1};
49
50 //----------------------------------------------------------------------
51 // Maximum number of points to visit
52 // We have an option for terminating the search early if the
53 // number of points visited exceeds some threshold. If the
54 // threshold is 0 (its default) this means there is no limit
55 // and the algorithm applies its normal termination condition.
56 //----------------------------------------------------------------------
57
58 extern int ANNmaxPtsVisited; // maximum number of pts visited
59 extern int ANNptsVisited; // number of pts visited in search
60
61 //----------------------------------------------------------------------
62 // Global function declarations
63 //----------------------------------------------------------------------
64
65 void annError( // ANN error routine
66 const char* msg, // error message
67 ANNerr level); // level of error
68
69 void annPrintPt( // print a point
70 ANNpoint pt, // the point
71 int dim, // the dimension
72 std::ostream &out); // output stream
73
74 //----------------------------------------------------------------------
75 // Orthogonal (axis aligned) rectangle
76 // Orthogonal rectangles are represented by two points, one
77 // for the lower left corner (min coordinates) and the other
78 // for the upper right corner (max coordinates).
79 //
80 // The constructor initializes from either a pair of coordinates,
81 // pair of points, or another rectangle. Note that all constructors
82 // allocate new point storage. The destructor deallocates this
83 // storage.
84 //
85 // BEWARE: Orthogonal rectangles should be passed ONLY BY REFERENCE.
86 // (C++'s default copy constructor will not allocate new point
87 // storage, then on return the destructor free's storage, and then
88 // you get into big trouble in the calling procedure.)
89 //----------------------------------------------------------------------
90
91 class ANNorthRect {
92 public:
93 ANNpoint lo; // rectangle lower bounds
94 ANNpoint hi; // rectangle upper bounds
95 //
96 ANNorthRect( // basic constructor
97 int dd, // dimension of space
98 ANNcoord l=0, // default is empty
99 ANNcoord h=0)
100 { lo = annAllocPt(dd, l); hi = annAllocPt(dd, h); }
101
102 ANNorthRect( // (almost a) copy constructor
103 int dd, // dimension
104 const ANNorthRect &r) // rectangle to copy
105 { lo = annCopyPt(dd, r.lo); hi = annCopyPt(dd, r.hi); }
106
107 ANNorthRect( // construct from points
108 int dd, // dimension
109 ANNpoint l, // low point
110 ANNpoint h) // hight point
111 { lo = annCopyPt(dd, l); hi = annCopyPt(dd, h); }
112
113 ~ANNorthRect() // destructor
114 { annDeallocPt(lo); annDeallocPt(hi); }
115
116 ANNbool inside(int dim, ANNpoint p);// is point p inside rectangle?
117 };
118
119 void annAssignRect( // assign one rect to another
120 int dim, // dimension (both must be same)
121 ANNorthRect &dest, // destination (modified)
122 const ANNorthRect &source); // source
123
124 //----------------------------------------------------------------------
125 // Orthogonal (axis aligned) halfspace
126 // An orthogonal halfspace is represented by an integer cutting
127 // dimension cd, coordinate cutting value, cv, and side, sd, which is
128 // either +1 or -1. Our convention is that point q lies in the (closed)
129 // halfspace if (q[cd] - cv)*sd >= 0.
130 //----------------------------------------------------------------------
131
132 class ANNorthHalfSpace {
133 public:
134 int cd; // cutting dimension
135 ANNcoord cv; // cutting value
136 int sd; // which side
137 //
138 ANNorthHalfSpace() // default constructor
139 { cd = 0; cv = 0; sd = 0; }
140
141 ANNorthHalfSpace( // basic constructor
142 int cdd, // dimension of space
143 ANNcoord cvv, // cutting value
144 int sdd) // side
145 { cd = cdd; cv = cvv; sd = sdd; }
146
147 ANNbool in(ANNpoint q) const // is q inside halfspace?
148 { return (ANNbool) ((q[cd] - cv)*sd >= 0); }
149
150 ANNbool out(ANNpoint q) const // is q outside halfspace?
151 { return (ANNbool) ((q[cd] - cv)*sd < 0); }
152
153 ANNdist dist(ANNpoint q) const // (squared) distance from q
154 { return (ANNdist) ANN_POW(q[cd] - cv); }
155
156 void setLowerBound(int d, ANNpoint p)// set to lower bound at p[i]
157 { cd = d; cv = p[d]; sd = +1; }
158
159 void setUpperBound(int d, ANNpoint p)// set to upper bound at p[i]
160 { cd = d; cv = p[d]; sd = -1; }
161
162 void project(ANNpoint &q) // project q (modified) onto halfspace
163 { if (out(q)) q[cd] = cv; }
164 };
165
166 // array of halfspaces
167 typedef ANNorthHalfSpace *ANNorthHSArray;
168
169 #endif