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