Quadrotor

//----------------------------------------------------------------------

// File:                        ANN.h

// Programmer:                Sunil Arya and David Mount

// Last modified:        05/03/05 (Release 1.1)

// Description:                Basic include file for approximate nearest

//                                        neighbor searching.

//----------------------------------------------------------------------

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

//        Revision 1.0  04/01/05

//                Added copyright and revision information

//                Added ANNcoordPrec for coordinate precision.

//                Added methods theDim, nPoints, maxPoints, thePoints to ANNpointSet.

//                Cleaned up C++ structure for modern compilers

//        Revision 1.1  05/03/05

//                Added fixed-radius k-NN searching

//----------------------------------------------------------------------

//----------------------------------------------------------------------

// ANN - approximate nearest neighbor searching

//        ANN is a library for approximate nearest neighbor searching,

//        based on the use of standard and priority search in kd-trees

//        and balanced box-decomposition (bbd) trees. Here are some

//        references to the main algorithmic techniques used here:

//

//                kd-trees:

//                        Friedman, Bentley, and Finkel, ``An algorithm for finding

//                                best matches in logarithmic expected time,'' ACM

//                                Transactions on Mathematical Software, 3(3):209-226, 1977.

//

//                Priority search in kd-trees:

//                        Arya and Mount, ``Algorithms for fast vector quantization,''

//                                Proc. of DCC '93: Data Compression Conference, eds. J. A.

//                                Storer and M. Cohn, IEEE Press, 1993, 381-390.

//

//                Approximate nearest neighbor search and bbd-trees:

//                        Arya, Mount, Netanyahu, Silverman, and Wu, ``An optimal

//                                algorithm for approximate nearest neighbor searching,''

//                                5th Ann. ACM-SIAM Symposium on Discrete Algorithms,

//                                1994, 573-582.

//----------------------------------------------------------------------

#ifndef ANN_H

#define ANN_H

#ifdef WIN32

  //----------------------------------------------------------------------

  // For Microsoft Visual C++, externally accessible symbols must be

  // explicitly indicated with DLL_API, which is somewhat like "extern."

  //

  // The following ifdef block is the standard way of creating macros

  // which make exporting from a DLL simpler. All files within this DLL

  // are compiled with the DLL_EXPORTS preprocessor symbol defined on the

  // command line. In contrast, projects that use (or import) the DLL

  // objects do not define the DLL_EXPORTS symbol. This way any other

  // project whose source files include this file see DLL_API functions as

  // being imported from a DLL, wheras this DLL sees symbols defined with

  // this macro as being exported.

  //----------------------------------------------------------------------

  #ifdef DLL_EXPORTS

         #define DLL_API __declspec(dllexport)

  #else

        #define DLL_API __declspec(dllimport)

  #endif

  //----------------------------------------------------------------------

  // DLL_API is ignored for all other systems

  //----------------------------------------------------------------------

#else

  #define DLL_API

#endif

//----------------------------------------------------------------------

//  basic includes

//----------------------------------------------------------------------

#include <cstdlib>                      // exit(int)

#include <cmath>                        // math includes

#include <iostream>                        // I/O streams

//----------------------------------------------------------------------

// Limits

// There are a number of places where we use the maximum double value as

// default initializers (and others may be used, depending on the

// data/distance representation). These can usually be found in limits.h

// (as LONG_MAX, INT_MAX) or in float.h (as DBL_MAX, FLT_MAX).

//

// Not all systems have these files.  If you are using such a system,

// you should set the preprocessor symbol ANN_NO_LIMITS_H when

// compiling, and modify the statements below to generate the

// appropriate value. For practical purposes, this does not need to be

// the maximum double value. It is sufficient that it be at least as

// large than the maximum squared distance between between any two

// points.

//----------------------------------------------------------------------

#ifdef ANN_NO_LIMITS_H                                        // limits.h unavailable

  #include <cvalues>                                        // replacement for limits.h

  const double ANN_DBL_MAX = MAXDOUBLE;        // insert maximum double

#else

  #include <climits>

  #include <cfloat>

  const double ANN_DBL_MAX = DBL_MAX;

