Point Cloud Library (PCL)  1.8.1-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 #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
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
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
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
boost::shared_ptr< const PointCloud< PointT > > ConstPtr
Definition: point_cloud.h:429
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
double getTotalVolume() const
Returns the total volume of the convex hull.
Definition: convex_hull.h:145
boost::shared_ptr< PointCloud< PointT > > Ptr
Definition: point_cloud.h:428
const Eigen::Vector3d z_axis_
Definition: convex_hull.h:264
PointCloud::ConstPtr PointCloudConstPtr
Definition: convex_hull.h:88
std::string getClassName() const
Class get name method.
Definition: convex_hull.h:234
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
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
void getHullPointIndices(pcl::PointIndices &hull_point_indices) const
Retrieve the indices of the input point cloud that for the convex hull.
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.
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'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