SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Sweep_line_2/Arr_overlay_traits_2.h

Go to the documentation of this file.

// Copyright (c) 2005  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/Sweep_line_2/Arr_overlay_traits_2.h $
// $Id: Arr_overlay_traits_2.h 50366 2009-07-05 12:56:48Z efif $
// 
//
// Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 Ron Wein <wein@post.tau.ac.il>
//                 Efi Fogel <efif@post.tau.ac.il>

#ifndef CGAL_ARR_OVERLAY_TRAITS_2_H
#define CGAL_ARR_OVERLAY_TRAITS_2_H

#include <CGAL/Object.h>
#include <CGAL/Arr_tags.h>

CGAL_BEGIN_NAMESPACE

template <typename Traits_,
          typename ArrangementRed_,
          typename ArrangementBlue_>
class Arr_overlay_traits_2
{
public:

  typedef Traits_                                   Traits_2;
  typedef ArrangementRed_                           Arrangement_red_2;
  typedef ArrangementBlue_                          Arrangement_blue_2;

  typedef typename Arrangement_red_2::Face_const_handle 
                                                    Face_handle_red;
  typedef typename Arrangement_blue_2::Face_const_handle
                                                    Face_handle_blue;

  typedef typename Arrangement_red_2::Halfedge_const_handle 
                                                    Halfedge_handle_red;
  typedef typename Arrangement_blue_2::Halfedge_const_handle
                                                    Halfedge_handle_blue;

  typedef typename Arrangement_red_2::Vertex_const_handle 
                                                    Vertex_handle_red;
  typedef typename Arrangement_blue_2::Vertex_const_handle
                                                    Vertex_handle_blue;

  typedef typename Traits_2::X_monotone_curve_2     Base_x_monotone_curve_2;
  typedef typename Traits_2::Point_2                Base_point_2;

  typedef typename Traits_2::Compare_x_2            Base_compare_x_2;
  typedef typename Traits_2::Compare_xy_2           Base_compare_xy_2;
  typedef typename Traits_2::Construct_min_vertex_2 Base_construct_min_vertex_2;
  typedef typename Traits_2::Construct_max_vertex_2 Base_construct_max_vertex_2;
  typedef typename Traits_2::Is_vertical_2          Base_is_vertical_2;
  typedef typename Traits_2::Compare_y_at_x_2       Base_compare_y_at_x_2;
  typedef typename Traits_2::Compare_y_at_x_right_2 Base_compare_y_at_x_right_2;
  typedef typename Traits_2::Intersect_2            Base_intersect_2;
  typedef typename Traits_2::Split_2                Base_split_2;
  typedef typename Traits_2::Equal_2                Base_equal_2;

  typedef typename CGALi::Arr_complete_left_side_tag< Traits_2 >::Tag
                                                    Arr_left_side_tag;
  typedef typename CGALi::Arr_complete_bottom_side_tag< Traits_2 >::Tag
                                                    Arr_bottom_side_tag;
  typedef typename CGALi::Arr_complete_top_side_tag< Traits_2 >::Tag
                                                    Arr_top_side_tag;
  typedef typename CGALi::Arr_complete_right_side_tag< Traits_2 >::Tag
                                                    Arr_right_side_tag;

  /* Overlay is implemented as sweep-line visitor. The sweep-line algorithm
   * never uses Compare_y_at_x_left_2, and it never performs merging of curves.
   * Thus, AreMergeable_2 and Merge_2 are not needed either.
   */
  typedef Tag_false                                 Has_left_category;
  typedef Tag_false                                 Has_merge_category;
  
  // The color of a feature.
  enum Color
  {
    RED,          // From the "red" arrangement.
    BLUE,         // From the "blue" arrangement.
    RB_OVERLAP    // Red-blue overlap.
  };

private:

  const Traits_2 * m_base_traits;        // The base traits object.

public:

  Arr_overlay_traits_2()
  {}

  Arr_overlay_traits_2 (const Traits_2 & base_tr) :
    m_base_traits (&base_tr)
  {}