#endif

#define ANNversion                 "1.1.1"                        // ANN version and information

#define ANNversionCmt        ""

#define ANNcopyright        "David M. Mount and Sunil Arya"

#define ANNlatestRev        "Aug 4, 2006"

//----------------------------------------------------------------------

//        ANNbool

//        This is a simple boolean type. Although ANSI C++ is supposed

//        to support the type bool, some compilers do not have it.

//----------------------------------------------------------------------

enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++)

//----------------------------------------------------------------------

//        ANNcoord, ANNdist

//                ANNcoord and ANNdist are the types used for representing

//                point coordinates and distances.  They can be modified by the

//                user, with some care.  It is assumed that they are both numeric

//                types, and that ANNdist is generally of an equal or higher type

//                from ANNcoord.        A variable of type ANNdist should be large

//                enough to store the sum of squared components of a variable

//                of type ANNcoord for the number of dimensions needed in the

//                application.  For example, the following combinations are

//                legal:

//

//                ANNcoord                ANNdist

//                ---------                -------------------------------

//                short                        short, int, long, float, double

//                int                                int, long, float, double

//                long                        long, float, double

//                float                        float, double

//                double                        double

//

//                It is the user's responsibility to make sure that overflow does

//                not occur in distance calculation.

//----------------------------------------------------------------------

typedef double        ANNcoord;                                // coordinate data type

typedef double        ANNdist;                                // distance data type

//----------------------------------------------------------------------

//        ANNidx

//                ANNidx is a point index.  When the data structure is built, the

//                points are given as an array.  Nearest neighbor results are

//                returned as an integer index into this array.  To make it

//                clearer when this is happening, we define the integer type

//                ANNidx.         Indexing starts from 0.

//                

//                For fixed-radius near neighbor searching, it is possible that

//                there are not k nearest neighbors within the search radius.  To

//                indicate this, the algorithm returns ANN_NULL_IDX as its result.

//                It should be distinguishable from any valid array index.

//----------------------------------------------------------------------

typedef int                ANNidx;                                        // point index

const ANNidx        ANN_NULL_IDX = -1;                // a NULL point index

//----------------------------------------------------------------------

//        Infinite distance:

//                The code assumes that there is an "infinite distance" which it

//                uses to initialize distances before performing nearest neighbor

//                searches.  It should be as larger or larger than any legitimate

//                nearest neighbor distance.

//

//                On most systems, these should be found in the standard include

//                file <limits.h> or possibly <float.h>.  If you do not have these

//                file, some suggested values are listed below, assuming 64-bit

//                long, 32-bit int and 16-bit short.

//

//                ANNdist ANN_DIST_INF        Values (see <limits.h> or <float.h>)

//                ------- ------------        ------------------------------------

//                double        DBL_MAX                        1.79769313486231570e+308

//                float        FLT_MAX                        3.40282346638528860e+38

//                long        LONG_MAX                0x7fffffffffffffff

//                int                INT_MAX                        0x7fffffff

//                short        SHRT_MAX                0x7fff

//----------------------------------------------------------------------

const ANNdist        ANN_DIST_INF = ANN_DBL_MAX;

//----------------------------------------------------------------------

//        Significant digits for tree dumps:

//                When floating point coordinates are used, the routine that dumps

//                a tree needs to know roughly how many significant digits there

//                are in a ANNcoord, so it can output points to full precision.

//                This is defined to be ANNcoordPrec.  On most systems these

//                values can be found in the standard include files <limits.h> or

//                <float.h>.  For integer types, the value is essentially ignored.

//

//                ANNcoord ANNcoordPrec        Values (see <limits.h> or <float.h>)

//                -------- ------------        ------------------------------------

//                double         DBL_DIG                15

//                float         FLT_DIG                6

//                long         doesn't matter 19

//                int                 doesn't matter 10

//                short         doesn't matter 5

//----------------------------------------------------------------------

#ifdef DBL_DIG                                                        // number of sig. bits in ANNcoord

        const int         ANNcoordPrec        = DBL_DIG;

#else

        const int         ANNcoordPrec        = 15;        // default precision

#endif

