arr_traits_adaptor_2.h

很多二维 三维几何计算算法 C++ 类库

// 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.3-branch/Arrangement_2/include/CGAL/Arrangement_2/Arr_traits_adaptor_2.h $
// $Id: Arr_traits_adaptor_2.h 36257 2007-02-14 16:05:16Z efif $
// $Date: 2007-02-14 17:05:16 +0100 (Wed, 14 Feb 2007) $
// 
//
// Author(s)     : Ron Wein             <[e-mail]>
//                 Efi Fogel            <[e-mail]>
//                 (based on old version by Iddo Hanniel
//                                          Eyal Flato
//                                          Oren Nechushtan
//                                          Efi Fogel
//                                          Ron Wein
//                                          Idit Haran)
#ifndef CGAL_ARR_TRAITS_ADAPTOR_2_H
#define CGAL_ARR_TRAITS_ADAPTOR_2_H

/*! \file
 * Definitions of the adaptor classes for the arrangement traits class.
 */

#include <CGAL/config.h>
#include <CGAL/tags.h>
#include <CGAL/Arr_enums.h>

CGAL_BEGIN_NAMESPACE

/*! \class
 * A traits-class adaptor that extends the basic traits-class interface.
 */
template <class ArrangementBasicTraits_>
class Arr_traits_basic_adaptor_2 : public ArrangementBasicTraits_
{
public:

  // Traits-class geometric types.
  typedef ArrangementBasicTraits_               Base;
  typedef Arr_traits_basic_adaptor_2<Base>      Self;
  typedef typename Base::X_monotone_curve_2     X_monotone_curve_2;
  typedef typename Base::Point_2                Point_2;

  // Tags.
  typedef typename Base::Has_left_category      Has_left_category;
  typedef typename Base::Has_boundary_category  Has_boundary_category;

  /// \name Construction.
  //@{
  /*! Default constructor. */
  Arr_traits_basic_adaptor_2 () :
    Base()
  {}

  /*! Constructor from a base-traits class. */
  Arr_traits_basic_adaptor_2 (const Base& traits) :
    Base (traits)
  {}
  //@}

  // Inherited functors:
  typedef typename Base::Compare_xy_2           Compare_xy_2;
  typedef typename Base::Construct_min_vertex_2 Construct_min_vertex_2;
  typedef typename Base::Construct_max_vertex_2 Construct_max_vertex_2;
  typedef typename Base::Is_vertical_2          Is_vertical_2;
  typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2;
  typedef typename Base::Equal_2                Equal_2;

  /// \name Overriden functors.
  //@{
  class Compare_x_2
  {
  public:
    /*! Constructor
     * \param base the base traits class. It must be passed, to handle the
     * case it is not stateless (e.g., it stores data)
     */
    Compare_x_2(const Base * base) : m_base(base) {}
    
    /*!
     * Redefining the mandatory comparison operator.
     */
    Comparison_result operator() (const Point_2& p1,
                                  const Point_2& p2) const
    {
      return (m_base->compare_x_2_object() (p1, p2));
    }

    /*!
     * Compare the relative x-positions of a vertical curve and another given
     * curves at y = +/- oo.
     * \param p A reference point; we refer to a vertical line incident to p.
     * \param cv The compared curve.
     * \param ind MIN_END if we refer to cv's minimal end; 
     *            MAX_END if we refer to its maximal end.
     * \pre cv's relevant end is defined at y = +/- oo.
     * \return SMALLER if p lies to the left of cv;
     *         LARGER if p lies to the right cv;
     *         EQUAL in case of an overlap.
     */
    Comparison_result operator() (const Point_2& p,
                                  const X_monotone_curve_2& cv,
                                  Curve_end ind) const
    {
      return (_compare_point_curve_imp (p, cv, ind,
                                        Has_boundary_category()));
    }

    /*!
     * Compare the relative x-positions of two curves at y = +/- oo.
     * \param cv1 The first curve.
     * \param ind1 MIN_END if we refer to cv1's minimal end; 
     *             MAX_END if we refer to its maximal end.
     * \param cv2 The second curve.
     * \param ind2 MIN_END if we refer to cv2's minimal end; 
     *             MAX_END if we refer to its maximal end.
     * \pre The curves are defined at y = +/- oo.
     * \return SMALLER if cv1 lies to the left of cv2;
     *         LARGER if cv1 lies to the right cv2;
     *         EQUAL in case of an overlap.
     */
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  Curve_end ind1,
                                  const X_monotone_curve_2& cv2,
                                  Curve_end ind2) const
    {
      return (_compare_curves_imp (cv1, ind1, cv2, ind2,
                                   Has_boundary_category()));
    }

