近似共面3d点的三角剖分/多边形化

Question

我有一个3d(由std::向量表示)和给定平面p中的点列表，使得:

1. 每个点与p的距离小于阈值。
2. 点列表中没有重复点

点在平面上的投影是一个二维多边形，可以是复简并和无孔。

我想对这些点进行三角剖分(或者，如果可能的话，多边形化)，使该三角剖分在平面上的投影对应于平面上的点的投影在2D中的三角剖分。换句话说，我需要"三角测量"one_answers"平面投影"这两个操作之间的交换性。

因此凸包是不令人满意的。

CGAL能做到吗?

Answer 1

下面的代码应该是您想要的。您需要知道平面的正交向量(您可以使用PCA包自动获得它)。

#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]);
}

使用CGAL 4.9，对于较大的多边形，以下代码将更快(它可以在4.8中工作，但需要以下补丁):

#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() );
}