Point Cloud Library (PCL)  1.11.0-dev
convex_hull.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2012, 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 Willow Garage, Inc. 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  * $Id$
37  *
38  */
39 
40 #pragma once
41 
42 #include <pcl/memory.h>
43 #include <pcl/pcl_macros.h>
44 #include <pcl/pcl_config.h>
45 #ifdef HAVE_QHULL
46 
47 // PCL includes
48 #include <pcl/surface/reconstruction.h>
49 #include <pcl/ModelCoefficients.h>
50 #include <pcl/PolygonMesh.h>
51 
52 namespace pcl
53 {
54  /** \brief Sort 2D points in a vector structure
55  * \param p1 the first point
56  * \param p2 the second point
57  * \ingroup surface
58  */
59  inline bool
60  comparePoints2D (const std::pair<int, Eigen::Vector4f> & p1, const std::pair<int, Eigen::Vector4f> & p2)
61  {
62  double angle1 = std::atan2 (p1.second[1], p1.second[0]) + M_PI;
63  double angle2 = std::atan2 (p2.second[1], p2.second[0]) + M_PI;
64  return (angle1 > angle2);
65  }
66 
67  ////////////////////////////////////////////////////////////////////////////////////////////
68  /** \brief @b ConvexHull using libqhull library.
69  * \author Aitor Aldoma, Alex Trevor
70  * \ingroup surface
71  */
72  template<typename PointInT>
73  class ConvexHull : public MeshConstruction<PointInT>
74  {
75  protected:
80 
81  public:
82  using Ptr = shared_ptr<ConvexHull<PointInT> >;
83  using ConstPtr = shared_ptr<const ConvexHull<PointInT> >;
84 
86 
88  using PointCloudPtr = typename PointCloud::Ptr;
90 
91  /** \brief Empty constructor. */
93  projection_angle_thresh_ (std::cos (0.174532925) ), qhull_flags ("qhull "),
94  x_axis_ (1.0, 0.0, 0.0), y_axis_ (0.0, 1.0, 0.0), z_axis_ (0.0, 0.0, 1.0)
95  {
96  };
97 
98  /** \brief Empty destructor */
100 
101  /** \brief Compute a convex hull for all points given.
102  *
103  * \note In 2D case (i.e. if the input points belong to one plane)
104  * the \a polygons vector will have a single item, whereas in 3D
105  * case it will contain one item for each hull facet.
106  *
107  * \param[out] points the resultant points lying on the convex hull.
108  * \param[out] polygons the resultant convex hull polygons, as a set of
109  * vertices. The Vertices structure contains an array of point indices.
110  */
111  void
112  reconstruct (PointCloud &points,
113  std::vector<pcl::Vertices> &polygons);
114 
115  /** \brief Compute a convex hull for all points given.
116  * \param[out] points the resultant points lying on the convex hull.
117  */
118  void
119  reconstruct (PointCloud &points);
120 
121  /** \brief If set to true, the qhull library is called to compute the total area and volume of the convex hull.
122  * NOTE: When this option is activated, the qhull library produces output to the console.
123  * \param[in] value whether to compute the area and the volume, default is false
124  */
125  void
126  setComputeAreaVolume (bool value)
127  {
128  compute_area_ = value;
129  if (compute_area_)
130  qhull_flags = std::string ("qhull FA");
131  else
132  qhull_flags = std::string ("qhull ");
133  }
134 
135  /** \brief Returns the total area of the convex hull. */
136  double
137  getTotalArea () const
138  {
139  return (total_area_);
140  }
141 
142  /** \brief Returns the total volume of the convex hull. Only valid for 3-dimensional sets.
143  * For 2D-sets volume is zero.
144  */
145  double
146  getTotalVolume () const
147  {
148  return (total_volume_);
149  }
150 
151  /** \brief Sets the dimension on the input data, 2D or 3D.
152  * \param[in] dimension The dimension of the input data. If not set, this will be determined automatically.
153  */
154  void
155  setDimension (int dimension)
156  {
157  if ((dimension == 2) || (dimension == 3))
158  dimension_ = dimension;
159  else
160  PCL_ERROR ("[pcl::%s::setDimension] Invalid input dimension specified!\n", getClassName ().c_str ());
161  }
162 
163  /** \brief Returns the dimensionality (2 or 3) of the calculated hull. */
164  inline int
165  getDimension () const
166  {
167  return (dimension_);
168  }
169 
170  /** \brief Retrieve the indices of the input point cloud that for the convex hull.
171  *
172  * \note Should only be called after reconstruction was performed.
173  * \param[out] hull_point_indices The indices of the points forming the point cloud
174  */
175  void
176  getHullPointIndices (pcl::PointIndices &hull_point_indices) const;
177 
178  protected:
179  /** \brief The actual reconstruction method.
180  *
181  * \param[out] points the resultant points lying on the convex hull
182  * \param[out] polygons the resultant convex hull polygons, as a set of
183  * vertices. The Vertices structure contains an array of point indices.
184  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
185  */
186  void
188  std::vector<pcl::Vertices> &polygons,
189  bool fill_polygon_data = false);
190 
191  /** \brief The reconstruction method for 2D data. Does not require dimension to be set.
192  *
193  * \param[out] points the resultant points lying on the convex hull
194  * \param[out] polygons the resultant convex hull polygons, as a set of
195  * vertices. The Vertices structure contains an array of point indices.
196  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
197  */
198  void
200  std::vector<pcl::Vertices> &polygons,
201  bool fill_polygon_data = false);
202 
203  /** \brief The reconstruction method for 3D data. Does not require dimension to be set.
204  *
205  * \param[out] points the resultant points lying on the convex hull
206  * \param[out] polygons the resultant convex hull polygons, as a set of
207  * vertices. The Vertices structure contains an array of point indices.
208  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
209  */
210  void
212  std::vector<pcl::Vertices> &polygons,
213  bool fill_polygon_data = false);
214 
215  /** \brief A reconstruction method that returns a polygonmesh.
216  *
217  * \param[out] output a PolygonMesh representing the convex hull of the input data.
218  */
219  void
220  performReconstruction (PolygonMesh &output) override;
221 
222  /** \brief A reconstruction method that returns the polygon of the convex hull.
223  *
224  * \param[out] polygons the polygon(s) representing the convex hull of the input data.
225  */
226  void
227  performReconstruction (std::vector<pcl::Vertices> &polygons) override;
228 
229  /** \brief Automatically determines the dimension of input data - 2D or 3D. */
230  void
232 
233  /** \brief Class get name method. */
234  std::string
235  getClassName () const override
236  {
237  return ("ConvexHull");
238  }
239 
240  /* \brief True if we should compute the area and volume of the convex hull. */
242 
243  /* \brief The area of the convex hull. */
244  double total_area_;
245 
246  /* \brief The volume of the convex hull (only for 3D hulls, zero for 2D). */
248 
249  /** \brief The dimensionality of the concave hull (2D or 3D). */
251 
252  /** \brief How close can a 2D plane's normal be to an axis to make projection problematic. */
254 
255  /** \brief Option flag string to be used calling qhull. */
256  std::string qhull_flags;
257 
258  /* \brief x-axis - for checking valid projections. */
259  const Eigen::Vector3d x_axis_;
260 
261  /* \brief y-axis - for checking valid projections. */
262  const Eigen::Vector3d y_axis_;
263 
264  /* \brief z-axis - for checking valid projections. */
265  const Eigen::Vector3d z_axis_;
266 
267  /* \brief vector containing the point cloud indices of the convex hull points. */
269 
270  public:
272  };
273 }
274 
275 #ifdef PCL_NO_PRECOMPILE
276 #include <pcl/surface/impl/convex_hull.hpp>
277 #endif
278 
279 #endif
pcl::ConvexHull::total_area_
double total_area_
Definition: convex_hull.h:244
pcl_macros.h
Defines all the PCL and non-PCL macros used.
pcl::ConvexHull::setComputeAreaVolume
void setComputeAreaVolume(bool value)
If set to true, the qhull library is called to compute the total area and volume of the convex hull.
Definition: convex_hull.h:126
pcl
Definition: convolution.h:46
pcl::ConvexHull::getHullPointIndices
void getHullPointIndices(pcl::PointIndices &hull_point_indices) const
Retrieve the indices of the input point cloud that for the convex hull.
Definition: convex_hull.hpp:499
pcl::ConvexHull::PointCloudConstPtr
typename PointCloud::ConstPtr PointCloudConstPtr
Definition: convex_hull.h:89
pcl::ConvexHull::dimension_
int dimension_
The dimensionality of the concave hull (2D or 3D).
Definition: convex_hull.h:250
pcl::ConvexHull::PointCloudPtr
typename PointCloud::Ptr PointCloudPtr
Definition: convex_hull.h:88
pcl::comparePoints2D
bool comparePoints2D(const std::pair< int, Eigen::Vector4f > &p1, const std::pair< int, Eigen::Vector4f > &p2)
Sort 2D points in a vector structure.
Definition: convex_hull.h:60
pcl::ConvexHull::performReconstruction3D
void performReconstruction3D(PointCloud &points, std::vector< pcl::Vertices > &polygons, bool fill_polygon_data=false)
The reconstruction method for 3D data.
Definition: convex_hull.hpp:292
pcl::ConvexHull::performReconstruction2D
void performReconstruction2D(PointCloud &points, std::vector< pcl::Vertices > &polygons, bool fill_polygon_data=false)
The reconstruction method for 2D data.
Definition: convex_hull.hpp:76
pcl::ConvexHull::hull_indices_
pcl::PointIndices hull_indices_
Definition: convex_hull.h:268
pcl::PCLBase
PCL base class.
Definition: pcl_base.h:69
pcl::ConvexHull::getDimension
int getDimension() const
Returns the dimensionality (2 or 3) of the calculated hull.
Definition: convex_hull.h:165
pcl::ConvexHull::reconstruct
void reconstruct(PointCloud &points, std::vector< pcl::Vertices > &polygons)
Compute a convex hull for all points given.
Definition: convex_hull.hpp:479
pcl::PointCloud< PointInT >
pcl::ConvexHull::getTotalArea
double getTotalArea() const
Returns the total area of the convex hull.
Definition: convex_hull.h:137
pcl::ConvexHull::total_volume_
double total_volume_
Definition: convex_hull.h:247
pcl::ConvexHull::z_axis_
const Eigen::Vector3d z_axis_
Definition: convex_hull.h:265
pcl::ConvexHull::~ConvexHull
~ConvexHull()
Empty destructor.
Definition: convex_hull.h:99
pcl::ConvexHull::compute_area_
bool compute_area_
Definition: convex_hull.h:241
pcl::ConvexHull::getClassName
std::string getClassName() const override
Class get name method.
Definition: convex_hull.h:235
pcl::ConvexHull::qhull_flags
std::string qhull_flags
Option flag string to be used calling qhull.
Definition: convex_hull.h:256
pcl::ConvexHull::setDimension
void setDimension(int dimension)
Sets the dimension on the input data, 2D or 3D.
Definition: convex_hull.h:155
M_PI
#define M_PI
Definition: pcl_macros.h:195
pcl::ConvexHull::ConstPtr
shared_ptr< const ConvexHull< PointInT > > ConstPtr
Definition: convex_hull.h:83
pcl::PolygonMesh
Definition: PolygonMesh.h:15
PCL_MAKE_ALIGNED_OPERATOR_NEW
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition: memory.h:63
pcl::ConvexHull::y_axis_
const Eigen::Vector3d y_axis_
Definition: convex_hull.h:262
pcl::ConvexHull::Ptr
shared_ptr< ConvexHull< PointInT > > Ptr
Definition: convex_hull.h:82
pcl::ConvexHull::projection_angle_thresh_
double projection_angle_thresh_
How close can a 2D plane's normal be to an axis to make projection problematic.
Definition: convex_hull.h:253
pcl::PointIndices
Definition: PointIndices.h:13
pcl::ConvexHull::ConvexHull
ConvexHull()
Empty constructor.
Definition: convex_hull.h:92
pcl::ConvexHull::calculateInputDimension
void calculateInputDimension()
Automatically determines the dimension of input data - 2D or 3D.
Definition: convex_hull.hpp:57
pcl::PointCloud< PointInT >::Ptr
shared_ptr< PointCloud< PointInT > > Ptr
Definition: point_cloud.h:429
pcl::PointCloud< PointInT >::ConstPtr
shared_ptr< const PointCloud< PointInT > > ConstPtr
Definition: point_cloud.h:430
pcl::ConvexHull::x_axis_
const Eigen::Vector3d x_axis_
Definition: convex_hull.h:259
pcl::ConvexHull
ConvexHull using libqhull library.
Definition: convex_hull.h:73
pcl::ConvexHull::performReconstruction
void performReconstruction(PointCloud &points, std::vector< pcl::Vertices > &polygons, bool fill_polygon_data=false)
The actual reconstruction method.
Definition: convex_hull.hpp:421
memory.h
Defines functions, macros and traits for allocating and using memory.
pcl::MeshConstruction
MeshConstruction represents a base surface reconstruction class.
Definition: reconstruction.h:187
pcl::ConvexHull::getTotalVolume
double getTotalVolume() const
Returns the total volume of the convex hull.
Definition: convex_hull.h:146