//----------------------------------------------------------------------

// Self match?

//        In some applications, the nearest neighbor of a point is not

//        allowed to be the point itself. This occurs, for example, when

//        computing all nearest neighbors in a set.  By setting the

//        parameter ANN_ALLOW_SELF_MATCH to ANNfalse, the nearest neighbor

//        is the closest point whose distance from the query point is

//        strictly positive.

//----------------------------------------------------------------------

const ANNbool        ANN_ALLOW_SELF_MATCH        = ANNtrue;

//----------------------------------------------------------------------

//        Norms and metrics:

//                ANN supports any Minkowski norm for defining distance.  In

//                particular, for any p >= 1, the L_p Minkowski norm defines the

//                length of a d-vector (v0, v1, ..., v(d-1)) to be

//

//                                (|v0|^p + |v1|^p + ... + |v(d-1)|^p)^(1/p),

//

//                (where ^ denotes exponentiation, and |.| denotes absolute

//                value).  The distance between two points is defined to be the

//                norm of the vector joining them.  Some common distance metrics

//                include

//

//                                Euclidean metric                p = 2

//                                Manhattan metric                p = 1

//                                Max metric                                p = infinity

//

//                In the case of the max metric, the norm is computed by taking

//                the maxima of the absolute values of the components.  ANN is

//                highly "coordinate-based" and does not support general distances

//                functions (e.g. those obeying just the triangle inequality).  It

//                also does not support distance functions based on

//                inner-products.

//

//                For the purpose of computing nearest neighbors, it is not

//                necessary to compute the final power (1/p).  Thus the only

//                component that is used by the program is |v(i)|^p.

//

//                ANN parameterizes the distance computation through the following

//                macros.  (Macros are used rather than procedures for

//                efficiency.) Recall that the distance between two points is

//                given by the length of the vector joining them, and the length

//                or norm of a vector v is given by formula:

//

//                                |v| = ROOT(POW(v0) # POW(v1) # ... # POW(v(d-1)))

//

//                where ROOT, POW are unary functions and # is an associative and

//                commutative binary operator mapping the following types:

//

//                        **        POW:        ANNcoord                                --> ANNdist

//                        **        #:                ANNdist x ANNdist                --> ANNdist

//                        **        ROOT:        ANNdist (>0)                        --> double

//

//                For early termination in distance calculation (partial distance

//                calculation) we assume that POW and # together are monotonically

//                increasing on sequences of arguments, meaning that for all

//                v0..vk and y:

//

//                POW(v0) #...# POW(vk) <= (POW(v0) #...# POW(vk)) # POW(y).

//

//        Incremental Distance Calculation:

//                The program uses an optimized method of computing distances for

//                kd-trees and bd-trees, called incremental distance calculation.

//                It is used when distances are to be updated when only a single

//                coordinate of a point has been changed.  In order to use this,

//                we assume that there is an incremental update function DIFF(x,y)

//                for #, such that if:

//

//                                        s = x0 # ... # xi # ... # xk 

//

//                then if s' is equal to s but with xi replaced by y, that is, 

//                

//                                        s' = x0 # ... # y # ... # xk

//

//                then the length of s' can be computed by:

//

//                                        |s'| = |s| # DIFF(xi,y).

//

//                Thus, if # is + then DIFF(xi,y) is (yi-x).  For the L_infinity

//                norm we make use of the fact that in the program this function

//                is only invoked when y > xi, and hence DIFF(xi,y)=y.

//

//                Finally, for approximate nearest neighbor queries we assume

//                that POW and ROOT are related such that

//

//                                        v*ROOT(x) = ROOT(POW(v)*x)

//

//                Here are the values for the various Minkowski norms:

//

//                L_p:        p even:                                                        p odd:

//                                -------------------------                ------------------------

//                                POW(v)                        = v^p                        POW(v)                        = |v|^p

//                                ROOT(x)                        = x^(1/p)                ROOT(x)                        = x^(1/p)

//                                #                                = +                                #                                = +

//                                DIFF(x,y)                = y - x                        DIFF(x,y)                = y - x 

//

//                L_inf:

//                                POW(v)                        = |v|

