CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

In the meantime I worked out an example of how to use the
Delaunay_triangulation_3 and Polyhedron_incremental_builder_3 to do the 
same job than documented functions in the case the input points are not 
contained in a plane.

S.


johnzjq wrote:
> <style> <!-- /* Font Definitions */ @font-face {font-family:宋体; 
> panose-1:2 1 6 0 3 1 1 1 1 1;} @font-face {font-family:"Cambria Math"; 
> panose-1:2 4 5 3 5 4 6 3 2 4;} @font-face {font-family:Calibri; 
> panose-1:2 15 5 2 2 2 4 3 2 4;} @font-face {font-family:"\@宋体"; 
> panose-1:2 1 6 0 3 1 1 1 1 1;} @font-face {font-family:Tahoma; 
> panose-1:2 11 6 4 3 5 4 4 2 4;} /* Style Definitions */ p.MsoNormal, 
> li.MsoNormal, div.MsoNormal {margin:0cm; margin-bottom:.0001pt; 
> font-size:12.0pt; font-family:"Times New Roman","serif";} a:link, 
> span.MsoHyperlink {mso-style-priority:99; color:blue; 
> text-decoration:underline;} a:visited, span.MsoHyperlinkFollowed 
> {mso-style-priority:99; color:purple; text-decoration:underline;} 
> span.EmailStyle17 {mso-style-type:personal-reply; 
> font-family:"Calibri","sans-serif"; color:#1F497D;} .MsoChpDefault 
> {mso-style-type:export-only;} @page WordSection1 {size:612.0pt 792.0pt; 
> margin:72.0pt 90.0pt 72.0pt 90.0pt;} div.WordSection1 
> {page:WordSection1;} --> </style>
>
> That’s very kind of you! I will try it by myself using newly updated Qhull.
>
>  
>
> John
>
> ------------------------------------------------------------------------
>
> View message @ 
> http://cgal-discuss.949826.n4.nabble.com/Convex-hull-errors-tp3078363p3095161.html 
> <http://cgal-discuss.949826.n4.nabble.com/Convex-hull-errors-tp3078363p3095161.html?by-user=t>
> To unsubscribe from Convex hull errors, click here 
> <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=3078363&code=am9obnpqcUBnbWFpbC5jb218MzA3ODM2M3wtMTE5MjU5NDk4Nw==&by-user=t>. 
>
>
>
> ------------------------------------------------------------------------
> View this message in context: 答复: Convex hull errors 
> <http://cgal-discuss.949826.n4.nabble.com/Convex-hull-errors-tp3078363p3095187.html>
> Sent from the cgal-discuss mailing list archive 
> <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyhedron_incremental_builder_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <fstream>

// A modifier creating a triangle with the incremental builder.
template <class HDS,class Triangulation>
class Build_convex_hull_from_triangulation_3 : public CGAL::Modifier_base<HDS> {
  typedef std::map<typename Triangulation::Vertex_handle,unsigned> Vertex_map;
  
  const Triangulation& t;
  template <class Builder>
  static unsigned get_vertex_index( Vertex_map& vertex_map,
                                    typename Triangulation::Vertex_handle vh,
                                    Builder& builder,
                                    unsigned& vindex)
  {
    std::pair<typename Vertex_map::iterator,bool>
      res=vertex_map.insert(std::make_pair(vh,vindex));
    if (res.second){
      builder.add_vertex(vh->point());
      ++vindex;
    }
    return res.first->second;
  }
  
public:
  Build_convex_hull_from_triangulation_3(const Triangulation& t_):t(t_) 
  {
    CGAL_assertion(t.dimension()==3);
  }
  void operator()( HDS& hds) {
    // Postcondition: `hds' is a valid polyhedral surface.
    typedef typename HDS::Vertex   Vertex;
    typedef typename Vertex::Point Point;    
    
    CGAL::Polyhedron_incremental_builder_3<HDS> B( hds, true);
    std::vector<typename Triangulation::Cell_handle>  ch_facets;
    Vertex_map vertex_map;
    t.incident_cells(t.infinite_vertex(),std::back_inserter(ch_facets));
    std::size_t nb_facets=ch_facets.size();
    //start the surface
    B.begin_surface( nb_facets, nb_facets);
    unsigned vindex=0;
    for (typename std::vector<typename Triangulation::Cell_handle>::const_iterator it=
          ch_facets.begin();it!=ch_facets.end();++it)
    {
      unsigned ifv_index= (*it)->index(t.infinite_vertex());
      bool is_odd=ifv_index%2==0;
      unsigned i0=get_vertex_index(vertex_map,(*it)->vertex((ifv_index + (is_odd?3:1) )%4),B,vindex);
      unsigned i1=get_vertex_index(vertex_map,(*it)->vertex((ifv_index + 2            )%4),B,vindex);
      unsigned i2=get_vertex_index(vertex_map,(*it)->vertex((ifv_index + (is_odd?1:3) )%4),B,vindex);
      B.begin_facet();
      B.add_vertex_to_facet( i0 );
      B.add_vertex_to_facet( i1 );
      B.add_vertex_to_facet( i2 );
      B.end_facet();      
    }
    B.end_surface();
  }
};

template <class PointIterator,class Polyhedron>
void make_convex_hull_3(PointIterator begin,PointIterator end,Polyhedron& P)
{
  typedef typename CGAL::Kernel_traits<
    typename std::iterator_traits<PointIterator>::value_type
  >::Kernel                                                      Kernel;
  typedef typename Polyhedron::HalfedgeDS                        HalfedgeDS;
  typedef typename CGAL::Delaunay_triangulation_3<Kernel>        Triangulation;
  Triangulation dt3(begin,end);

  Build_convex_hull_from_triangulation_3<HalfedgeDS,Triangulation> get_chull(dt3);
  P.delegate( get_chull );
  CGAL_assertion( P.is_pure_triangle() );  
}

typedef CGAL::Exact_predicates_inexact_constructions_kernel     Kernel;
typedef CGAL::Polyhedron_3<Kernel>                              Polyhedron;


int main() {
  std::ifstream iFile;
  iFile.open("1.off");
  if (!iFile.is_open())
  {
    std::cerr<<"Error opening file\n";
    exit(EXIT_FAILURE);
  }
  Polyhedron P_tmp;
  iFile >> P_tmp;
  iFile.close();

  Polyhedron chull;
  make_convex_hull_3(P_tmp.points_begin(),P_tmp.points_end(),chull);
  
  std::ofstream out("out.off");
  out << chull;
  
  return 0;
}