Point Cloud Library (PCL)  1.12.1-dev
brute_force.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2011, Willow Garage, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of the copyright holder(s) nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  */
37 
38 #pragma once
39 
40 #include <pcl/search/search.h>
41 
42 namespace pcl
43 {
44  namespace search
45  {
46  /** \brief Implementation of a simple brute force search algorithm.
47  * \author Suat Gedikli
48  * \ingroup search
49  */
50  template<typename PointT>
51  class BruteForce: public Search<PointT>
52  {
53  using PointCloud = typename Search<PointT>::PointCloud;
54  using PointCloudConstPtr = typename Search<PointT>::PointCloudConstPtr;
55 
56  using IndicesPtr = pcl::IndicesPtr;
57  using IndicesConstPtr = pcl::IndicesConstPtr;
58 
62 
63  struct Entry
64  {
65  Entry (index_t idx, float dist) : index (idx), distance (dist) {}
66 
67  Entry () : index (0), distance (0) {}
68  index_t index;
69  float distance;
70 
71  inline bool
72  operator < (const Entry& other) const
73  {
74  return (distance < other.distance);
75  }
76 
77  inline bool
78  operator > (const Entry& other) const
79  {
80  return (distance > other.distance);
81  }
82  };
83 
84  // replace by some metric functor
85  float getDistSqr (const PointT& point1, const PointT& point2) const;
86  public:
87  BruteForce (bool sorted_results = false)
88  : Search<PointT> ("BruteForce", sorted_results)
89  {
90  }
91 
92  /** \brief Destructor for KdTree. */
93 
94  ~BruteForce () override = default;
95 
96  /** \brief Search for the k-nearest neighbors for the given query point.
97  * \param[in] point the given query point
98  * \param[in] k the number of neighbors to search for
99  * \param[out] k_indices the resultant indices of the neighboring points (must be resized to \a k a priori!)
100  * \param[out] k_distances the resultant squared distances to the neighboring points (must be resized to \a k
101  * a priori!)
102  * \return number of neighbors found
103  */
104  int
105  nearestKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const override;
106 
107  /** \brief Search for all the nearest neighbors of the query point in a given radius.
108  * \param[in] point the given query point
109  * \param[in] radius the radius of the sphere bounding all of p_q's neighbors
110  * \param[out] k_indices the resultant indices of the neighboring points
111  * \param[out] k_sqr_distances the resultant squared distances to the neighboring points
112  * \param[in] max_nn if given, bounds the maximum returned neighbors to this value. If \a max_nn is set to
113  * 0 or to a number higher than the number of points in the input cloud, all neighbors in \a radius will be
114  * returned.
115  * \return number of neighbors found in radius
116  */
117  int
118  radiusSearch (const PointT& point, double radius,
119  Indices &k_indices, std::vector<float> &k_sqr_distances,
120  unsigned int max_nn = 0) const override;
121 
122  private:
123  int
124  denseKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const;
125 
126  int
127  sparseKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const;
128 
129  int
130  denseRadiusSearch (const PointT& point, double radius,
131  Indices &k_indices, std::vector<float> &k_sqr_distances,
132  unsigned int max_nn = 0) const;
133 
134  int
135  sparseRadiusSearch (const PointT& point, double radius,
136  Indices &k_indices, std::vector<float> &k_sqr_distances,
137  unsigned int max_nn = 0) const;
138  };
139  }
140 }
141 
142 #ifdef PCL_NO_PRECOMPILE
143 #include <pcl/search/impl/brute_force.hpp>
144 #endif
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition: point_cloud.h:173
Implementation of a simple brute force search algorithm.
Definition: brute_force.h:52
int nearestKSearch(const PointT &point, int k, Indices &k_indices, std::vector< float > &k_distances) const override
Search for the k-nearest neighbors for the given query point.
Definition: brute_force.hpp:54
~BruteForce() override=default
Destructor for KdTree.
int radiusSearch(const PointT &point, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const override
Search for all the nearest neighbors of the query point in a given radius.
BruteForce(bool sorted_results=false)
Definition: brute_force.h:87
Generic search class.
Definition: search.h:75
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: search.h:79
float distance(const PointT &p1, const PointT &p2)
Definition: geometry.h:60
shared_ptr< const Indices > IndicesConstPtr
Definition: pcl_base.h:59
detail::int_type_t< detail::index_type_size, detail::index_type_signed > index_t
Type used for an index in PCL.
Definition: types.h:112
IndicesAllocator<> Indices
Type used for indices in PCL.
Definition: types.h:133
shared_ptr< Indices > IndicesPtr
Definition: pcl_base.h:58
A point structure representing Euclidean xyz coordinates, and the RGB color.