BWAPI
SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Sweep_line_2/Arr_basic_insertion_traits_2.h
Go to the documentation of this file.
00001 // Copyright (c) 1997  Tel-Aviv University (Israel).
00002 // All rights reserved.
00003 //
00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under
00005 // the terms of the Q Public License version 1.0.
00006 // See the file LICENSE.QPL distributed with CGAL.
00007 //
00008 // Licensees holding a valid commercial license may use this file in
00009 // accordance with the commercial license agreement provided with the software.
00010 //
00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00013 //
00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/Sweep_line_2/Arr_basic_insertion_traits_2.h $
00015 // $Id: Arr_basic_insertion_traits_2.h 50366 2009-07-05 12:56:48Z efif $
00016 // 
00017 //
00018 // Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
00019 //                 Ron Wein <wein@post.tau.ac.il>
00020 //                 Efi Fogel <efif@post.tau.ac.il>
00021 
00022 #ifndef CGAL_ARR_BASIC_INSERTION_TRAITS_2_H
00023 #define CGAL_ARR_BASIC_INSERTION_TRAITS_2_H
00024 
00029 #include <CGAL/Object.h>
00030 #include <CGAL/Arr_tags.h>
00031 
00032 #include <list>
00033 #include <iterator>
00034 
00035 CGAL_BEGIN_NAMESPACE
00036 
00042 template <typename Traits_, typename Arrangement_>
00043 class Arr_basic_insertion_traits_2 
00044 {
00045 public:
00046 
00047   typedef Traits_                                   Traits_2;
00048   typedef Arrangement_                              Arrangement_2;
00049 
00050   typedef typename Arrangement_2::Halfedge_handle   Halfedge_handle;
00051   typedef typename Arrangement_2::Vertex_handle     Vertex_handle;
00052   typedef typename Traits_2::X_monotone_curve_2     Base_x_monotone_curve_2;
00053   typedef typename Traits_2::Point_2                Base_point_2;
00054   typedef typename Traits_2::Construct_min_vertex_2 Base_construct_min_vertex_2;
00055   typedef typename Traits_2::Construct_max_vertex_2 Base_construct_max_vertex_2;
00056   typedef typename Traits_2::Compare_x_2            Base_compare_x_2;
00057   typedef typename Traits_2::Compare_xy_2           Base_compare_xy_2;
00058   typedef typename Traits_2::Compare_y_at_x_2       Base_compare_y_at_x_2;
00059   typedef typename Traits_2::Compare_y_at_x_right_2 Base_compare_y_at_x_right_2;
00060   typedef typename Traits_2::Equal_2                Base_equal_2;
00061   typedef typename Traits_2::Is_vertical_2          Base_is_vertical_2;
00062 
00063   
00064   typedef typename CGALi::Arr_complete_left_side_tag< Traits_2 >::Tag
00065                                                     Arr_left_side_tag;
00066   typedef typename CGALi::Arr_complete_bottom_side_tag< Traits_2 >::Tag
00067                                                     Arr_bottom_side_tag;
00068   typedef typename CGALi::Arr_complete_top_side_tag< Traits_2 >::Tag
00069                                                     Arr_top_side_tag;
00070   typedef typename CGALi::Arr_complete_right_side_tag< Traits_2 >::Tag
00071                                                     Arr_right_side_tag;
00072 
00073   /* Insertion is implemented as sweep-line visitor. The sweep-line algorithm
00074    * never uses Compare_y_at_x_left_2.
00075    */
00076   typedef Tag_false                                 Has_left_category;
00077 
00078 protected:
00079 
00081   const Traits_2 * m_base_traits;
00082 
00083 public:
00084 
00086   Arr_basic_insertion_traits_2 (const Traits_2 & tr):
00087     m_base_traits (&tr)
00088   {}
00089 
00093   class Ex_x_monotone_curve_2 
00094   {
00095   public:
00096 
00097     typedef  Base_x_monotone_curve_2  Base;
00098 
00099   protected:
00100 
00101     Base                m_base_xcv;    // The base x-monotone curve.
00102     Halfedge_handle     m_he_handle;   // The corresponding arrangement edge
00103                                        // (may be invalid).
00104     bool                m_overlap;     // Does this curve represent and overlap
00105                                        // of two other curves.
00106 
00107   public:
00108 
00109     Ex_x_monotone_curve_2():
00110       m_base_xcv(),
00111       m_he_handle(),
00112       m_overlap(false)
00113     {}
00114 
00115     Ex_x_monotone_curve_2(const Base& xcv):
00116       m_base_xcv (xcv),
00117       m_he_handle(),
00118       m_overlap(false)
00119     {}
00120 
00121     Ex_x_monotone_curve_2(const Base& xcv, Halfedge_handle he) :
00122       m_base_xcv (xcv),
00123       m_he_handle (he),
00124       m_overlap(false)
00125     {
00126       CGAL_precondition (he == Halfedge_handle() ||
00127                          he->direction() == ARR_RIGHT_TO_LEFT);
00128     }
00129 
00130     const Base& base() const
00131     {
00132       return (m_base_xcv);
00133     }
00134 
00135     Base& base()
00136     {
00137       return (m_base_xcv);
00138     }
00139 
00140     operator const Base& () const
00141     {
00142       return (m_base_xcv);
00143     }
00144 
00145     Ex_x_monotone_curve_2& operator= (const Base& xcv)
00146     {
00147       m_base_xcv = xcv;
00148       m_he_handle = Halfedge_handle();
00149       return (*this);
00150     }
00151 
00152     Halfedge_handle halfedge_handle() const
00153     {
00154       return (m_he_handle);
00155     }
00156 
00157     void set_halfedge_handle(Halfedge_handle he)
00158     {
00159       CGAL_precondition (he == Halfedge_handle() ||
00160                          he->direction() == ARR_RIGHT_TO_LEFT);
00161       m_he_handle = he;
00162     }
00163 
00164     bool is_overlapping () const
00165     {
00166       return (m_overlap);
00167     }
00168 
00169     void set_overlapping ()
00170     {
00171       m_overlap = true;
00172     }
00173   };
00174 
00175   typedef Ex_x_monotone_curve_2                     X_monotone_curve_2;
00176 
00177 #ifdef CGAL_SL_VERBOSE
00178   // For debugging purposes:
00179   friend std::ostream& operator<< (std::ostream& os,
00180                                    const X_monotone_curve_2& xcv)
00181   {
00182     os << xcv.base();
00183     return (os);
00184   }
00185 #endif
00186  
00190   class Ex_point_2 
00191   {
00192   public:
00193 
00194     typedef  Base_point_2            Base;
00195 
00196   protected:
00197 
00198     Base             m_base_pt;        // The base point.
00199     Vertex_handle    m_v;              // The corresponding arrangement vertex
00200                                        // (may be invalid).
00201 
00202   public:
00203 
00204     Ex_point_2() :
00205       m_base_pt(),
00206       m_v()
00207     {}
00208 
00209     Ex_point_2 (const Base& pt) :
00210       m_base_pt (pt),
00211       m_v()
00212     {}
00213 
00214     Ex_point_2 (const Base& pt, Vertex_handle v) :
00215       m_base_pt (pt),
00216       m_v (v)
00217     {}
00218 
00219     const Base& base() const
00220     {
00221       return (m_base_pt);
00222     }
00223     
00224     operator const Base& () const
00225     {
00226       return (m_base_pt);
00227     }
00228 
00229     Vertex_handle vertex_handle() const
00230     {
00231       return m_v;
00232     }
00233 
00234     void set_vertex_handle(Vertex_handle v)
00235     {
00236       m_v = v;
00237     }
00238   };
00239 
00240   typedef Ex_point_2                                Point_2;
00241 
00242 #ifdef CGAL_SL_VERBOSE
00243   // For debugging purposes:
00244   friend std::ostream& operator<< (std::ostream& os,
00245                                    const Point_2& pt)
00246   {
00247     os << pt.base();
00248     return (os);
00249   }
00250 #endif
00251 
00253   class Construct_min_vertex_2 {
00254   protected:
00255     Base_construct_min_vertex_2  m_base_min_v;
00256     Base_equal_2                 m_base_equal;
00257     Halfedge_handle              invalid_he;
00258 
00264     Construct_min_vertex_2 (const Base_construct_min_vertex_2& base_min_v,
00265                             const Base_equal_2& base_equal) :
00266       m_base_min_v (base_min_v),
00267       m_base_equal (base_equal),
00268       invalid_he()
00269     {}
00270 
00272     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00273     
00274   public:
00275     Point_2 operator() (const X_monotone_curve_2 & xcv) 
00276     {
00277       // If there is not halfedge associated with the curve, just return
00278       // a point with invalid halfedge handle.
00279       const Base_point_2&  base_p = m_base_min_v(xcv.base());
00280 
00281       if (xcv.halfedge_handle() == invalid_he)
00282         return (Point_2 (base_p));
00283 
00284       // Note that the halfedge associated with the curve is always directed
00285       // from right to left, so its target is the leftmost vertex.
00286       // We probably have to associate the point with the target vertex of
00287       // the halfedge associated with the curve.
00288       Vertex_handle        vh = xcv.halfedge_handle()->target();
00289 
00290       if (! xcv.is_overlapping())
00291         return (Point_2(base_p, vh));
00292 
00293       // In case of an overlapping curve, make sure the curve endpoint equals
00294       // the point associated with the vertex. If not, we attach an invalid
00295       // vertex to the extended point.
00296       if (! vh->is_at_open_boundary() && m_base_equal (base_p, vh->point()))
00297         return (Point_2(base_p, vh));
00298       else
00299         return (Point_2 (base_p));
00300     }
00301   };
00302 
00304   Construct_min_vertex_2 construct_min_vertex_2_object () const
00305   {
00306     return (Construct_min_vertex_2
00307             (m_base_traits->construct_min_vertex_2_object(),
00308              m_base_traits->equal_2_object()));
00309   }
00310 
00312   class Construct_max_vertex_2 {
00313   protected:
00314     Base_construct_max_vertex_2  m_base_max_v;
00315     Base_equal_2                 m_base_equal;
00316     Halfedge_handle              invalid_he;
00317 
00323     Construct_max_vertex_2 (const Base_construct_max_vertex_2& base_max_v,
00324                             const Base_equal_2& base_equal) :
00325       m_base_max_v (base_max_v),
00326       m_base_equal (base_equal),
00327       invalid_he()
00328     {}
00329 
00330 
00332     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00333 
00334   public:
00335     Point_2 operator() (const X_monotone_curve_2 & xcv) 
00336     {
00337       // If there is not halfedge associated with the curve, just return
00338       // a point with invalid halfedge handle.
00339       const Base_point_2&  base_p = m_base_max_v(xcv.base());
00340 
00341       if (xcv.halfedge_handle() == invalid_he)
00342         return (Point_2 (base_p));
00343 
00344       // Note that the halfedge associated with the curve is always directed
00345       // from right to left, so its source is the rightmost vertex.
00346       // We probably have to associate the point with the source vertex of
00347       // the halfedge associated with the curve.
00348       Vertex_handle        vh = xcv.halfedge_handle()->source();
00349 
00350       if (! xcv.is_overlapping())
00351         return (Point_2(base_p, vh));
00352 
00353       // In case of an overlapping curve, make sure the curve endpoint equals
00354       // the point associated with the vertex. If not, we attach an invalid
00355       // vertex to the extended point.
00356       if (! vh->is_at_open_boundary() && m_base_equal (base_p, vh->point()))
00357         return (Point_2(base_p, vh));
00358       else
00359         return (Point_2 (base_p));
00360     }
00361   };
00362 
00364   Construct_max_vertex_2 construct_max_vertex_2_object () const
00365   {
00366     return (Construct_max_vertex_2
00367             (m_base_traits->construct_max_vertex_2_object(),
00368              m_base_traits->equal_2_object()));
00369   }
00370 
00372   class Compare_xy_2 {
00373   protected:
00374     Base_compare_xy_2 m_base_cmp_xy;
00375 
00381     Compare_xy_2(const Base_compare_xy_2 & base) : m_base_cmp_xy(base) {}
00382 
00384     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00385 
00386   public:
00387     Comparison_result operator() (const Point_2& p1, const Point_2& p2) const
00388     {
00389       if(p1.vertex_handle() == p2.vertex_handle() &&
00390          p1.vertex_handle() != Vertex_handle())
00391         return (EQUAL);
00392 
00393       return (m_base_cmp_xy(p1.base(), p2.base()));
00394     }
00395   };
00396 
00398   Compare_xy_2 compare_xy_2_object () const
00399   {
00400     return (Compare_xy_2 (m_base_traits->compare_xy_2_object()));
00401   }
00402 
00406   class Compare_y_at_x_2 {
00407   protected:
00408     Base_compare_y_at_x_2 m_base_cmp_y_at_x;
00409 
00415     Compare_y_at_x_2(const Base_compare_y_at_x_2& base) :
00416         m_base_cmp_y_at_x(base)
00417     {}
00418 
00420     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00421 
00422   public:
00423     Comparison_result operator() (const Point_2& p,
00424                                   const X_monotone_curve_2& xcv) const
00425     {
00426       return (m_base_cmp_y_at_x (p.base(), xcv.base()));
00427     }
00428   };
00429 
00431   Compare_y_at_x_2 compare_y_at_x_2_object () const
00432   {
00433     return (Compare_y_at_x_2 (m_base_traits->compare_y_at_x_2_object()));
00434   }
00435 
00439   class Compare_y_at_x_right_2 {
00440   protected:
00441     Base_compare_y_at_x_right_2 m_base_cmp_y_at_x_right;
00442 
00448     Compare_y_at_x_right_2(const Base_compare_y_at_x_right_2& base) :
00449         m_base_cmp_y_at_x_right(base)
00450     {}
00451 
00453     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00454 
00455   public:
00456     Comparison_result operator() (const X_monotone_curve_2& xcv1,
00457                                   const X_monotone_curve_2& xcv2,
00458                                   const Point_2& p) const
00459     {
00460       return (m_base_cmp_y_at_x_right(xcv1.base(),
00461                                       xcv2.base(),
00462                                       p.base()));
00463     }
00464   };
00465 
00467   Compare_y_at_x_right_2 compare_y_at_x_right_2_object () const
00468   {
00469     return (Compare_y_at_x_right_2
00470             (m_base_traits->compare_y_at_x_right_2_object()));
00471   }
00472 
00476   class Equal_2 {
00477   protected:
00478     Base_equal_2 m_base_eq;
00479 
00485     Equal_2(const Base_equal_2& base) : m_base_eq(base) {}
00486 
00488     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00489 
00490   public:
00492     bool operator() (const X_monotone_curve_2& xcv1,
00493                      const X_monotone_curve_2& xcv2) const
00494     {
00495       return (m_base_eq(xcv1.base(), xcv2.base()));
00496     }
00497 
00499     bool operator() (const Point_2& p1, const Point_2& p2) const
00500     {
00501       return (m_base_eq(p1.base(), p2.base()));
00502     }
00503   };
00504 
00506   Equal_2 equal_2_object () const
00507   {
00508     return (Equal_2 (m_base_traits->equal_2_object()));
00509   }
00510 
00512   class Compare_x_2 {
00513   protected:
00514     Base_compare_x_2 m_base_cmp_x;
00515 
00521     Compare_x_2(const Base_compare_x_2& base) : m_base_cmp_x(base) {}
00522 
00524     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00525 
00526   public:
00527     Comparison_result operator() (const Point_2& p1, const Point_2& p2) const
00528     {
00529       return (m_base_cmp_x(p1.base(), p2.base()));
00530     }
00531   };
00532 
00534   Compare_x_2 compare_x_2_object () const
00535   {
00536     return (Compare_x_2 (m_base_traits->compare_x_2_object()));
00537   }
00538 
00540   class Is_vertical_2 {
00541   protected:
00542     Base_is_vertical_2 m_base_is_vert;
00543 
00549     Is_vertical_2(const Base_is_vertical_2& base) : m_base_is_vert(base) {}
00550 
00552     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00553 
00554   public:
00555      bool operator() (const X_monotone_curve_2& xcv) const
00556     {
00557       return (m_base_is_vert(xcv.base()));
00558     }
00559   };
00560 
00562   Is_vertical_2 is_vertical_2_object() const
00563   {
00564     return (Is_vertical_2(m_base_traits->is_vertical_2_object()));
00565   }
00566 
00567   // left-right
00568 
00572   class Parameter_space_in_x_2 {
00573   protected:
00575     const Traits_2 * m_base;
00576 
00584     Parameter_space_in_x_2 (const Traits_2 * tr) : m_base(tr) {}
00585 
00587     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00588 
00589   public:
00590     Arr_parameter_space operator() (const X_monotone_curve_2 & xcv,
00591                                     Arr_curve_end ce) const
00592     {
00593       return (m_base->parameter_space_in_x_2_object() (xcv.base(), ce));
00594     }
00595 
00596     Arr_parameter_space operator()(const Point_2 & p) const
00597     {
00598       return m_base->parameter_space_in_x_2_object() (p.base());
00599     }
00600 
00601     Arr_parameter_space operator()(const X_monotone_curve_2 & xcv) const
00602     {
00603       return m_base->parameter_space_in_x_2_object() (xcv.base());
00604     }
00605   
00606   };
00607 
00609   Parameter_space_in_x_2 parameter_space_in_x_2_object () const
00610   {
00611     return Parameter_space_in_x_2 (m_base_traits);
00612   }
00613   
00617   class Compare_y_near_boundary_2 {
00618   protected:
00620     const Traits_2 * m_base;
00621 
00629     Compare_y_near_boundary_2(const Traits_2 * base) : m_base(base) {}
00630 
00632     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00633 
00634   public:
00638     Comparison_result operator() (const X_monotone_curve_2 & xcv1,
00639                                   const X_monotone_curve_2 & xcv2, 
00640                                   Arr_curve_end ce) const
00641     {
00642       return m_base->compare_y_near_boundary_2_object() (xcv1.base(),
00643                                                          xcv2.base(), ce);
00644     }
00645 
00646   };
00647 
00650   Compare_y_near_boundary_2 compare_y_near_boundary_2_object() const
00651   {
00652     return Compare_y_near_boundary_2 (m_base_traits);
00653   }
00654   
00658   class Compare_y_on_boundary_2 
00659   {
00660   protected:
00662     const Traits_2 * m_base;
00663     
00671     Compare_y_on_boundary_2 (const Traits_2 * base) : m_base(base) {}
00672 
00674     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00675 
00676   public:
00680     Comparison_result operator() (const Point_2 & p1,
00681                                   const Point_2 & p2) const
00682     {
00683       return m_base->compare_y_on_boundary_2_object()(p1.base(), p2.base());
00684     }
00685 
00686   };
00687 
00690   Compare_y_on_boundary_2 compare_y_on_boundary_2_object() const
00691   {
00692     return Compare_y_on_boundary_2(m_base_traits);
00693   }
00694 
00695   // TODO Is_on_x_identification_2
00696   
00697 
00698   // bottom-top
00699 
00703   class Parameter_space_in_y_2 {
00704   protected:
00706     const Traits_2 * m_base;
00707 
00715     Parameter_space_in_y_2(const Traits_2 * tr) : m_base(tr) {}
00716 
00718     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00719 
00720   public:
00721     Arr_parameter_space operator() (const X_monotone_curve_2& xcv,
00722                                     Arr_curve_end ce) const
00723     {
00724       return m_base->parameter_space_in_y_2_object() (xcv.base(), ce);
00725     }
00726 
00727     Arr_parameter_space operator()(const Point_2 & p) const
00728     {
00729       return m_base->parameter_space_in_y_2_object() (p.base());
00730     }
00731 
00732     Arr_parameter_space operator()(const X_monotone_curve_2 & xcv) const
00733     {
00734       return m_base->parameter_space_in_y_2_object() (xcv.base());
00735     }
00736 
00737   };
00738 
00740   Parameter_space_in_y_2 parameter_space_in_y_2_object () const
00741   {
00742     return Parameter_space_in_y_2 (m_base_traits);
00743   }
00744 
00748   class Compare_x_near_boundary_2 {
00749   protected:
00751     const Traits_2 * m_base;
00752 
00760     Compare_x_near_boundary_2 (const Traits_2 * base) : m_base(base) {}
00761 
00763     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00764 
00765   public:
00769     Comparison_result operator() (const Point_2 & p,
00770                                   const X_monotone_curve_2 & xcv,
00771                                   Arr_curve_end ce) const
00772     {
00773 
00774       return m_base->compare_x_near_boundary_2_object() (p.base(),
00775                                                          xcv.base(), ce);
00776     }
00777 
00781     Comparison_result operator() (const X_monotone_curve_2 & xcv1,
00782                                   Arr_curve_end ce1,
00783                                   const X_monotone_curve_2 & xcv2,
00784                                   Arr_curve_end ce2) const
00785     {
00786       return m_base->compare_x_near_boundary_2_object() (xcv1.base(), ce1,
00787                                                          xcv2.base(), ce2);
00788     }
00789 
00790   };
00791   
00794   Compare_x_near_boundary_2 compare_x_near_boundary_2_object() const
00795   {
00796     return Compare_x_near_boundary_2(m_base_traits);
00797   }
00798 
00802   class Compare_x_on_boundary_2 
00803   {
00804   protected:
00806     const Traits_2 * m_base;
00807     
00815     Compare_x_on_boundary_2 (const Traits_2 * base) : m_base(base) {}
00816 
00818     friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>;
00819 
00820   public:
00824     Comparison_result operator() (const Point_2 & p1,
00825                                   const Point_2 & p2) const
00826     {
00827       return m_base->compare_x_on_boundary_2_object()(p1.base(), p2.base());
00828     }
00829 
00830   };
00831 
00834   Compare_x_on_boundary_2 compare_x_on_boundary_2_object() const
00835   {
00836     return Compare_x_on_boundary_2(m_base_traits);
00837   }
00838 
00839   // TODO Is_on_y_identification_2
00840 
00841 };
00842 
00843 CGAL_END_NAMESPACE
00844 
00845 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines