← Back to branch summary

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

« back to all changes in this revision

Viewing changes to include/CGAL/Arr_spherical_topology_traits_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/Arr_spherical_topology_traits_2.h
57
57
namespace CGAL {
58
58
 
59
59
// Forward declaration:
60
 
template <class GeomTraits, class TopTraits>
 
60
template <typename GeomTraits, typename TopTraits>
61
61
class Arrangement_on_surface_2;
62
62
 
63
63
/*! This class handles the topology for arrangements of great spherical
64
64
 * arcs on the sphere embedded on 2D parametric surdace.
65
65
 */
66
 
template <class GeomTraits, class T_Dcel = Arr_default_dcel<GeomTraits> >
 
66
template <typename GeomTraits_, typename Dcel_ = Arr_default_dcel<GeomTraits_> >
67
67
class Arr_spherical_topology_traits_2 {
68
68
public:
69
69
 
70
70
  ///! \name The geometry-traits types.
71
71
  //@{
72
 
  typedef GeomTraits                                      Geometry_traits_2;
 
72
  typedef GeomTraits_                                     Geometry_traits_2;
73
73
  typedef typename Geometry_traits_2::Point_2             Point_2;
74
74
  typedef typename Geometry_traits_2::X_monotone_curve_2  X_monotone_curve_2;
75
75
  //@}
76
76
 
77
77
  ///! \name The DCEL types.
78
78
  //@{
79
 
  typedef T_Dcel                                          Dcel;
 
79
  typedef Dcel_                                           Dcel;
80
80
  typedef typename Dcel::Size                             Size;
81
81
  typedef typename Dcel::Vertex                           Vertex;
82
82
  typedef typename Dcel::Halfedge                         Halfedge;
129
129
   * An auxiliary structure for rebinding the topology traits with a new
130
130
   * geometry-traits class and a new DCEL class.
131
131
   */
132
 
  template<typename T, typename D>
133
 
  struct rebind
134
 