  const Traits_2 * base_traits() const { return m_base_traits; }

  class Ex_x_monotone_curve_2   
  {
  public:

    typedef  Base_x_monotone_curve_2     Base;

  protected:
    
    Base                  m_base_xcv;               // The base curve.
    Halfedge_handle_red   m_red_halfedge_handle;    // The red halfedge.
    Halfedge_handle_blue  m_blue_halfedge_handle;   // The blue halfedge.

  public:

    Ex_x_monotone_curve_2() : 
      m_base_xcv(),
      m_red_halfedge_handle(),
      m_blue_halfedge_handle()
    {}

    Ex_x_monotone_curve_2 (const Base& xcv):
      m_base_xcv(xcv),
      m_red_halfedge_handle(),
      m_blue_halfedge_handle()
    {}

    Ex_x_monotone_curve_2 (const Base& xcv,
                           Halfedge_handle_red  he_r,
                           Halfedge_handle_blue he_b): 
      m_base_xcv(xcv),
      m_red_halfedge_handle (he_r),
      m_blue_halfedge_handle (he_b)
    {
      CGAL_precondition (he_r == Halfedge_handle_red() ||
                         he_r->direction() == ARR_RIGHT_TO_LEFT);
      CGAL_precondition (he_b == Halfedge_handle_blue() ||
                         he_b->direction() == ARR_RIGHT_TO_LEFT);
    }

    const Base& base () const
    {
      return (m_base_xcv);
    }

    Base& base ()
    {
      return (m_base_xcv);
    }

    operator const Base& () const
    {
      return (m_base_xcv);
    }

    operator Base&()
    {
      return (m_base_xcv);
    }

    Halfedge_handle_red red_halfedge_handle() const
    {
      return (m_red_halfedge_handle);
    }
    
    Halfedge_handle_blue blue_halfedge_handle() const
    {
      return (m_blue_halfedge_handle);
    }

    void set_red_halfedge_handle (Halfedge_handle_red he_r)
    {
      CGAL_precondition (he_r == Halfedge_handle_red() ||
                         he_r->direction() == ARR_RIGHT_TO_LEFT);

      m_red_halfedge_handle = he_r;
    }

    void set_blue_halfedge_handle (Halfedge_handle_blue he_b)
    {
      CGAL_precondition (he_b == Halfedge_handle_blue() ||
                         he_b->direction() == ARR_RIGHT_TO_LEFT);

      m_blue_halfedge_handle = he_b;
    }

    Color color () const
    {
      Halfedge_handle_red     null_red_he;
      Halfedge_handle_blue    null_blue_he;

      if (m_red_halfedge_handle != null_red_he &&
          m_blue_halfedge_handle == null_blue_he)
        return (RED);

      if (m_blue_halfedge_handle != null_blue_he &&
          m_red_halfedge_handle == null_red_he)
        return (BLUE);
      
      // Overlap, return the RB_OVERLAP color:
      CGAL_assertion (m_red_halfedge_handle != null_red_he && 
                      m_blue_halfedge_handle != null_blue_he);
      return (RB_OVERLAP);
    }
    
  }; // nested class Ex_x_monotone_curve_2 - END
  
  typedef Ex_x_monotone_curve_2                     X_monotone_curve_2;

#ifdef CGAL_SL_VERBOSE
  // For debugging purposes:
  friend std::ostream& operator<< (std::ostream& os,
                                   const X_monotone_curve_2& xcv)
  {
    os << xcv.base();
    return (os);
  }
#endif
 
  class Ex_point_2 
  {
  public:

    typedef Base_point_2    Base;

  protected:

    Base          m_base_pt;        // The base point.
    Object        m_red_obj;        // The "red" object.
    Object        m_blue_obj;       // The "blue" object.

  public:

    Ex_point_2() :
      m_base_pt(),
      m_red_obj(),
      m_blue_obj()
    {}

    Ex_point_2 (const Base& pt) :
      m_base_pt (pt),
      m_red_obj(),
      m_blue_obj()
    {}

