pm_traits_wrap_2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 633 行 · 第 1/2 页

      // Case 3: cv1 is defined to the left of p, and cv2 to its right.
      return ((dir == DIR_LEFT &&
	       curves_compare_y_at_x_left (cv1, cv, p) == SMALLER) ||
	      (dir == DIR_RIGHT &&
	       curves_compare_y_at_x_right (cv2, cv, p) == SMALLER) ||
	      dir == DIR_UP);
    }
    else
    {
      // Case 4: cv1 is defined to the right of p, and cv2 to its left.
      return ((dir == DIR_RIGHT &&
	       curves_compare_y_at_x_right (cv1, cv, p) == LARGER) ||
	      (dir == DIR_LEFT &&
	       curves_compare_y_at_x_left (cv2, cv, p) == LARGER) ||
	      dir == DIR_DOWN);
    }
  }

  /*! curves_compare_y_at_x_from_bottom()
   *
   * \precondition  cv1,cv2 are adjacent to q
   * \postcondition returns which of cv1,cv2 is first in clockwise sweep
   * around q starting from bottom direction.
   */
  Comparison_result 
  curves_compare_y_at_x_from_bottom(const X_monotone_curve_2 & cv1, 
				 const X_monotone_curve_2 & cv2, 
				 const Point_2 & q) const
  {
    if (!curve_is_vertical(cv1)) {
      if (!curve_is_vertical(cv2)) {
        if (point_equal(curve_rightmost(cv1),q))  
        {
          // cv1 extends leftwards from q
          if (point_equal(curve_rightmost(cv2),q))
          {
            // cv2 extends leftwards from q
            return curves_compare_y_at_x_left(cv1,cv2,q);
          }
          else // cv2 extends rightwards from q
          {
            return SMALLER;
          }
        }
        else  // cv1 extends rightwards from q
        {
          if (point_equal(curve_leftmost(cv2),q))
          {
            // cv2 extends rightwards from q
            return curves_compare_y_at_x_right(cv2,cv1,q);
          }
          else // cv2 extends leftwards from q
          {
            return LARGER;
          }
        }
      } else {
        // cv2 is vertical, cv1 is not vertical 
        if (point_equal(curve_rightmost(cv1),q) && 
          point_equal(curve_leftlow_most(cv2),   q))
          return SMALLER;
        else
          return LARGER;
      }
    } else {
      // cv1 is vertical
      if (point_equal(curve_righttop_most(cv1),q))
        if (!curve_is_vertical(cv2) || 
	    point_equal(curve_leftlow_most(cv2),q))
          return SMALLER;
        else
          return EQUAL; // both curves extend downwards
      else // cv1 extends from q upwards
        if (point_equal(curve_righttop_most(cv2),q))
          return LARGER;
        else if (!curve_is_vertical(cv2)) // extends rightwards
          return SMALLER;
        else // cv2 extends upwards
          return EQUAL;
    }
  }

  /*! curves_compare_y_at_x_from_top()
   */
  Comparison_result 
  curves_compare_y_at_x_from_top(const X_monotone_curve_2 & cv1, 
			      const X_monotone_curve_2 & cv2, 
			      const Point_2 & q)
    const 
  {
    if (!curve_is_vertical(cv1))
      if (!curve_is_vertical(cv2))
        if (point_equal(curve_rightmost(cv1),q)) 
        {
          // cv1 extends leftwards from q
          if (point_equal(curve_rightmost(cv2),q))
          {
            // cv2 extends leftwards from q
            return curves_compare_y_at_x_left(cv1,cv2,q);
          }
          else // cv2 extends rightwards from q
          {
            return LARGER;
          }
        }
        else  // cv1 extends rightwards from q
        {
          if (point_equal(curve_leftmost(cv2),q))
          {
            // cv2 extends rightwards from q
            return curves_compare_y_at_x_right(cv2,cv1,q);
          }
          else // cv2 extends leftwards from q
          {
            return SMALLER;
          }
        }
      else // cv2 is vertical, cv1 is not vertical 
      {
        if (point_equal(curve_leftmost(cv1),q) &&
          point_equal(curve_righttop_most(cv2), q))
          return SMALLER;
        else
          return LARGER;
      }
    else // cv1 is vertical
    {
      if (point_equal(curve_leftlow_most(cv1),q))
        if (!curve_is_vertical(cv2) || 
	    point_equal(curve_righttop_most(cv2),q))
          return SMALLER;
        else
          return EQUAL; // both curves extend upwards
      else // cv1 extends from q downwards
        if (point_equal(curve_leftlow_most(cv2),q))
          return LARGER;
        else if (!curve_is_vertical(cv2)) // extends leftwards
          return SMALLER;
        else // cv2 extends downwards
          return EQUAL;
    }
  }

  /*! curve_is_unbounded()
   */
  bool curve_is_unbounded(const X_monotone_curve_2 & cv) const 
  {
    return (curve_is_source_unbounded(cv)||
	    curve_is_target_unbounded(cv));
  }
    
  /*! curves_compare_y_at_x_left() 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 reflects the given point and curves about the origin, and calls the
   * "right" version.
   *
   * curves_compare_y_at_x_left() compares the y value of two curves in an
   * epsilon environment to the left of the x value of the input point
   *
   * \pre The point q is in the x range of the two curves, and both
   * of them must be also be defined to its left. The two curves must also
   * intersect at x(q).
   */
  Comparison_result curves_compare_y_at_x_left(const X_monotone_curve_2 & cv1,
                                            const X_monotone_curve_2 & cv2, 
                                            const Point_2 & q) const 
  {
    return curves_compare_y_at_x_left_imp(cv1, cv2, q, Has_left_category());
  }

  Comparison_result
  curves_compare_y_at_x_left_imp(const X_monotone_curve_2 & cv1,
                                 const X_monotone_curve_2 & cv2, 
                                 const Point_2 & q,
                                 Tag_true) const
  {
    //std::cout << "base left implementation " << std::endl;
    return Base::curves_compare_y_at_x_left(cv1, cv2, q);
  }
    
  // if the function is not implemented in the traits, 
  // call an inside implementation - if the reflect function is 
  // implemented - use it, otherwise, use other implementation
  Comparison_result
  curves_compare_y_at_x_left_imp(const X_monotone_curve_2 & cv1,
                                 const X_monotone_curve_2 & cv2, 
                                 const Point_2 & q,
                                 Tag_false) const 
  { 
    return curves_compare_y_at_x_left_imp(cv1, cv2, q, Tag_false(), 
					  Has_reflect_category());
  }

  //implement the function using reflect
  Comparison_result
  curves_compare_y_at_x_left_imp(const X_monotone_curve_2 & cv1,
                                 const X_monotone_curve_2 & cv2, 
                                 const Point_2 & q,
                                 Tag_false, Tag_true) const 
  {
    //std::cout << "reflect left implementation " << std::endl;
    Point_2 rq = point_reflect_in_x_and_y(q);
    X_monotone_curve_2 rcv1 = curve_reflect_in_x_and_y(cv1);
    X_monotone_curve_2 rcv2 = curve_reflect_in_x_and_y(cv2);
    Comparison_result cr = curves_compare_y_at_x_right(rcv1, rcv2, rq);
    if (cr == SMALLER) return LARGER;
    if (cr == LARGER) return SMALLER;
    return EQUAL;
  }

  //implement the function without reflect
  Comparison_result
  curves_compare_y_at_x_left_imp(const X_monotone_curve_2 & cv1,
                                 const X_monotone_curve_2 & cv2, 
                                 const Point_2 & q,
                                 Tag_false, Tag_false) const
  {  
    //std::cout << "Idit left implementation " << std::endl;

    // The two curves must not be vertical.
    CGAL_precondition(! curve_is_vertical(cv1));
    CGAL_precondition(! curve_is_vertical(cv2));

    // The two curve must be defined at q and also to its left.
    // Since the curves are continuous, if they are not equal at q, the same
    // result also applies to q's left.
    CGAL_precondition (point_equal(curve_rightmost(cv1),
				   curve_rightmost(cv2)));
 
    // <cv2> and <cv1> meet at a point with the same x-coordinate as q   
    CGAL_precondition (point_equal_x(curve_rightmost(cv1),q));
    
    // get the right-most endpoint between the left endpoints of cv1 and cv2
    Point_2 left1 = curve_leftmost(cv1);
    Point_2 left2 = curve_leftmost(cv2);
    const Point_2& pnt = point_rightmost(left1, left2);

    //if the two left endpoints are equal, we need to compare to the right 
    if (point_equal(left1,left2))
    {
      return curves_compare_y_at_x_right(cv1,cv2,pnt);
    }    
       
    //compare the y value of the left endpoint of the curves in the rightmost
    return curves_compare_y_at_x(cv1,cv2,pnt);
  }

