OMPL
Overview
Download
Documentation
Primer
Installation
Tutorials
Demos
Python Bindings
Available Planners
Available State Spaces
FAQ
External links:
OMPL ROS Interface
OMPL ROS Tutorial
Code
API Overview
Classes
Files
Browse Repository
TeamCity Build Server
Issues
Community
Developers
Contributions
Education
Gallery
About
License
Citations
Acknowledgments
Contact Us
Blog
All
Classes
Namespaces
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Groups
Pages
src
ompl
datastructures
NearestNeighborsSqrtApprox.h
1
/*********************************************************************
2
* Software License Agreement (BSD License)
3
*
4
* Copyright (c) 2008, Willow Garage, Inc.
5
* All rights reserved.
6
*
7
* Redistribution and use in source and binary forms, with or without
8
* modification, are permitted provided that the following conditions
9
* are met:
10
*
11
* * Redistributions of source code must retain the above copyright
12
* notice, this list of conditions and the following disclaimer.
13
* * Redistributions in binary form must reproduce the above
14
* copyright notice, this list of conditions and the following
15
* disclaimer in the documentation and/or other materials provided
16
* with the distribution.
17
* * Neither the name of the Willow Garage nor the names of its
18
* contributors may be used to endorse or promote products derived
19
* from this software without specific prior written permission.
20
*
21
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32
* POSSIBILITY OF SUCH DAMAGE.
33
*********************************************************************/
34
35
/* Author: Ioan Sucan */
36
37
#ifndef OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_SQRT_APPROX_
38
#define OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_SQRT_APPROX_
39
40
#include "ompl/datastructures/NearestNeighborsLinear.h"
41
#include <algorithm>
42
#include <cmath>
43
44
namespace
ompl
45
{
56
template
<
typename
_T>
57
class
NearestNeighborsSqrtApprox
:
public
NearestNeighborsLinear
<_T>
58
{
59
public
:
60
NearestNeighborsSqrtApprox
(
void
) :
NearestNeighborsLinear<_T>
(),
checks_
(0),
offset_
(0)
61
{
62
}
63
64
virtual
~
NearestNeighborsSqrtApprox
(
void
)
65
{
66
}
67
68
virtual
void
clear
(
void
)
69
{
70
NearestNeighborsLinear<_T>::clear
();
71
checks_
= 0;
72
offset_
= 0;
73
}
74
75
virtual
void
add
(
const
_T &data)
76
{
77
NearestNeighborsLinear<_T>::add
(data);
78
updateCheckCount
();
79
}
80
81
virtual
void
add
(
const
std::vector<_T> &data)
82
{
83
NearestNeighborsLinear<_T>::add
(data);
84
updateCheckCount
();
85
}
86
87
virtual
bool
remove
(
const
_T &data)
88
{
89
bool
result =
NearestNeighborsLinear<_T>::remove
(data);
90
if
(result)
91
updateCheckCount
();
92
return
result;
93
}
94
95
virtual
_T
nearest
(
const
_T &data)
const
96
{
97
const
std::size_t n =
NearestNeighborsLinear<_T>::data_
.
size
();
98
std::size_t pos = n;
99
100
if
(
checks_
> 0 && n > 0)
101
{
102
double
dmin = 0.0;
103
for
(std::size_t j = 0 ; j <
checks_
; ++j)
104
{
105
std::size_t i = (j * checks_ +
offset_
) % n;
106
107
double
distance =
NearestNeighbors<_T>::distFun_
(
NearestNeighborsLinear<_T>::data_
[i], data);
108
if
(pos == n || dmin > distance)
109
{
110
pos = i;
111
dmin = distance;
112
}
113
}
114
offset_
= (
offset_
+ 1) % checks_;
115
}
116
if
(pos != n)
117
return
NearestNeighborsLinear<_T>::data_
[pos];
118
119
throw
Exception
(
"No elements found in nearest neighbors data structure"
);
120
}
121
122
protected
:
123
125
inline
void
updateCheckCount
(
void
)
126
{
127
checks_
= 1 + (std::size_t)floor(sqrt((
double
)
NearestNeighborsLinear<_T>::data_
.
size
()));
128
}
129
131
std::size_t
checks_
;
132
134
mutable
std::size_t
offset_
;
135
136
};
137
138
}
139
140
#endif