Point Cloud Library (PCL) 1.13.0
Loading...
Searching...
No Matches
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
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.
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.
~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
PointCloudConstPtr input_
Definition search.h:401
typename PointCloud::ConstPtr PointCloudConstPtr
Definition search.h:79
IndicesConstPtr indices_
Definition search.h:402
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.