← Back to branch summary

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

« back to all changes in this revision

Viewing changes to include/CGAL/Arr_unb_planar_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_unb_planar_topology_traits_2.h
38
38
namespace CGAL {
39
39
 
40
40
// Forward declaration:
41
 
template <class GeomTraits_, class TopTraits_>
 
41
template <typename GeomTraits_, typename TopTraits_>
42
42
class Arrangement_on_surface_2;
43
43
 
44
44
/*! \class Arr_unb_planar_topology_traits_2
45
45
 * A topology-traits class that encapsulates the embedding of 2D arrangements
46
46
 * of unbounded curves on the plane.
47
47
 */
48
 
template <class GeomTraits_,
49
 
          class Dcel_ = Arr_default_dcel<GeomTraits_> >
 
48
template <typename GeomTraits_,
 
49
          typename Dcel_ = Arr_default_dcel<GeomTraits_> >
50
50
class Arr_unb_planar_topology_traits_2 :
51
51
  public Arr_planar_topology_traits_base_2<GeomTraits_, Dcel_>
52
52
{
53
53
private:
54
 
 
55
 
  typedef Arr_planar_topology_traits_base_2<GeomTraits_,
56
 
                                            Dcel_>        Base;
 
54
  typedef Arr_planar_topology_traits_base_2<GeomTraits_, Dcel_>
 
55
                                                          Base;
57
56
 
58
57
public:
59
 
 
60
58
  ///! \name The geometry-traits types.
61
59
  //@{
62
60
  typedef GeomTraits_                                     Geometry_traits_2;
76
74
  typedef typename Base::Isolated_vertex                  Isolated_vertex;
77
75
  //@}
78
76
 
79
 
 
80
77
  //! \name Arrangement types
81
78
  //!@{
82
79
  typedef Arr_unb_planar_topology_traits_2<Geometry_traits_2, Dcel> Self;
120
117
   * An auxiliary structure for rebinding the topology traits with a new
121
118
   * geometry-traits class and a new DCEL class.
122
119
   */
123
 
  template<typename T, typename D>
124
 
  struct rebind
125
 
  {
126
 
    typedef Arr_unb_planar_topology_traits_2<T,D> other;
 
120
  template <typename T, typename D>
 
121
  struct rebind {
 
122
    typedef Arr_unb_planar_topology_traits_2<T, D> other;
127
123
  };
128
124
 
129
125
protected:
130
 
 
131
126
  // Data members:
132
 
  Vertex             *v_bl;         // A fictitious vertex at (-oo,-oo).
133
 
  Vertex             *v_tl;         // A fictitious vertex at (-oo,+oo).
134
 
  Vertex             *v_br;         // A fictitious vertex at (-oo,+oo).
135
 
  Vertex             *v_tr;         // A fictitious vertex at (+oo,+oo).
136
 
  Size                n_inf_verts;  // Number of vertices at infinity.
137
 
  Face               *fict_face;    // The fictitious DCEL face.
 
127
  Vertex* v_bl;         // A fictitious vertex at (-oo,-oo).
 
128
  Vertex* v_tl;         // A fictitious vertex at (-oo,+oo).
 
129
  Vertex* v_br;         // A fictitious vertex at (-oo,+oo).
 
130
  Vertex* v_tr;         // A fictitious vertex at (+oo,+oo).
 
131
  Size n_inf_verts;     // Number of vertices at infinity.
 
132
  Face* fict_face;      // The fictitious DCEL face.
138
133
 
139
134
  // Copy constructor and assignment operator - not supported.
140
 
  Arr_unb_planar_topology_traits_2 (const Self& );
141
 
  Self& operator= (const Self& );
 
135
  Arr_unb_planar_topology_traits_2(const Self&);
 
136
  Self& operator=(const Self&);
142
137
 
143
138
public:
144
 
 
145
139
  ///! \name Construction methods.
146
140
  //@{
147
141
 
148
142
  /*! Default constructor. */
149
 
  Arr_unb_planar_topology_traits_2 ();
 
143
  Arr_unb_planar_topology_traits_2();
150
144
 
151
145
  /*! Constructor with a geometry-traits class. */
152
 
  Arr_unb_planar_topology_traits_2 (const Geometry_traits_2 *tr);
 
146
  Arr_unb_planar_topology_traits_2(const Geometry_traits_2* tr);
153
147
 
154
148
  /*! Assign the contents of another topology-traits class. */
155
 
  void assign (const Self& other);
 
149
  void assign(const Self& other);
156
150
  //@}
157
151
 
158
152
  ///! \name Accessing the DCEL and constructing iterators.
159
153
  //@{
160
154
 
161
155
  /*! Determine whether the DCEL reprsenets an empty structure. */
162
 
  bool is_empty_dcel () const
 
156
  bool is_empty_dcel() const
163
157
  {
164
158
    // An empty arrangement contains just two four vertices at infinity
165
159
    // and eight fictitious halfedges connecting them.
168
162
  }
169
163
 
170
164
  /*! Check if the given vertex is concrete (associated with a point). */
171
 
  bool is_concrete_vertex (const Vertex *v) const
 
165
  bool is_concrete_vertex(const Vertex* v) const
172
166
  {
173
167
    return (! v->has_null_point());
174
168
  }
175
169
 
176
170
  /*! Get the number of concrete vertices. */
177
 
  Size number_of_concrete_vertices () const
 
171
  Size number_of_concrete_vertices() const
178
172
  {
179
173
    // All vertices not lying at infinity are concrete.
180
174
    return (this->m_dcel.size_of_vertices() - n_inf_verts);
181
175
  }
182
176
 
183
177
  /*! Check if the given vertex is valid (not a fictitious one). */
184
 
  bool is_valid_vertex (const Vertex *v) const
 
178
  bool is_valid_vertex(const Vertex* v) const
185
179
  {
186
180
    return (! v->has_null_point() ||
187
181
            (v != v_bl && v != v_tl && v != v_br && v != v_tr));
188
182
  }
189
183
 
190
184
  /*! Get the number of valid vertices. */
191
 
  Size number_of_valid_vertices () const
 
185
  Size number_of_valid_vertices() const
192
186
  {
193
187
    // All vertices, except the four fictitious one, are valid.
194
188
    return (this->m_dcel.size_of_vertices() - 4);
195
189
  }
196
190
 
197
191
  /*! Check if the given halfedge is valid (not a fictitious one). */
198
 
  bool is_valid_halfedge (const Halfedge *he) const
 
192
  bool is_valid_halfedge(const Halfedge* he) const
199
193
  {
200
194
    return (! he->has_null_curve());
201
195
  }
202
196
 
203
197
  /*! Get the number of valid halfedges. */
204
 
  Size number_of_valid_halfedges () const
 
198
  Size number_of_valid_halfedges() const
205
199
  {
206
200
    // Note that we do not count fictitious halfedges (each vertex at infinity
207
201
    // induces two fictitious halfedges).
209
203
  }
210
204
 
211
205
  /*! Check if the given face is valid (not a fictitious one). */
212
 
  bool is_valid_face (const Face *f) const
 
206
  bool is_valid_face (const Face* f) const
213
207
  {
214
208
    return (! f->is_fictitious());
215
209
  }
216
210
 
217
211
  /*! Get the number of valid faces. */
218
 
  Size number_of_valid_faces () const
 
212
  Size number_of_valid_faces() const
219
213
  {
220
214
    // We do not count the ficitious DCEL face.
221
215
    return (this->m_dcel.size_of_faces() - 1);
223
217
  //@}
224
218
 
225
219
private:
226
 
 
227
220
  /// \name Auxiliary type definitions.
228
221
  //@{
229
 
  typedef Arrangement_on_surface_2<Geometry_traits_2, Self>             Arr;
 
222
  typedef Arrangement_on_surface_2<Geometry_traits_2, Self>    Arr;
230
223
 
231
224
  // Type definition for the constuction sweep-line visitor.
232
225
  typedef Arr_construction_subcurve<Geometry_traits_2>         CSubcurve;
233
 
  typedef Arr_construction_event<Geometry_traits_2,
234
 
                                 CSubcurve,
235
 
                                 Arr>                          CEvent;
 
226
  typedef Arr_construction_event<Geometry_traits_2, CSubcurve, Arr>
 
227
                                                               CEvent;
236
228
  typedef Arr_unb_planar_construction_helper<Geometry_traits_2,
237
229
                                             Arr,
238
230
                                             CEvent,
241
233
  // Type definition for the basic insertion sweep-line visitor.
242
234
  typedef Arr_basic_insertion_traits_2<Geometry_traits_2, Arr> BInsTraits;
243
235
  typedef Arr_construction_subcurve<BInsTraits>                BISubcurve;
244
 
  typedef Arr_construction_event<BInsTraits,
245
 
                                 BISubcurve,
246
 
                                 Arr>                          BIEvent;
247
 
  typedef Arr_unb_planar_insertion_helper<BInsTraits,
248
 
                                          Arr,
249
 
                                          BIEvent,
250
 
                                          BISubcurve>          BIHelper;
 
236
  typedef Arr_construction_event<BInsTraits, BISubcurve, Arr>
 
237
                                                               BIEvent;
 
238
  typedef Arr_unb_planar_insertion_helper<BInsTraits, Arr, BIEvent, BISubcurve>
 
239
                                                               BIHelper;
251
240
 
252
241
  // Type definition for the insertion sweep-line visitor.
253
242
  typedef Arr_insertion_traits_2<Geometry_traits_2, Arr>       InsTraits;
254
243
  typedef Arr_construction_subcurve<InsTraits>                 ISubcurve;
255
 
  typedef Arr_construction_event<InsTraits,
256
 
                                 ISubcurve,
257
 
                                 Arr>                          IEvent;
258
 
  typedef Arr_unb_planar_insertion_helper<InsTraits,
259
 
                                          Arr,
260
 
                                          IEvent,
261
 
                                          ISubcurve>           IHelper;
 
244
  typedef Arr_construction_event<InsTraits, ISubcurve, Arr>
 
245
                                                               IEvent;
 
246
  typedef Arr_unb_planar_insertion_helper<InsTraits, Arr, IEvent, ISubcurve>
 
247
                                                               IHelper;
262
248
 
263
249
  // Type definition for the batched point-location sweep-line visitor.
264
250
  typedef Arr_batched_point_location_traits_2<Arr>             BplTraits;
292
278
    typedef typename Base::Subcurve                      Subcurve;
293
279
    typedef typename Base::Construction_helper           Construction_helper;
294
280
 
295
 
    _Overlay_helper (const ArrangementA_ *arrA,
296
 
                     const ArrangementB_ *arrB) :
297
 
      Base (arrA, arrB)
298
 
    {}
 
281
    _Overlay_helper(const ArrangementA_* arrA, const ArrangementB_* arrB) :
 
282
      Base(arrA, arrB) {}
299
283
  };
300
284
  //@}
301
285
 
302
286
public:
303
 
 
304
287
  ///! \name Visitor types.
305
288
  //@{
306
289
 
338
321
    public Arr_vert_decomp_sl_visitor<VdHelper, OutputIterator_>
339
322
  {
340
323
    typedef OutputIterator_                                   Output_iterator;
341
 
    typedef Arr_vert_decomp_sl_visitor<VdHelper,
342
 
                                       Output_iterator>       Base;
 
324
    typedef Arr_vert_decomp_sl_visitor<VdHelper, Output_iterator>
 
325
                                                             Base;
343
326
 
344
327
    typedef typename Base::Traits_2                           Traits_2;
345
328
    typedef typename Base::Event                              Event;
346
329
    typedef typename Base::Subcurve                           Subcurve;
347
330
 
348
 
    Sweep_line_vertical_decomposition_visitor (const Arr *arr,
349
 
                                               Output_iterator *oi) :
350
 
      Base (arr, oi)
351
 
    {}
 
331
    Sweep_line_vertical_decomposition_visitor(const Arr* arr,
 
332
                                              Output_iterator* oi) :
 
333
      Base(arr, oi) {}
352
334
  };
353
335
 
354
336
  template <class ArrangementA_, class ArrangementB_, class OverlayTraits_>
381
363
    typedef typename Base::Event                     Event;
382
364
    typedef typename Base::Subcurve                  Subcurve;
383
365
 
384
 
    Sweep_line_overlay_visitor (const ArrangementA_2 *arrA,
385
 
                                const ArrangementB_2 *arrB,
386
 
                                Arrangement_result_2 *arr_res,
387
 
                                Overlay_traits *overlay_tr) :
388
 
      Base (arrA, arrB, arr_res, overlay_tr)
 
366
    Sweep_line_overlay_visitor(const ArrangementA_2* arrA,
 
367
                               const ArrangementB_2* arrB,
 
368
                               Arrangement_result_2* arr_res,
 
369
                               Overlay_traits* overlay_tr) :
 
370
      Base(arrA, arrB, arr_res, overlay_tr)
389
371
    {}
390
372
  };
391
373
 
392
374
  typedef Arr_inc_insertion_zone_visitor<Arr>
393
 
                                              Zone_insertion_visitor;
394
 
 
395
 
  typedef Arr_walk_along_line_point_location<Arr>
396
 
                                              Default_point_location_strategy;
 
375
                                        Zone_insertion_visitor;
 
376
 
 
377
  typedef Arr_walk_along_line_point_location<Arr>
 
378
                                        Default_point_location_strategy;
 
379
 
 
380
  typedef Arr_walk_along_line_point_location<Arr>
 
381
                                        Default_vertical_ray_shooting_strategy;
397
382
  //@}
398
383
 
399
384
  ///! \name Topology-traits methods.
402
387
  /*!
403
388
   * Initialize an empty DCEL structure.
404
389
   */
405
 
  void init_dcel ();
 
390
  void init_dcel();
406
391
 
407
392
  /*!
408
393
   * Make the necessary updates after the DCEL structure have been updated.
409
394
   */
410
 
  void dcel_updated ();
 
395
  void dcel_updated();
411
396
 
412
397
  /*!
413
398
   * Check if the given vertex is associated with the given curve end.
419
404
   * \pre The curve has a boundary condition in either x or y.
420
405
   * \return Whether v represents the given curve end.
421
406
   */
422
 
  bool are_equal (const Vertex *v,
423
 
                  const X_monotone_curve_2& cv, Arr_curve_end ind,
424
 
                  Arr_parameter_space ps_x, Arr_parameter_space ps_y) const;
 
407
  bool are_equal(const Vertex* v,
 
408
                 const X_monotone_curve_2& cv, Arr_curve_end ind,
 
409
                 Arr_parameter_space ps_x, Arr_parameter_space ps_y) const;
425
410
 
426
411
  /*!
427
412
   * Given a curve end with boundary conditions and a face that contains the
436
421
   * \return An object that contains the curve end.
437
422
   *         In our case this object always wraps a fictitious edge.
438
423
   */
439
 
  CGAL::Object place_boundary_vertex (Face *f,
440
 
                                      const X_monotone_curve_2& cv,
441
 
                                      Arr_curve_end ind,
442
 
                                      Arr_parameter_space ps_x,
443
 
                                      Arr_parameter_space ps_y);
 
424
  CGAL::Object place_boundary_vertex(Face* f,
 
425
                                     const X_monotone_curve_2& cv,
 
426
                                     Arr_curve_end ind,
 
427
                                     Arr_parameter_space ps_x,
 
428
                                     Arr_parameter_space ps_y);
444
429
 
445
430
  /*!
446
431
   * Locate the predecessor halfedge for the given curve around a given
455
440
   * \return An object that contains the curve end.
456
441
   */
457
442
  Halfedge*
458
 
  locate_around_boundary_vertex (Vertex* /* v */,
459
 
                                 const X_monotone_curve_2& /* cv */,
460
 
                                 Arr_curve_end /* ind */,
461
 
                                 Arr_parameter_space /* ps_x */,
462
 
                                 Arr_parameter_space /* ps_y */) const
 
443
  locate_around_boundary_vertex(Vertex* /* v */,
 
444
                                const X_monotone_curve_2& /* cv */,
 
445
                                Arr_curve_end /* ind */,
 
446
                                Arr_parameter_space /* ps_x */,
 
447
                                Arr_parameter_space /* ps_y */) const
463
448
  {
464
449
    CGAL_error();
465
450
    return (NULL);
476
461
   *         In our case this object may either wrap an unbounded face,
477
462
   *         or an edge with an end-vertex at infinity (in case of an overlap).
478
463
   */
479
 
  CGAL::Object locate_curve_end (const X_monotone_curve_2& cv,
480
 
                                 Arr_curve_end ind,
481
 
                                 Arr_parameter_space ps_x,
482
 
                                 Arr_parameter_space ps_y);
 
464
  CGAL::Object locate_curve_end(const X_monotone_curve_2& cv,
 
465
                                Arr_curve_end ind,
 
466
                                Arr_parameter_space ps_x,
 
467
                                Arr_parameter_space ps_y);
483
468
 
484
469
  /*!
485
470
   * Split a fictitious edge using the given vertex.
489
474
   * \return A halfedge whose direction is the same as e's and whose target is
490
475
   *         the split vertex v.
491
476
   */
492
 
  Halfedge* split_fictitious_edge (Halfedge *e, Vertex *v);
 
477
  Halfedge* split_fictitious_edge(Halfedge* e, Vertex* v);
493
478
 
494
479
  /*!
495
480
   * Determine whether the given face is unbounded.
496
481
   * \param f The face.
497
482
   * \return Whether f is unbounded.
498
483
   */
499
 
  bool is_unbounded (const Face *f) const;
 
484
  bool is_unbounded(const Face* f) const;
500
485
 
501
486
  /*!
502
487
   * Determine whether the given boundary vertex is redundant.
503
488
   * \param v The vertex.
504
489
   * \return Whether v is redundant, and should be erased.
505
490
   */
506
 
  bool is_redundant (const Vertex *v) const;
 
491
  bool is_redundant(const Vertex* v) const;
507
492
 
508
493
  /*!
509
494
   * Erase the given redundant vertex by merging a fictitious edge.
512
497
   * \pre v is a redundant vertex.
513
498
   * \return One of the pair of halfedges that form the merged edge.
514
499
   */
515
 
  Halfedge* erase_redundant_vertex (Vertex *v);
 
500
  Halfedge* erase_redundant_vertex(Vertex* v);
516
501
 
517
502
    //! reference_face (const version).
518
503
  /*! The function returns a reference face of the arrangement.
544
529
  //@{
545
530
 
546
531
  /*! This function is used by the "walk" point-location strategy. */
547
 
  const Face* initial_face () const
548
 
  {
549
 
    return (fict_face);
550
 
  }
 
532
  const Face* initial_face() const { return fict_face; }
551
533
 
552
534
  /*! Get the fictitious face (const version). */
553
 
  const Face* fictitious_face () const
554
 
  {
555
 
    return (fict_face);
556
 
  }
 
535
  const Face* fictitious_face() const { return fict_face; }
557
536
 
558
537
  /*! Get the fictitious face (non-const version). */
559
 
  Face* fictitious_face ()
560
 
  {
561
 
    return (fict_face);
562
 
  }
 
538
  Face* fictitious_face() { return fict_face; }
563
539
 
564
540
  /*! Get the bottom-left fictitious vertex (const version). */
565
 
  const Vertex* bottom_left_vertex () const
566
 
  {
567
 
    return (v_bl);
568
 
  }
 
541
  const Vertex* bottom_left_vertex() const { return (v_bl); }
569
542
 
570
543
  /*! Get the bottom-left fictitious vertex (non-const version). */
571
 
  Vertex* bottom_left_vertex ()
572
 
  {
573
 
    return (v_bl);
574
 
  }
 
544
  Vertex* bottom_left_vertex() { return (v_bl); }
575
545
 
576
546
  /*! Get the top-left fictitious vertex (const version). */
577
 
  const Vertex* top_left_vertex () const
578
 
  {
579
 
    return (v_tl);
580
 
  }
 
547
  const Vertex* top_left_vertex() const { return (v_tl); }
581
548
 
582
549
  /*! Get the top-left fictitious vertex (non-const version). */
583
 
  Vertex* top_left_vertex ()
584
 
  {
585
 
    return (v_tl);
586
 
  }
 
550
  Vertex* top_left_vertex() { return (v_tl); }
587
551
 
588
552
  /*! Get the bottom-right fictitious vertex (const version). */
589
 
  const Vertex* bottom_right_vertex () const
590
 
  {
591
 
    return (v_br);
592
 
  }
 
553
  const Vertex* bottom_right_vertex() const { return (v_br); }
593
554
 
594
555
  /*! Get the bottom-right fictitious vertex (non-const version). */
595
 
  Vertex* bottom_right_vertex ()
596
 
  {
597
 
    return (v_br);
598
 
  }
 
556
  Vertex* bottom_right_vertex() { return (v_br); }
599
557
 
600
558
  /*! Get the top-right fictitious vertex (const version). */
601
 
  const Vertex* top_right_vertex () const
602
 
  {
603
 
    return (v_tr);
604
 
  }
 
559
  const Vertex* top_right_vertex() const { return (v_tr); }
605
560
 
606
561
  /*! Get the top-right fictitious vertex (non-const version). */
607
 
  Vertex* top_right_vertex ()
608
 
  {
609
 
    return (v_tr);
610
 
  }
 
562
  Vertex* top_right_vertex() { return (v_tr); }
611
563
  //@}
612
564
 
613
565
  /// \name Additional predicates, specialized for this topology-traits class.
619
571
   * \param v The vertex.
620
572
   * \return The result of the comparison of the x-coordinates of p and v.
621
573
   */
622
 
  virtual Comparison_result compare_x (const Point_2& p,
 
574
  virtual Comparison_result compare_x(const Point_2& p,
 
575
                                      const Vertex* v) const;
 
576
 
 
577
  /*!
 
578
   * Compare the given vertex (which may lie at infinity) and the given point.
 
579
   * \param p The point.
 
580
   * \param v The vertex.
 
581
   * \return The result of the xy-lexicographic comparison of p and v.
 
582
   */
 
583
  virtual Comparison_result compare_xy(const Point_2& p,
623
584
                                       const Vertex* v) const;
624
585
 
625
586
  /*!
626
 
   * Compare the given vertex (which may lie at infinity) and the given point.
627
 
   * \param p The point.
628
 
   * \param v The vertex.
629
 
   * \return The result of the xy-lexicographic comparison of p and v.
630
 
   */
631
 
  virtual Comparison_result compare_xy (const Point_2& p,
632
 
                                        const Vertex* v) const;
633
 
 
634
 
  /*!
635
587
   * Compare the relative y-position of the given point and the given edge
636
588
   * (which may be fictitious).
637
589
   * \param p The point.
639
591
   * \pre p should lie in the x-range of the given edge.
640
592
   * \return The relative y-position of the point p and the edge.
641
593
   */
642
 
  virtual Comparison_result compare_y_at_x (const Point_2& p,
643
 
                                            const Halfedge* he) const;
 
594
  virtual Comparison_result compare_y_at_x(const Point_2& p,
 
595
                                           const Halfedge* he) const;
644
596
  //@}
645
597
 
646
598
protected:
656
608
   * \pre v is a valid (not fictitious) boundary.
657
609
   * \return The curve that induces v, or NULL if v has no incident curves yet.
658
610
   */
659
 
  const X_monotone_curve_2* _curve (const Vertex *v, Arr_curve_end& ind) const;
 
611
  const X_monotone_curve_2* _curve(const Vertex* v, Arr_curve_end& ind) const;
660
612
 
661
613
  /*!
662
614
   * Check whether the given infinite curve end lies on the given fictitious
670
622
   * \param eq_target Output: Whether the curve coincides with he's target.
671
623
   * \return Whether the curve end lies on the fictitious halfedge.
672
624
   */
673
 
  bool _is_on_fictitious_edge (const X_monotone_curve_2& cv, Arr_curve_end ind,
 
625
  bool _is_on_fictitious_edge(const X_monotone_curve_2& cv, Arr_curve_end ind,
674
626
                               Arr_parameter_space ps_x,
675
627
                               Arr_parameter_space ps_y,
676
 
                               const Halfedge *he,
 
628
                               const Halfedge* he,
677
629
                               bool& eq_source, bool& eq_target);
678
630
  //@}
679
631
};