    Ex_point_2 (const Base& pt, const Object& obj_r, const Object& obj_b) :
      m_base_pt (pt),
      m_red_obj (obj_r),
      m_blue_obj (obj_b)
    {}

    const Base& base () const
    {
      return (m_base_pt);
    }

    Base& base ()
    {
      return (m_base_pt);
    }

    operator const Base& () const
    {
      return (m_base_pt);
    }

    operator Base& ()
    {
      return (m_base_pt);
    }

    const Object& red_object() const  
    { 
      return (m_red_obj);  
    }

    const Object& blue_object() const
    {
      return (m_blue_obj); 
    }

    bool is_red_object_empty () const
    {
      return (m_red_obj.is_empty());
    }

    bool is_blue_object_empty () const
    {
      return (m_blue_obj.is_empty());
    }

    void set_red_object (const Object& obj_r)
    {
      m_red_obj = obj_r;
    }

    void set_blue_object (const Object& obj_b)
    {
      m_blue_obj = obj_b;
    }

  };

  typedef Ex_point_2                                Point_2;

#ifdef CGAL_SL_VERBOSE
  // For debugging purposes:
  friend std::ostream& operator<< (std::ostream& os,
                                   const Point_2& pt)
  {
    os << pt.base();
    return (os);
  }
#endif

  class Intersect_2 {
  protected:
    const Arr_overlay_traits_2 * m_traits;

    Intersect_2(const Arr_overlay_traits_2 * traits) : m_traits(traits) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    template<class OutputIterator>
    OutputIterator operator() (const X_monotone_curve_2 & xcv1,
                               const X_monotone_curve_2 & xcv2,
                               OutputIterator oi)
    {
      // In case the curves originate from the same arrangement, they are
      // obviously interior-disjoint.
      if (xcv1.color() == xcv2.color())
        return (oi);
      
      if (xcv1.color() == RB_OVERLAP || xcv2.color() == RB_OVERLAP)
        return (oi);

      // Compute the intersection points between the curves. Note that if
      // xcv1 and xcv2 are subcruves of x-monotone curves that had intersected
      // before the current point on the status line, we may get a filter
      // failure if we send the subcurve whose left endpoint is to the left
      // of the other curve - this is because their previously computed
      // intersection point p may be equal to the this left endpoint. As many
      // traits classes start by computing the intersection between the
      // supporting curves and then check whether the result is in the x-range
      // of both subcurves, this will result in a filter failure. However, if
      // we send xcv1 first, then p is obviusly not in its x-range and there is
      // no filter failure.
      //
      //              / xcv1
      //             /
      //            /
      //       ----+--
      //          /
      //         /
      //      p +------------- xcv2
      //              ^
      //              |
      //              status line
      //
      // Note that we do not bother with curves whose left ends are open,
      // since such curved did not intersect before.

      const std::pair<Base_point_2, unsigned int>   *base_ipt;
      const Base_x_monotone_curve_2                 *overlap_xcv;
      bool                                           send_xcv1_first = true;
      OutputIterator                                 oi_end;

      Parameter_space_in_x_2      ps_x_op =
        m_traits->parameter_space_in_x_2_object();
      Parameter_space_in_y_2      ps_y_op =
        m_traits->parameter_space_in_y_2_object();
      const Arr_parameter_space  bx1 = ps_x_op (xcv1, ARR_MIN_END);
      const Arr_parameter_space  by1 = ps_y_op (xcv1, ARR_MIN_END);
      const Arr_parameter_space  bx2 = ps_x_op (xcv2, ARR_MIN_END);
      const Arr_parameter_space  by2 = ps_y_op (xcv2, ARR_MIN_END);

      const Traits_2 * m_base_tr = m_traits->base_traits();

      if (bx1 == ARR_INTERIOR && by1 == ARR_INTERIOR &&
          bx2 == ARR_INTERIOR && by2 == ARR_INTERIOR)
      {
        send_xcv1_first =
          (m_base_tr->compare_xy_2_object()
           (m_base_tr->construct_min_vertex_2_object()(xcv1.base()),
            m_base_tr->construct_min_vertex_2_object()(xcv2.base())) == LARGER);
      }

      oi_end = (send_xcv1_first) ?
        m_base_tr->intersect_2_object()(xcv1.base(), xcv2.base(), oi) :
        m_base_tr->intersect_2_object()(xcv2.base(), xcv1.base(), oi);

      // Convert objects that are associated with Base_x_monotone_curve_2 to
      // the exteneded X_monotone_curve_2. 
      for (; oi != oi_end; ++oi)
      {
        base_ipt = object_cast<std::pair<Base_point_2, unsigned int> >(&(*oi));

        if (base_ipt != NULL)
        {
          // We have an red-blue intersection point, so we attach the
          // intersecting red and blue halfedges to it.
          Object   red_obj;
          Object   blue_obj;

          if (xcv1.color() == RED)
          {
            CGAL_assertion (xcv2.color() == BLUE);
            red_obj = CGAL::make_object (xcv1.red_halfedge_handle());
            blue_obj = CGAL::make_object (xcv2.blue_halfedge_handle());
          }
          else
          {
            CGAL_assertion(xcv2.color() == RED &&
                           xcv1.color() == BLUE);
            red_obj = CGAL::make_object(xcv2.red_halfedge_handle());
            blue_obj = CGAL::make_object(xcv1.blue_halfedge_handle());
          }

          // Create the extended point and add the multiplicity.
          Point_2   ex_point (base_ipt->first,
                              red_obj, blue_obj);
          *oi = CGAL::make_object(std::make_pair (ex_point, 
                                                  base_ipt->second));
        }
        else
        {
          overlap_xcv = object_cast<Base_x_monotone_curve_2> (&(*oi));
          CGAL_assertion (overlap_xcv != NULL);

          // We have a red-blue overlap, so we mark the curve accordingly.
          Halfedge_handle_red        red_he;
          Halfedge_handle_blue       blue_he;
          
          if (xcv1.color() == RED)
          {
            red_he = xcv1.red_halfedge_handle();
            
            // Overlap can occur only between curves from a different color.
            CGAL_assertion(xcv2.color() == BLUE);
            blue_he = xcv2.blue_halfedge_handle();
          }
          else
          {
            CGAL_assertion(xcv1.color() == BLUE &&
                           xcv2.color() == RED);

            red_he = xcv2.red_halfedge_handle();
            blue_he = xcv1.blue_halfedge_handle();
          }

          *oi = CGAL::make_object (X_monotone_curve_2 (*overlap_xcv,
                                                       red_he, blue_he));
        }
      }

      // Return the past-the-end iterator.
      return (oi_end);
    }
  };

