Quadrotor

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

// File:                        bd_tree.h

// Programmer:                David Mount

// Description:                Declarations for standard bd-tree routines

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

//        Revision 1.0  04/01/05

//                Changed IN, OUT to ANN_IN, ANN_OUT

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

#ifndef ANN_bd_tree_H

#define ANN_bd_tree_H

#include <ANN/ANNx.h>                                        // all ANN includes

#include "kd_tree.h"                                        // kd-tree includes

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

//        bd-tree shrinking node.

//                The main addition in the bd-tree is the shrinking node, which

//                is declared here.

//

//                Shrinking nodes are defined by list of orthogonal halfspaces.

//                These halfspaces define a (possibly unbounded) orthogonal

//                rectangle.  There are two children, in and out.  Points that

//                lie within this rectangle are stored in the in-child, and the

//                other points are stored in the out-child.

//

//                We use a list of orthogonal halfspaces rather than an

//                orthogonal rectangle object because typically the number of

//                sides of the shrinking box will be much smaller than the

//                worst case bound of 2*dim.

//

//                BEWARE: Note that constructor just copies the pointer to the

//                bounding array, but the destructor deallocates it.  This is

//                rather poor practice, but happens to be convenient.  The list

//                is allocated in the bd-tree building procedure rbd_tree() just

//                prior to construction, and is used for no other purposes.

//

//                WARNING: In the near neighbor searching code it is assumed that

//                the list of bounding halfspaces is irredundant, meaning that there

//                are no two distinct halfspaces in the list with the same outward

//                pointing normals.

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

class ANNbd_shrink : public ANNkd_node        // splitting node of a kd-tree

{

        int                                        n_bnds;                        // number of bounding halfspaces

        ANNorthHSArray                bnds;                        // list of bounding halfspaces

        ANNkd_ptr                        child[2];                // in and out children

public:

        ANNbd_shrink(                                                // constructor

                int                                nb,                                // number of bounding halfspaces

                ANNorthHSArray        bds,                        // list of bounding halfspaces

                ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL)        // children

                {

                        n_bnds                        = nb;                                // cutting dimension

                        bnds                        = bds;                                // assign bounds

                        child[ANN_IN]        = ic;                                // set children

                        child[ANN_OUT]        = oc;

                }

        ~ANNbd_shrink()                                                // destructor

                {

                        if (child[ANN_IN]!= NULL && child[ANN_IN]!=  KD_TRIVIAL) 

                                delete child[ANN_IN];

                        if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL) 

                                delete child[ANN_OUT];

                        if (bnds != NULL)

                                delete [] bnds;                        // delete bounds

                }

        virtual void getStats(                                                // get tree statistics

                                int dim,                                                // dimension of space

                                ANNkdStats &st,                                        // statistics

                                ANNorthRect &bnd_box);                        // bounding box

        virtual void print(int level, ostream &out);// print node

        virtual void dump(ostream &out);                        // dump node

        virtual void ann_search(ANNdist);                        // standard search

        virtual void ann_pri_search(ANNdist);                // priority search

        virtual void ann_FR_search(ANNdist);                 // fixed-radius search

};

#endif