Point Cloud Library (PCL)  1.7.0
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 wheter 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  protected:
170  /** \brief The actual reconstruction method.
171  *
172  * \param[out] points the resultant points lying on the convex hull
173  * \param[out] polygons the resultant convex hull polygons, as a set of
174  * vertices. The Vertices structure contains an array of point indices.
175  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
176  */
177  void
179  std::vector<pcl::Vertices> &polygons,
180  bool fill_polygon_data = false);
181 
182  /** \brief The reconstruction method for 2D data. Does not require dimension to be set.
183  *
184  * \param[out] points the resultant points lying on the convex hull
185  * \param[out] polygons the resultant convex hull polygons, as a set of
186  * vertices. The Vertices structure contains an array of point indices.
187  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
188  */
189  void
191  std::vector<pcl::Vertices> &polygons,
192  bool fill_polygon_data = false);
193 
194  /** \brief The reconstruction method for 3D data. Does not require dimension to be set.
195  *
196  * \param[out] points the resultant points lying on the convex hull
197  * \param[out] polygons the resultant convex hull polygons, as a set of
198  * vertices. The Vertices structure contains an array of point indices.
199  * \param[in] fill_polygon_data true if polygons should be filled, false otherwise
200  */
201  void
203  std::vector<pcl::Vertices> &polygons,
204  bool fill_polygon_data = false);
205 
206  /** \brief A reconstruction method that returns a polygonmesh.
207  *
208  * \param[out] output a PolygonMesh representing the convex hull of the input data.
209  */
210  virtual void
212 
213  /** \brief A reconstruction method that returns the polygon of the convex hull.
214  *
215  * \param[out] polygons the polygon(s) representing the convex hull of the input data.
216  */
217  virtual void
218  performReconstruction (std::vector<pcl::Vertices> &polygons);
219 
220  /** \brief Automatically determines the dimension of input data - 2D or 3D. */
221  void
223 
224  /** \brief Class get name method. */
225  std::string
226  getClassName () const
227  {
228  return ("ConvexHull");
229  }
230 
231  /* \brief True if we should compute the area and volume of the convex hull. */
233 
234  /* \brief The area of the convex hull. */
235  double total_area_;
236 
237  /* \brief The volume of the convex hull (only for 3D hulls, zero for 2D). */
239 
240  /** \brief The dimensionality of the concave hull (2D or 3D). */
242 
243  /** \brief How close can a 2D plane's normal be to an axis to make projection problematic. */
245 
246  /** \brief Option flag string to be used calling qhull. */
247  std::string qhull_flags;
248 
249  /* \brief x-axis - for checking valid projections. */
250  const Eigen::Vector3d x_axis_;
251 
252  /* \brief y-axis - for checking valid projections. */
253  const Eigen::Vector3d y_axis_;
254 
255  /* \brief z-axis - for checking valid projections. */
256  const Eigen::Vector3d z_axis_;
257 
258  public:
259  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
260  };
261 }
262 
263 #ifdef PCL_NO_PRECOMPILE
264 #include <pcl/surface/impl/convex_hull.hpp>
265 #endif
266 
267 #endif //#ifndef PCL_CONVEX_HULL_2D_H_
268 #endif