  Intersect_2 intersect_2_object () const
  {
    return Intersect_2(this); 
  }

  class Split_2 {
  protected:
    Base_split_2    m_base_split;

    Split_2 (const Base_split_2& base) : m_base_split (base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    void operator() (const X_monotone_curve_2& xcv, const Point_2 & p,
                     X_monotone_curve_2& c1, X_monotone_curve_2& c2)
    {
      // Split the base curve.
      m_base_split(xcv.base(), p.base(), c1.base(), c2.base());

      // Duplicate the halfedge data to the resulting curves.
      c1.set_red_halfedge_handle (xcv.red_halfedge_handle());
      c1.set_blue_halfedge_handle (xcv.blue_halfedge_handle());

      c2.set_red_halfedge_handle (xcv.red_halfedge_handle());
      c2.set_blue_halfedge_handle (xcv.blue_halfedge_handle());
    }
  };

  Split_2 split_2_object () const
  {
    return Split_2(m_base_traits->split_2_object());
  }

  class Construct_min_vertex_2 {
  protected:
    Base_construct_min_vertex_2  m_base_min_v;
    Base_equal_2                 m_base_equal;

    Construct_min_vertex_2 (const Base_construct_min_vertex_2& base_min_v,
                            const Base_equal_2& base_equal) :
      m_base_min_v (base_min_v),
      m_base_equal (base_equal)
    {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Point_2 operator() (const X_monotone_curve_2& xcv) 
    {
      // Create the objects that wrap the arrangement vertex.
      // Note that the halfedges associated with the curves are always
      // directed from right to left, so their target is the smaller end.
      const Base_point_2&   base_p = m_base_min_v (xcv.base());
      Object                obj_red, obj_blue;

      if (xcv.color() == RED)
      {
        obj_red = CGAL::make_object (xcv.red_halfedge_handle()->target());
      }
      else if (xcv.color() == BLUE)
      {
        obj_blue = CGAL::make_object (xcv.blue_halfedge_handle()->target());
      }
      else
      {
        CGAL_assertion (xcv.color() == RB_OVERLAP);

        if (! xcv.red_halfedge_handle()->target()->is_at_open_boundary() &&
            m_base_equal (base_p,
                          xcv.red_halfedge_handle()->target()->point()))
        {
          obj_red = CGAL::make_object (xcv.red_halfedge_handle()->target());
        }

        if (! xcv.blue_halfedge_handle()->target()->is_at_open_boundary() &&
            m_base_equal (base_p,
                          xcv.blue_halfedge_handle()->target()->point()))
        {
          obj_blue = CGAL::make_object (xcv.blue_halfedge_handle()->target());
        }
      }

      return (Point_2 (base_p, obj_red, obj_blue));
    }
  };

