Debian Codegraph @

src/kd_split.h

raw
1 //----------------------------------------------------------------------
2 // File: kd_split.h
3 // Programmer: Sunil Arya and David Mount
4 // Description: Methods for splitting kd-trees
5 // Last modified: 01/04/05 (Version 1.0)
6 //----------------------------------------------------------------------
7 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
8 // David Mount. All Rights Reserved.
9 //
10 // This software and related documentation is part of the Approximate
11 // Nearest Neighbor Library (ANN). This software is provided under
12 // the provisions of the Lesser GNU Public License (LGPL). See the
13 // file ../ReadMe.txt for further information.
14 //
15 // The University of Maryland (U.M.) and the authors make no
16 // representations about the suitability or fitness of this software for
17 // any purpose. It is provided "as is" without express or implied
18 // warranty.
19 //----------------------------------------------------------------------
20 // History:
21 // Revision 0.1 03/04/98
22 // Initial release
23 //----------------------------------------------------------------------
24
25 #ifndef ANN_KD_SPLIT_H
26 #define ANN_KD_SPLIT_H
27
28 #include "kd_tree.h" // kd-tree definitions
29
30 //----------------------------------------------------------------------
31 // External entry points
32 // These are all splitting procedures for kd-trees.
33 //----------------------------------------------------------------------
34
35 void kd_split( // standard (optimized) kd-splitter
36 ANNpointArray pa, // point array (unaltered)
37 ANNidxArray pidx, // point indices (permuted on return)
38 const ANNorthRect &bnds, // bounding rectangle for cell
39 int n, // number of points
40 int dim, // dimension of space
41 int &cut_dim, // cutting dimension (returned)
42 ANNcoord &cut_val, // cutting value (returned)
43 int &n_lo); // num of points on low side (returned)
44
45 void midpt_split( // midpoint kd-splitter
46 ANNpointArray pa, // point array (unaltered)
47 ANNidxArray pidx, // point indices (permuted on return)
48 const ANNorthRect &bnds, // bounding rectangle for cell
49 int n, // number of points
50 int dim, // dimension of space
51 int &cut_dim, // cutting dimension (returned)
52 ANNcoord &cut_val, // cutting value (returned)
53 int &n_lo); // num of points on low side (returned)
54
55 void sl_midpt_split( // sliding midpoint kd-splitter
56 ANNpointArray pa, // point array (unaltered)
57 ANNidxArray pidx, // point indices (permuted on return)
58 const ANNorthRect &bnds, // bounding rectangle for cell
59 int n, // number of points
60 int dim, // dimension of space
61 int &cut_dim, // cutting dimension (returned)
62 ANNcoord &cut_val, // cutting value (returned)
63 int &n_lo); // num of points on low side (returned)
64
65 void fair_split( // fair-split kd-splitter
66 ANNpointArray pa, // point array (unaltered)
67 ANNidxArray pidx, // point indices (permuted on return)
68 const ANNorthRect &bnds, // bounding rectangle for cell
69 int n, // number of points
70 int dim, // dimension of space
71 int &cut_dim, // cutting dimension (returned)
72 ANNcoord &cut_val, // cutting value (returned)
73 int &n_lo); // num of points on low side (returned)
74
75 void sl_fair_split( // sliding fair-split kd-splitter
76 ANNpointArray pa, // point array (unaltered)
77 ANNidxArray pidx, // point indices (permuted on return)
78 const ANNorthRect &bnds, // bounding rectangle for cell
79 int n, // number of points
80 int dim, // dimension of space
81 int &cut_dim, // cutting dimension (returned)
82 ANNcoord &cut_val, // cutting value (returned)
83 int &n_lo); // num of points on low side (returned)
84
85 #endif