Triangulation/polygonisation of approximataly coplanar 3d points

Question

I have a list of points in 3d (represented by a std::vector) and a given plane P such that:

Each point is at a distance smaller than a threshold from P.
There are no duplicates in the list of points.

The projection of the points on the plane is a 2D polygon which can be complex degenerate and without holes.

I want a triangulation (or, if possible, a polygonization) of those points such that the projection of that triangulation on the plane corresponds to a triangulation in 2D of the projections of the points on the plane. In other words， I need commutativity between the operations : "Triangulate" and "project on plane".

Therefore a convex hull is not satisfying.

Can CGAL do that?

sloriot sloriot · Accepted Answer · 2016-06-29T07:57:48

The following code should be doing what you want. You need to know the orthogonal vector of the plane (you can use the PCA package to get it automatically).

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_2_projection_traits_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_2_projection_traits_3<K> CDT_traits;
typedef CGAL::Constrained_Delaunay_triangulation_2<CDT_traits> CDT;
typedef std::pair<K::Point_3, K::Point_3> Constraint;

int main()
{
  K::Vector_3 plane_orthogonal_vector(1,1,0);
  CDT_traits traits(plane_orthogonal_vector);
  CDT cdt(traits);

  std::vector<CDT::Vertex_handle> vertices;
  vertices.push_back( cdt.insert(K::Point_3(0,0,0)) );
  vertices.push_back( cdt.insert(K::Point_3(1,1,0)) );
  vertices.push_back( cdt.insert(K::Point_3(1,1,1)) );
  vertices.push_back( cdt.insert(K::Point_3(0,0,1)) );

  cdt.insert_constraint(vertices[0],vertices[1]);
  cdt.insert_constraint(vertices[1],vertices[2]);
  cdt.insert_constraint(vertices[2],vertices[3]);
  cdt.insert_constraint(vertices[3],vertices[0]);
}

With CGAL 4.9, the following code will be faster for larger polygons (It is working with 4.8 but the following patch is needed):

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_2_projection_traits_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_2_projection_traits_3<K> CDT_traits;
typedef CGAL::Constrained_Delaunay_triangulation_2<CDT_traits> CDT;
typedef std::pair<std::size_t, std::size_t> Index_pair;

int main()
{
  K::Vector_3 plane_orthogonal_vector(1,1,0);
  CDT_traits traits(plane_orthogonal_vector);
  CDT cdt(traits);

  std::vector<K::Point_3> points;
  points.push_back( K::Point_3(0,0,0) );
  points.push_back( K::Point_3(1,1,0) );
  points.push_back( K::Point_3(1,1,1) );
  points.push_back( K::Point_3(0,0,1) );

  std::vector<Index_pair > constraint_indices;
  constraint_indices.push_back( Index_pair(0,1) );
  constraint_indices.push_back( Index_pair(1,2) );
  constraint_indices.push_back( Index_pair(2,3) );
  constraint_indices.push_back( Index_pair(3,0) );


  cdt.insert_constraints( points.begin(), points.end(),
                          constraint_indices.begin(), constraint_indices.end() );

}

Triangulation/polygonisation of approximataly coplanar 3d points

1 Answers