  Construct_min_vertex_2 construct_min_vertex_2_object () const
  {
    return 
      (Construct_min_vertex_2 (m_base_traits->construct_min_vertex_2_object(),
                               m_base_traits->equal_2_object()));
  }
 
  class Construct_max_vertex_2 {
  protected:
    Base_construct_max_vertex_2  m_base_max_v;
    Base_equal_2                 m_base_equal;

    Construct_max_vertex_2 (const Base_construct_max_vertex_2& base_max_v,
                            const Base_equal_2& base_equal) :
      m_base_max_v (base_max_v),
      m_base_equal (base_equal)
    {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Point_2 operator() (const X_monotone_curve_2 & xcv) const
    {
      // Create the objects that wrap the arrangement vertex.
      // Note that the halfedges associated with the curves are always
      // directed from right to left, so their target is the smaller end.
      const Base_point_2&   base_p = m_base_max_v (xcv.base());
      Object                obj_red, obj_blue;

      if(xcv.color() == RED)
      {
        obj_red = CGAL::make_object (xcv.red_halfedge_handle()->source());
      }
      else if(xcv.color() == BLUE)
      {
        obj_blue = CGAL::make_object (xcv.blue_halfedge_handle()->source());
      }
      else
      {
        CGAL_assertion(xcv.color() == RB_OVERLAP);

        if (! xcv.red_halfedge_handle()->source()->is_at_open_boundary() &&
            m_base_equal (base_p,
                          xcv.red_halfedge_handle()->source()->point()))
        {
          obj_red = CGAL::make_object (xcv.red_halfedge_handle()->source());
        }

        if (! xcv.blue_halfedge_handle()->source()->is_at_open_boundary() &&
            m_base_equal (base_p,
                          xcv.blue_halfedge_handle()->source()->point()))
        {
          obj_blue = CGAL::make_object (xcv.blue_halfedge_handle()->source());
        }
      }

      return (Point_2 (base_p, obj_red, obj_blue));
    }
  };

  Construct_max_vertex_2 construct_max_vertex_2_object () const
  {
    return
      (Construct_max_vertex_2 (m_base_traits->construct_max_vertex_2_object(),
                               m_base_traits->equal_2_object()));
  }

  class Is_vertical_2 {
  protected:
    Base_is_vertical_2 m_base_is_vert;

    Is_vertical_2 (const Base_is_vertical_2 & base) : m_base_is_vert(base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    bool operator() (const X_monotone_curve_2 & xcv) const
    {
      return m_base_is_vert (xcv.base());
    }
  };

  Is_vertical_2 is_vertical_2_object () const
  {
    return Is_vertical_2(m_base_traits->is_vertical_2_object());
  }

