Point Cloud Library (PCL)
1.7.0
|
00001 /* 00002 * Software License Agreement (BSD License) 00003 * 00004 * Point Cloud Library (PCL) - www.pointclouds.org 00005 * Copyright (c) 2010-2011, Willow Garage, Inc. 00006 * 00007 * All rights reserved. 00008 * 00009 * Redistribution and use in source and binary forms, with or without 00010 * modification, are permitted provided that the following conditions 00011 * are met: 00012 * 00013 * * Redistributions of source code must retain the above copyright 00014 * notice, this list of conditions and the following disclaimer. 00015 * * Redistributions in binary form must reproduce the above 00016 * copyright notice, this list of conditions and the following 00017 * disclaimer in the documentation and/or other materials provided 00018 * with the distribution. 00019 * * Neither the name of the copyright holder(s) nor the names of its 00020 * contributors may be used to endorse or promote products derived 00021 * from this software without specific prior written permission. 00022 * 00023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00024 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00025 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00026 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00027 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00028 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 00029 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 00030 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00031 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00032 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 00033 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00034 * POSSIBILITY OF SUCH DAMAGE. 00035 * 00036 */ 00037 00038 #ifndef PCL_SEARCH_BRUTE_FORCE_H_ 00039 #define PCL_SEARCH_BRUTE_FORCE_H_ 00040 00041 #include <pcl/search/search.h> 00042 00043 namespace pcl 00044 { 00045 namespace search 00046 { 00047 /** \brief Implementation of a simple brute force search algorithm. 00048 * \author Suat Gedikli 00049 * \ingroup search 00050 */ 00051 template<typename PointT> 00052 class BruteForce: public Search<PointT> 00053 { 00054 typedef typename Search<PointT>::PointCloud PointCloud; 00055 typedef typename Search<PointT>::PointCloudConstPtr PointCloudConstPtr; 00056 00057 typedef boost::shared_ptr<std::vector<int> > IndicesPtr; 00058 typedef boost::shared_ptr<const std::vector<int> > IndicesConstPtr; 00059 00060 using pcl::search::Search<PointT>::input_; 00061 using pcl::search::Search<PointT>::indices_; 00062 using pcl::search::Search<PointT>::sorted_results_; 00063 00064 struct Entry 00065 { 00066 Entry (int idx, float dist) : index (idx), distance (dist) {} 00067 00068 Entry () : index (0), distance (0) {} 00069 unsigned index; 00070 float distance; 00071 00072 inline bool 00073 operator < (const Entry& other) const 00074 { 00075 return (distance < other.distance); 00076 } 00077 00078 inline bool 00079 operator > (const Entry& other) const 00080 { 00081 return (distance > other.distance); 00082 } 00083 }; 00084 00085 // replace by some metric functor 00086 float getDistSqr (const PointT& point1, const PointT& point2) const; 00087 public: 00088 BruteForce (bool sorted_results = false) 00089 : Search<PointT> ("BruteForce", sorted_results) 00090 { 00091 } 00092 00093 /** \brief Destructor for KdTree. */ 00094 virtual 00095 ~BruteForce () 00096 { 00097 } 00098 00099 /** \brief Search for the k-nearest neighbors for the given query point. 00100 * \param[in] point the given query point 00101 * \param[in] k the number of neighbors to search for 00102 * \param[out] k_indices the resultant indices of the neighboring points (must be resized to \a k a priori!) 00103 * \param[out] k_distances the resultant squared distances to the neighboring points (must be resized to \a k 00104 * a priori!) 00105 * \return number of neighbors found 00106 */ 00107 int 00108 nearestKSearch (const PointT &point, int k, std::vector<int> &k_indices, std::vector<float> &k_distances) const; 00109 00110 /** \brief Search for all the nearest neighbors of the query point in a given radius. 00111 * \param[in] point the given query point 00112 * \param[in] radius the radius of the sphere bounding all of p_q's neighbors 00113 * \param[out] k_indices the resultant indices of the neighboring points 00114 * \param[out] k_sqr_distances the resultant squared distances to the neighboring points 00115 * \param[in] max_nn if given, bounds the maximum returned neighbors to this value. If \a max_nn is set to 00116 * 0 or to a number higher than the number of points in the input cloud, all neighbors in \a radius will be 00117 * returned. 00118 * \return number of neighbors found in radius 00119 */ 00120 int 00121 radiusSearch (const PointT& point, double radius, 00122 std::vector<int> &k_indices, std::vector<float> &k_sqr_distances, 00123 unsigned int max_nn = 0) const; 00124 00125 private: 00126 int 00127 denseKSearch (const PointT &point, int k, std::vector<int> &k_indices, std::vector<float> &k_distances) const; 00128 00129 int 00130 sparseKSearch (const PointT &point, int k, std::vector<int> &k_indices, std::vector<float> &k_distances) const; 00131 00132 int 00133 denseRadiusSearch (const PointT& point, double radius, 00134 std::vector<int> &k_indices, std::vector<float> &k_sqr_distances, 00135 unsigned int max_nn = 0) const; 00136 00137 int 00138 sparseRadiusSearch (const PointT& point, double radius, 00139 std::vector<int> &k_indices, std::vector<float> &k_sqr_distances, 00140 unsigned int max_nn = 0) const; 00141 }; 00142 } 00143 } 00144 00145 #ifdef PCL_NO_PRECOMPILE 00146 #include <pcl/search/impl/brute_force.hpp> 00147 #endif 00148 00149 #endif // PCL_SEARCH_BRUTE_FORCE_H_