00001 //---------------------------------------------------------------------- 00002 // File: kd_split.h 00003 // Programmer: Sunil Arya and David Mount 00004 // Description: Methods for splitting kd-trees 00005 // Last modified: 01/04/05 (Version 1.0) 00006 //---------------------------------------------------------------------- 00007 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and 00008 // David Mount. All Rights Reserved. 00009 // 00010 // This software and related documentation is part of the Approximate 00011 // Nearest Neighbor Library (ANN). This software is provided under 00012 // the provisions of the Lesser GNU Public License (LGPL). See the 00013 // file ../ReadMe.txt for further information. 00014 // 00015 // The University of Maryland (U.M.) and the authors make no 00016 // representations about the suitability or fitness of this software for 00017 // any purpose. It is provided "as is" without express or implied 00018 // warranty. 00019 //---------------------------------------------------------------------- 00020 // History: 00021 // Revision 0.1 03/04/98 00022 // Initial release 00023 //---------------------------------------------------------------------- 00024 00025 #ifndef ANN_KD_SPLIT_H 00026 #define ANN_KD_SPLIT_H 00027 00028 #include "kd_tree.h" // kd-tree definitions 00029 00030 //---------------------------------------------------------------------- 00031 // External entry points 00032 // These are all splitting procedures for kd-trees. 00033 //---------------------------------------------------------------------- 00034 00035 void kd_split( // standard (optimized) kd-splitter 00036 ANNpointArray pa, // point array (unaltered) 00037 ANNidxArray pidx, // point indices (permuted on return) 00038 const ANNorthRect &bnds, // bounding rectangle for cell 00039 int n, // number of points 00040 int dim, // dimension of space 00041 int &cut_dim, // cutting dimension (returned) 00042 ANNcoord &cut_val, // cutting value (returned) 00043 int &n_lo); // num of points on low side (returned) 00044 00045 void midpt_split( // midpoint kd-splitter 00046 ANNpointArray pa, // point array (unaltered) 00047 ANNidxArray pidx, // point indices (permuted on return) 00048 const ANNorthRect &bnds, // bounding rectangle for cell 00049 int n, // number of points 00050 int dim, // dimension of space 00051 int &cut_dim, // cutting dimension (returned) 00052 ANNcoord &cut_val, // cutting value (returned) 00053 int &n_lo); // num of points on low side (returned) 00054 00055 void sl_midpt_split( // sliding midpoint kd-splitter 00056 ANNpointArray pa, // point array (unaltered) 00057 ANNidxArray pidx, // point indices (permuted on return) 00058 const ANNorthRect &bnds, // bounding rectangle for cell 00059 int n, // number of points 00060 int dim, // dimension of space 00061 int &cut_dim, // cutting dimension (returned) 00062 ANNcoord &cut_val, // cutting value (returned) 00063 int &n_lo); // num of points on low side (returned) 00064 00065 void fair_split( // fair-split kd-splitter 00066 ANNpointArray pa, // point array (unaltered) 00067 ANNidxArray pidx, // point indices (permuted on return) 00068 const ANNorthRect &bnds, // bounding rectangle for cell 00069 int n, // number of points 00070 int dim, // dimension of space 00071 int &cut_dim, // cutting dimension (returned) 00072 ANNcoord &cut_val, // cutting value (returned) 00073 int &n_lo); // num of points on low side (returned) 00074 00075 void sl_fair_split( // sliding fair-split kd-splitter 00076 ANNpointArray pa, // point array (unaltered) 00077 ANNidxArray pidx, // point indices (permuted on return) 00078 const ANNorthRect &bnds, // bounding rectangle for cell 00079 int n, // number of points 00080 int dim, // dimension of space 00081 int &cut_dim, // cutting dimension (returned) 00082 ANNcoord &cut_val, // cutting value (returned) 00083 int &n_lo); // num of points on low side (returned) 00084 00085 #endif
1.6.1