Point Cloud Library (PCL) 1.12.1
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
42namespace 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
95 {
96 }
97
98 /** \brief Search for the k-nearest neighbors for the given query point.
99 * \param[in] point the given query point
100 * \param[in] k the number of neighbors to search for
101 * \param[out] k_indices the resultant indices of the neighboring points (must be resized to \a k a priori!)
102 * \param[out] k_distances the resultant squared distances to the neighboring points (must be resized to \a k
103 * a priori!)
104 * \return number of neighbors found
105 */
106 int
107 nearestKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const override;
108
109 /** \brief Search for all the nearest neighbors of the query point in a given radius.
110 * \param[in] point the given query point
111 * \param[in] radius the radius of the sphere bounding all of p_q's neighbors
112 * \param[out] k_indices the resultant indices of the neighboring points
113 * \param[out] k_sqr_distances the resultant squared distances to the neighboring points
114 * \param[in] max_nn if given, bounds the maximum returned neighbors to this value. If \a max_nn is set to
115 * 0 or to a number higher than the number of points in the input cloud, all neighbors in \a radius will be
116 * returned.
117 * \return number of neighbors found in radius
118 */
119 int
120 radiusSearch (const PointT& point, double radius,
121 Indices &k_indices, std::vector<float> &k_sqr_distances,
122 unsigned int max_nn = 0) const override;
123
124 private:
125 int
126 denseKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const;
127
128 int
129 sparseKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_distances) const;
130
131 int
132 denseRadiusSearch (const PointT& point, double radius,
133 Indices &k_indices, std::vector<float> &k_sqr_distances,
134 unsigned int max_nn = 0) const;
135
136 int
137 sparseRadiusSearch (const PointT& point, double radius,
138 Indices &k_indices, std::vector<float> &k_sqr_distances,
139 unsigned int max_nn = 0) const;
140 };
141 }
142}
143
144#ifdef PCL_NO_PRECOMPILE
145#include <pcl/search/impl/brute_force.hpp>
146#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()
Destructor for KdTree.
Definition: brute_force.h:94
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
PointCloudConstPtr input_
Definition: search.h:403
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: search.h:79
IndicesConstPtr indices_
Definition: search.h:404
bool sorted_results_
Definition: search.h:405
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.