Statistics
| Branch: | Revision:

root / rgbdslam / gicp / ann_1.1.1 / src / kd_util.h @ 9240aaa3

History | View | Annotate | Download (4.64 KB)

1
//----------------------------------------------------------------------
2
// File:                        kd_util.h
3
// Programmer:                Sunil Arya and David Mount
4
// Description:                Common utilities for 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_util_H
26
#define ANN_kd_util_H
27

    
28
#include "kd_tree.h"                                        // kd-tree declarations
29

    
30
//----------------------------------------------------------------------
31
//        externally accessible functions
32
//----------------------------------------------------------------------
33

    
34
double annAspectRatio(                        // compute aspect ratio of box
35
        int                                        dim,                        // dimension
36
        const ANNorthRect        &bnd_box);                // bounding cube
37

    
38
void annEnclRect(                                // compute smallest enclosing rectangle
39
        ANNpointArray                pa,                                // point array
40
        ANNidxArray                        pidx,                        // point indices
41
        int                                        n,                                // number of points
42
        int                                        dim,                        // dimension
43
        ANNorthRect &bnds);                                        // bounding cube (returned)
44

    
45
void annEnclCube(                                // compute smallest enclosing cube
46
        ANNpointArray                pa,                                // point array
47
        ANNidxArray                        pidx,                        // point indices
48
        int                                        n,                                // number of points
49
        int                                        dim,                        // dimension
50
        ANNorthRect &bnds);                                        // bounding cube (returned)
51

    
52
ANNdist annBoxDistance(                        // compute distance from point to box
53
        const ANNpoint                q,                                // the point
54
        const ANNpoint                lo,                                // low point of box
55
        const ANNpoint                hi,                                // high point of box
56
        int                                        dim);                        // dimension of space
57

    
58
ANNcoord annSpread(                                // compute point spread along dimension
59
        ANNpointArray                pa,                                // point array
60
        ANNidxArray                        pidx,                        // point indices
61
        int                                        n,                                // number of points
62
        int                                        d);                                // dimension to check
63

    
64
void annMinMax(                                        // compute min and max coordinates along dim
65
        ANNpointArray                pa,                                // point array
66
        ANNidxArray                        pidx,                        // point indices
67
        int                                        n,                                // number of points
68
        int                                        d,                                // dimension to check
69
        ANNcoord&                        min,                        // minimum value (returned)
70
        ANNcoord&                        max);                        // maximum value (returned)
71

    
72
int annMaxSpread(                                // compute dimension of max spread
73
        ANNpointArray                pa,                                // point array
74
        ANNidxArray                        pidx,                        // point indices
75
        int                                        n,                                // number of points
76
        int                                        dim);                        // dimension of space
77

    
78
void annMedianSplit(                        // split points along median value
79
        ANNpointArray                pa,                                // points to split
80
        ANNidxArray                        pidx,                        // point indices
81
        int                                        n,                                // number of points
82
        int                                        d,                                // dimension along which to split
83
        ANNcoord                        &cv,                        // cutting value
84
        int                                        n_lo);                        // split into n_lo and n-n_lo
85

    
86
void annPlaneSplit(                                // split points by a plane
87
        ANNpointArray                pa,                                // points to split
88
        ANNidxArray                        pidx,                        // point indices
89
        int                                        n,                                // number of points
90
        int                                        d,                                // dimension along which to split
91
        ANNcoord                        cv,                                // cutting value
92
        int                                        &br1,                        // first break (values < cv)
93
        int                                        &br2);                        // second break (values == cv)
94

    
95
void annBoxSplit(                                // split points by a box
96
        ANNpointArray                pa,                                // points to split
97
        ANNidxArray                        pidx,                        // point indices
98
        int                                        n,                                // number of points
99
        int                                        dim,                        // dimension of space
100
        ANNorthRect                        &box,                        // the box
101
        int                                        &n_in);                        // number of points inside (returned)
102

    
103
int annSplitBalance(                        // determine balance factor of a split
104
        ANNpointArray                pa,                                // points to split
105
        ANNidxArray                        pidx,                        // point indices
106
        int                                        n,                                // number of points
107
        int                                        d,                                // dimension along which to split
108
        ANNcoord                        cv);                        // cutting value
109

    
110
void annBox2Bnds(                                // convert inner box to bounds
111
        const ANNorthRect        &inner_box,                // inner box
112
        const ANNorthRect        &bnd_box,                // enclosing box
113
        int                                        dim,                        // dimension of space
114
        int                                        &n_bnds,                // number of bounds (returned)
115
        ANNorthHSArray                &bnds);                        // bounds array (returned)
116

    
117
void annBnds2Box(                                // convert bounds to inner box
118
        const ANNorthRect        &bnd_box,                // enclosing box
119
        int                                        dim,                        // dimension of space
120
        int                                        n_bnds,                        // number of bounds
121
        ANNorthHSArray                bnds,                        // bounds array
122
        ANNorthRect                        &inner_box);        // inner box (returned)
123

    
124
#endif