//                                ROOT(x)                        = x

//                                #                                = max

//                                DIFF(x,y)                = y

//

//                By default the Euclidean norm is assumed.  To change the norm,

//                uncomment the appropriate set of macros below.

//----------------------------------------------------------------------

//----------------------------------------------------------------------

//        Use the following for the Euclidean norm

//----------------------------------------------------------------------

#define ANN_POW(v)                        ((v)*(v))

#define ANN_ROOT(x)                        sqrt(x)

#define ANN_SUM(x,y)                ((x) + (y))

#define ANN_DIFF(x,y)                ((y) - (x))

//----------------------------------------------------------------------

//        Use the following for the L_1 (Manhattan) norm

//----------------------------------------------------------------------

// #define ANN_POW(v)                fabs(v)

// #define ANN_ROOT(x)                (x)

// #define ANN_SUM(x,y)                ((x) + (y))

// #define ANN_DIFF(x,y)        ((y) - (x))

//----------------------------------------------------------------------

//        Use the following for a general L_p norm

//----------------------------------------------------------------------

// #define ANN_POW(v)                pow(fabs(v),p)

// #define ANN_ROOT(x)                pow(fabs(x),1/p)

// #define ANN_SUM(x,y)                ((x) + (y))

// #define ANN_DIFF(x,y)        ((y) - (x))

//----------------------------------------------------------------------

//        Use the following for the L_infinity (Max) norm

//----------------------------------------------------------------------

// #define ANN_POW(v)                fabs(v)

// #define ANN_ROOT(x)                (x)

// #define ANN_SUM(x,y)                ((x) > (y) ? (x) : (y))

// #define ANN_DIFF(x,y)        (y)

//----------------------------------------------------------------------

//        Array types

//                The following array types are of basic interest.  A point is

//                just a dimensionless array of coordinates, a point array is a

//                dimensionless array of points.  A distance array is a

//                dimensionless array of distances and an index array is a

//                dimensionless array of point indices.  The latter two are used

//                when returning the results of k-nearest neighbor queries.

//----------------------------------------------------------------------

typedef ANNcoord* ANNpoint;                        // a point

typedef ANNpoint* ANNpointArray;        // an array of points 

typedef ANNdist*  ANNdistArray;                // an array of distances 

typedef ANNidx*   ANNidxArray;                // an array of point indices

//----------------------------------------------------------------------

//        Basic point and array utilities:

//                The following procedures are useful supplements to ANN's nearest

//                neighbor capabilities.

//

//                annDist():

//                        Computes the (squared) distance between a pair of points.

//                        Note that this routine is not used internally by ANN for

//                        computing distance calculations.  For reasons of efficiency

//                        this is done using incremental distance calculation.  Thus,

//                        this routine cannot be modified as a method of changing the

//                        metric.

//

//                Because points (somewhat like strings in C) are stored as

//                pointers.  Consequently, creating and destroying copies of

//                points may require storage allocation.  These procedures do

//                this.

//

//                annAllocPt() and annDeallocPt():

//                                Allocate a deallocate storage for a single point, and

//                                return a pointer to it.  The argument to AllocPt() is

//                                used to initialize all components.

//

//                annAllocPts() and annDeallocPts():

//                                Allocate and deallocate an array of points as well a

//                                place to store their coordinates, and initializes the

//                                points to point to their respective coordinates.  It

//                                allocates point storage in a contiguous block large

//                                enough to store all the points.  It performs no

//                                initialization.

//

//                annCopyPt():

//                                Creates a copy of a given point, allocating space for

//                                the new point.  It returns a pointer to the newly

//                                allocated copy.

//----------------------------------------------------------------------

DLL_API ANNdist annDist(

        int                                dim,                // dimension of space

        ANNpoint                p,                        // points

        ANNpoint                q);

DLL_API ANNpoint annAllocPt(

        int                                dim,                // dimension

        ANNcoord                c = 0);                // coordinate value (all equal)

DLL_API ANNpointArray annAllocPts(

        int                                n,                        // number of points

        int                                dim);                // dimension

DLL_API void annDeallocPt(

        ANNpoint                &p);                // deallocate 1 point

