arr_traits_adaptor_2.h

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

        return (LARGER);
      }

      // Perform the comparison based on the existance of bounded left
      // endpoints.
      if (has_left1 && has_left2)
      {
        // Get the left endpoints of cv1 and cv2.
        Point_2        left1 = min_vertex(cv1);
        Point_2        left2 = min_vertex(cv2);
          
        if (equal (left1, left2))
        {
          // The two curves have a common left endpoint:
          // Compare them to the right of this point.
          return (m_self->compare_y_at_x_right_2_object() (cv1, cv2, left1));
        }    
      }

      // We now that the curves do not shar a common endpoint, and we can
      // compare their relative y-position (which does not change to the left
      // of the given point p).
      return (m_self->compare_y_position_2_object() (cv1, cv2));      
    }
  };

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


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

    /*!
     * Check if an end of a given x-monotone curve is infinite at x.
     * \param cv The curve.
     * \param ind MIN_END if we refer to cv's minimal end,
     *            MAX_END if we refer to its maximal end.
     * \return MINUS_INFINITY if the curve end lies at x = -oo;
     *         NO_BOUNDARY if the curve end has a finite x-coordinate;
     *         PLUS_INFINITY if the curve end lies at x = +oo.
     */
    Boundary_type operator() (const X_monotone_curve_2& cv,
                              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 NO_BOUNDARY to mark the curve is bounded.
      return _boundary_in_x_imp (cv, ind, Has_boundary_category());
    }

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

    /*!
     * Implementation of the operator() in case the HasInfinite tag is true.
     */
    Boundary_type _boundary_in_x_imp (const X_monotone_curve_2& cv,
                                      Curve_end ind,
                                      Tag_true) const
    {
      return (m_base->boundary_in_x_2_object() (cv, ind));
    }

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

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


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

    /*!
     * Check if an end of a given x-monotone curve is infinite at y.
     * \param cv The curve.
     * \param ind MIN_END if we refer to cv's minimal end,
     *            MAX_END if we refer to its maximal end.
     * \return MINUS_INFINITY if the curve end lies at y = -oo;
     *         NO_BOUNDARY if the curve end has a finite y-coordinate;
     *         PLUS_INFINITY if the curve end lies at y = +oo.
     */
    Boundary_type operator() (const X_monotone_curve_2& cv,
                              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 NO_BOUNDARY to mark the curve is finite.
      return _boundary_in_y_imp (cv, ind, Has_boundary_category());
    }

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

    /*!
     * Implementation of the operator() in case the HasInfinite tag is true.
     */
    Boundary_type _boundary_in_y_imp (const X_monotone_curve_2& cv,
                                      Curve_end ind,
                                      Tag_true) const
    {
      return (m_base->boundary_in_y_2_object() (cv, ind));
    }

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

  /*! Get an Boundary_in_y_2 functor object. */
  Boundary_in_y_2 boundary_in_y_2_object () const
  {
    return Boundary_in_y_2(this);
  }
  //@}

  /// \name Additional auxiliary functors.
  //@{
  class Is_in_x_range_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)
     */
    Is_in_x_range_2(const Self * self) : m_self(self) {}

    /*!
     * Check whether the given point is in the x-range of the given x-monotone
     * curve.
     * \param cv The x-monotone curve.
     * \param p The point.
     * \return (true) if x(cv_left) <= x(p) <= x(cv_right); (false) otherwise.
     */
    bool operator() (const X_monotone_curve_2& cv, const Point_2& p) 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();
      Compare_x_2         compare_x =  m_self->compare_x_2_object();

      // Compare p to the position of the left end of the curve.
      // Note that if the left end of cv lies at x = -oo, p is obviously to
      // its right.
      Boundary_type           inf_x, inf_y;
      Comparison_result       res;

      inf_x = infinite_x (cv, MIN_END);

      if (inf_x == NO_BOUNDARY)
      {
        inf_y = infinite_y (cv, MIN_END);

        if (inf_y == NO_BOUNDARY)
        {
          // The left endpoint of cv is a normal point.
          res = compare_x (p, m_self->construct_min_vertex_2_object() (cv));
        }
        else
        {
          // The left end of cv lies at y = +/- oo:
          res = compare_x (p, cv, MIN_END);
        }

        if (res == SMALLER)
          return (false);         // p is to the left of the x-range.
        else if (res == EQUAL)
          return (true);
      }

      // If necessary, compare p to the right end of the curve.
      // Note that if this end lies at x = +oo, p is obviously to its left.
      inf_x = infinite_x (cv, MAX_END);

      if (inf_x != NO_BOUNDARY)
        return (true);
      
      inf_y = infinite_y (cv, MAX_END);

      if (inf_y == NO_BOUNDARY)
      {
        // The right endpoint of cv is a normal point.
        res = compare_x (p, m_self->construct_max_vertex_2_object() (cv));
      }
      else
      {
        // The right end of cv lies at y = +/- oo:
        res = compare_x (p, cv, MAX_END);
      }

      return (res != LARGER);
    }

    /*!
     * Check whether the x-ranges of the given x-monotone curves overlap.
     * \param cv1 The first x-monotone curve.
     * \param cv2 The second x-monotone curve.
     * \return (true) if there is an overlap in the x-ranges of the given
     *         curves; (false) otherwise.
     */
    bool operator() (const X_monotone_curve_2& cv1,
                     const X_monotone_curve_2& cv2) 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();
      Compare_x_2             compare_x = m_self->compare_x_2_object();
      Construct_min_vertex_2  min_vertex =
        m_self->construct_min_vertex_2_object();
      Construct_max_vertex_2  max_vertex =
        m_self->construct_max_vertex_2_object();

      // Locate the rightmost of the two left endpoints of the two curves.
      // Note that we guard for curves with infinite ends.
      Boundary_type             inf_x1, inf_y1;
      Boundary_type             inf_x2, inf_y2;
      const X_monotone_curve_2 *cv_l;
      Boundary_type             inf_yl;
      Comparison_result         res;

      inf_x1 = infinite_x (cv1, MIN_END);
      inf_x2 = infinite_x (cv2, MIN_END);

      if (inf_x1 != NO_BOUNDARY)
      {
        // If both curves are defined at x = -oo, they obviously overlap in
        // their x-ranges.
        if (inf_x2 != NO_BOUNDARY)
          return (true);

        // As cv2 is not defined at x = -oo, take its left end as the
        // rightmost.
        cv_l = &cv2;
        inf_yl = infinite_y (cv2, MIN_END);
      }
      else if (inf_x2 != NO_BOUNDARY)
      {
        // As cv1 is not defined at x = -oo, take its left end as the
        // rightmost.
        cv_l = &cv1;
        inf_yl = infinite_y (cv1, MIN_END);
      }
      else
      {
        // Compare the (finite) x-coordinates of the two left ends.
        inf_y1 = infinite_y (cv1, MIN_END);
        inf_y2 = infinite_y (cv2, MIN_END);

        if (inf_y1 == NO_BOUNDARY)
        {
          if (inf_y2 == NO_BOUNDARY)
          {
            res = compare_x (min_vertex (cv1), min_vertex (cv2));
          }
          else
          {
            res = compare_x (min_vertex (cv1), cv2, MIN_END);
           }
        }
        else
        {
          if (inf_y2 == NO_BOUNDARY)
          {
            res = compare_x (min_vertex (cv2), cv1, MIN_END);
            if (res != EQUAL)
              res = (res == SMALLER) ? LARGER : SMALLER;

          }
          else
          {
            res = compare_x (cv1, MIN_END, cv2, MIN_END);
          }
        }

        if (res == LARGER)
        {
          cv_l = &cv1;
          inf_yl = inf_y1;
        }
        else
        {
          cv_l = &cv2;
          inf_yl = inf_y2;
        }
      }
      
      // Locate the leftmost of the two right endpoints of the two curves.
      // Note that we guard for curves with infinite ends.
      const X_monotone_curve_2 *cv_r;
      Boundary_type             inf_yr;

      inf_x1 = infinite_x (cv1, MAX_END);
      inf_x2 = infinite_x (cv2, MAX_END);

      if (inf_x1 != NO_BOUNDARY)
      {
        // If both curves are defined at x = +oo, they obviously overlap in
        // their x-ranges.
        if (inf_x2 != NO_BOUNDARY)
          return (true);

        // As cv2 is not defined at x = +oo, take its right end as the
        // leftmost.
        cv_r = &cv2;
        inf_yr = infinite_y (cv2, MAX_END);
      }
      else if (inf_x2 != NO_BOUNDARY)
      {
        // As cv1 is not defined at x = +oo, take its right end as the
        // leftmost.
        cv_r = &cv1;
        inf_yr = infinite_y (cv1, MAX_END);
      }
      else
      {
        // Compare the (finite) x-coordinates of the two right ends.
        inf_y1 = infinite_y (cv1, MAX_END);
        inf_y2 = infinite_y (cv2, MAX_END);

        if (inf_y1 == NO_BOUNDARY)
        {
          if (inf_y2 == NO_BOUNDARY)
          {
            res = compare_x (max_vertex (cv1), max_vertex (cv2));
          }
          else
          {
            res = compare_x (max_vertex (cv1), cv2, MAX_END);
           }
        }
        else
        {
          if (inf_y2 == NO_BOUNDARY)
          {
            res = compare_x (max_vertex (cv2), cv1, MAX_END);
            if (res != EQUAL)
              res = (res == SMALLER) ? LARGER : SMALLER;
          }
          else
          {
            res = compare_x (cv1, MAX_END, cv2, MAX_END);
          }