  {
135
 
    typedef Arr_spherical_topology_traits_2<T,D> other;
 
132
  template <typename T, typename D>
 
133
  struct rebind {
 
134
    typedef Arr_spherical_topology_traits_2<T, D> other;
136
135
  };
137
136
 
138
137
private:
139
 
 
140
138
  //! A container of boundary vertices.
141
139
  struct Vertex_key_comparer {
142
140
    /*! Construct default */
143
 
    Vertex_key_comparer() : m_traits(NULL) {}
 
141
    Vertex_key_comparer() : m_geom_traits(NULL) {}
144
142
 
145
143
    /*! Construct */
146
 
    Vertex_key_comparer(const Traits_adaptor_2* traits) : m_traits(traits) {}
147
 
    const Traits_adaptor_2* m_traits;
 
144
    Vertex_key_comparer(const Traits_adaptor_2* geom_traits) :
 
145
      m_geom_traits(geom_traits)
 
146
    {}
 
147
 
 
148
    const Traits_adaptor_2* m_geom_traits;
 
149
 
148
150
    bool operator()(const Point_2& p1, const Point_2& p2) const
149
151
    {
150
 
      return (m_traits->compare_y_on_boundary_2_object()(p1, p2) ==
 
152
      return (m_geom_traits->compare_y_on_boundary_2_object()(p1, p2) ==
151
153
              SMALLER);
152
154
    }
153
155
  };
154
156
 
155
157
  //! \todo define the key to be 'const Point_2*'.
156
 
  typedef std::map<Point_2,Vertex*,Vertex_key_comparer>  Vertex_map;
157
 
  typedef std::pair<Point_2,Vertex*>                     Vertex_value;
 
158
  typedef std::map<Point_2, Vertex*, Vertex_key_comparer> Vertex_map;
 
159
  typedef std::pair<Point_2, Vertex*>                     Vertex_value;
158
160
 
159
161
protected:
160
162
  // Data members:
174
176
  Vertex_map m_boundary_vertices;
175
177
 
176
178
  //! The geometry-traits adaptor.
177
 
  const Traits_adaptor_2* m_traits;
 
179
  const Traits_adaptor_2* m_geom_traits;
178
180
 
179
 
  // Inidicates whether the traits object should evetually be freed.
180
 
  bool m_own_traits;
 
181
  //! Inidicates whether the traits object should evetually be freed.
 
182
  bool m_own_geom_traits;
181
183
 
182
184
  // Copy constructor and assignment operator - not supported.
183
 
  Arr_spherical_topology_traits_2(const Self &);
184
 
  Self& operator=(const Self &);
 
185
  Arr_spherical_topology_traits_2(const Self&);
 
186
  Self& operator=(const Self&);
185
187
 
186
188
public:
187
189
  ///! \name Construction methods.
190
192
  /*! Default constructor. */
191
193
  Arr_spherical_topology_traits_2();
192
194
 
193
 
  /*! Constructor with a geometry-traits class.
 
195
  /*! Constructor from a geometry-traits object.
194
196
   * \param traits the traits.
195
197
   */
196
198
  Arr_spherical_topology_traits_2(const Geometry_traits_2* traits);
197
199
 
 
200
  /*! Destructor */
 
201
  ~Arr_spherical_topology_traits_2();
 
202
 
198
203
  /*! Assign the contents of another topology-traits class.
199
204
   * \param other the other spherical topology-traits.
200
205
   */
288
293
  const Vertex* north_pole() const { return m_north_pole; }
289
294
 
290
295
  /*! Obtain the north pole (non-const version). */
291
 
  Vertex* north_pole()
292
 
  { return m_north_pole; }
 
296
  Vertex* north_pole() { return m_north_pole; }
293
297
 
294
298
  /*! Obtain a vertex on the line of discontinuity that corresponds to
295
299
   *  the given curve-end (or return NULL if no such vertex exists).
296
300
   */
297
301
  Vertex* discontinuity_vertex(const X_monotone_curve_2 xc, Arr_curve_end ind)
298
302
  {
299
 
    Point_2 key;
300
 
    key = (ind == ARR_MIN_END) ?
301
 
      m_traits->construct_min_vertex_2_object()(xc) :
302
 
      m_traits->construct_max_vertex_2_object()(xc);
 
303
    Point_2 key = (ind == ARR_MIN_END) ?
 
304
      m_geom_traits->construct_min_vertex_2_object()(xc) :
 
305
      m_geom_traits->construct_max_vertex_2_object()(xc);
303
306
    typename Vertex_map::iterator it = m_boundary_vertices.find(key);
304
307
    return (it != m_boundary_vertices.end()) ? it->second : NULL;
305
308
  }
308
311
private:
309
312
  /// \name Auxiliary type definitions.
310
313
  //@{
311
 
  typedef Arrangement_on_surface_2<Geometry_traits_2, Self>        Arr;
 
314
  typedef Arrangement_on_surface_2<Geometry_traits_2, Self>     Arr;
312
315
 
313
316
  // Type definition for the constuction sweep-line visitor.
314
317
  typedef Arr_construction_subcurve<Geometry_traits_2>          CSubcurve;
315
 
  typedef Arr_construction_event<Geometry_traits_2,CSubcurve,Arr>
 
318
  typedef Arr_construction_event<Geometry_traits_2, CSubcurve, Arr>
316
319
                                                                CEvent;
317
 
  typedef Arr_spherical_construction_helper<Geometry_traits_2,Arr,
 
320
  typedef Arr_spherical_construction_helper<Geometry_traits_2, Arr,
318
321
    CEvent,CSubcurve>                                           CHelper;
319
322
 
320
323
  // Type definition for the basic insertion sweep-line visitor.
321
324
  typedef Arr_basic_insertion_traits_2<Geometry_traits_2, Arr>  BInsTraits;
322
325
  typedef Arr_construction_subcurve<BInsTraits>                 BISubcurve;
323
 
  typedef Arr_construction_event<BInsTraits,BISubcurve,Arr>     BIEvent;
324
 
  typedef Arr_spherical_insertion_helper<BInsTraits,Arr,BIEvent,BISubcurve>
 
326
  typedef Arr_construction_event<BInsTraits, BISubcurve, Arr>   BIEvent;
 
327
  typedef Arr_spherical_insertion_helper<BInsTraits, Arr, BIEvent, BISubcurve>
325
328
                                                                BIHelper;
326
329
 
327
330
  // Type definition for the insertion sweep-line visitor.
328
331
  typedef Arr_insertion_traits_2<Geometry_traits_2, Arr>        InsTraits;
329
332
  typedef Arr_construction_subcurve<InsTraits>                  ISubcurve;
330
333
  typedef Arr_construction_event<InsTraits,ISubcurve,Arr>       IEvent;
331
 
  typedef Arr_spherical_insertion_helper<InsTraits,Arr,IEvent,ISubcurve>
 
334
  typedef Arr_spherical_insertion_helper<InsTraits, Arr, IEvent, ISubcurve>
332
335
                                                                IHelper;
333
336
 
334
337
  // Type definition for the batched point-location sweep-line visitor.
340
343
  typedef Arr_spherical_vert_decomp_helper<VdTraits, Arr>       VdHelper;
341
344
 
342
345
  // Type definition for the overlay sweep-line visitor.
343
 
  template <class ExGeomTraits_, class ArrangementA_, class ArrangementB_>
 
346
  template <typename ExGeomTraits_, typename ArrangementA_,
 
347
            typename ArrangementB_>
344
348
  struct _Overlay_helper :
345
 
    public Arr_spherical_overlay_helper<ExGeomTraits_, ArrangementA_,
346
 
    ArrangementB_, Arr, Arr_construction_event<ExGeomTraits_,
347
 
    Arr_overlay_subcurve<ExGeomTraits_>, Arr>,
348
 
    Arr_overlay_subcurve<ExGeomTraits_> >
 
349
    public Arr_spherical_overlay_helper
 
350
    <ExGeomTraits_, ArrangementA_, ArrangementB_, Arr,
 
351
     Arr_construction_event<ExGeomTraits_,
 
352
                            Arr_overlay_subcurve<ExGeomTraits_>, Arr>,
 
353
     Arr_overlay_subcurve<ExGeomTraits_> >
349
354
  {
350
 
    typedef Arr_spherical_overlay_helper<ExGeomTraits_, ArrangementA_,
351
 
      ArrangementB_, Arr, Arr_construction_event<ExGeomTraits_,
352
 
      Arr_overlay_subcurve<ExGeomTraits_>, Arr>,
353
 
      Arr_overlay_subcurve<ExGeomTraits_> >             Base;
 
355
    typedef ExGeomTraits_                               Ex_geomt_raits;
 
356
    typedef ArrangementA_                               Arrangement_a;
 
357
    typedef ArrangementB_                               Arrangement_b;
 
358
 
 
359
    typedef Arr_overlay_subcurve<Ex_geomt_raits>        Overlay_subcurve;
 
360
    typedef Arr_construction_event<Ex_geomt_raits, Overlay_subcurve, Arr>
 
361
                                                        Construction_event;
 
362
 
 
363
    typedef Arr_spherical_overlay_helper<Ex_geomt_raits,
 
364
                                         Arrangement_a, Arrangement_b, Arr,
 
365
                                         Construction_event, Overlay_subcurve>
 
366
                                                        Base;
354
367
 
355
368
    typedef typename Base::Traits_2                     Traits_2;
356
369
    typedef typename Base::Arrangement_red_2            Arrangement_red_2;
360
373
    typedef typename Base::Subcurve                     Subcurve;
361
374
    typedef typename Base::Construction_helper          Construction_helper;
362
375
 
363
 
    _Overlay_helper(const ArrangementA_* arrA, const ArrangementB_* arrB) :
364
 
      Base(arrA, arrB) {}
 
376
    _Overlay_helper(const Arrangement_a* arr_a, const Arrangement_b* arr_b) :
 
377
      Base(arr_a, arr_b)
 
378
    {}
365
379
  };
366
380
  //@}
367
381
 
381
395
  typedef Arr_basic_insertion_sl_visitor<BIHelper>
382
396
    Sweep_line_non_intersecting_insertion_visitor;
383
397
 
384
 
  template <class OutputIterator_>
 
398
  template <typename OutputIterator_>
385
399
  struct Sweep_line_batched_point_location_visitor :
386
400
    public Arr_batched_pl_sl_visitor<BplHelper, OutputIterator_>
387
401
  {
388
 
    typedef OutputIterator_                             Output_iterator;
 
402
    typedef OutputIterator_                                     Output_iterator;
389
403
 
390
 
    typedef Arr_batched_pl_sl_visitor<BplHelper, Output_iterator>   Base;
391
 
    typedef typename Base::Traits_2                                 Traits_2;
392
 
    typedef typename Base::Event                                    Event;
393
 
    typedef typename Base::Subcurve                                 Subcurve;
 
404
    typedef Arr_batched_pl_sl_visitor<BplHelper, Output_iterator> Base;
 
405
    typedef typename Base::Traits_2                             Traits_2;
 
406
    typedef typename Base::Event                                Event;
 
407
    typedef typename Base::Subcurve                             Subcurve;
394
408
 
395
409
    Sweep_line_batched_point_location_visitor(const Arr* arr,
396
410
                                              Output_iterator& oi) :
398
412
    {}
399
413
  };
400
414
 
401
 
  template <class OutputIterator_>
 
415
  template <typename OutputIterator_>
402
416
  struct Sweep_line_vertical_decomposition_visitor :
403
417
    public Arr_vert_decomp_sl_visitor<VdHelper, OutputIterator_>
404
418
  {
405
 
    typedef OutputIterator_                             Output_iterator;
 
419
    typedef OutputIterator_                                     Output_iterator;
406
420
    typedef Arr_vert_decomp_sl_visitor<VdHelper,Output_iterator>  Base;
407
421
 
408
 
    typedef typename Base::Traits_2                     Traits_2;
409
 
    typedef typename Base::Event                        Event;
410
 
    typedef typename Base::Subcurve                     Subcurve;
 
422
    typedef typename Base::Traits_2                             Traits_2;
 
423
    typedef typename Base::Event                                Event;
 
424
    typedef typename Base::Subcurve                             Subcurve;
411
425
 
412
426
    Sweep_line_vertical_decomposition_visitor(const Arr* arr,
413
427
                                              Output_iterator* oi) :
415
429
    {}
416
430
  };
417
431
 
418
 
  template <class ArrangementA_, class ArrangementB_, class OverlayTraits_>
 
432
  template <typename ArrangementA_, typename ArrangementB_,
 
433
            typename OverlayTraits_>
419
434
  struct Sweep_line_overlay_visitor :
420
435
    public Arr_overlay_sl_visitor
421
 
  <_Overlay_helper<Arr_overlay_traits_2<Geometry_traits_2,ArrangementA_,
422
 
    ArrangementB_>,
423
 
    ArrangementA_, ArrangementB_>, OverlayTraits_>
 
436
    <_Overlay_helper<Arr_overlay_traits_2<Geometry_traits_2,ArrangementA_,
 
437
                                          ArrangementB_>,
 
438
                     ArrangementA_, ArrangementB_>, OverlayTraits_>
424
439
  {
425
 
    typedef ArrangementA_                               ArrangementA_2;
426
 
    typedef ArrangementB_                               ArrangementB_2;
 
440
    typedef ArrangementA_                               Arrangement_a;
 
441
    typedef ArrangementB_                               Arrangement_b;
427
442
    typedef Arr                                         Arrangement_result_2;
428
443
    typedef OverlayTraits_                              Overlay_traits;
429
444
 
430
 
    typedef Arr_overlay_traits_2<Geometry_traits_2,ArrangementA_2,
431
 
      ArrangementB_2>                                   Geom_ovl_traits_2;
432
 
 
433
 
    typedef _Overlay_helper<Geom_ovl_traits_2,ArrangementA_2,ArrangementB_2>
434
 
                                                        Ovl_helper;
435
 
 
436
 
    typedef Arr_overlay_sl_visitor<Ovl_helper,Overlay_traits>   Base;
437
 
 
438
 
    typedef typename Base::Traits_2                     Traits_2;
439
 
    typedef typename Base::Event                        Event;
440
 
    typedef typename Base::Subcurve                     Subcurve;
441
 
 
442
 
    Sweep_line_overlay_visitor(const ArrangementA_2* arrA,
443
 
                               const ArrangementB_2* arrB,
 
445
    typedef Arr_overlay_traits_2<Geometry_traits_2,
 
446
                                 Arrangement_a,
 
447
                                 Arrangement_b>         Geom_ovl_traits_2;
 
448
 
 
449
    typedef _Overlay_helper<Geom_ovl_traits_2, Arrangement_a, Arrangement_b>
 
450
                                                                Ovl_helper;
 
451
 
 
452
    typedef Arr_overlay_sl_visitor<Ovl_helper, Overlay_traits>  Base;
 
453
 
 
454
    typedef typename Base::Traits_2                             Traits_2;
 
455
    typedef typename Base::Event                                Event;
 
456
    typedef typename Base::Subcurve                             Subcurve;
 
457
 
 
458
    Sweep_line_overlay_visitor(const Arrangement_a* arr_a,
 
459
                               const Arrangement_b* arr_b,
444
460
                               Arrangement_result_2* arr_res,
445
461
                               Overlay_traits* overlay_tr) :
446
 
      Base(arrA, arrB, arr_res, overlay_tr)
 
462
      Base(arr_a, arr_b, arr_res, overlay_tr)
447
463
    {}
448
464
  };
449
465
 
450
466
  typedef Arr_inc_insertion_zone_visitor<Arr> Zone_insertion_visitor;
451
467
 
452
 
  typedef Arr_naive_point_location<Arr>       Default_point_location_strategy;
 
468
  typedef Arr_naive_point_location<Arr> Default_point_location_strategy;
 
469
  typedef Arr_naive_point_location<Arr> Default_vertical_ray_shooting_strategy;
453
470
  //@}
454
471
 
455
472
  ///! \name Topology-traits methods.
494
511
   *         will form a hole in the original face.
495
512
   */
496
513
  std::pair<bool, bool>
497
 
  face_split_after_edge_insertion(std::pair< CGAL::Sign, CGAL::Sign > /* signs1 */,
498
 
                                  std::pair< CGAL::Sign, CGAL::Sign > /* signs2 */) const {
 
514
  face_split_after_edge_insertion(std::pair< CGAL::Sign,
 
515
                                             CGAL::Sign > /* signs1 */,
 
516
                                  std::pair< CGAL::Sign,
 
517
                                             CGAL::Sign > /* signs2 */) const
 
518
  {
499
519
    // In case of a spherical topology, connecting two vertices on the same
500
520
    // inner CCB closes a new face that becomes a hole in the original face:
501
521
    return (std::make_pair(true, true));
632
652
  //@}
633
653
 
634
654
protected:
635
 
 
636
655
  /// \name Auxiliary functions.
637
656
  //@{
638
657
 
643
662
   * \pre v is a valid boundary.
644
663
   * \return The curve that induces v.
645
664
   */
646
 
  const X_monotone_curve_2& _curve(const Vertex* v,
647
 
                                   Arr_curve_end& ind) const;
 
665
  const X_monotone_curve_2& _curve(const Vertex* v, Arr_curve_end& ind) const;
648
666
 
649
667
  /*! Return the halfedge, the target vertex of which is given, that is
650
668
   * the predecessor of a halfedge, the curve of which is given, that is about
651
669
   * to be inserted into the dcel.
652
670
   */
653
 
  Halfedge *
654
 
  _locate_around_vertex_on_discontinuity(Vertex* v,
655
 
                                         const X_monotone_curve_2& xc,
656
 
                                         Arr_curve_end ind) const;
 
671
  Halfedge* _locate_around_vertex_on_discontinuity(Vertex* v,
 
672
                                                   const X_monotone_curve_2& xc,
 
673
                                                   Arr_curve_end ind) const;
657
674
 
658
675
  /*! Return the halfedge, the target vertex of which is a given pole,
659
676
   * that is the predecessor of a halfedge, the curve of which is given, that