DLL_API void annDeallocPts(

        ANNpointArray        &pa);                // point array

DLL_API ANNpoint annCopyPt(

        int                                dim,                // dimension

        ANNpoint                source);        // point to copy

//----------------------------------------------------------------------

//Overall structure: ANN supports a number of different data structures

//for approximate and exact nearest neighbor searching.  These are:

//

//                ANNbruteForce        A simple brute-force search structure.

//                ANNkd_tree                A kd-tree tree search structure.  ANNbd_tree

//                A bd-tree tree search structure (a kd-tree with shrink

//                capabilities).

//

//                At a minimum, each of these data structures support k-nearest

//                neighbor queries.  The nearest neighbor query, annkSearch,

//                returns an integer identifier and the distance to the nearest

//                neighbor(s) and annRangeSearch returns the nearest points that

//                lie within a given query ball.

//

//                Each structure is built by invoking the appropriate constructor

//                and passing it (at a minimum) the array of points, the total

//                number of points and the dimension of the space.  Each structure

//                is also assumed to support a destructor and member functions

//                that return basic information about the point set.

//

//                Note that the array of points is not copied by the data

//                structure (for reasons of space efficiency), and it is assumed

//                to be constant throughout the lifetime of the search structure.

//

//                The search algorithm, annkSearch, is given the query point (q),

//                and the desired number of nearest neighbors to report (k), and

//                the error bound (eps) (whose default value is 0, implying exact

//                nearest neighbors).  It returns two arrays which are assumed to

//                contain at least k elements: one (nn_idx) contains the indices

//                (within the point array) of the nearest neighbors and the other

//                (dd) contains the squared distances to these nearest neighbors.

//

//                The search algorithm, annkFRSearch, is a fixed-radius kNN

//                search.  In addition to a query point, it is given a (squared)

//                radius bound.  (This is done for consistency, because the search

//                returns distances as squared quantities.) It does two things.

//                First, it computes the k nearest neighbors within the radius

//                bound, and second, it returns the total number of points lying

//                within the radius bound. It is permitted to set k = 0, in which

//                case it effectively answers a range counting query.  If the

//                error bound epsilon is positive, then the search is approximate

//                in the sense that it is free to ignore any point that lies

//                outside a ball of radius r/(1+epsilon), where r is the given

//                (unsquared) radius bound.

//

//                The generic object from which all the search structures are

//                dervied is given below.  It is a virtual object, and is useless

//                by itself.

//----------------------------------------------------------------------

class DLL_API ANNpointSet {

public:

        virtual ~ANNpointSet() {}                        // virtual distructor

        virtual void annkSearch(                        // approx k near neighbor search

                ANNpoint                q,                                // query point

                int                                k,                                // number of near neighbors to return

                ANNidxArray                nn_idx,                        // nearest neighbor array (modified)

                ANNdistArray        dd,                                // dist to near neighbors (modified)

                double                        eps=0.0                        // error bound

                ) = 0;                                                        // pure virtual (defined elsewhere)

        virtual int annkFRSearch(                        // approx fixed-radius kNN search

                ANNpoint                q,                                // query point

                ANNdist                        sqRad,                        // squared radius

                int                                k = 0,                        // number of near neighbors to return

                ANNidxArray                nn_idx = NULL,        // nearest neighbor array (modified)

                ANNdistArray        dd = NULL,                // dist to near neighbors (modified)

                double                        eps=0.0                        // error bound

                ) = 0;                                                        // pure virtual (defined elsewhere)

        virtual int theDim() = 0;                        // return dimension of space

        virtual int nPoints() = 0;                        // return number of points

                                                                                // return pointer to points

        virtual ANNpointArray thePoints() = 0;

};

//----------------------------------------------------------------------

//        Brute-force nearest neighbor search:

//                The brute-force search structure is very simple but inefficient.

//                It has been provided primarily for the sake of comparison with

//                and validation of the more complex search structures.

//

//                Query processing is the same as described above, but the value

//                of epsilon is ignored, since all distance calculations are

//                performed exactly.

//

//                WARNING: This data structure is very slow, and should not be

