arr_traits_adaptor_2.h

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

            }
            return (true);
          }
          return (true);
        }
      }
      
      if (cv1_to_right && cv2_to_right)
      {
        // Case 2: Both cv1 and cv2 are defined to the right of p.
        r_res = compare_y_at_x_right (cv1, cv2, p);

        if (r_res == LARGER)
        {
          // Case 2(a) : cv1 is above cv2.
          if (cv_to_right)
          {
            res1 = compare_y_at_x_right (cv1, cv, p);
            res2 = compare_y_at_x_right (cv2, cv, p);

            if (res1 == EQUAL)
              cv_equal_cv1 = true;
            if (res2 == EQUAL)
              cv_equal_cv2 = true;

            return (res1 == LARGER && res2 == SMALLER);
          }
          return (false);
        }
        else if (r_res == SMALLER)
        {
          // Case 2(b): cv1 is below cv2.
          if (cv_to_right)
          {
            res1 = compare_y_at_x_right (cv1, cv, p);
            res2 = compare_y_at_x_right (cv2, cv, p);

            if (res1 == EQUAL)
              cv_equal_cv1 = true;
            if (res2 == EQUAL)
              cv_equal_cv2 = true;

            return (res1 == LARGER || res2 == SMALLER);
          }
          return (true);
        }
        else
        {
          // Overlapping segments.
          if (cv_to_right)
          {
            res1 = compare_y_at_x_right (cv1, cv, p);
          
            if (res1 == EQUAL)
            {
              cv_equal_cv1 = true;
              cv_equal_cv2 = true;             
              return (false);
            }
            return (true);
          }
          return (true);
        }
      }

      if (!cv1_to_right && cv2_to_right)
      {
        // Case 3: cv1 is defined to the left of p, and cv2 to its right.
        if (!cv_to_right)
        {
          res1 = compare_y_at_x_left (cv1, cv, p);

          if (res1 == EQUAL)
            cv_equal_cv1 = true;
        
          return (res1 == SMALLER);
        }
        else
        {
          res2 = compare_y_at_x_right (cv2, cv, p);

          if (res2 == EQUAL)
            cv_equal_cv2 = true;

          return (res2 == SMALLER);
        }
      }

      CGAL_assertion (cv1_to_right && !cv2_to_right);

      // Case 4: cv1 is defined to the right of p, and cv2 to its left.
      if (cv_to_right)
      {
	res1 = compare_y_at_x_right (cv1, cv, p);
	
	if (res1 == EQUAL)
	  cv_equal_cv1 = true;
        
	return (res1  == LARGER);
      }
      else
      {
        res2 = compare_y_at_x_left (cv2, cv, p);
        
        if (res2 == EQUAL)
          cv_equal_cv2 = true;
	
        return (res2 == LARGER);
      }
    }
    
  private:
    /*! The traits */
    const Self * m_self;
  };

  /*! Get an Is_between_cw_2 functor object. */
  Is_between_cw_2 is_between_cw_2_object () const
  {
    return Is_between_cw_2(this);
  }

  class Compare_cw_around_point_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_cw_around_point_2(const Self * self) : m_self(self) {}
    
    /*!
     * Compare the two interior disjoint x-monotone curves in a clockwise
     * order around their common endpoint.
     * \param cv1 The first curve.
     * \param cv1_to_right Is cv1 directed from left to right.
     * \param cv2 The second curve.
     * \param cv2_to_right Is cv2 directed from left to right.
     * \param p The common endpoint.
     * \param from_top (true) if we start from 12 o'clock, 
     *                 (false) if we start from 6 o'clock.
     * \pre The point p is an endpoint of both curves.
     * \return SMALLER if we encounter cv1 before cv2;
     *         LARGER if we encounter cv2 before cv1;
     *         EQUAL otherwise.
     */
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  bool cv1_to_right,
                                  const X_monotone_curve_2& cv2,
                                  bool cv2_to_right,
                                  const Point_2& p,
                                  bool from_top = true) const
    {
      // Act according to where cv1 and cv2 lie.
      if (!cv1_to_right && !cv2_to_right)
      {
        // Both are defined to the left of p, and we encounter cv1 before
        // cv2 if it is below cv2:
        return (m_self->compare_y_at_x_left_2_object() (cv1, cv2, p));
      }
      
      if (cv1_to_right && cv2_to_right)
      {
        // Both are defined to the right of p, and we encounter cv1 before
        // cv2 if it is above cv2. We therefore reverse the order of the
        // curves when we invoke compare_y_at_x_right:
        return (m_self->compare_y_at_x_right_2_object() (cv2, cv1, p));
      }
      
      if (!cv1_to_right && cv2_to_right)
      {
        // If we start from the top, we encounter the right curve (which
        // is cv2) first. If we start from the bottom, we encounter cv1 first.
        return (from_top ? LARGER : SMALLER);
      }

      CGAL_assertion (cv1_to_right && !cv2_to_right);

      // If we start from the top, we encounter the right curve (which
      // is cv1) first. If we start from the bottom, we encounter cv2 first.
      return (from_top ? SMALLER : LARGER);
    }

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

  /*! Get a Compare_cw_around_point_2 functor object. */
  Compare_cw_around_point_2 compare_cw_around_point_2_object () const
  {
    return Compare_cw_around_point_2(this);
  }
  //@}
};

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

  // Traits-class geometric types.
  typedef ArrangementTraits_                             Base_traits_2;
  typedef Arr_traits_basic_adaptor_2<ArrangementTraits_> Base;

  typedef typename Base_traits_2::Curve_2                Curve_2;
  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_merge_category              Has_merge_category;

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

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

  // Inherited functors:
  typedef typename Base::Compare_x_2            Compare_x_2;
  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_2       Compare_y_at_x_2;
  typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2;
  typedef typename Base::Compare_y_at_x_left_2  Compare_y_at_x_left_2;
  typedef typename Base::Equal_2                Equal_2;

  // Note that the basic adaptor does not have to support these functors:
  typedef typename Base_traits_2::Make_x_monotone_2  Make_x_monotone_2;
  typedef typename Base_traits_2::Split_2            Split_2; 
  typedef typename Base_traits_2::Intersect_2        Intersect_2;

  /// \name Overriden functors.
  //@{

  class Are_mergeable_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)
     */
    Are_mergeable_2(const Base * base) : m_base(base) {}

    /*!
     * Check whether it is possible to merge two given x-monotone curves.
     * \param cv1 The first curve.
     * \param cv2 The second curve.
     * \return (true) if the two curves are mergeable - if they are supported
     *         by the same line and share a common endpoint; (false) otherwise.
     */
    bool operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2) const
    {
      // The function is implemented based on the Has_merge category.
      return (_are_mergeable_imp (cv1, cv2, Has_merge_category()));
    }

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

    /*!
     * Implementation of the operator() in case the HasMerge tag is true.
     */
    bool _are_mergeable_imp (const X_monotone_curve_2& cv1,
           const X_monotone_curve_2& cv2,
           Tag_true) const
    {
      return (m_base->are_mergeable_2_object() (cv1, cv2));      
    }

    /*!
     * Implementation of the operator() in case the HasMerge tag is false.
     */
    bool _are_mergeable_imp (const X_monotone_curve_2& ,
           const X_monotone_curve_2& ,
           Tag_false) const
    {
      // Curve merging is not supported:
      return (false);
    }
  };

  /*! Get an Are_mergeable_2 functor object. */
  Are_mergeable_2 are_mergeable_2_object () const
  {
    return Are_mergeable_2(this);
  }

  class Merge_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)
     */
    Merge_2(const Base * base) : m_base(base) {}

    /*!
     * Merge two given x-monotone curves into a single curve (segment).
     * \param cv1 The first curve.
     * \param cv2 The second curve.
     * \param c Output: The merged curve.
     * \pre The two curves are mergeable, that is they are supported by the
     *      curve line and share a common endpoint.
     */
    void operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2,
                     X_monotone_curve_2& c) const
    {
      // The function is implemented based on the Has_merge category.
      _merge_imp (cv1, cv2, c, Has_merge_category());
    }

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

    /*!
     * Implementation of the operator() in case the HasMerge tag is true.
     */
    void _merge_imp (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2,
                     X_monotone_curve_2& c,
                     Tag_true) const
    {
      return (m_base->merge_2_object() (cv1, cv2, c));      
    }

    /*!
     * Implementation of the operator() in case the HasMerge tag is false.
     */
    void _merge_imp (const X_monotone_curve_2& ,
                     const X_monotone_curve_2& ,
                     X_monotone_curve_2& ,
                     Tag_false) const
    {
      // This function should never be called!
      CGAL_assertion_msg (false,
                          "Merging curves is not supported.");
    }
  };

  /*! Get a Merge_2 functor object. */
  Merge_2 merge_2_object () const
  {
    return Merge_2(this);
  }
  //@}

};

CGAL_END_NAMESPACE

#endif