  private:
    /*! The base traits */
    const Base * m_base;
    
    /*!
     * Implementation of the operator() in case the HasInfinite tag is true.
     */
    Comparison_result _compare_point_curve_imp (const Point_2& p,
                                                const X_monotone_curve_2& cv,
                                                Curve_end ind,
                                                Tag_true) const
    {
      return (m_base->compare_x_2_object() (p, cv, ind));
    }

    /*!
     * Implementation of the operator() in case the HasInfinite tag is false.
     */
    Comparison_result _compare_point_curve_imp (const Point_2& ,
                                                const X_monotone_curve_2& ,
                                                Curve_end ,
                                                Tag_false) const
    {
      return (EQUAL);
    }

    /*!
     * Implementation of the operator() in case the HasInfinite tag is true.
     */
    Comparison_result _compare_curves_imp (const X_monotone_curve_2& cv1, 
                                           Curve_end ind1,
                                           const X_monotone_curve_2& cv2,
                                           Curve_end ind2,
                                           Tag_true) const
    {
      return (m_base->compare_x_2_object() (cv1, ind1, cv2, ind2));
    }

    /*!
     * Implementation of the operator() in case the HasInfinite tag is false.
     */
    Comparison_result _compare_curves_imp (const X_monotone_curve_2&,
                                           Curve_end,
                                           const X_monotone_curve_2&, 
                                           Curve_end,
                                           Tag_false) const
    {
      return (EQUAL);
    }

  };

  /*! Get a Compare_x_2 functor object. */
  Compare_x_2 compare_x_2_object () const
  {
    return Compare_x_2(this);
  }


  class Compare_y_at_x_2
  {
  public:
    /*! Constructor
     * \param base the base traits class. It must be passed, to handle the
     * case it is not stateless (e.g., it stores data)
     */
    Compare_y_at_x_2(const Base * base) : m_base(base) {}

    /*!
     * Redefining the mandatory comparison operator.
     */
    Comparison_result operator() (const Point_2& p,
                                  const X_monotone_curve_2& cv) const
    {
      return (m_base->compare_y_at_x_2_object() (p, cv));
    }

    /*!
     * Compare the relative y-positions of two curves at x = +/- oo.
     * \param cv1 The first curve.
     * \param cv2 The second curve.
     * \param ind MIN_END if we compare at x = -oo;
     *            MAX_END if we compare at x = +oo.
     * \pre The curves are defined at x = +/- oo.
     * \return SMALLER if cv1 lies below cv2;
     *         LARGER if cv1 lies above cv2;
     *         EQUAL in case of an overlap.
     */
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  const X_monotone_curve_2& cv2, 
                                  Curve_end ind) const
    {
      // The function is implemented based on the Has_infinite category.
      // If the traits class does not support unbounded curves, we just
      // return EQUAL, as this comparison will not be invoked anyway.
      return _comp_y_at_infinity_imp (cv1, cv2, ind, 
                                      Has_boundary_category());
    }

  private:
    /*! The base traits */
    const Base * m_base;

    /*!
     * Implementation of the operator() in case the HasInfinite tag is true.
     */
    Comparison_result _comp_y_at_infinity_imp (const X_monotone_curve_2& cv1,
                                               const X_monotone_curve_2& cv2, 
                                               Curve_end ind,
                                               Tag_true) const
    {
      return (m_base->compare_y_at_x_2_object() (cv1, cv2, ind));
    }

    /*!
     * Implementation of the operator() in case the HasInfinite tag is false.
     */
    Comparison_result _comp_y_at_infinity_imp (const X_monotone_curve_2& ,
                                               const X_monotone_curve_2& , 
                                               Curve_end ,
                                               Tag_false) const
    {
      return (EQUAL);
    }
  };

  /*! Get a Compare_y_at_x_2 functor object. */
  Compare_y_at_x_2 compare_y_at_x_2_object () const
  {
    return Compare_y_at_x_2(this);
  }


  class Compare_y_at_x_left_2
  {
  public:
    /*! Constructor
     * \param self the traits class. It must be passed, to handle the case
     * it is not stateless (e.g., it stores data)
     */
    Compare_y_at_x_left_2(const Self * self) : m_self(self) {}

    /*!
     * Compare two curves immediately to the left of their intersection point.
     * \param cv1 The first curve.
     * \param cv2 The second curve.
     * \param p The query point.
     * \pre The two curves intersect at p, and they are defined to its left.
     * \return SMALLER if cv1 lies below cv2 to the left of q;
     *         LARGER if cv1 lies above cv2 to the left of q;
     *         EQUAL in case of an overlap to the left of q.
     */
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  const X_monotone_curve_2& cv2,
                                  const Point_2& p) const 
    {
      // The function is implemented based on the Has_left category. If the 
      // category indicates that the "left" version is available, it calls the
      // function with same name defined in the base class. Otherwise, it 
      // uses other predicates to provide this comparison.
      return _compare_y_at_x_left_imp (cv1, cv2, p, Has_left_category());
    }

  private:
    /*! The traits */
    const Self * m_self;

    /*!
     * Implementation of the operator() in case the HasLeft tag is true.
     */
    Comparison_result _compare_y_at_x_left_imp (const X_monotone_curve_2& cv1,
                                                const X_monotone_curve_2& cv2,
                                                const Point_2& p,
                                                Tag_true) const
    {
      const Base * base = m_self;
      return (base->compare_y_at_x_left_2_object() (cv1, cv2, p));
    }

    /*!
     * Implementation of the operator() in case the HasLeft tag is false.
     */
    Comparison_result _compare_y_at_x_left_imp (const X_monotone_curve_2& cv1,
                                                const X_monotone_curve_2& cv2,
                                                const Point_2& p,
                                                Tag_false) const
    {
      Boundary_in_x_2      infinite_x = m_self->boundary_in_x_2_object();
      Boundary_in_y_2      infinite_y = m_self->boundary_in_y_2_object();
      Construct_min_vertex_2 min_vertex =
        m_self->construct_min_vertex_2_object();
      Equal_2              equal = m_self->equal_2_object();

      // Check if the left ends of the curves are bounded endpoints.
      const Boundary_type  inf_x1 = infinite_x (cv1, MIN_END);
      const Boundary_type  inf_y1 = (inf_x1 != NO_BOUNDARY ? 
                                     NO_BOUNDARY : infinite_y (cv1, MIN_END));
      const bool           has_left1 = (inf_x1 == NO_BOUNDARY && inf_y1 == NO_BOUNDARY);
      const Boundary_type  inf_x2 = infinite_x (cv2, MIN_END);
      const Boundary_type  inf_y2 = (inf_x2 != NO_BOUNDARY ? 
                                     NO_BOUNDARY : infinite_y (cv2, MIN_END));
      const bool           has_left2 = (inf_x2 == NO_BOUNDARY && inf_y2 == NO_BOUNDARY);

      CGAL_assertion (inf_x1 != PLUS_INFINITY && inf_x2 != PLUS_INFINITY);

      // Make sure that p lies on both curves, and that both are defined to its
      // right (so their right endpoint is lexicographically larger than p).
      CGAL_precondition_code (
        Compare_xy_2       compare_xy = m_self->compare_xy_2_object();
        Compare_y_at_x_2   compare_y_at_x = m_self->compare_y_at_x_2_object();
      );

      CGAL_precondition (compare_y_at_x (p, cv1) == EQUAL &&
                         compare_y_at_x (p, cv2) == EQUAL);

      CGAL_precondition ((! has_left1 ||
                          compare_xy(min_vertex (cv1), p) == SMALLER) &&
                         (! has_left2 ||
                          compare_xy(min_vertex (cv2), p) == SMALLER));

      // If one of the curves is vertical, it is below the other one.
      Is_vertical_2       is_vertical = m_self->is_vertical_2_object();

      if (is_vertical(cv1))
      {
        if (is_vertical (cv2))
          // Both are vertical:
          return (EQUAL);
        else
          return (SMALLER);
      }
      else if (is_vertical (cv2))
      {