protected:

  /*!
   * Enum used only be the curve_is_between_cw() function.
   */
  enum Curve_dir_at_point
  {
    DIR_UP,           // Vertical segment, point at 12 o'clock.
    DIR_RIGHT,        // Non-vertical segment going towards the right.
    DIR_DOWN,         // Vertical segment, point at 6 o'clock.
    DIR_LEFT          // Non-vertical segment going towards the left.
  };

  /*!
   * Return the curve direction, with respect to a given refernece point.
   * \param cv The curve.
   * \param p The reference point.
   * \pre p must be an end-point of the segment.
   * \return DIR_UP if cv is a vertical segment pointing at 12 o'clock;
   *         DIR_RIGHT if cv is a non-vertical curve going to the right of p;
   *         DIR_DOWN if cv is a vertical segment pointing at 6 o'clock;
   *         DIR_LEFT if cv is a non-vertical curve going to the left of p;
   */
  Curve_dir_at_point _curve_direction_at_point (const X_monotone_curve_2& cv,
						const Point_2& p) const
  {
    // p is one of the end-point. Compare it with the other end-point.
    Comparison_result res;

    if (curve_is_vertical(cv))
    {
      // Special treatment for vertical segments:
      res = compare_xy(p, curve_source(cv));

      if (res == EQUAL)
      {
	res = compare_xy(p, curve_target(cv));
      }
      else
      {
	// Make sure that p is indeed an end-point.
	CGAL_precondition(compare_xy(p, curve_target(cv)) == EQUAL);
      }

      return ((res == SMALLER) ? DIR_UP : DIR_DOWN);
    }

    // In case cv is not vertical:
    res = compare_x(p, curve_source(cv));

    if (res == EQUAL)
    {
      res = compare_x(p, curve_target(cv));
    }
    else
    {
      // Make sure that p is indeed an end-point.
      CGAL_precondition(compare_xy(p, curve_target(cv)) == EQUAL);
    }

    return ((res == SMALLER) ? DIR_RIGHT : DIR_LEFT);
  }
};

CGAL_END_NAMESPACE
 
#endif