Triangulation/Polygonisierung von approximataly coplanar 3D-Punkten

Question

Ich habe eine Liste von Punkten in 3D (dargestellt durch einen std :: vector) und eine gegebene Ebene P derart, daß:

1. Jeder Punkt in einem Abstand kleiner als ein Schwellenwert von P.
2. Es gibt keine Duplikate in der Liste der Punkte.

Die Projektion der Punkte auf der Ebene ist ein 2D-Vieleck, dasKomplex degenerierten und ohne Löcher sein können.

Ich möchte eine Triangulation (oder, wenn möglich, eine Polygonisierung) dieser Punkte, so dass die Projektion dieser Triangulation in der Ebene einer Triangulation in 2D der Projektionen der Punkte auf der Ebene entspricht. Mit anderen Worten, ich brauche Kommutativität zwischen den Operationen: "Triangulate" und "Projekt auf Ebene".

Daher ist eine konvexe Hülle nicht befriedigend.

Kann CGAL das tun?

Answer 1

Der folgende Code sollte tun, was Sie wollen. Sie müssen den orthogonalen Vektor der Ebene kennen (Sie können das Paket PCA verwenden, um es automatisch zu erhalten).

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

Mit CGAL 4,9, wird der folgende Code schneller für größeren Polygone (Es ist mit 4.8 arbeiten, aber die folgenden patch erforderlich):

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

}