Point Cloud Library (PCL)  1.8.1
concave_hull.hpp
1 /**
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2011, 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_SURFACE_IMPL_CONCAVE_HULL_H_
44 #define PCL_SURFACE_IMPL_CONCAVE_HULL_H_
45 
46 #include <map>
47 #include <pcl/surface/concave_hull.h>
48 #include <pcl/common/common.h>
49 #include <pcl/common/eigen.h>
50 #include <pcl/common/centroid.h>
51 #include <pcl/common/transforms.h>
52 #include <pcl/kdtree/kdtree_flann.h>
53 #include <pcl/common/io.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <pcl/surface/qhull.h>
57 
58 //////////////////////////////////////////////////////////////////////////
59 /** \brief Get dimension of concave hull
60  * \return dimension
61  */
62 template <typename PointInT> int
64 {
65  return (getDimension ());
66 }
67 
68 //////////////////////////////////////////////////////////////////////////
69 template <typename PointInT> void
71 {
72  output.header = input_->header;
73  if (alpha_ <= 0)
74  {
75  PCL_ERROR ("[pcl::%s::reconstruct] Alpha parameter must be set to a positive number!\n", getClassName ().c_str ());
76  output.points.clear ();
77  return;
78  }
79 
80  if (!initCompute ())
81  {
82  output.points.clear ();
83  return;
84  }
85 
86  // Perform the actual surface reconstruction
87  std::vector<pcl::Vertices> polygons;
88  performReconstruction (output, polygons);
89 
90  output.width = static_cast<uint32_t> (output.points.size ());
91  output.height = 1;
92  output.is_dense = true;
93 
94  deinitCompute ();
95 }
96 
97 //////////////////////////////////////////////////////////////////////////
98 template <typename PointInT> void
99 pcl::ConcaveHull<PointInT>::reconstruct (PointCloud &output, std::vector<pcl::Vertices> &polygons)
100 {
101  output.header = input_->header;
102  if (alpha_ <= 0)
103  {
104  PCL_ERROR ("[pcl::%s::reconstruct] Alpha parameter must be set to a positive number!\n", getClassName ().c_str ());
105  output.points.clear ();
106  return;
107  }
108 
109  if (!initCompute ())
110  {
111  output.points.clear ();
112  return;
113  }
114 
115  // Perform the actual surface reconstruction
116  performReconstruction (output, polygons);
117 
118  output.width = static_cast<uint32_t> (output.points.size ());
119  output.height = 1;
120  output.is_dense = true;
121 
122  deinitCompute ();
123 }
124 
125 #ifdef __GNUC__
126 #pragma GCC diagnostic ignored "-Wold-style-cast"
127 #endif
128 //////////////////////////////////////////////////////////////////////////
129 template <typename PointInT> void
130 pcl::ConcaveHull<PointInT>::performReconstruction (PointCloud &alpha_shape, std::vector<pcl::Vertices> &polygons)
131 {
132  Eigen::Vector4d xyz_centroid;
133  compute3DCentroid (*input_, *indices_, xyz_centroid);
134  EIGEN_ALIGN16 Eigen::Matrix3d covariance_matrix;
135  computeCovarianceMatrixNormalized (*input_, *indices_, xyz_centroid, covariance_matrix);
136 
137  // Check if the covariance matrix is finite or not.
138  for (int i = 0; i < 3; ++i)
139  for (int j = 0; j < 3; ++j)
140  if (!pcl_isfinite (covariance_matrix.coeffRef (i, j)))
141  return;
142 
143  EIGEN_ALIGN16 Eigen::Vector3d eigen_values;
144  EIGEN_ALIGN16 Eigen::Matrix3d eigen_vectors;
145  pcl::eigen33 (covariance_matrix, eigen_vectors, eigen_values);
146 
147  Eigen::Affine3d transform1;
148  transform1.setIdentity ();
149 
150  // If no input dimension is specified, determine automatically
151  if (dim_ == 0)
152  {
153  PCL_DEBUG ("[pcl::%s] WARNING: Input dimension not specified. Automatically determining input dimension.\n", getClassName ().c_str ());
154  if (std::abs (eigen_values[0]) < std::numeric_limits<double>::epsilon () || std::abs (eigen_values[0] / eigen_values[2]) < 1.0e-3)
155  dim_ = 2;
156  else
157  dim_ = 3;
158  }
159 
160  if (dim_ == 2)
161  {
162  // we have points laying on a plane, using 2d convex hull
163  // compute transformation bring eigen_vectors.col(i) to z-axis
164 
165  transform1 (2, 0) = eigen_vectors (0, 0);
166  transform1 (2, 1) = eigen_vectors (1, 0);
167  transform1 (2, 2) = eigen_vectors (2, 0);
168 
169  transform1 (1, 0) = eigen_vectors (0, 1);
170  transform1 (1, 1) = eigen_vectors (1, 1);
171  transform1 (1, 2) = eigen_vectors (2, 1);
172  transform1 (0, 0) = eigen_vectors (0, 2);
173  transform1 (0, 1) = eigen_vectors (1, 2);
174  transform1 (0, 2) = eigen_vectors (2, 2);
175  }
176  else
177  {
178  transform1.setIdentity ();
179  }
180 
181  PointCloud cloud_transformed;
182  pcl::demeanPointCloud (*input_, *indices_, xyz_centroid, cloud_transformed);
183  pcl::transformPointCloud (cloud_transformed, cloud_transformed, transform1);
184 
185  // True if qhull should free points in qh_freeqhull() or reallocation
186  boolT ismalloc = True;
187  // option flags for qhull, see qh_opt.htm
188  char flags[] = "qhull d QJ";
189  // output from qh_produce_output(), use NULL to skip qh_produce_output()
190  FILE *outfile = NULL;
191  // error messages from qhull code
192  FILE *errfile = stderr;
193  // 0 if no error from qhull
194  int exitcode;
195 
196  // Array of coordinates for each point
197  coordT *points = reinterpret_cast<coordT*> (calloc (cloud_transformed.points.size () * dim_, sizeof(coordT)));
198 
199  for (size_t i = 0; i < cloud_transformed.points.size (); ++i)
200  {
201  points[i * dim_ + 0] = static_cast<coordT> (cloud_transformed.points[i].x);
202  points[i * dim_ + 1] = static_cast<coordT> (cloud_transformed.points[i].y);
203 
204  if (dim_ > 2)
205  points[i * dim_ + 2] = static_cast<coordT> (cloud_transformed.points[i].z);
206  }
207 
208  // Compute concave hull
209  exitcode = qh_new_qhull (dim_, static_cast<int> (cloud_transformed.points.size ()), points, ismalloc, flags, outfile, errfile);
210 
211  if (exitcode != 0)
212  {
213  PCL_ERROR ("[pcl::%s::performReconstrution] ERROR: qhull was unable to compute a concave hull for the given point cloud (%lu)!\n", getClassName ().c_str (), cloud_transformed.points.size ());
214 
215  //check if it fails because of NaN values...
216  if (!cloud_transformed.is_dense)
217  {
218  bool NaNvalues = false;
219  for (size_t i = 0; i < cloud_transformed.size (); ++i)
220  {
221  if (!pcl_isfinite (cloud_transformed.points[i].x) ||
222  !pcl_isfinite (cloud_transformed.points[i].y) ||
223  !pcl_isfinite (cloud_transformed.points[i].z))
224  {
225  NaNvalues = true;
226  break;
227  }
228  }
229 
230  if (NaNvalues)
231  PCL_ERROR ("[pcl::%s::performReconstruction] ERROR: point cloud contains NaN values, consider running pcl::PassThrough filter first to remove NaNs!\n", getClassName ().c_str ());
232  }
233 
234  alpha_shape.points.resize (0);
235  alpha_shape.width = alpha_shape.height = 0;
236  polygons.resize (0);
237 
238  qh_freeqhull (!qh_ALL);
239  int curlong, totlong;
240  qh_memfreeshort (&curlong, &totlong);
241 
242  return;
243  }
244 
245  qh_setvoronoi_all ();
246 
247  int num_vertices = qh num_vertices;
248  alpha_shape.points.resize (num_vertices);
249 
250  vertexT *vertex;
251  // Max vertex id
252  int max_vertex_id = 0;
253  FORALLvertices
254  {
255  if (vertex->id + 1 > max_vertex_id)
256  max_vertex_id = vertex->id + 1;
257  }
258 
259  facetT *facet; // set by FORALLfacets
260 
261  ++max_vertex_id;
262  std::vector<int> qhid_to_pcidx (max_vertex_id);
263 
264  int num_facets = qh num_facets;
265  int dd = 0;
266 
267  if (dim_ == 3)
268  {
269  setT *triangles_set = qh_settemp (4 * num_facets);
270  if (voronoi_centers_)
271  voronoi_centers_->points.resize (num_facets);
272 
273  int non_upper = 0;
274  FORALLfacets
275  {
276  // Facets are tetrahedrons (3d)
277  if (!facet->upperdelaunay)
278  {
279  vertexT *anyVertex = static_cast<vertexT*> (facet->vertices->e[0].p);
280  double *center = facet->center;
281  double r = qh_pointdist (anyVertex->point,center,dim_);
282  facetT *neighb;
283 
284  if (voronoi_centers_)
285  {
286  voronoi_centers_->points[non_upper].x = static_cast<float> (facet->center[0]);
287  voronoi_centers_->points[non_upper].y = static_cast<float> (facet->center[1]);
288  voronoi_centers_->points[non_upper].z = static_cast<float> (facet->center[2]);
289  }
290 
291  non_upper++;
292 
293  if (r <= alpha_)
294  {
295  // all triangles in tetrahedron are good, add them all to the alpha shape (triangles_set)
296  qh_makeridges (facet);
297  facet->good = true;
298  facet->visitid = qh visit_id;
299  ridgeT *ridge, **ridgep;
300  FOREACHridge_ (facet->ridges)
301  {
302  neighb = otherfacet_ (ridge, facet);
303  if ((neighb->visitid != qh visit_id))
304  qh_setappend (&triangles_set, ridge);
305  }
306  }
307  else
308  {
309  // consider individual triangles from the tetrahedron...
310  facet->good = false;
311  facet->visitid = qh visit_id;
312  qh_makeridges (facet);
313  ridgeT *ridge, **ridgep;
314  FOREACHridge_ (facet->ridges)
315  {
316  facetT *neighb;
317  neighb = otherfacet_ (ridge, facet);
318  if ((neighb->visitid != qh visit_id))
319  {
320  // check if individual triangle is good and add it to triangles_set
321 
322  PointInT a, b, c;
323  a.x = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[0].p))->point[0]);
324  a.y = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[0].p))->point[1]);
325  a.z = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[0].p))->point[2]);
326  b.x = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[1].p))->point[0]);
327  b.y = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[1].p))->point[1]);
328  b.z = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[1].p))->point[2]);
329  c.x = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[2].p))->point[0]);
330  c.y = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[2].p))->point[1]);
331  c.z = static_cast<float> ((static_cast<vertexT*>(ridge->vertices->e[2].p))->point[2]);
332 
333  double r = pcl::getCircumcircleRadius (a, b, c);
334  if (r <= alpha_)
335  qh_setappend (&triangles_set, ridge);
336  }
337  }
338  }
339  }
340  }
341 
342  if (voronoi_centers_)
343  voronoi_centers_->points.resize (non_upper);
344 
345  // filter, add points to alpha_shape and create polygon structure
346 
347  int num_good_triangles = 0;
348  ridgeT *ridge, **ridgep;
349  FOREACHridge_ (triangles_set)
350  {
351  if (ridge->bottom->upperdelaunay || ridge->top->upperdelaunay || !ridge->top->good || !ridge->bottom->good)
352  num_good_triangles++;
353  }
354 
355  polygons.resize (num_good_triangles);
356 
357  int vertices = 0;
358  std::vector<bool> added_vertices (max_vertex_id, false);
359 
360  int triangles = 0;
361  FOREACHridge_ (triangles_set)
362  {
363  if (ridge->bottom->upperdelaunay || ridge->top->upperdelaunay || !ridge->top->good || !ridge->bottom->good)
364  {
365  polygons[triangles].vertices.resize (3);
366  int vertex_n, vertex_i;
367  FOREACHvertex_i_ ((*ridge).vertices) //3 vertices per ridge!
368  {
369  if (!added_vertices[vertex->id])
370  {
371  alpha_shape.points[vertices].x = static_cast<float> (vertex->point[0]);
372  alpha_shape.points[vertices].y = static_cast<float> (vertex->point[1]);
373  alpha_shape.points[vertices].z = static_cast<float> (vertex->point[2]);
374 
375  qhid_to_pcidx[vertex->id] = vertices; //map the vertex id of qhull to the point cloud index
376  added_vertices[vertex->id] = true;
377  vertices++;
378  }
379 
380  polygons[triangles].vertices[vertex_i] = qhid_to_pcidx[vertex->id];
381 
382  }
383 
384  triangles++;
385  }
386  }
387 
388  alpha_shape.points.resize (vertices);
389  alpha_shape.width = static_cast<uint32_t> (alpha_shape.points.size ());
390  alpha_shape.height = 1;
391  }
392  else
393  {
394  // Compute the alpha complex for the set of points
395  // Filters the delaunay triangles
396  setT *edges_set = qh_settemp (3 * num_facets);
397  if (voronoi_centers_)
398  voronoi_centers_->points.resize (num_facets);
399 
400  FORALLfacets
401  {
402  // Facets are the delaunay triangles (2d)
403  if (!facet->upperdelaunay)
404  {
405  // Check if the distance from any vertex to the facet->center
406  // (center of the voronoi cell) is smaller than alpha
407  vertexT *anyVertex = static_cast<vertexT*>(facet->vertices->e[0].p);
408  double r = (sqrt ((anyVertex->point[0] - facet->center[0]) *
409  (anyVertex->point[0] - facet->center[0]) +
410  (anyVertex->point[1] - facet->center[1]) *
411  (anyVertex->point[1] - facet->center[1])));
412  if (r <= alpha_)
413  {
414  pcl::Vertices facet_vertices; //TODO: is not used!!
415  qh_makeridges (facet);
416  facet->good = true;
417 
418  ridgeT *ridge, **ridgep;
419  FOREACHridge_ (facet->ridges)
420  qh_setappend (&edges_set, ridge);
421 
422  if (voronoi_centers_)
423  {
424  voronoi_centers_->points[dd].x = static_cast<float> (facet->center[0]);
425  voronoi_centers_->points[dd].y = static_cast<float> (facet->center[1]);
426  voronoi_centers_->points[dd].z = 0.0f;
427  }
428 
429  ++dd;
430  }
431  else
432  facet->good = false;
433  }
434  }
435 
436  int vertices = 0;
437  std::vector<bool> added_vertices (max_vertex_id, false);
438  std::map<int, std::vector<int> > edges;
439 
440  ridgeT *ridge, **ridgep;
441  FOREACHridge_ (edges_set)
442  {
443  if (ridge->bottom->upperdelaunay || ridge->top->upperdelaunay || !ridge->top->good || !ridge->bottom->good)
444  {
445  int vertex_n, vertex_i;
446  int vertices_in_ridge=0;
447  std::vector<int> pcd_indices;
448  pcd_indices.resize (2);
449 
450  FOREACHvertex_i_ ((*ridge).vertices) //in 2-dim, 2 vertices per ridge!
451  {
452  if (!added_vertices[vertex->id])
453  {
454  alpha_shape.points[vertices].x = static_cast<float> (vertex->point[0]);
455  alpha_shape.points[vertices].y = static_cast<float> (vertex->point[1]);
456 
457  if (dim_ > 2)
458  alpha_shape.points[vertices].z = static_cast<float> (vertex->point[2]);
459  else
460  alpha_shape.points[vertices].z = 0;
461 
462  qhid_to_pcidx[vertex->id] = vertices; //map the vertex id of qhull to the point cloud index
463  added_vertices[vertex->id] = true;
464  pcd_indices[vertices_in_ridge] = vertices;
465  vertices++;
466  }
467  else
468  {
469  pcd_indices[vertices_in_ridge] = qhid_to_pcidx[vertex->id];
470  }
471 
472  vertices_in_ridge++;
473  }
474 
475  // make edges bidirectional and pointing to alpha_shape pointcloud...
476  edges[pcd_indices[0]].push_back (pcd_indices[1]);
477  edges[pcd_indices[1]].push_back (pcd_indices[0]);
478  }
479  }
480 
481  alpha_shape.points.resize (vertices);
482 
483  std::vector<std::vector<int> > connected;
484  PointCloud alpha_shape_sorted;
485  alpha_shape_sorted.points.resize (vertices);
486 
487  // iterate over edges until they are empty!
488  std::map<int, std::vector<int> >::iterator curr = edges.begin ();
489  int next = - 1;
490  std::vector<bool> used (vertices, false); // used to decide which direction should we take!
491  std::vector<int> pcd_idx_start_polygons;
492  pcd_idx_start_polygons.push_back (0);
493 
494  // start following edges and removing elements
495  int sorted_idx = 0;
496  while (!edges.empty ())
497  {
498  alpha_shape_sorted.points[sorted_idx] = alpha_shape.points[(*curr).first];
499  // check where we can go from (*curr).first
500  for (size_t i = 0; i < (*curr).second.size (); i++)
501  {
502  if (!used[((*curr).second)[i]])
503  {
504  // we can go there
505  next = ((*curr).second)[i];
506  break;
507  }
508  }
509 
510  used[(*curr).first] = true;
511  edges.erase (curr); // remove edges starting from curr
512 
513  sorted_idx++;
514 
515  if (edges.empty ())
516  break;
517 
518  // reassign current
519  curr = edges.find (next); // if next is not found, then we have unconnected polygons.
520  if (curr == edges.end ())
521  {
522  // set current to any of the remaining in edge!
523  curr = edges.begin ();
524  pcd_idx_start_polygons.push_back (sorted_idx);
525  }
526  }
527 
528  pcd_idx_start_polygons.push_back (sorted_idx);
529 
530  alpha_shape.points = alpha_shape_sorted.points;
531 
532  polygons.reserve (pcd_idx_start_polygons.size () - 1);
533 
534  for (size_t poly_id = 0; poly_id < pcd_idx_start_polygons.size () - 1; poly_id++)
535  {
536  // Check if we actually have a polygon, and not some degenerated output from QHull
537  if (pcd_idx_start_polygons[poly_id + 1] - pcd_idx_start_polygons[poly_id] >= 3)
538  {
539  pcl::Vertices vertices;
540  vertices.vertices.resize (pcd_idx_start_polygons[poly_id + 1] - pcd_idx_start_polygons[poly_id]);
541  // populate points in the corresponding polygon
542  for (int j = pcd_idx_start_polygons[poly_id]; j < pcd_idx_start_polygons[poly_id + 1]; ++j)
543  vertices.vertices[j - pcd_idx_start_polygons[poly_id]] = static_cast<uint32_t> (j);
544 
545  polygons.push_back (vertices);
546  }
547  }
548 
549  if (voronoi_centers_)
550  voronoi_centers_->points.resize (dd);
551  }
552 
553  qh_freeqhull (!qh_ALL);
554  int curlong, totlong;
555  qh_memfreeshort (&curlong, &totlong);
556 
557  Eigen::Affine3d transInverse = transform1.inverse ();
558  pcl::transformPointCloud (alpha_shape, alpha_shape, transInverse);
559  xyz_centroid[0] = - xyz_centroid[0];
560  xyz_centroid[1] = - xyz_centroid[1];
561  xyz_centroid[2] = - xyz_centroid[2];
562  pcl::demeanPointCloud (alpha_shape, xyz_centroid, alpha_shape);
563 
564  // also transform voronoi_centers_...
565  if (voronoi_centers_)
566  {
567  pcl::transformPointCloud (*voronoi_centers_, *voronoi_centers_, transInverse);
568  pcl::demeanPointCloud (*voronoi_centers_, xyz_centroid, *voronoi_centers_);
569  }
570 
571  if (keep_information_)
572  {
573  // build a tree with the original points
574  pcl::KdTreeFLANN<PointInT> tree (true);
575  tree.setInputCloud (input_, indices_);
576 
577  std::vector<int> neighbor;
578  std::vector<float> distances;
579  neighbor.resize (1);
580  distances.resize (1);
581 
582  // for each point in the concave hull, search for the nearest neighbor in the original point cloud
583  hull_indices_.header = input_->header;
584  hull_indices_.indices.clear ();
585  hull_indices_.indices.reserve (alpha_shape.points.size ());
586 
587  for (size_t i = 0; i < alpha_shape.points.size (); i++)
588  {
589  tree.nearestKSearch (alpha_shape.points[i], 1, neighbor, distances);
590  hull_indices_.indices.push_back (neighbor[0]);
591  }
592 
593  // replace point with the closest neighbor in the original point cloud
594  pcl::copyPointCloud (*input_, hull_indices_.indices, alpha_shape);
595  }
596 }
597 #ifdef __GNUC__
598 #pragma GCC diagnostic warning "-Wold-style-cast"
599 #endif
600 
601 //////////////////////////////////////////////////////////////////////////////////////////
602 template <typename PointInT> void
604 {
605  // Perform reconstruction
606  pcl::PointCloud<PointInT> hull_points;
607  performReconstruction (hull_points, output.polygons);
608 
609  // Convert the PointCloud into a PCLPointCloud2
610  pcl::toPCLPointCloud2 (hull_points, output.cloud);
611 }
612 
613 //////////////////////////////////////////////////////////////////////////////////////////
614 template <typename PointInT> void
615 pcl::ConcaveHull<PointInT>::performReconstruction (std::vector<pcl::Vertices> &polygons)
616 {
617  pcl::PointCloud<PointInT> hull_points;
618  performReconstruction (hull_points, polygons);
619 }
620 
621 //////////////////////////////////////////////////////////////////////////////////////////
622 template <typename PointInT> void
624 {
625  hull_point_indices = hull_indices_;
626 }
627 
628 #define PCL_INSTANTIATE_ConcaveHull(T) template class PCL_EXPORTS pcl::ConcaveHull<T>;
629 
630 #endif // PCL_SURFACE_IMPL_CONCAVE_HULL_H_
631 #endif
KdTreeFLANN is a generic type of 3D spatial locator using kD-tree structures.
Definition: kdtree_flann.h:69
std::vector< PointT, Eigen::aligned_allocator< PointT > > points
The point data.
Definition: point_cloud.h:410
struct pcl::PointXYZIEdge EIGEN_ALIGN16
void setInputCloud(const PointCloudConstPtr &cloud, const IndicesConstPtr &indices=IndicesConstPtr())
Provide a pointer to the input dataset.
std::vector< uint32_t > vertices
Definition: Vertices.h:19
PCL_EXPORTS void copyPointCloud(const pcl::PCLPointCloud2 &cloud_in, const std::vector< int > &indices, pcl::PCLPointCloud2 &cloud_out)
Extract the indices of a given point cloud as a new point cloud.
uint32_t height
The point cloud height (if organized as an image-structure).
Definition: point_cloud.h:415
Describes a set of vertices in a polygon mesh, by basically storing an array of indices.
Definition: Vertices.h:14
Define standard C methods and C++ classes that are common to all methods.
uint32_t width
The point cloud width (if organized as an image-structure).
Definition: point_cloud.h:413
void transformPointCloud(const pcl::PointCloud< PointT > &cloud_in, pcl::PointCloud< PointT > &cloud_out, const Eigen::Transform< Scalar, 3, Eigen::Affine > &transform, bool copy_all_fields=true)
Apply an affine transform defined by an Eigen Transform.
Definition: transforms.hpp:42
void demeanPointCloud(ConstCloudIterator< PointT > &cloud_iterator, const Eigen::Matrix< Scalar, 4, 1 > &centroid, pcl::PointCloud< PointT > &cloud_out, int npts=0)
Subtract a centroid from a point cloud and return the de-meaned representation.
Definition: centroid.hpp:631
void reconstruct(PointCloud &points, std::vector< pcl::Vertices > &polygons)
Compute a concave hull for all points given.
void getHullPointIndices(pcl::PointIndices &hull_point_indices) const
Retrieve the indices of the input point cloud that for the convex hull.
std::vector< ::pcl::Vertices > polygons
Definition: PolygonMesh.h:24
pcl::PCLHeader header
The point cloud header.
Definition: point_cloud.h:407
void eigen33(const Matrix &mat, typename Matrix::Scalar &eigenvalue, Vector &eigenvector)
determines the eigenvector and eigenvalue of the smallest eigenvalue of the symmetric positive semi d...
Definition: eigen.hpp:251
int nearestKSearch(const PointT &point, int k, std::vector< int > &k_indices, std::vector< float > &k_sqr_distances) const
Search for k-nearest neighbors for the given query point.
::pcl::PCLPointCloud2 cloud
Definition: PolygonMesh.h:22
void toPCLPointCloud2(const pcl::PointCloud< PointT > &cloud, pcl::PCLPointCloud2 &msg)
Convert a pcl::PointCloud<T> object to a PCLPointCloud2 binary data blob.
Definition: conversions.h:242
double getCircumcircleRadius(const PointT &pa, const PointT &pb, const PointT &pc)
Compute the radius of a circumscribed circle for a triangle formed of three points pa,...
Definition: common.hpp:376
bool is_dense
True if no points are invalid (e.g., have NaN or Inf values).
Definition: point_cloud.h:418
void performReconstruction(PointCloud &points, std::vector< pcl::Vertices > &polygons)
The actual reconstruction method.
unsigned int computeCovarianceMatrixNormalized(const pcl::PointCloud< PointT > &cloud, const Eigen::Matrix< Scalar, 4, 1 > &centroid, Eigen::Matrix< Scalar, 3, 3 > &covariance_matrix)
Compute normalized the 3x3 covariance matrix of a given set of points.
Definition: centroid.hpp:251
unsigned int compute3DCentroid(ConstCloudIterator< PointT > &cloud_iterator, Eigen::Matrix< Scalar, 4, 1 > &centroid)
Compute the 3D (X-Y-Z) centroid of a set of points and return it as a 3D vector.
Definition: centroid.hpp:50
int getDim() const
Returns the dimensionality (2 or 3) of the calculated hull.
Define methods for centroid estimation and covariance matrix calculus.
size_t size() const
Definition: point_cloud.h:448