← Back to branch summary

~ubuntu-branches/debian/stretch/cgal/stretch

« back to all changes in this revision

Viewing changes to include/CGAL/Constrained_Delaunay_triangulation_2.h

  • Committer: Package Import Robot
  • Author(s): Joachim Reichel
  • Date: 2014-04-05 10:56:43 UTC
  • mfrom: (1.2.4)
  • Revision ID: package-import@ubuntu.com-20140405105643-jgnrpu2thtx23zfs
Tags: 4.4-1
* New upstream release.
* Remove patches do-not-link-example-with-qt4-support-library.patch and
  fix_jet_fitting_3.patch (applied upstream).

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/CGAL/Constrained_Delaunay_triangulation_2.h
32
32
#include <boost/iterator/zip_iterator.hpp>
33
33
#include <boost/mpl/and.hpp>
34
34
 
 
35
#include <boost/iterator/counting_iterator.hpp>
 
36
 
35
37
namespace CGAL {
36
38
 
37
39
namespace internal{
332
334
  }
333
335
#endif //CGAL_TRIANGULATION_2_DONT_INSERT_RANGE_OF_POINTS_WITH_INFO
334
336
 
 
337
 
 
338
  template <class IndicesIterator>
 
339
  std::size_t insert_constraints( const std::vector<Point>& points,
 
340
                                  IndicesIterator indices_first,
 
341
                                  IndicesIterator indices_beyond )
 
342
  {
 
343
    typedef std::vector<std::ptrdiff_t> Vertex_indices;
 
344
    typedef std::vector<Vertex_handle> Vertices;
 
345
 
 
346
    Vertex_indices vertex_indices;
 
347
    vertex_indices.resize(points.size());
 
348
 
 
349
    std::copy(boost::counting_iterator<std::ptrdiff_t>(0),
 
350
              boost::counting_iterator<std::ptrdiff_t>(points.size()),
 
351
              std::back_inserter(vertex_indices));
 
352
 
 
353
    size_type n = this->number_of_vertices();
 
354
    Spatial_sort_traits_adapter_2<Gt, const Point*> sort_traits(&(points[0]));
 
355
 
 
356
    spatial_sort(vertex_indices.begin(), vertex_indices.end(), sort_traits);
 
357
 
 
358
    Vertices vertices;
 
359
    vertices.resize(points.size());
 
360
 
 
361
    Face_handle hint;
 
362
    for(typename Vertex_indices::const_iterator
 
363
          it_pti = vertex_indices.begin(), end = vertex_indices.end();
 
364
          it_pti != end; ++it_pti)
 
365
    {
 
366
      vertices[*it_pti] = insert(points[*it_pti], hint);
 
367
      hint=vertices[*it_pti]->face();
 
368
    }
 
369
 
 
370
    for(IndicesIterator it_cst=indices_first, end=indices_beyond;
 
371
        it_cst!=end; ++it_cst)
 
372
    {
 
373
      Vertex_handle v1 = vertices[it_cst->first];
 
374
      Vertex_handle v2 = vertices[it_cst->second];
 
375
      if(v1 != v2) insert_constraint(v1, v2);
 
376
    }
 
377
 
 
378
    return this->number_of_vertices() - n;
 
379
  }
 
380
 
 
381
  template <class PointIterator, class IndicesIterator>
 
382
  std::size_t insert_constraints(PointIterator points_first,
 
383
                                 PointIterator points_beyond,
 
384
                                 IndicesIterator indices_first,
 
385
                                 IndicesIterator indices_beyond)
 
386
  {
 
387
    std::vector<Point> points(points_first, points_beyond);
 
388
    return insert_constraints(points, indices_first, indices_beyond);
 
389
  }
 
390
 
 
391
  template <class Segment_2>
 
392
  static const Point& get_source(const Segment_2& segment){
 
393
    return segment.source();
 
394
  }
 
395
  template <class Segment_2>
 
396
  static const Point& get_target(const Segment_2& segment){
 
397
    return segment.target();
 
398
  }
 
399
 
 
400
  static const Point& get_source(const Constraint& cst){
 
401
    return cst.first;
 
402
  }
 
403
  static const Point& get_target(const Constraint& cst){
 
404
    return cst.second;
 
405
  }
 
406
 
 
407
  template <class ConstraintIterator>
 
408
  std::size_t insert_constraints(ConstraintIterator first,
 
409
                                 ConstraintIterator beyond)
 
410
  {
 
411
    std::vector<Point> points;
 
412
    for (ConstraintIterator s_it=first; s_it!=beyond; ++s_it)
 
413
    {
 
414
      points.push_back( get_source(*s_it) );
 
415
      points.push_back( get_target(*s_it) );
 
416
    }
 
417
 
 
418
    std::vector< std::pair<std::size_t, std::size_t> > segment_indices;
 
419
    std::size_t nb_segments = points.size() / 2;
 
420
    segment_indices.reserve( nb_segments );
 
421
    for (std::size_t k=0; k < nb_segments; ++k)
 
422
      segment_indices.push_back( std::make_pair(2*k,2*k+1) );
 
423
 
 
424
    return insert_constraints( points,
 
425
                               segment_indices.begin(),
 
426
                               segment_indices.end() );
 
427
  }
 
428
 
335
429
  template <class OutputItFaces, class OutputItBoundaryEdges> 
336
430
  std::pair<OutputItFaces,OutputItBoundaryEdges>
337
431
  get_conflicts_and_boundary(const Point  &p,