//                used unless the number of points is very small.

//

//                Internal information:

//                ---------------------

//                This data structure bascially consists of the array of points

//                (each a pointer to an array of coordinates).  The search is

//                performed by a simple linear scan of all the points.

//----------------------------------------------------------------------

class DLL_API ANNbruteForce: public ANNpointSet {

        int                                dim;                                // dimension

        int                                n_pts;                                // number of points

        ANNpointArray        pts;                                // point array

public:

        ANNbruteForce(                                                // constructor from point array

                ANNpointArray        pa,                                // point array

                int                                n,                                // number of points

                int                                dd);                        // dimension

        ~ANNbruteForce();                                        // destructor

        void annkSearch(                                        // approx k near neighbor search

                ANNpoint                q,                                // query point

                int                                k,                                // number of near neighbors to return

                ANNidxArray                nn_idx,                        // nearest neighbor array (modified)

                ANNdistArray        dd,                                // dist to near neighbors (modified)

                double                        eps=0.0);                // error bound

        int annkFRSearch(                                        // approx fixed-radius kNN search

                ANNpoint                q,                                // query point

                ANNdist                        sqRad,                        // squared radius

                int                                k = 0,                        // number of near neighbors to return

                ANNidxArray                nn_idx = NULL,        // nearest neighbor array (modified)

                ANNdistArray        dd = NULL,                // dist to near neighbors (modified)

                double                        eps=0.0);                // error bound

        int theDim()                                                // return dimension of space

                { return dim; }

        int nPoints()                                                // return number of points

                { return n_pts; }

        ANNpointArray thePoints()                        // return pointer to points

                {  return pts;  }

};

//----------------------------------------------------------------------

// kd- and bd-tree splitting and shrinking rules

//                kd-trees supports a collection of different splitting rules.

//                In addition to the standard kd-tree splitting rule proposed

//                by Friedman, Bentley, and Finkel, we have introduced a

//                number of other splitting rules, which seem to perform

//                as well or better (for the distributions we have tested).

//

//                The splitting methods given below allow the user to tailor

//                the data structure to the particular data set.  They are

//                are described in greater details in the kd_split.cc source

//                file.  The method ANN_KD_SUGGEST is the method chosen (rather

//                subjectively) by the implementors as the one giving the

//                fastest performance, and is the default splitting method.

//

//                As with splitting rules, there are a number of different

//                shrinking rules.  The shrinking rule ANN_BD_NONE does no

//                shrinking (and hence produces a kd-tree tree).  The rule

//                ANN_BD_SUGGEST uses the implementors favorite rule.

//----------------------------------------------------------------------

enum ANNsplitRule {

                ANN_KD_STD                                = 0,        // the optimized kd-splitting rule

                ANN_KD_MIDPT                        = 1,        // midpoint split

                ANN_KD_FAIR                                = 2,        // fair split

                ANN_KD_SL_MIDPT                        = 3,        // sliding midpoint splitting method

                ANN_KD_SL_FAIR                        = 4,        // sliding fair split method

                ANN_KD_SUGGEST                        = 5};        // the authors' suggestion for best

const int ANN_N_SPLIT_RULES                = 6;        // number of split rules

enum ANNshrinkRule {

                ANN_BD_NONE                                = 0,        // no shrinking at all (just kd-tree)

                ANN_BD_SIMPLE                        = 1,        // simple splitting

                ANN_BD_CENTROID                        = 2,        // centroid splitting

                ANN_BD_SUGGEST                        = 3};        // the authors' suggested choice

const int ANN_N_SHRINK_RULES        = 4;        // number of shrink rules

//----------------------------------------------------------------------

//        kd-tree:

//                The main search data structure supported by ANN is a kd-tree.

//                The main constructor is given a set of points and a choice of

//                splitting method to use in building the tree.

//

//                Construction:

//                -------------

//                The constructor is given the point array, number of points,

//                dimension, bucket size (default = 1), and the splitting rule

//                (default = ANN_KD_SUGGEST).  The point array is not copied, and

//                is assumed to be kept constant throughout the lifetime of the

