arr_traits_adaptor_2.h

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

        }

        if (res == SMALLER)
        {
          cv_r = &cv1;
          inf_yr = inf_y1;
        }
        else
        {
          cv_r = &cv2;
          inf_yr = inf_y2;
        }
      }
          
      // Now compare the (finite) x-coordiates of the left end of cv_l and
      // the right end of cv_r.
      if (inf_yl == NO_BOUNDARY)
      {
        if (inf_yr == NO_BOUNDARY)
        {
          res = compare_x (min_vertex (*cv_l), max_vertex (*cv_r));
        }
        else
        {
          res = compare_x (min_vertex (*cv_l), *cv_r, MAX_END);
        }
      }
      else
      {
        if (inf_yr == NO_BOUNDARY)
        {
          res = compare_x (max_vertex (*cv_r), *cv_l, MIN_END);
          if (res != EQUAL)
            res = (res == SMALLER) ? LARGER : SMALLER;
        }
        else
        {
          res = compare_x (*cv_l, MIN_END, *cv_r, MAX_END);
        }
      }

      // The two curves overlap in their x-range if and only if the left end
      // of cv_l is not to the right if the right end of cv_r.
      return (res != LARGER);
    }

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

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

  class Compare_y_position_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_position_2(const Self * self) : m_self(self) {}

    /*!
     * Get the relative of two x-monotone curves with overlapping x-ranges
     * that are disjoint in their interiors.
     * \param cv1 The first x-monotone curve.
     * \param cv2 The second x-monotone curve.
     * \pre The x-ranges of the two curves overlap.
     * \return SMALLER if cv1 lies below cv2;
     *         LARGER if cv1 lies above cv2;
     *         EQUAL in case the common x-range is a single point.
     */
    Comparison_result operator() (const X_monotone_curve_2& cv1,
                                  const X_monotone_curve_2& cv2) const
    {
      CGAL_precondition_code (
        Is_in_x_range_2  is_in_x_range = m_self->is_in_x_range_2_object();
      );
      CGAL_precondition (is_in_x_range (cv1, cv2));

      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_y_at_x_2        compare_y_at_x =
        m_self->compare_y_at_x_2_object();
      Construct_min_vertex_2  min_vertex =
        m_self->construct_min_vertex_2_object();
 
      // First check whether any of the curves is defined at x = -oo.
      const Boundary_type     inf_x1 = infinite_x (cv1, MIN_END);
      const Boundary_type     inf_x2 = infinite_x (cv2, MIN_END);
      Comparison_result       res;

      if (inf_x1 != NO_BOUNDARY)
      {
        if (inf_x2 != NO_BOUNDARY)
        {
          // Compare the relative position of the curve at x = -oo.
          return (compare_y_at_x (cv1, cv2, MIN_END));
        }
        
        // Check if the left end of cv2 lies at y = +/- oo.
        const Boundary_type    inf_y2 = infinite_y (cv2, MIN_END);

        if (inf_y2 == MINUS_INFINITY)
          return (LARGER);          // cv2 is obviously below cv1.
        else if (inf_y2 == PLUS_INFINITY)
          return (SMALLER);         // cv2 is obviously above cv1.
          
        // Compare the position of the left end of cv2 (which is a normal
        // point) to cv1.
        res = compare_y_at_x (min_vertex (cv2), cv1);

        // Swap the result.
        if (res == EQUAL)
          return (EQUAL);

        return ((res == SMALLER) ? LARGER : SMALLER);
      }
      else if (inf_x2 != NO_BOUNDARY)
      {
        // Check if the left end of cv1 lies at y = +/- oo.
        const Boundary_type    inf_y1 = infinite_y (cv1, MIN_END);

        if (inf_y1 == MINUS_INFINITY)
          return (SMALLER);         // cv1 is obviously below cv2.
        else if (inf_y1 == PLUS_INFINITY)
          return (LARGER);          // cv1 is obviously above cv2.

        // Compare the position of the left end of cv1 (which is a normal
        // point) to cv2.
        res = compare_y_at_x (min_vertex (cv1), cv2);

        return (res);
      }
      
      // Check if the left curve end lie at y = +/- oo.
      const Boundary_type     inf_y1 = infinite_y (cv1, MIN_END);
      const Boundary_type     inf_y2 = infinite_y (cv2, MIN_END);
      Comparison_result       l_res;

      if (inf_y1 != NO_BOUNDARY)
      {
        if (inf_y2 != NO_BOUNDARY)
        {
          // If one curve has a left end at y = -oo and the other at y = +oo,
          // we readily know their relative position (recall that they do not
          // instersect).
          if (inf_y1 == MINUS_INFINITY && inf_y2 == PLUS_INFINITY)
            return (SMALLER);
          else if (inf_y1 == PLUS_INFINITY && inf_y2 == MINUS_INFINITY)
            return (LARGER);

          // Both curves have vertical asymptotes at y = -oo (or at y = +oo).
          // Check which asymptote is the rightmost. Note that in this case
          // the vertical asymptotes cannot be equal.
          l_res = m_self->compare_x_2_object() (cv1, MIN_END,
                                                cv2, MIN_END);
          CGAL_assertion (l_res != EQUAL);

          if (inf_y1 == PLUS_INFINITY)
            return (l_res);
          else
            return ((l_res == SMALLER) ? LARGER : SMALLER);
        }

        // cv1 has a vertical asymptote and cv2 has a normal left endpoint.
        // Compare the x-positions of this endpoint and the asymptote.
        const Point_2&  left2 = min_vertex(cv2);
        
        l_res = m_self->compare_x_2_object() (left2, cv1, MIN_END);

        if (l_res == LARGER)
        {
          // left2 lies in the x-range of cv1, so it is safe to compare:
          res = compare_y_at_x (left2, cv1);

          // Swap the result.
          if (res == EQUAL)
            return (EQUAL);

          return ((res == SMALLER) ? LARGER : SMALLER);
        }
        else
        {
          if (inf_y1 == MINUS_INFINITY)
            return (SMALLER);          // cv1 is obviously below cv2.
          else
            return (LARGER);           // cv2 is obviously above cv1.
        }
      }
      else if (inf_y2 != NO_BOUNDARY)
      {
        // cv2 has a vertical asymptote and cv1 has a normal left endpoint.
        // Compare the x-positions of this endpoint and the asymptote.
        const Point_2&  left1 = min_vertex(cv1);
        
        l_res = m_self->compare_x_2_object() (left1, cv2, MIN_END);

        if (l_res == LARGER)
        {
          // left1 lies in the x-range of cv2, so it is safe to compare:
          return (compare_y_at_x (left1, cv2));
        }
        else
        {
          if (inf_y2 == MINUS_INFINITY)
            return (LARGER);           // cv2 is obviously below cv1.
          else
            return (SMALLER);          // cv1 is obviously above cv2.
        }
      }

      // In this case we compare two normal points.
      Compare_xy_2            compare_xy = m_self->compare_xy_2_object();
      Compare_y_at_x_right_2  compare_y_at_x_right =
        m_self->compare_y_at_x_right_2_object();

      // Get the left endpoints of cv1 and cv2.
      const Point_2&  left1 = min_vertex(cv1);
      const Point_2&  left2 = min_vertex(cv2);

      // Locate the rightmost point of left1 and left2 and compare its position
      // to the other curve.
      l_res = compare_xy (left1, left2);

      if (l_res != SMALLER)
      {
        // left1 is in the x-range of cv2:
        res = compare_y_at_x (left1, cv2);

        if (res == EQUAL)
        {
          // The two curves intersect at left1. If both curves are defined to
          // the right of the reference point, we can compare them to its 
          // right. Otherwise, their share a common endpoint (which is the only
          // overlap in their x-ranges) and are really equal.
          if (l_res == EQUAL)
            res = compare_y_at_x_right (cv1, cv2, left1);
        }

        return (res);
      }
      else
      {
        // left2 is in the x-range of cv1:
        res = compare_y_at_x (left2, cv1);

        if (res == EQUAL)
        {
          // The two curves share a common endpoint (which is the only overlap
          // in their x-ranges) and are really equal.
          return (EQUAL);
        }

        // Swap the result:
        return ((res == SMALLER) ? LARGER : SMALLER);
      }
    }

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

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

  class Is_between_cw_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_between_cw_2(const Self * self) : m_self(self) {}

    /*!
     * Check whether the given query curve is encountered when rotating the
     * first curve in a clockwise direction around a given point until reaching
     * the second curve.
     * \param cv The query curve.
     * \param cv_to_right Is cv directed from left to right (that is, the
     *                    common vertex is cv's left 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 point around which we rotate cv1.
     * \param cv_equal_cv1 Output: does cv equal cv1.
     * \param cv_equal_cv2 Output: does cv equal cv2.
     * \pre p is an end-point of all three curves.
     * \return (true) if cv is between cv1 and cv2; (false) otherwise.
     *         If cv overlaps cv1 or cv2 the result is always (false).
     *         If cv1 and cv2 overlap, the result is (true), unless cv 
     *         also overlaps them.
     */
    bool operator() (const X_monotone_curve_2& cv, bool cv_to_right,
                     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& cv_equal_cv1, 
                     bool& cv_equal_cv2) const
    {
      Compare_y_at_x_left_2   compare_y_at_x_left =
        m_self->compare_y_at_x_left_2_object();
      Compare_y_at_x_right_2  compare_y_at_x_right =
        m_self->compare_y_at_x_right_2_object();

      // Initialize output flags.
      cv_equal_cv1 = false;
      cv_equal_cv2 = false;
    
      // Take care of the general 4 cases:
      Comparison_result  l_res, r_res;
      Comparison_result  res1, res2;
    
      if (!cv1_to_right && !cv2_to_right)
      {
        // Case 1: Both cv1 and cv2 are defined to the left of p.
        l_res = compare_y_at_x_left (cv1, cv2, p);
      
        if (l_res == LARGER)
        {
          // Case 1(a) : cv1 is above cv2.
          if (!cv_to_right)
          {
            res1 = compare_y_at_x_left (cv1, cv, p);
            res2 = compare_y_at_x_left (cv2, cv, p);
          
            if (res1 == EQUAL)
              cv_equal_cv1 = true;
            if (res2 == EQUAL)
              cv_equal_cv2 = true;
          
            return (res1 == SMALLER || res2 == LARGER);
          }
          return (true);
        }
        else if (l_res == SMALLER)
        {
          // Case 1(b): cv1 is below cv2.
          if (!cv_to_right)
          {
            res1 = compare_y_at_x_left (cv1, cv, p);
            res2 = compare_y_at_x_left (cv2, cv, p);
          
            if (res1 == EQUAL)
              cv_equal_cv1 = true;
            if (res2 == EQUAL)
              cv_equal_cv2 = true;
          
            return (res1 == SMALLER && res2  == LARGER);
          }
          return (false);
        }
        else
        {
          // Overlapping segments.
          if (!cv_to_right)
          {
            res1 = compare_y_at_x_left (cv1, cv, p);
            if (res1 == EQUAL)
            {
              cv_equal_cv1 = true;
              cv_equal_cv2 = true;
              return (false);