  class Equal_2 {
  protected:
    Base_equal_2 m_base_equal;

    Equal_2 (const Base_equal_2 & base) : m_base_equal(base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    bool operator() (const Point_2 & p1, const Point_2 & p2) const
    {
      return m_base_equal (p1.base(), p2.base());
    }

    bool operator() (const X_monotone_curve_2 & xcv1,
                     const X_monotone_curve_2 & xcv2) const
    {
      return m_base_equal (xcv1.base(), xcv2.base());
    }
  };

  Equal_2 equal_2_object () const
  {
    return Equal_2(m_base_traits->equal_2_object());
  }
  
  class Compare_x_2 {
  protected:
    Base_compare_x_2 m_base_cmp_x;

    Compare_x_2 (const Base_compare_x_2 & base) : m_base_cmp_x(base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator() (const Point_2 & p1, const Point_2 & p2) const
    {
      return m_base_cmp_x (p1.base(), p2.base());
    }
  };

  Compare_x_2 compare_x_2_object () const
  {
    return Compare_x_2(m_base_traits->compare_x_2_object());
  }

  class Compare_xy_2 {
  protected:
    Base_compare_xy_2 m_base_cmp_xy;

    Compare_xy_2(const Base_compare_xy_2& base) :
        m_base_cmp_xy(base)
    {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator() (const Point_2& p1, const Point_2& p2) const
    {
      // Check if there wither points represent red or blue vertices.
      Vertex_handle_red  vr1;
      Vertex_handle_red  vr2;

      Vertex_handle_blue vb1;
      Vertex_handle_blue vb2;

      const bool         assign_v1_red  = CGAL::assign (vr1, p1.red_object());
      const bool         assign_v2_red  = CGAL::assign (vr2, p2.red_object());
      const bool         assign_v1_blue = CGAL::assign (vb1, p1.blue_object());
      const bool         assign_v2_blue = CGAL::assign (vb2, p2.blue_object());

      if ((assign_v1_red && assign_v1_blue) ||
          (assign_v2_red && assign_v2_blue))
      {
        // In case of an overlapping vertex, just perform the comparison.
        return (m_base_cmp_xy (p1.base(), p2.base()));
      }

      // If both points are vertices of the same color, avoid the geometric
      // comparison if they refer to the same vertex.
      if ((assign_v1_red && assign_v2_red && vr1 == vr2) ||
          (assign_v1_blue && assign_v2_blue && vb1 == vb2))
      {
        return (EQUAL);
      }

      return (m_base_cmp_xy (p1.base(), p2.base()));
    }
  };

  Compare_xy_2 compare_xy_2_object () const
  {
    return (Compare_xy_2(m_base_traits->compare_xy_2_object()));
  }

  class Compare_y_at_x_2 {
  protected:
    Base_compare_y_at_x_2 m_base_cmp_y_at_x;

    Compare_y_at_x_2(const Base_compare_y_at_x_2& base):
        m_base_cmp_y_at_x(base)
    {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator() (const Point_2 & p,
                                  const X_monotone_curve_2 & xcv) const
    {
      return (m_base_cmp_y_at_x (p.base(), xcv.base()));
    }
  };

  Compare_y_at_x_2 compare_y_at_x_2_object () const
  {
    return (Compare_y_at_x_2(m_base_traits->compare_y_at_x_2_object()));
  }

  class Compare_y_at_x_right_2 {
  protected:
    Base_compare_y_at_x_right_2    m_base_cmp_y_at_x_right;

    Compare_y_at_x_right_2(const Base_compare_y_at_x_right_2& base):
        m_base_cmp_y_at_x_right(base)
    {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator() (const X_monotone_curve_2& xcv1,
                                  const X_monotone_curve_2& xcv2,
                                  const Point_2& p) const
    {
      return (m_base_cmp_y_at_x_right(xcv1.base(),
                                      xcv2.base(),
                                      p.base()));
    }
  };

