1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
//----------------------------------------------------------------------
// 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
|