//                search structure.  There is also a "load" constructor that

//                builds a tree from a file description that was created by the

//                Dump operation.

//

//                Search:

//                -------

//                There are two search methods:

//

//                        Standard search (annkSearch()):

//                                Searches nodes in tree-traversal order, always visiting

//                                the closer child first.

//                        Priority search (annkPriSearch()):

//                                Searches nodes in order of increasing distance of the

//                                associated cell from the query point.  For many

//                                distributions the standard search seems to work just

//                                fine, but priority search is safer for worst-case

//                                performance.

//

//                Printing:

//                ---------

//                There are two methods provided for printing the tree.  Print()

//                is used to produce a "human-readable" display of the tree, with

//                indenation, which is handy for debugging.  Dump() produces a

//                format that is suitable reading by another program.  There is a

//                "load" constructor, which constructs a tree which is assumed to

//                have been saved by the Dump() procedure.

//                

//                Performance and Structure Statistics:

//                -------------------------------------

//                The procedure getStats() collects statistics information on the

//                tree (its size, height, etc.)  See ANNperf.h for information on

//                the stats structure it returns.

//

//                Internal information:

//                ---------------------

//                The data structure consists of three major chunks of storage.

//                The first (implicit) storage are the points themselves (pts),

//                which have been provided by the users as an argument to the

//                constructor, or are allocated dynamically if the tree is built

//                using the load constructor).  These should not be changed during

//                the lifetime of the search structure.  It is the user's

//                responsibility to delete these after the tree is destroyed.

//

//                The second is the tree itself (which is dynamically allocated in

//                the constructor) and is given as a pointer to its root node

//                (root).  These nodes are automatically deallocated when the tree

//                is deleted.  See the file src/kd_tree.h for further information

//                on the structure of the tree nodes.

//

//                Each leaf of the tree does not contain a pointer directly to a

//                point, but rather contains a pointer to a "bucket", which is an

//                array consisting of point indices.  The third major chunk of

//                storage is an array (pidx), which is a large array in which all

//                these bucket subarrays reside.  (The reason for storing them

//                separately is the buckets are typically small, but of varying

//                sizes.  This was done to avoid fragmentation.)  This array is

//                also deallocated when the tree is deleted.

//

//                In addition to this, the tree consists of a number of other

//                pieces of information which are used in searching and for

//                subsequent tree operations.  These consist of the following:

//

//                dim                                                Dimension of space

//                n_pts                                        Number of points currently in the tree

//                n_max                                        Maximum number of points that are allowed

//                                                                in the tree

//                bkt_size                                Maximum bucket size (no. of points per leaf)

//                bnd_box_lo                                Bounding box low point

//                bnd_box_hi                                Bounding box high point

//                splitRule                                Splitting method used

//

//----------------------------------------------------------------------

//----------------------------------------------------------------------

// Some types and objects used by kd-tree functions

// See src/kd_tree.h and src/kd_tree.cpp for definitions

//----------------------------------------------------------------------

class ANNkdStats;                                // stats on kd-tree

class ANNkd_node;                                // generic node in a kd-tree

typedef ANNkd_node*        ANNkd_ptr;        // pointer to a kd-tree node

class DLL_API ANNkd_tree: public ANNpointSet {

protected:

        int                                dim;                                // dimension of space

        int                                n_pts;                                // number of points in tree

        int                                bkt_size;                        // bucket size

        ANNpointArray        pts;                                // the points

        ANNidxArray                pidx;                                // point indices (to pts array)

        ANNkd_ptr                root;                                // root of kd-tree

        ANNpoint                bnd_box_lo;                        // bounding box low point

        ANNpoint                bnd_box_hi;                        // bounding box high point

        void SkeletonTree(                                        // construct skeleton tree

                int                                n,                                // number of points

                int                                dd,                                // dimension

                int                                bs,                                // bucket size

                ANNpointArray pa = NULL,                // point array (optional)

                ANNidxArray pi = NULL);                        // point indices (optional)

public:

        ANNkd_tree(                                                        // build skeleton tree

                int                                n = 0,                        // number of points

                int                                dd = 0,                        // dimension

                int                                bs = 1);                // bucket size

