diff options
Diffstat (limited to 'geom_bottleneck/bottleneck/include')
17 files changed, 0 insertions, 2818 deletions
diff --git a/geom_bottleneck/bottleneck/include/ANN/ANN.h b/geom_bottleneck/bottleneck/include/ANN/ANN.h deleted file mode 100644 index 004dfe2..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/ANN.h +++ /dev/null @@ -1,917 +0,0 @@ -//---------------------------------------------------------------------- -// File: ANN.h -// Programmer: Sunil Arya and David Mount -// Description: Basic include file for approximate nearest -// neighbor searching. -// Last modified: 01/27/10 (Version 1.1.2) -//---------------------------------------------------------------------- -// Copyright (c) 1997-2010 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 -// Revision 1.1.2 01/27/10 -// Fixed minor compilation bugs for new versions of gcc -// -------------------------------------------------------------------- -// 2015 - modified by A. Nigmetov to support deletion of points -//---------------------------------------------------------------------- - -//---------------------------------------------------------------------- -// 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 - -// A. Nigmetov: ANN code is integrated into bottleneck library, -// CMake will take care of correct __declspec, no need to define DLL_API -#define DLL_API -//#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> // standard lib includes -#include <cmath> // math includes -#include <cstring> // C-style strings -#include <vector> -#include <assert.h> - -//---------------------------------------------------------------------- -// 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.2" // ANN version and information -#define ANNversionCmt "" -#define ANNcopyright "David M. Mount and Sunil Arya" -#define ANNlatestRev "Jan 27, 2010" - -#include "def_debug_bt.h" - -#ifndef FOR_R_TDA -#include <iostream> // I/O streams -#endif - -namespace geom_bt { -//---------------------------------------------------------------------- -// 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 - - -//---------------------------------------------------------------------- -// Orthogonal (axis aligned) rectangle -// Orthogonal rectangles are represented by two points, one -// for the lower left corner (min coordinates) and the other -// for the upper right corner (max coordinates). -// -// The constructor initializes from either a pair of coordinates, -// pair of points, or another rectangle. Note that all constructors -// allocate new point storage. The destructor deallocates this -// storage. -// -// BEWARE: Orthogonal rectangles should be passed ONLY BY REFERENCE. -// (C++'s default copy constructor will not allocate new point -// storage, then on return the destructor free's storage, and then -// you get into big trouble in the calling procedure.) -//---------------------------------------------------------------------- - -class DLL_API ANNorthRect { -public: - ANNpoint lo; // rectangle lower bounds - ANNpoint hi; // rectangle upper bounds -// - ANNorthRect( // basic constructor - int dd, // dimension of space - ANNcoord l=0, // default is empty - ANNcoord h=0) - { lo = annAllocPt(dd, l); hi = annAllocPt(dd, h); } - - ANNorthRect( // (almost a) copy constructor - int dd, // dimension - const ANNorthRect &r) // rectangle to copy - { lo = annCopyPt(dd, r.lo); hi = annCopyPt(dd, r.hi); } - - ANNorthRect( // construct from points - int dd, // dimension - ANNpoint l, // low point - ANNpoint h) // hight point - { lo = annCopyPt(dd, l); hi = annCopyPt(dd, h); } - - ~ANNorthRect() // destructor - { annDeallocPt(lo); annDeallocPt(hi); } - - ANNbool inside(const int dim, ANNpoint p) const;// is point p inside rectangle? - bool contains(const int dim, const ANNorthRect& r) const; - bool intersects(const int dim, const ANNorthRect& r) const; -}; - - -//---------------------------------------------------------------------- -//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 - // for kd-trees with deletion - //ANN_KD_STD_WD = 6, - //ANN_KD_MIDPT_WD = 7, - //ANN_KD_SL_MIDPT_WD = 8 - }; -const int ANN_N_SPLIT_RULES = 6; // number of split rules -//const int ANN_N_SPLIT_RULES = 9; // 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 ANNkd_leaf; - -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 - -#ifndef FOR_R_TDA - ANNkd_tree( // build from dump file - std::istream& in); // input stream for dump file -#endif - - ~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; } - -#ifndef FOR_R_TDA - 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 -#endif - - virtual void getStats( // compute tree statistics - ANNkdStats& st); // the statistics (modified) - - /////////////////////////////////////////////////////////////// - // for deletion - std::vector<ANNkd_leaf*> pointToLeafVec; - std::vector<bool> isDeleted; // will be used to check implementation; - //TODO remove after testing - void delete_point(const int point_idx); - int actual_num_points; - int getActualNumPoints(void) const { return actual_num_points; } - void range_search(const ANNorthRect& region, std::vector<size_t>& pointIdices); -}; - -//---------------------------------------------------------------------- -// 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 - -#ifndef FOR_R_TDA - ANNbd_tree( // build from dump file - std::istream& in); // input stream for dump file -#endif -}; - -//---------------------------------------------------------------------- -// 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 diff --git a/geom_bottleneck/bottleneck/include/ANN/ANNperf.h b/geom_bottleneck/bottleneck/include/ANN/ANNperf.h deleted file mode 100644 index d242266..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/ANNperf.h +++ /dev/null @@ -1,225 +0,0 @@ -//---------------------------------------------------------------------- -// File: ANNperf.h -// Programmer: Sunil Arya and David Mount -// Last modified: 03/04/98 (Release 0.1) -// Description: Include file for ANN performance stats -// -// Some of the code for statistics gathering has been adapted -// from the SmplStat.h package in the g++ library. -//---------------------------------------------------------------------- -// 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 ANN_ prefix to avoid name conflicts. -//---------------------------------------------------------------------- - -#ifndef ANNperf_H -#define ANNperf_H - -//---------------------------------------------------------------------- -// basic includes -//---------------------------------------------------------------------- - -#include <ANN/ANN.h> // basic ANN includes - -namespace geom_bt { -//---------------------------------------------------------------------- -// kd-tree stats object -// This object is used for collecting information about a kd-tree -// or bd-tree. -//---------------------------------------------------------------------- - -class ANNkdStats { // stats on kd-tree -public: - int dim; // dimension of space - int n_pts; // no. of points - int bkt_size; // bucket size - int n_lf; // no. of leaves (including trivial) - int n_tl; // no. of trivial leaves (no points) - int n_spl; // no. of splitting nodes - int n_shr; // no. of shrinking nodes (for bd-trees) - int depth; // depth of tree - float sum_ar; // sum of leaf aspect ratios - float avg_ar; // average leaf aspect ratio - // - // reset stats - void reset(int d=0, int n=0, int bs=0) - { - dim = d; n_pts = n; bkt_size = bs; - n_lf = n_tl = n_spl = n_shr = depth = 0; - sum_ar = avg_ar = 0.0; - } - - ANNkdStats() // basic constructor - { reset(); } - - void merge(const ANNkdStats &st); // merge stats from child -}; - -//---------------------------------------------------------------------- -// ANNsampStat -// A sample stat collects numeric (double) samples and returns some -// simple statistics. Its main functions are: -// -// reset() Reset to no samples. -// += x Include sample x. -// samples() Return number of samples. -// mean() Return mean of samples. -// stdDev() Return standard deviation -// min() Return minimum of samples. -// max() Return maximum of samples. -//---------------------------------------------------------------------- -class DLL_API ANNsampStat { - int n; // number of samples - double sum; // sum - double sum2; // sum of squares - double minVal, maxVal; // min and max -public : - void reset() // reset everything - { - n = 0; - sum = sum2 = 0; - minVal = ANN_DBL_MAX; - maxVal = -ANN_DBL_MAX; - } - - ANNsampStat() { reset(); } // constructor - - void operator+=(double x) // add sample - { - n++; sum += x; sum2 += x*x; - if (x < minVal) minVal = x; - if (x > maxVal) maxVal = x; - } - - int samples() { return n; } // number of samples - - double mean() { return sum/n; } // mean - - // standard deviation - double stdDev() { return sqrt((sum2 - (sum*sum)/n)/(n-1));} - - double min() { return minVal; } // minimum - double max() { return maxVal; } // maximum -}; - -//---------------------------------------------------------------------- -// Operation count updates -//---------------------------------------------------------------------- - -#ifdef ANN_PERF - #define ANN_FLOP(n) {ann_Nfloat_ops += (n);} - #define ANN_LEAF(n) {ann_Nvisit_lfs += (n);} - #define ANN_SPL(n) {ann_Nvisit_spl += (n);} - #define ANN_SHR(n) {ann_Nvisit_shr += (n);} - #define ANN_PTS(n) {ann_Nvisit_pts += (n);} - #define ANN_COORD(n) {ann_Ncoord_hts += (n);} -#else - #define ANN_FLOP(n) - #define ANN_LEAF(n) - #define ANN_SPL(n) - #define ANN_SHR(n) - #define ANN_PTS(n) - #define ANN_COORD(n) -#endif - -//---------------------------------------------------------------------- -// Performance statistics -// The following data and routines are used for computing performance -// statistics for nearest neighbor searching. Because these routines -// can slow the code down, they can be activated and deactiviated by -// defining the ANN_PERF variable, by compiling with the option: -// -DANN_PERF -//---------------------------------------------------------------------- - -//---------------------------------------------------------------------- -// Global counters for performance measurement -// -// visit_lfs The number of leaf nodes visited in the -// tree. -// -// visit_spl The number of splitting nodes visited in the -// tree. -// -// visit_shr The number of shrinking nodes visited in the -// tree. -// -// visit_pts The number of points visited in all the -// leaf nodes visited. Equivalently, this -// is the number of points for which distance -// calculations are performed. -// -// coord_hts The number of times a coordinate of a -// data point is accessed. This is generally -// less than visit_pts*d if partial distance -// calculation is used. This count is low -// in the sense that if a coordinate is hit -// many times in the same routine we may -// count it only once. -// -// float_ops The number of floating point operations. -// This includes all operations in the heap -// as well as distance calculations to boxes. -// -// average_err The average error of each query (the -// error of the reported point to the true -// nearest neighbor). For k nearest neighbors -// the error is computed k times. -// -// rank_err The rank error of each query (the difference -// in the rank of the reported point and its -// true rank). -// -// data_pts The number of data points. This is not -// a counter, but used in stats computation. -//---------------------------------------------------------------------- - -extern int ann_Ndata_pts; // number of data points -extern int ann_Nvisit_lfs; // number of leaf nodes visited -extern int ann_Nvisit_spl; // number of splitting nodes visited -extern int ann_Nvisit_shr; // number of shrinking nodes visited -extern int ann_Nvisit_pts; // visited points for one query -extern int ann_Ncoord_hts; // coordinate hits for one query -extern int ann_Nfloat_ops; // floating ops for one query -extern ANNsampStat ann_visit_lfs; // stats on leaf nodes visits -extern ANNsampStat ann_visit_spl; // stats on splitting nodes visits -extern ANNsampStat ann_visit_shr; // stats on shrinking nodes visits -extern ANNsampStat ann_visit_nds; // stats on total nodes visits -extern ANNsampStat ann_visit_pts; // stats on points visited -extern ANNsampStat ann_coord_hts; // stats on coordinate hits -extern ANNsampStat ann_float_ops; // stats on floating ops -//---------------------------------------------------------------------- -// The following need to be part of the public interface, because -// they are accessed outside the DLL in ann_test.cpp. -//---------------------------------------------------------------------- -DLL_API extern ANNsampStat ann_average_err; // average error -DLL_API extern ANNsampStat ann_rank_err; // rank error - -//---------------------------------------------------------------------- -// Declaration of externally accessible routines for statistics -//---------------------------------------------------------------------- - -DLL_API void annResetStats(int data_size); // reset stats for a set of queries - -DLL_API void annResetCounts(); // reset counts for one queries - -DLL_API void annUpdateStats(); // update stats with current counts - -DLL_API void annPrintStats(ANNbool validate); // print statistics for a run - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/ANNx.h b/geom_bottleneck/bottleneck/include/ANN/ANNx.h deleted file mode 100644 index 0c9e190..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/ANNx.h +++ /dev/null @@ -1,127 +0,0 @@ -//---------------------------------------------------------------------- -// File: ANNx.h -// Programmer: Sunil Arya and David Mount -// Description: Internal include file for ANN -// Last modified: 01/27/10 (Version 1.1.2) -// -// These declarations are of use in manipulating some of -// the internal data objects appearing in ANN, but are not -// needed for applications just using the nearest neighbor -// search. -// -// Typical users of ANN should not need to access this file. -//---------------------------------------------------------------------- -// Copyright (c) 1997-2010 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 LO, HI, IN, OUT to ANN_LO, ANN_HI, etc. -// Revision 1.1.2 01/27/10 -// Fixed minor compilation bugs for new versions of gcc -//---------------------------------------------------------------------- - -#ifndef ANNx_H -#define ANNx_H - -#include <iomanip> // I/O manipulators -#include <ANN/ANN.h> // ANN includes - -namespace geom_bt { - -//---------------------------------------------------------------------- -// Global constants and types -//---------------------------------------------------------------------- -enum {ANN_LO=0, ANN_HI=1}; // splitting indices -enum {ANN_IN=0, ANN_OUT=1}; // shrinking indices - // what to do in case of error -enum ANNerr {ANNwarn = 0, ANNabort = 1}; - -//---------------------------------------------------------------------- -// Maximum number of points to visit -// We have an option for terminating the search early if the -// number of points visited exceeds some threshold. If the -// threshold is 0 (its default) this means there is no limit -// and the algorithm applies its normal termination condition. -//---------------------------------------------------------------------- - -extern int ANNmaxPtsVisited; // maximum number of pts visited -extern int ANNptsVisited; // number of pts visited in search - -//---------------------------------------------------------------------- -// Global function declarations -//---------------------------------------------------------------------- - -void annError( // ANN error routine - const char* msg, // error message - ANNerr level); // level of error - -void annPrintPt( // print a point - ANNpoint pt, // the point - int dim, // the dimension - std::ostream &out); // output stream - -void annAssignRect( // assign one rect to another - int dim, // dimension (both must be same) - ANNorthRect &dest, // destination (modified) - const ANNorthRect &source); // source - -//---------------------------------------------------------------------- -// Orthogonal (axis aligned) halfspace -// An orthogonal halfspace is represented by an integer cutting -// dimension cd, coordinate cutting value, cv, and side, sd, which is -// either +1 or -1. Our convention is that point q lies in the (closed) -// halfspace if (q[cd] - cv)*sd >= 0. -//---------------------------------------------------------------------- - -class ANNorthHalfSpace { -public: - int cd; // cutting dimension - ANNcoord cv; // cutting value - int sd; // which side -// - ANNorthHalfSpace() // default constructor - { cd = 0; cv = 0; sd = 0; } - - ANNorthHalfSpace( // basic constructor - int cdd, // dimension of space - ANNcoord cvv, // cutting value - int sdd) // side - { cd = cdd; cv = cvv; sd = sdd; } - - ANNbool in(ANNpoint q) const // is q inside halfspace? - { return (ANNbool) ((q[cd] - cv)*sd >= 0); } - - ANNbool out(ANNpoint q) const // is q outside halfspace? - { return (ANNbool) ((q[cd] - cv)*sd < 0); } - - ANNdist dist(ANNpoint q) const // (squared) distance from q - { return (ANNdist) ANN_POW(q[cd] - cv); } - - void setLowerBound(int d, ANNpoint p)// set to lower bound at p[i] - { cd = d; cv = p[d]; sd = +1; } - - void setUpperBound(int d, ANNpoint p)// set to upper bound at p[i] - { cd = d; cv = p[d]; sd = -1; } - - void project(ANNpoint &q) // project q (modified) onto halfspace - { if (out(q)) q[cd] = cv; } -}; - - // array of halfspaces -typedef ANNorthHalfSpace *ANNorthHSArray; - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/bd_tree.h b/geom_bottleneck/bottleneck/include/ANN/bd_tree.h deleted file mode 100644 index 38cecb7..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/bd_tree.h +++ /dev/null @@ -1,105 +0,0 @@ -//---------------------------------------------------------------------- -// 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 -#include "def_debug_bt.h" - -namespace geom_bt { -//---------------------------------------------------------------------- -// 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 -#ifndef FOR_R_TDA - virtual void dump(ostream &out); // dump node -#endif - - 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 diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_fix_rad_search.h b/geom_bottleneck/bottleneck/include/ANN/kd_fix_rad_search.h deleted file mode 100644 index 36f9528..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_fix_rad_search.h +++ /dev/null @@ -1,46 +0,0 @@ -//---------------------------------------------------------------------- -// File: kd_fix_rad_search.h -// Programmer: Sunil Arya and David Mount -// Description: Standard kd-tree fixed-radius kNN search -// Last modified: 05/03/05 (Version 1.1) -//---------------------------------------------------------------------- -// 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 1.1 05/03/05 -// Initial release -//---------------------------------------------------------------------- - -#ifndef ANN_kd_fix_rad_search_H -#define ANN_kd_fix_rad_search_H - -#include "kd_tree.h" // kd-tree declarations -#include "kd_util.h" // kd-tree utilities -#include "pr_queue_k.h" // k-element priority queue - -#include <ANN/ANNperf.h> // performance evaluation - -namespace geom_bt { -//---------------------------------------------------------------------- -// Global variables -// These are active for the life of each call to -// annRangeSearch(). They are set to save the number of -// variables that need to be passed among the various search -// procedures. -//---------------------------------------------------------------------- - -extern ANNpoint ANNkdFRQ; // query point (static copy) - -} -#endif
\ No newline at end of file diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_pr_search.h b/geom_bottleneck/bottleneck/include/ANN/kd_pr_search.h deleted file mode 100644 index 1f4c4fc..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_pr_search.h +++ /dev/null @@ -1,51 +0,0 @@ -//---------------------------------------------------------------------- -// File: kd_pr_search.h -// Programmer: Sunil Arya and David Mount -// Description: Priority kd-tree search -// 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_pr_search_H -#define ANN_kd_pr_search_H - -#include "kd_tree.h" // kd-tree declarations -#include "kd_util.h" // kd-tree utilities -#include "pr_queue.h" // priority queue declarations -#include "pr_queue_k.h" // k-element priority queue - -#include <ANN/ANNperf.h> // performance evaluation - -namespace geom_bt { -//---------------------------------------------------------------------- -// Global variables -// Active for the life of each call to Appx_Near_Neigh() or -// Appx_k_Near_Neigh(). -//---------------------------------------------------------------------- - -extern double ANNprEps; // the error bound -extern int ANNprDim; // dimension of space -extern ANNpoint ANNprQ; // query point -extern double ANNprMaxErr; // max tolerable squared error -extern ANNpointArray ANNprPts; // the points -extern ANNpr_queue *ANNprBoxPQ; // priority queue for boxes -extern ANNmin_k *ANNprPointMK; // set of k closest points - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_search.h b/geom_bottleneck/bottleneck/include/ANN/kd_search.h deleted file mode 100644 index 7491779..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_search.h +++ /dev/null @@ -1,50 +0,0 @@ -//---------------------------------------------------------------------- -// File: kd_search.h -// Programmer: Sunil Arya and David Mount -// Description: Standard kd-tree search -// 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_search_H -#define ANN_kd_search_H - -#include "kd_tree.h" // kd-tree declarations -#include "kd_util.h" // kd-tree utilities -#include "pr_queue_k.h" // k-element priority queue - -#include <ANN/ANNperf.h> // performance evaluation - -namespace geom_bt { -//---------------------------------------------------------------------- -// More global variables -// These are active for the life of each call to annkSearch(). They -// are set to save the number of variables that need to be passed -// among the various search procedures. -//---------------------------------------------------------------------- - -extern int ANNkdDim; // dimension of space (static copy) -extern ANNpoint ANNkdQ; // query point (static copy) -extern double ANNkdMaxErr; // max tolerable squared error -extern ANNpointArray ANNkdPts; // the points (static copy) -extern ANNmin_k *ANNkdPointMK; // set of k closest points -extern int ANNptsVisited; // number of points visited - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_split.h b/geom_bottleneck/bottleneck/include/ANN/kd_split.h deleted file mode 100644 index 62533a1..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_split.h +++ /dev/null @@ -1,123 +0,0 @@ -//---------------------------------------------------------------------- -// File: kd_split.h -// Programmer: Sunil Arya and David Mount -// Description: Methods for splitting 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_SPLIT_H -#define ANN_KD_SPLIT_H - -#include "kd_tree.h" // kd-tree definitions - -namespace geom_bt { -//---------------------------------------------------------------------- -// External entry points -// These are all splitting procedures for kd-trees. -//---------------------------------------------------------------------- - -void kd_split( // standard (optimized) kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -void midpt_split( // midpoint kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -void sl_midpt_split( // sliding midpoint kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -void fair_split( // fair-split kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -void sl_fair_split( // sliding fair-split kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -//////////////////////////////////////////////////////////////////////////////// -// -void kd_split_wd( // standard (optimized) kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo, // num of points on low side (returned) - int &cut_pt_idx); // index of cutting point (returned) - -void midpt_split_wd( // midpoint kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo, // num of points on low side (returned) - int &cut_pt_idx); // index of cutting point (returned) - -void sl_midpt_split_wd( // sliding midpoint kd-splitter - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo, // num of points on low side (returned) - int &cut_pt_idx); // index of cutting point (returned) - - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_tree.h b/geom_bottleneck/bottleneck/include/ANN/kd_tree.h deleted file mode 100644 index a1e53e5..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_tree.h +++ /dev/null @@ -1,260 +0,0 @@ -//---------------------------------------------------------------------- -// File: kd_tree.h -// Programmer: Sunil Arya and David Mount -// Description: Declarations for standard kd-tree routines -// Last modified: 05/03/05 (Version 1.1) -//---------------------------------------------------------------------- -// 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.1 05/03/05 -// Added fixed radius kNN search -// -------------------------------------------------------------------- -// 2015 - modified by A. Nigmetov to support deletion of points -//---------------------------------------------------------------------- - -#ifndef ANN_kd_tree_H -#define ANN_kd_tree_H - -#include <utility> // for std::pair -#include <ANN/ANNx.h> // all ANN includes -#include "def_debug_bt.h" - -using namespace std; // make std:: available - -namespace geom_bt { -//---------------------------------------------------------------------- -// Generic kd-tree node -// -// Nodes in kd-trees are of two types, splitting nodes which contain -// splitting information (a splitting hyperplane orthogonal to one -// of the coordinate axes) and leaf nodes which contain point -// information (an array of points stored in a bucket). This is -// handled by making a generic class kd_node, which is essentially an -// empty shell, and then deriving the leaf and splitting nodes from -// this. -//---------------------------------------------------------------------- -//class ANNkd_node; -class ANNkd_split; - -//typedef std::pair<ANNidx, ANNkd_node*> ANNreplaceSearchRes; - -class ANNkd_node{ // generic kd-tree node (empty shell) -protected: - int actual_num_points; // - ANNkd_split* parent; -public: - ANNkd_split* getParent() const { return parent; } - void setParent(ANNkd_split* par) { parent = par; } - int getNumPoints() const { return actual_num_points; } - void setNumPoints(int n) { assert(n >=0 ); actual_num_points = n; } - void decNumPoints() { assert(actual_num_points > 0); actual_num_points--; } - virtual ~ANNkd_node() {} // virtual distroyer - - virtual void ann_search(ANNdist) = 0; // tree search - virtual void ann_pri_search(ANNdist) = 0; // priority search - virtual void ann_FR_search(ANNdist) = 0; // fixed-radius search - - virtual void getStats( // get tree statistics - int dim, // dimension of space - ANNkdStats &st, // statistics - ANNorthRect &bnd_box) = 0; // bounding box - // print node - virtual void print(int level, ostream &out) = 0; -#ifndef FOR_R_TDA - virtual void dump(ostream &out) = 0; // dump node -#endif - - friend class ANNkd_tree; // allow kd-tree to access us - - //////////////////////////////////////////////////////////////////////// - // deletion - virtual void delete_point(const int point_idx) {} - // range search - virtual void range_search(const ANNorthRect& region, // query region - int ANNkdDim, // dimension of points, - ANNpointArray ANNkdPts, // array of points - ANNorthRect& bnd_box, // bounding box of the current node, - // comes precomputed from the caller - std::vector<size_t>& pointIdices) {} // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& pointIdices) {} // add all points to pointIdices -}; - - - -//---------------------------------------------------------------------- -// kd-splitting function: -// kd_splitter is a pointer to a splitting routine for preprocessing. -// Different splitting procedures result in different strategies -// for building the tree. -//---------------------------------------------------------------------- -typedef void (*ANNkd_splitter)( // splitting routine for kd-trees - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices (permuted on return) - const ANNorthRect &bnds, // bounding rectangle for cell - int n, // number of points - int dim, // dimension of space - int &cut_dim, // cutting dimension (returned) - ANNcoord &cut_val, // cutting value (returned) - int &n_lo); // num of points on low side (returned) - -//---------------------------------------------------------------------- -// Leaf kd-tree node -// Leaf nodes of the kd-tree store the set of points associated -// with this bucket, stored as an array of point indices. These -// are indices in the array points, which resides with the -// root of the kd-tree. We also store the number of points -// that reside in this bucket. -//---------------------------------------------------------------------- - -class ANNkd_leaf: public ANNkd_node // leaf node for kd-tree -{ - int n_pts; - ANNidxArray bkt; // bucket of points -public: - ANNkd_leaf( // constructor - int n, // number of points - ANNidxArray b) : // bucket - n_pts(n), - bkt(b) - { - setNumPoints(n); - parent = NULL; - } - - ~ANNkd_leaf() { } // destructor (none) - - 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 -#ifndef FOR_R_TDA - virtual void dump(ostream &out); // dump node -#endif - - virtual void ann_search(ANNdist); // standard search - virtual void ann_pri_search(ANNdist); // priority search - virtual void ann_FR_search(ANNdist); // fixed-radius search - // deletion - void delete_point(const int point_idx, const bool killYourself); - // range search - virtual void range_search(const ANNorthRect& region, // query region - int ANNkdDim, // dimension of points, - ANNpointArray ANNkdPts, // array of points - ANNorthRect& bnd_box, // bounding box of the current node, - // comes precomputed from the caller - std::vector<size_t>& pointIdices); // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& pointIdices); // add all points to pointIdices -}; - -//---------------------------------------------------------------------- -// KD_TRIVIAL is a special pointer to an empty leaf node. Since -// some splitting rules generate many (more than 50%) trivial -// leaves, we use this one shared node to save space. -// -// The pointer is initialized to NULL, but whenever a kd-tree is -// created, we allocate this node, if it has not already been -// allocated. This node is *never* deallocated, so it produces -// a small memory leak. -//---------------------------------------------------------------------- - -extern ANNkd_leaf *KD_TRIVIAL; // trivial (empty) leaf node - -//---------------------------------------------------------------------- -// kd-tree splitting node. -// Splitting nodes contain a cutting dimension and a cutting value. -// These indicate the axis-parellel plane which subdivide the -// box for this node. The extent of the bounding box along the -// cutting dimension is maintained (this is used to speed up point -// to box distance calculations) [we do not store the entire bounding -// box since this may be wasteful of space in high dimensions]. -// We also store pointers to the 2 children. -//---------------------------------------------------------------------- - -class ANNkd_split : public ANNkd_node // splitting node of a kd-tree -{ - int cut_dim; // dim orthogonal to cutting plane - ANNcoord cut_val; // location of cutting plane - ANNcoord cd_bnds[2]; // lower and upper bounds of - // rectangle along cut_dim - ANNkd_ptr child[2]; // left and right children -public: - ANNkd_split( // constructor - int cd, // cutting dimension - ANNcoord cv, // cutting value - ANNcoord lv, ANNcoord hv, // low and high values - ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) // children - { - cut_dim = cd; // cutting dimension - cut_val = cv; // cutting value - cd_bnds[ANN_LO] = lv; // lower bound for rectangle - cd_bnds[ANN_HI] = hv; // upper bound for rectangle - child[ANN_LO] = lc; // left child - child[ANN_HI] = hc; // right child - parent = NULL; - } - - - ~ANNkd_split() // destructor - { - if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL) - delete child[ANN_LO]; - if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL) - delete child[ANN_HI]; - } - - 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 -#ifndef FOR_R_TDA - virtual void dump(ostream &out); // dump node -#endif - - virtual void ann_search(ANNdist); // standard search - virtual void ann_pri_search(ANNdist); // priority search - virtual void ann_FR_search(ANNdist); // fixed-radius search - - /////// - void delete_leaf(ANNkd_leaf* childToDelete); // set the leaf to KD_TRIVIAL - // range search - virtual void range_search(const ANNorthRect& region, // query region - int ANNkdDim, // dimension of points, - ANNpointArray ANNkdPts, // array of points - ANNorthRect& bnd_box, // bounding box of the current node, - // comes precomputed from the caller - std::vector<size_t>& pointIdices); // indices of points are returned in this vector - virtual void range_search_add(std::vector<size_t>& pointIdices); // add all points to pointIdices -}; - -//---------------------------------------------------------------------- -// External entry points -//---------------------------------------------------------------------- - -ANNkd_ptr rkd_tree( // recursive construction of kd-tree - ANNpointArray pa, // point array (unaltered) - ANNidxArray pidx, // point indices to store in subtree - int n, // number of points - int dim, // dimension of space - int bsp, // bucket space - ANNorthRect &bnd_box, // bounding box for current node - ANNkd_splitter splitter, // splitting routine - vector<ANNkd_leaf*>* ppointToLeafVec); - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/ANN/kd_util.h b/geom_bottleneck/bottleneck/include/ANN/kd_util.h deleted file mode 100644 index fa9f554..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/kd_util.h +++ /dev/null @@ -1,126 +0,0 @@ -//---------------------------------------------------------------------- -// 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 - -namespace geom_bt { -//---------------------------------------------------------------------- -// 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 diff --git a/geom_bottleneck/bottleneck/include/ANN/pr_queue.h b/geom_bottleneck/bottleneck/include/ANN/pr_queue.h deleted file mode 100644 index f938a73..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/pr_queue.h +++ /dev/null @@ -1,127 +0,0 @@ -//---------------------------------------------------------------------- -// File: pr_queue.h -// Programmer: Sunil Arya and David Mount -// Description: Include file for priority queue and related -// structures. -// 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 PR_QUEUE_H -#define PR_QUEUE_H - -#include <ANN/ANNx.h> // all ANN includes -#include <ANN/ANNperf.h> // performance evaluation - -namespace geom_bt { -//---------------------------------------------------------------------- -// Basic types. -//---------------------------------------------------------------------- -typedef void *PQinfo; // info field is generic pointer -typedef ANNdist PQkey; // key field is distance - -//---------------------------------------------------------------------- -// Priority queue -// A priority queue is a list of items, along with associated -// priorities. The basic operations are insert and extract_minimum. -// -// The priority queue is maintained using a standard binary heap. -// (Implementation note: Indexing is performed from [1..max] rather -// than the C standard of [0..max-1]. This simplifies parent/child -// computations.) User information consists of a void pointer, -// and the user is responsible for casting this quantity into whatever -// useful form is desired. -// -// Because the priority queue is so central to the efficiency of -// query processing, all the code is inline. -//---------------------------------------------------------------------- - -class ANNpr_queue { - - struct pq_node { // node in priority queue - PQkey key; // key value - PQinfo info; // info field - }; - int n; // number of items in queue - int max_size; // maximum queue size - pq_node *pq; // the priority queue (array of nodes) - -public: - ANNpr_queue(int max) // constructor (given max size) - { - n = 0; // initially empty - max_size = max; // maximum number of items - pq = new pq_node[max+1]; // queue is array [1..max] of nodes - } - - ~ANNpr_queue() // destructor - { delete [] pq; } - - ANNbool empty() // is queue empty? - { if (n==0) return ANNtrue; else return ANNfalse; } - - ANNbool non_empty() // is queue nonempty? - { if (n==0) return ANNfalse; else return ANNtrue; } - - void reset() // make existing queue empty - { n = 0; } - - inline void insert( // insert item (inlined for speed) - PQkey kv, // key value - PQinfo inf) // item info - { - if (++n > max_size) annError("Priority queue overflow.", ANNabort); - register int r = n; - while (r > 1) { // sift up new item - register int p = r/2; - ANN_FLOP(1) // increment floating ops - if (pq[p].key <= kv) // in proper order - break; - pq[r] = pq[p]; // else swap with parent - r = p; - } - pq[r].key = kv; // insert new item at final location - pq[r].info = inf; - } - - inline void extr_min( // extract minimum (inlined for speed) - PQkey &kv, // key (returned) - PQinfo &inf) // item info (returned) - { - kv = pq[1].key; // key of min item - inf = pq[1].info; // information of min item - register PQkey kn = pq[n--].key;// last item in queue - register int p = 1; // p points to item out of position - register int r = p<<1; // left child of p - while (r <= n) { // while r is still within the heap - ANN_FLOP(2) // increment floating ops - // set r to smaller child of p - if (r < n && pq[r].key > pq[r+1].key) r++; - if (kn <= pq[r].key) // in proper order - break; - pq[p] = pq[r]; // else swap with child - p = r; // advance pointers - r = p<<1; - } - pq[p] = pq[n+1]; // insert last item in proper place - } -}; - -} -#endif
\ No newline at end of file diff --git a/geom_bottleneck/bottleneck/include/ANN/pr_queue_k.h b/geom_bottleneck/bottleneck/include/ANN/pr_queue_k.h deleted file mode 100644 index 133a766..0000000 --- a/geom_bottleneck/bottleneck/include/ANN/pr_queue_k.h +++ /dev/null @@ -1,120 +0,0 @@ -//---------------------------------------------------------------------- -// File: pr_queue_k.h -// Programmer: Sunil Arya and David Mount -// Description: Include file for priority queue with k items. -// 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 PR_QUEUE_K_H -#define PR_QUEUE_K_H - -#include <ANN/ANNx.h> // all ANN includes -#include <ANN/ANNperf.h> // performance evaluation - -namespace geom_bt { -//---------------------------------------------------------------------- -// Basic types -//---------------------------------------------------------------------- -typedef ANNdist PQKkey; // key field is distance -typedef int PQKinfo; // info field is int - -//---------------------------------------------------------------------- -// Constants -// The NULL key value is used to initialize the priority queue, and -// so it should be larger than any valid distance, so that it will -// be replaced as legal distance values are inserted. The NULL -// info value must be a nonvalid array index, we use ANN_NULL_IDX, -// which is guaranteed to be negative. -//---------------------------------------------------------------------- - -const PQKkey PQ_NULL_KEY = ANN_DIST_INF; // nonexistent key value -const PQKinfo PQ_NULL_INFO = ANN_NULL_IDX; // nonexistent info value - -//---------------------------------------------------------------------- -// ANNmin_k -// An ANNmin_k structure is one which maintains the smallest -// k values (of type PQKkey) and associated information (of type -// PQKinfo). The special info and key values PQ_NULL_INFO and -// PQ_NULL_KEY means that thise entry is empty. -// -// It is currently implemented using an array with k items. -// Items are stored in increasing sorted order, and insertions -// are made through standard insertion sort. (This is quite -// inefficient, but current applications call for small values -// of k and relatively few insertions.) -// -// Note that the list contains k+1 entries, but the last entry -// is used as a simple placeholder and is otherwise ignored. -//---------------------------------------------------------------------- - -class ANNmin_k { - struct mk_node { // node in min_k structure - PQKkey key; // key value - PQKinfo info; // info field (user defined) - }; - - int k; // max number of keys to store - int n; // number of keys currently active - mk_node *mk; // the list itself - -public: - ANNmin_k(int max) // constructor (given max size) - { - n = 0; // initially no items - k = max; // maximum number of items - mk = new mk_node[max+1]; // sorted array of keys - } - - ~ANNmin_k() // destructor - { delete [] mk; } - - PQKkey ANNmin_key() // return minimum key - { return (n > 0 ? mk[0].key : PQ_NULL_KEY); } - - PQKkey max_key() // return maximum key - { return (n == k ? mk[k-1].key : PQ_NULL_KEY); } - - PQKkey ith_smallest_key(int i) // ith smallest key (i in [0..n-1]) - { return (i < n ? mk[i].key : PQ_NULL_KEY); } - - PQKinfo ith_smallest_info(int i) // info for ith smallest (i in [0..n-1]) - { return (i < n ? mk[i].info : PQ_NULL_INFO); } - - inline void insert( // insert item (inlined for speed) - PQKkey kv, // key value - PQKinfo inf) // item info - { - register int i; - // slide larger values up - for (i = n; i > 0; i--) { - if (mk[i-1].key > kv) - mk[i] = mk[i-1]; - else - break; - } - mk[i].key = kv; // store element here - mk[i].info = inf; - if (n < k) n++; // increment number of items - ANN_FLOP(k-i+1) // increment floating ops - } -}; - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/basic_defs_bt.h b/geom_bottleneck/bottleneck/include/basic_defs_bt.h deleted file mode 100644 index 5d6d264..0000000 --- a/geom_bottleneck/bottleneck/include/basic_defs_bt.h +++ /dev/null @@ -1,198 +0,0 @@ -/* - Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov - - This file is part of GeomBottleneck. - - GeomBottleneck is free software: you can redistribute it and/or modify - it under the terms of the Lesser GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - GeomBottleneck is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. - -*/ - - -#ifndef BASIC_DEFS_BT_H -#define BASIC_DEFS_BT_H - -#ifdef _WIN32 -#include <ciso646> -#endif - -#include <vector> -#include <stdexcept> -#include <cmath> -#include <cstddef> -#include <unordered_map> -#include <unordered_set> -#include <string> -#include <cassert> - -#include "def_debug_bt.h" - -#ifndef FOR_R_TDA -#include <iostream> -#endif - - -namespace geom_bt { - -typedef double CoordinateType; -typedef int IdType; -constexpr IdType MinValidId = 10; - -struct Point { - CoordinateType x, y; - bool operator==(const Point& other) const; - bool operator!=(const Point& other) const; - Point(CoordinateType ax, CoordinateType ay) : x(ax), y(ay) {} - Point() : x(0.0), y(0.0) {} -#ifndef FOR_R_TDA - friend std::ostream& operator<<(std::ostream& output, const Point p); -#endif -}; - -struct DiagramPoint -{ - // Points above the diagonal have type NORMAL - // Projections onto the diagonal have type DIAG - // for DIAG points only x-coordinate is relevant - // to-do: add getters/setters, checks in constructors, etc - enum Type { NORMAL, DIAG}; - // data members -private: - CoordinateType x, y; -public: - Type type; - IdType id; - // operators, constructors - bool operator==(const DiagramPoint& other) const; - bool operator!=(const DiagramPoint& other) const; - DiagramPoint(CoordinateType xx, CoordinateType yy, Type ttype, IdType uid); - bool isDiagonal(void) const { return type == DIAG; } - bool isNormal(void) const { return type == NORMAL; } - CoordinateType inline getRealX() const // return the x-coord - { - return x; - //if (DiagramPoint::NORMAL == type) - //return x; - //else - //return 0.5 * ( x + y); - } - - CoordinateType inline getRealY() const // return the y-coord - { - return y; - //if (DiagramPoint::NORMAL == type) - //return y; - //else - //return 0.5 * ( x + y); - } - -#ifndef FOR_R_TDA - friend std::ostream& operator<<(std::ostream& output, const DiagramPoint p); -#endif -}; - -struct PointHash { - size_t operator()(const Point& p) const{ - return std::hash<CoordinateType>()(p.x)^std::hash<CoordinateType>()(p.y); - } -}; - -struct DiagramPointHash { - size_t operator()(const DiagramPoint& p) const{ - //return std::hash<CoordinateType>()(p.x)^std::hash<CoordinateType>()(p.y)^std::hash<bool>()(p.type == DiagramPoint::NORMAL); - assert(p.id >= MinValidId); - return std::hash<int>()(p.id); - } -}; - -CoordinateType sqrDist(const Point& a, const Point& b); -CoordinateType dist(const Point& a, const Point& b); -CoordinateType distLInf(const DiagramPoint& a, const DiagramPoint& b); - -typedef std::unordered_set<Point, PointHash> PointSet; - -class DiagramPointSet { -public: - void insert(const DiagramPoint p); - void erase(const DiagramPoint& p, bool doCheck = true); // if doCheck, erasing non-existing elements causes assert - void erase(const std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator it); - void removeDiagonalPoints(); - size_t size() const; - void reserve(const size_t newSize); - void clear(); - bool empty() const; - bool hasElement(const DiagramPoint& p) const; - std::unordered_set<DiagramPoint, DiagramPointHash>::iterator find(const DiagramPoint& p) { return points.find(p); }; - std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator find(const DiagramPoint& p) const { return points.find(p); }; - std::unordered_set<DiagramPoint, DiagramPointHash>::iterator begin() { return points.begin(); }; - std::unordered_set<DiagramPoint, DiagramPointHash>::iterator end() { return points.end(); } - std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator cbegin() const { return points.cbegin(); } - std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator cend() const { return points.cend(); } -#ifndef FOR_R_TDA - friend std::ostream& operator<<(std::ostream& output, const DiagramPointSet& ps); -#endif - friend void addProjections(DiagramPointSet& A, DiagramPointSet& B); - template<class PairIterator> DiagramPointSet(PairIterator first, PairIterator last); - template<class PairIterator> void fillIn(PairIterator first, PairIterator last); - // default ctor, empty diagram - DiagramPointSet(IdType minId = MinValidId + 1) : maxId(minId + 1) {}; - IdType nextId() { return maxId + 1; } -private: - bool isLinked { false }; - IdType maxId {MinValidId + 1}; - std::unordered_set<DiagramPoint, DiagramPointHash> points; -}; - -template<typename DiagPointContainer> -CoordinateType getFurthestDistance3Approx(DiagPointContainer& A, DiagPointContainer& B) -{ - CoordinateType result { 0.0 }; - DiagramPoint begA = *(A.begin()); - DiagramPoint optB = *(B.begin()); - for(const auto& pointB : B) { - if (distLInf(begA, pointB) > result) { - result = distLInf(begA, pointB); - optB = pointB; - } - } - for(const auto& pointA : A) { - if (distLInf(pointA, optB) > result) { - result = distLInf(pointA, optB); - } - } - return result; -} - -template<class PairIterator> -void DiagramPointSet::fillIn(PairIterator start, PairIterator end) -{ - isLinked = false; - clear(); - IdType uniqueId = MinValidId + 1; - for(auto iter = start; iter != end; ++iter) { - insert(DiagramPoint(iter->first, iter->second, DiagramPoint::NORMAL, uniqueId++)); - } -} - -template<class PairIterator> -DiagramPointSet::DiagramPointSet(PairIterator start, PairIterator end) -{ - fillIn(start, end); -} - -// preprocess diagrams A and B by adding projections onto diagonal of points of -// A to B and vice versa. NB: ids of points will be changed! -void addProjections(DiagramPointSet& A, DiagramPointSet& B); - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/bottleneck.h b/geom_bottleneck/bottleneck/include/bottleneck.h deleted file mode 100644 index 75c902f..0000000 --- a/geom_bottleneck/bottleneck/include/bottleneck.h +++ /dev/null @@ -1,138 +0,0 @@ -/* - Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov - - This file is part of GeomBottleneck. - - GeomBottleneck is free software: you can redistribute it and/or modify - it under the terms of the Lesser GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - GeomBottleneck is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. - -*/ - -#ifndef BOTTLENECK_H -#define BOTTLENECK_H - - -//#include <iostream> -#include <fstream> -#include <vector> -#include <algorithm> -#include <limits> -#include <random> - -#include "basic_defs_bt.h" -#include "bound_match.h" -//#include "test_neighb_oracle.h" -//#include "test_dist_calc.h" - -namespace geom_bt { -typedef std::pair<double, std::pair<size_t, size_t>> DistVerticesPair; - -// functions taking DiagramPointSet as input. -// ATTENTION: parameters A and B (diagrams) will be changed after the call -// (projections added). - -// return the interval (distMin, distMax) such that: -// a) actual bottleneck distance between A and B is contained in the interval -// b) if the interval is not (0,0), then (distMax - distMin) / distMin < epsilon -std::pair<double, double> bottleneckDistApproxInterval(DiagramPointSet& A, DiagramPointSet& B, const double epsilon); - - -// heuristic (sample diagram to estimate the distance) -std::pair<double, double> bottleneckDistApproxIntervalHeur(DiagramPointSet& A, DiagramPointSet& B, const double epsilon); - -// get approximate distance, -// see bottleneckDistApproxInterval -double bottleneckDistApprox(DiagramPointSet& A, DiagramPointSet& B, const double epsilon); - -// get exact bottleneck distance, -double bottleneckDistExact(DiagramPointSet& A, DiagramPointSet& B, const int decPrecision); - -// get exact bottleneck distance, -double bottleneckDistExact(DiagramPointSet& A, DiagramPointSet& B); - - -// functions taking containers as input -// template parameter PairContainer must be a container of pairs of real -// numbers (pair.first = x-coordinate, pair.second = y-coordinate) -// PairContainer class must support iteration of the form -// for(it = pairContainer.begin(); it != pairContainer.end(); ++it) - -// return the interval (distMin, distMax) such that: -// a) actual bottleneck distance between A and B is contained in the interval -// b) if the interval is not (0,0), then (distMax - distMin) / distMin < epsilon -template<class PairContainer> -std::pair<double, double> bottleneckDistApproxInterval(PairContainer& A, PairContainer& B, const double epsilon) -{ - DiagramPointSet a(A.begin(), A.end()); - DiagramPointSet b(B.begin(), B.end()); - return bottleneckDistApproxInterval(a, b, epsilon); -} - - -template<class PairContainer> -double bottleneckDistApproxHeur(PairContainer& A, PairContainer& B, const double epsilon) -{ - DiagramPointSet a(A.begin(), A.end()); - DiagramPointSet b(B.begin(), B.end()); - std::pair<double, double> resPair = bottleneckDistApproxIntervalHeur(a, b, epsilon); - return resPair.second; -} - - -// get approximate distance, -// see bottleneckDistApproxInterval -template<class PairContainer> -double bottleneckDistApprox(PairContainer& A, PairContainer& B, const double epsilon) -{ - DiagramPointSet a(A.begin(), A.end()); - DiagramPointSet b(B.begin(), B.end()); - return bottleneckDistApprox(a, b, epsilon); -} - -// get exact bottleneck distance, -template<class PairContainer> -double bottleneckDistExact(PairContainer& A, PairContainer& B) -{ - DiagramPointSet a(A.begin(), A.end()); - DiagramPointSet b(B.begin(), B.end()); - return bottleneckDistExact(a, b, 14); -} - - -// get exact bottleneck distance, -template<class PairContainer> -double bottleneckDistExact(PairContainer& A, PairContainer& B, const int decPrecision) -{ - DiagramPointSet a(A.begin(), A.end()); - DiagramPointSet b(B.begin(), B.end()); - return bottleneckDistExact(a, b, decPrecision); -} - -// fill in result with points from file fname -// return false if file can't be opened -// or error occurred while reading -// decPrecision is the maximal decimal precision in the input, -// it is zero if all coordinates in the input are integers -bool readDiagramPointSet(const char* fname, std::vector<std::pair<double, double>>& result, int& decPrecision); -// wrapper for standard string -bool readDiagramPointSet(const std::string& fname, std::vector<std::pair<double, double>>& result, int& decPrecision); - - -// these two functions are now just wrappers for the previous ones, -// in case someone needs them; decPrecision is ignored -bool readDiagramPointSet(const char* fname, std::vector<std::pair<double, double>>& result); -// wrapper for standard string -bool readDiagramPointSet(const std::string& fname, std::vector<std::pair<double, double>>& result); - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/bound_match.h b/geom_bottleneck/bottleneck/include/bound_match.h deleted file mode 100644 index 2e2d369..0000000 --- a/geom_bottleneck/bottleneck/include/bound_match.h +++ /dev/null @@ -1,80 +0,0 @@ -/* - Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov - - This file is part of GeomBottleneck. - - GeomBottleneck is free software: you can redistribute it and/or modify - it under the terms of the Lesser GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - GeomBottleneck is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. - -*/ - -#ifndef BOUND_MATCH_H -#define BOUND_MATCH_H - -#include <unordered_map> - -#include "basic_defs_bt.h" -#include "neighb_oracle.h" - - -namespace geom_bt { -typedef std::vector<DiagramPoint> Path; - -class Matching { -public: - Matching(const DiagramPointSet& AA, const DiagramPointSet& BB) : A(AA), B(BB) {}; - DiagramPointSet getExposedVertices(bool forA = true) const ; - bool isExposed(const DiagramPoint& p) const; - void getAllAdjacentVertices(const DiagramPointSet& setIn, DiagramPointSet& setOut, bool forA = true) const; - void increase(const Path& augmentingPath); - void checkAugPath(const Path& augPath) const; - bool getMatchedVertex(const DiagramPoint& p, DiagramPoint& result) const; - bool isPerfect() const; - void trimMatching(const double newThreshold); - friend std::ostream& operator<<(std::ostream& output, const Matching& m); -private: - DiagramPointSet A; - DiagramPointSet B; - std::unordered_map<DiagramPoint, DiagramPoint, DiagramPointHash> AToB, BToA; - void matchVertices(const DiagramPoint& pA, const DiagramPoint& pB); - void sanityCheck() const; -}; - - - -class BoundMatchOracle { -public: - BoundMatchOracle(DiagramPointSet psA, DiagramPointSet psB, double dEps, bool useRS = true); - bool isMatchLess(double r); - void setInnerOracle(NeighbOracleAbstract* innerOracle) { neighbOracle = innerOracle; } - bool buildMatchingForThreshold(const double r); - ~BoundMatchOracle(); -private: - DiagramPointSet A, B; - Matching M; - void printLayerGraph(void); - void buildLayerGraph(double r); - void buildLayerOracles(double r); - bool buildAugmentingPath(const DiagramPoint startVertex, Path& result); - void removeFromLayer(const DiagramPoint& p, const int layerIdx); - NeighbOracleAbstract* neighbOracle; - bool augPathExist; - std::vector<DiagramPointSet> layerGraph; - std::vector<NeighbOracle*> layerOracles; - double distEpsilon; - bool useRangeSearch; - double prevQueryValue; -}; - -} -#endif diff --git a/geom_bottleneck/bottleneck/include/def_debug_bt.h b/geom_bottleneck/bottleneck/include/def_debug_bt.h deleted file mode 100644 index 888ded6..0000000 --- a/geom_bottleneck/bottleneck/include/def_debug_bt.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov - - This file is part of GeomBottleneck. - - GeomBottleneck is free software: you can redistribute it and/or modify - it under the terms of the Lesser GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - GeomBottleneck is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. - -*/ - -#ifndef DEF_DEBUG_BT_H -#define DEF_DEBUG_BT_H - -//#define DEBUG_BOUND_MATCH -//#define DEBUG_NEIGHBOUR_ORACLE -//#define DEBUG_MATCHING -//#define DEBUG_AUCTION -// This symbol should be defined only in the version -// for R package TDA, to comply with some CRAN rules -// like no usage of cout, cerr, cin, exit, etc. -//#define FOR_R_TDA -//#define VERBOSE_BOTTLENECK - -#endif diff --git a/geom_bottleneck/bottleneck/include/neighb_oracle.h b/geom_bottleneck/bottleneck/include/neighb_oracle.h deleted file mode 100644 index f6f78b1..0000000 --- a/geom_bottleneck/bottleneck/include/neighb_oracle.h +++ /dev/null @@ -1,91 +0,0 @@ -/* - Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov - - This file is part of GeomBottleneck. - - GeomBottleneck is free software: you can redistribute it and/or modify - it under the terms of the Lesser GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - GeomBottleneck is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. - -*/ - -#ifndef NEIGHB_ORACLE_H -#define NEIGHB_ORACLE_H - -#include <unordered_map> -#include "basic_defs_bt.h" -#include <ANN/ANN.h> - -namespace geom_bt { -class NeighbOracleAbstract{ -public: - virtual void deletePoint(const DiagramPoint& p) = 0; - virtual void rebuild(const DiagramPointSet& S, double rr) = 0; - // return true, if r-neighbour of q exists in pointSet, - // false otherwise. - // the neighbour is returned in result - virtual bool getNeighbour(const DiagramPoint& q, DiagramPoint& result) const = 0; - virtual void getAllNeighbours(const DiagramPoint& q, std::vector<DiagramPoint>& result) = 0; - virtual ~NeighbOracleAbstract() {}; -protected: - double r; - double distEpsilon; -}; - -class NeighbOracleSimple : public NeighbOracleAbstract -{ -public: - NeighbOracleSimple(); - NeighbOracleSimple(const DiagramPointSet& S, const double rr, const double dEps); - void deletePoint(const DiagramPoint& p); - void rebuild(const DiagramPointSet& S, const double rr); - bool getNeighbour(const DiagramPoint& q, DiagramPoint& result) const; - void getAllNeighbours(const DiagramPoint& q, std::vector<DiagramPoint>& result); - ~NeighbOracleSimple() {}; -private: - DiagramPointSet pointSet; -}; - -class NeighbOracleAnn : public NeighbOracleAbstract -{ -public: - NeighbOracleAnn(const DiagramPointSet& S, const double rr, const double dEps); - void deletePoint(const DiagramPoint& p); - void rebuild(const DiagramPointSet& S, const double rr); - bool getNeighbour(const DiagramPoint& q, DiagramPoint& result) const; - void getAllNeighbours(const DiagramPoint& q, std::vector<DiagramPoint>& result); - ~NeighbOracleAnn(); -//private: - //DiagramPointSet originalPointSet; - std::vector<DiagramPoint> allPoints; - DiagramPointSet diagonalPoints; - std::unordered_map<DiagramPoint, size_t, DiagramPointHash> pointIdxLookup; - // ann-stuff - static constexpr double annEpsilon {0}; - static const int annK {1}; - static const int annDim{2}; - ANNpointArray annPoints; - ANNkd_tree* kdTree; - ANNidxArray annNeigbIndices; - ANNpoint annQueryPoint; - // to use in getAllNeighbours - ANNpoint lo; - ANNpoint hi; - ANNidxArray annIndices; - ANNdistArray annDistances; -}; - -//typedef NeighbOracleSimple NeighbOracle; -typedef NeighbOracleAnn NeighbOracle; - -} -#endif |