  Compare_y_at_x_right_2 compare_y_at_x_right_2_object () const
  {
    return 
      (Compare_y_at_x_right_2(m_base_traits->compare_y_at_x_right_2_object()));
  }

  // left-right

  class Parameter_space_in_x_2 {
  protected:
    const Traits_2 * m_base;

    Parameter_space_in_x_2 (const Traits_2 * tr) : m_base (tr) {}
 
    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Arr_parameter_space operator() (const X_monotone_curve_2 & xcv,
                                    Arr_curve_end ce) const
    {
      return m_base->parameter_space_in_x_2_object() (xcv.base(), ce);
    }

    Arr_parameter_space operator() (const Point_2 & p) const
    {
      return m_base->parameter_space_in_x_2_object() (p.base());
    }

    Arr_parameter_space operator() (const X_monotone_curve_2 & xcv) const
    {
      return m_base->parameter_space_in_x_2_object() (xcv.base());
    }

  };

  class Compare_y_near_boundary_2 {
  protected:
    const Traits_2 * m_base;

    Compare_y_near_boundary_2(const Traits_2 * base) : m_base(base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator() (const X_monotone_curve_2 & xcv1,
                                  const X_monotone_curve_2 & xcv2, 
                                  Arr_curve_end ce) const
    {
      // If the traits class does not support open curves, we just
      // return EQUAL, as this comparison will not be invoked anyway.
      return m_base->compare_y_near_boundary_2_object()(xcv1.base(),
                                                        xcv2.base(), ce);
    }
  };
  
  Compare_y_near_boundary_2 compare_y_near_boundary_2_object () const
  {
    return Compare_y_near_boundary_2(m_base_traits);
  }
  
  // TODO Compare_y_on_boundary_2
  // TODO Is_on_x_identification_2

  // bottom-top
  
  Parameter_space_in_x_2 parameter_space_in_x_2_object () const
  {
    return Parameter_space_in_x_2 (m_base_traits);
  } 

  class Parameter_space_in_y_2 {
  protected:
    const Traits_2 * m_base;

    Parameter_space_in_y_2 (const Traits_2 *tr) : m_base (tr) {}
   
    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Arr_parameter_space operator() (const X_monotone_curve_2 & xcv,
                                    Arr_curve_end ce) const
    {
      return m_base->parameter_space_in_y_2_object()(xcv.base(), ce);
    }

    Arr_parameter_space operator()(const Point_2 & p) const
    {
      return m_base->parameter_space_in_y_2_object()(p.base());
    }

    Arr_parameter_space operator()(const X_monotone_curve_2 & xcv) const
    {
      return m_base->parameter_space_in_y_2_object()(xcv.base());
    }
    
  };

  Parameter_space_in_y_2 parameter_space_in_y_2_object () const
  {
    return (Parameter_space_in_y_2 (m_base_traits));
  } 

  class Compare_x_near_boundary_2 {
  protected:
    const Traits_2 * m_base;

    Compare_x_near_boundary_2(const Traits_2 * base) : m_base(base) {}

    friend class Arr_overlay_traits_2<Traits_2,
                                      Arrangement_red_2,
                                      Arrangement_blue_2>;
    
  public:
    Comparison_result operator()(const Point_2 & p,
                                 const X_monotone_curve_2 & xcv,
                                 Arr_curve_end ce) const
    {
      return m_base->compare_x_near_boundary_2_object()(p.base(),
                                                        xcv.base(), ce);
    }

    Comparison_result operator()(const X_monotone_curve_2 & xcv1,
                                 Arr_curve_end ce1,
                                 const X_monotone_curve_2 & xcv2,
                                 Arr_curve_end ce2) const
    {
      return m_base->compare_x_near_boundary_2_object()(xcv1.base(), ce1,
                                                        xcv2.base(), ce2);
    }

  };

  Compare_x_near_boundary_2 compare_x_near_boundary_2_object () const
  {
    return Compare_x_near_boundary_2(m_base_traits);
  }

  // TODO Compare_x_on_boundary_2
  // TODO Is_on_y_identification_2
  
};

CGAL_END_NAMESPACE

#endif