35 #ifndef SHARK_ALGORITHMS_NEARESTNEIGHBORS_LCTREE_H 36 #define SHARK_ALGORITHMS_NEARESTNEIGHBORS_LCTREE_H 42 #include <boost/array.hpp> 78 template <
class VectorType = RealVector,
int CuttingAccuracy = 25>
90 : base_type(dataset.numberOfElements())
93 PointSet points(dataset);
97 std::vector<iterator> elements(
m_size);
98 boost::iota(elements,iterator(boost::begin(points),0));
103 for(std::size_t i = 0; i !=
m_size; ++i){
140 : base_type(parent, list, size){}
144 template<
class Range>
146 typedef typename Range::value_type pointIterator;
147 typedef typename Range::iterator iterator;
158 if (
m_size <= CuttingAccuracy){
162 boost::array<pointIterator,CuttingAccuracy> samples;
163 for(std::size_t i = 0; i != CuttingAccuracy; i++)
164 samples[i] = points[
m_size * (2*i+1) / (2*CuttingAccuracy)];
169 std::vector<double> distance(
m_size);
170 for(std::size_t i = 0; i !=
m_size; ++i){
171 distance[i] = inner_prod(
m_normal, *points[i]);
176 iterator split = this->
splitList(distance,points);
177 iterator begin = boost::begin(points);
178 iterator end = boost::end(points);
186 std::size_t leftSize = split-begin;
191 boost::iterator_range<iterator>
left(begin,split);
192 boost::iterator_range<iterator>
right(split,end);
200 return inner_prod(
m_normal, reference);
205 template<
class Range>
207 std::size_t numSamples = samples.size();
208 std::size_t besti = 0;
209 std::size_t bestj = 0;
210 double best_dist2 = -1.0;
211 for (std::size_t i = 1; i != numSamples; i++){
212 for (std::size_t j = 0; j != i; j++){
213 double dist2 = distanceSqr(*samples[i], *samples[j]);
214 if (dist2 > best_dist2){
221 double factor = 1.0 / std::sqrt(best_dist2);
222 if (! (boost::math::isfinite)(factor))
225 m_normal = factor * (*samples[besti] - *samples[bestj]);