        ANNkd_tree(                                                        // build from point array

                ANNpointArray        pa,                                // point array

                int                                n,                                // number of points

                int                                dd,                                // dimension

                int                                bs = 1,                        // bucket size

                ANNsplitRule        split = ANN_KD_SUGGEST);        // splitting method

        ANNkd_tree(                                                        // build from dump file

                std::istream&        in);                        // input stream for dump file

        ~ANNkd_tree();                                                // tree destructor

        void annkSearch(                                        // approx k near neighbor search

                ANNpoint                q,                                // query point

                int                                k,                                // number of near neighbors to return

                ANNidxArray                nn_idx,                        // nearest neighbor array (modified)

                ANNdistArray        dd,                                // dist to near neighbors (modified)

                double                        eps=0.0);                // error bound

        void annkPriSearch(                                 // priority k near neighbor search

                ANNpoint                q,                                // query point

                int                                k,                                // number of near neighbors to return

                ANNidxArray                nn_idx,                        // nearest neighbor array (modified)

                ANNdistArray        dd,                                // dist to near neighbors (modified)

                double                        eps=0.0);                // error bound

        int annkFRSearch(                                        // approx fixed-radius kNN search

                ANNpoint                q,                                // the query point

                ANNdist                        sqRad,                        // squared radius of query ball

                int                                k,                                // number of neighbors to return

                ANNidxArray                nn_idx = NULL,        // nearest neighbor array (modified)

                ANNdistArray        dd = NULL,                // dist to near neighbors (modified)

                double                        eps=0.0);                // error bound

        int theDim()                                                // return dimension of space

                { return dim; }

        int nPoints()                                                // return number of points

                { return n_pts; }

        ANNpointArray thePoints()                        // return pointer to points

                {  return pts;  }

        virtual void Print(                                        // print the tree (for debugging)

                ANNbool                        with_pts,                // print points as well?

                std::ostream&        out);                        // output stream

        virtual void Dump(                                        // dump entire tree

                ANNbool                        with_pts,                // print points as well?

                std::ostream&        out);                        // output stream

        virtual void getStats(                                // compute tree statistics

                ANNkdStats&                st);                        // the statistics (modified)

};                                                                

//----------------------------------------------------------------------

//        Box decomposition tree (bd-tree)

//                The bd-tree is inherited from a kd-tree.  The main difference

//                in the bd-tree and the kd-tree is a new type of internal node

//                called a shrinking node (in the kd-tree there is only one type

//                of internal node, a splitting node).  The shrinking node

//                makes it possible to generate balanced trees in which the

//                cells have bounded aspect ratio, by allowing the decomposition

//                to zoom in on regions of dense point concentration.  Although

//                this is a nice idea in theory, few point distributions are so

//                densely clustered that this is really needed.

//----------------------------------------------------------------------

class DLL_API ANNbd_tree: public ANNkd_tree {

public:

        ANNbd_tree(                                                        // build skeleton tree

                int                                n,                                // number of points

                int                                dd,                                // dimension

                int                                bs = 1)                        // bucket size

                : ANNkd_tree(n, dd, bs) {}                // build base kd-tree

        ANNbd_tree(                                                        // build from point array

                ANNpointArray        pa,                                // point array

                int                                n,                                // number of points

                int                                dd,                                // dimension

                int                                bs = 1,                        // bucket size

                ANNsplitRule        split  = ANN_KD_SUGGEST,        // splitting rule

                ANNshrinkRule        shrink = ANN_BD_SUGGEST);        // shrinking rule

        ANNbd_tree(                                                        // build from dump file

                std::istream&        in);                        // input stream for dump file

};

//----------------------------------------------------------------------

//        Other functions

//        annMaxPtsVisit                Sets a limit on the maximum number of points

//                                                to visit in the search.

//  annClose                        Can be called when all use of ANN is finished.

//                                                It clears up a minor memory leak.

//----------------------------------------------------------------------

DLL_API void annMaxPtsVisit(        // max. pts to visit in search

        int                                maxPts);        // the limit

DLL_API void annClose();                // called to end use of ANN

#endif