bezier_x_monotone_2.h

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

    can_refine = ! _ps.is_exact();
    do
    {
      const Rat_point_2&  ps = _curve (ps_org->point_bound().t_max);

      if ((_dir_right && CGAL::compare (ps.x(), x_min) != LARGER) ||
          (! _dir_right && CGAL::compare (ps.x(), x_max) != SMALLER))
        break;

      if (can_refine)
        can_refine = _ps.refine();
    } while (can_refine);

    // Examine the parameter range of the originator of the target point
    // with respect to the current subcurve B, and make sure that B(t_min)
    // lies to the right of p if the curve is directed from left to right
    // (or to the left of p, if the subcurve is directed from right to left).
    can_refine = ! _pt.is_exact();
    do
    {
      const Rat_point_2&  pt = _curve (pt_org->point_bound().t_min);

      if ((_dir_right && CGAL::compare (pt.x(), x_max) != SMALLER) ||
          (! _dir_right && CGAL::compare (pt.x(), x_min) != LARGER))
        break;

      if (can_refine)
        can_refine = _pt.refine();
    } while (can_refine);

    // In this case the parameter value of the source is smaller than the
    // target's, so we compare the point with the subcurve of B defined over
    // the proper parameter range.
    res_bound = p.vertical_position (cp,
                                     ps_org->point_bound().t_max,
                                     pt_org->point_bound().t_min);
  }
  else if (CGAL::compare (pt_org->point_bound().t_max,
                          ps_org->point_bound().t_min) == SMALLER)
  {
    // Examine the parameter range of the originator of the source point
    // with respect to the current subcurve B, and make sure that B(t_min)
    // lies to the left of p if the curve is directed from left to right
    // (or to the right of p, if the subcurve is directed from right to left).
    can_refine = ! _ps.is_exact();
    do
    {
      const Rat_point_2&  ps = _curve (ps_org->point_bound().t_min);

      if ((_dir_right && CGAL::compare (ps.x(), x_min) != LARGER) ||
          (! _dir_right && CGAL::compare (ps.x(), x_max) != SMALLER))
        break;

      if (can_refine)
        can_refine = _ps.refine();
    } while (can_refine);

    // Examine the parameter range of the originator of the target point
    // with respect to the current subcurve B, and make sure that B(t_max)
    // lies to the right of p if the curve is directed from left to right
    // (or to the left of p, if the subcurve is directed from right to left).
    can_refine = ! _pt.is_exact();
    do
    {
      const Rat_point_2&  pt = _curve (pt_org->point_bound().t_max);

      if ((_dir_right && CGAL::compare (pt.x(), x_max) != SMALLER) ||
          (! _dir_right && CGAL::compare (pt.x(), x_min) != LARGER))
        break;

      if (can_refine)
        can_refine = _pt.refine();
    } while (can_refine);

    // In this case the parameter value of the source is large than the
    // target's, so we compare the point with the subcurve of B defined over
    // the proper parameter range.
    res_bound = p.vertical_position (cp,
                                     pt_org->point_bound().t_max,
                                     ps_org->point_bound().t_min);
  }

  if (res_bound != EQUAL)
    return (res_bound);
 
  // In this case we have to switch to exact computations and check whether
  // p lies of the given subcurve. We take one of p's originating curves and
  // compute its intersections with our x-monotone curve.
  if (! p.is_exact())
    p.make_exact (cache);

  CGAL_assertion (p.originators_begin() != p.originators_end());
    
  // Iddo: If the point is a rational point (e.g., ray shooting)
  //       use comparison between Y(root_of(X0-X(t))) and Y0.
  Originator   org = *(p.originators_begin());
  bool         do_ovlp;
  bool         swap_order = (_curve.id() > org.curve().id());
  const Intersect_list&  inter_list = (! swap_order ?
    (cache.get_intersections (_curve.id(),
                              _curve.x_polynomial(), _curve.x_norm(),
                              _curve.y_polynomial(), _curve.y_norm(),
                              org.curve().id(),
                              org.curve().x_polynomial(), org.curve().x_norm(),
                              org.curve().y_polynomial(), org.curve().y_norm(),
                              do_ovlp)) :
    (cache.get_intersections (org.curve().id(),
                              org.curve().x_polynomial(), org.curve().x_norm(),
                              org.curve().y_polynomial(), org.curve().y_norm(),
                              _curve.id(),
                              _curve.x_polynomial(), _curve.x_norm(),
                              _curve.y_polynomial(), _curve.y_norm(),
                              do_ovlp)));

  if (do_ovlp)
    return (EQUAL);
    
  // Go over the intersection points and look for p there.
  Intersect_iter       iit;
    
  for (iit = inter_list.begin(); iit != inter_list.end(); ++iit)
  {
    // Get the parameter of the originator and compare it to p's parameter.
    const Algebraic&  s = swap_order ? iit->s : iit->t;
      
    if (CGAL::compare (s, org.parameter()) == EQUAL)
    {
      // Add this curve as an originator for p.
      const Algebraic&  t = swap_order ? iit->t : iit->s;
    
      CGAL_assertion (_is_in_range (t, cache));

      Point_2&  pt = const_cast<Point_2&> (p);
      pt.add_originator (Originator (_curve, t));

      // The point p lies on the subcurve.
      return (EQUAL);
    }
  }
  
  // We now that p is not on the subcurve. We therefore subdivide the curve
  // using exact rational arithmetic, until we reach a separation between the
  // curve and the point. (This case should be very rare.)
  // Note that we first try to work with inexact endpoint representation, and
  // only if we fail we make the endpoints of the x-monotone curves exact.
  if (! p.is_exact())
    p.make_exact (cache);

  Comparison_result  exact_res = _exact_vertical_position (p, false);

  if (exact_res != EQUAL)
    return (exact_res);

  if (! _ps.is_exact())
    _ps.make_exact (cache);
  
  if (! _pt.is_exact())
    _pt.make_exact (cache);

  return (_exact_vertical_position (p, true));
}

// ---------------------------------------------------------------------------
// Compare the relative y-position of two x-monotone subcurves to the right
// of their intersection point.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
Comparison_result
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::compare_to_right
        (const Self& cv,
         const Point_2& p,
         Bezier_cache& cache) const
{
  CGAL_precondition (p.compare_xy (right(), cache) != LARGER);
  CGAL_precondition (p.compare_xy (cv.right(), cache) != LARGER);
  
  if (this == &cv)
    return (EQUAL);
  
  // Make sure that p is incident to both curves (either equals the left
  // endpoint or lies in the curve interior). Note that this is important to
  // carry out these tests, as it assures us the eventually both curves are
  // originators of p.
  if (! p.equals (left(), cache))
  {
    if (point_position (p, cache) != EQUAL)
    {
      CGAL_precondition_msg (false, "p is not on cv1");
    }
  }
  
  if (! p.equals (cv.left(), cache))
  {
    if (cv.point_position (p, cache) != EQUAL)
    {
      CGAL_precondition_msg (false, "p is not on cv2");
    }
  }

  // Check for vertical subcurves. A vertical segment is above any other
  // x-monotone subcurve to the right of their common endpoint.
  if (is_vertical())
  {
    if (cv.is_vertical())
      // Both are vertical segments with a common endpoint, so they overlap:
      return (EQUAL);
    
    return (LARGER);
  }
  else if (cv.is_vertical())
  {
    return (SMALLER);
  }
    
  // Check if both subcurves originate from the same Bezier curve.
  Nt_traits       nt_traits;

  if (_curve.is_same (cv._curve))
  {
    // Get the originator, and make sure that p is a vertical tangency
    // point of this originator.
    Originator_iterator  org = p.get_originator(_curve);
    
    CGAL_assertion (org != p.originators_end());    
    CGAL_assertion (_inc_to_right != cv._inc_to_right);
    
    if (! p.is_exact())
    {
      CGAL_assertion (org->point_bound().point_type ==
                      Bez_point_bound::VERTICAL_TANGENCY_PT);

      // Comparison based on the control polygon of the bounded vertical
      // tangency point, using the fact this polygon is y-monotone.
      const typename Bounding_traits::Control_point_vec& cp = 
        org->point_bound().bounding_polyline;
      
      if (_inc_to_right)
      {
        return (CGAL::compare (cp.back().y(), cp.front().y()));
      }
      else
      {
        return (CGAL::compare (cp.front().y(), cp.back().y()));
      }
    }
    
    // Iddo: Handle rational points (using de Casteljau derivative)?
    
    // In this case we know that we have a vertical tangency at t0, so
    // X'(t0) = 0. We evaluate the sign of Y'(t0) in order to find the
    // vertical position of the two subcurves to the right of this point.
    CGAL_assertion (org->has_parameter());
    
    const Algebraic&  t0 = org->parameter();
    Polynomial        polyY_der = nt_traits.derive (_curve.y_polynomial());
    const CGAL::Sign  sign_der =
      CGAL::sign (nt_traits.evaluate_at (polyY_der, t0));
    
    CGAL_assertion (sign_der != CGAL::ZERO);
    
    if (_inc_to_right)
      return ((sign_der == CGAL::POSITIVE) ? LARGER : SMALLER);
    else
      return ((sign_der == CGAL::NEGATIVE) ? LARGER : SMALLER);
  }
  
  // Compare the slopes of the two supporting curves at p. In the general
  // case, the slopes are not equal and their comparison gives us the
  // vertical order to p's right. 
  Comparison_result   slope_res = _compare_slopes (cv, p);
  
  if (slope_res != EQUAL)
    return (slope_res);

  // Compare the two subcurves by choosing some point to the right of p
  // and comparing the vertical position there.
  Comparison_result   right_res;
  
  if (right().compare_x (cv.right(), cache) != LARGER)
  {
    right_res = _compare_to_side (cv, p,
                                  true,           // Compare to p's right.
                                  cache);
  }
  else
  {
    right_res = cv._compare_to_side (*this, p,
                                     true,        // Compare to p's right.
                                     cache);
    
    right_res = CGAL::opposite (right_res);
  }
  
  return (right_res);
}

// ---------------------------------------------------------------------------
// Compare the relative y-position of two x-monotone subcurve to the left
// of their intersection point.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
Comparison_result
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::compare_to_left
        (const Self& cv,
         const Point_2& p,
         Bezier_cache& cache) const
{
  CGAL_precondition (p.compare_xy (left(), cache) != SMALLER);
  CGAL_precondition (p.compare_xy (cv.left(), cache) != SMALLER);
  
  if (this == &cv)
    return (EQUAL);

  // Make sure that p is incident to both curves (either equals the right
  // endpoint or lies in the curve interior). Note that this is important to
  // carry out these tests, as it assures us the eventually both curves are
  // originators of p.
  if (! p.equals (right(), cache))
  {
    if (point_position (p, cache) != EQUAL)
    {
      CGAL_precondition_msg (false, "p is not on cv1");
    }
  }

  if (! p.equals (cv.right(), cache))
  {
    if (cv.point_position (p, cache) != EQUAL)
    {
      CGAL_precondition_msg (false, "p is not on cv2");
    }
  }
  
  // Check for vertical subcurves. A vertical segment is below any other
  // x-monotone subcurve to the left of their common endpoint.
  if (is_vertical())
  {
    if (cv.is_vertical())
      // Both are vertical segments with a common endpoint, so they overlap:
      return (EQUAL);
    
    return (SMALLER);
  }
  else if (cv.is_vertical())
  {
    return (LARGER);
  }
    
  // Check if both subcurves originate from the same Bezier curve.
  Nt_traits       nt_traits;

  if (_curve.is_same (cv._curve))
  {
    // Get the originator, and make sure that p is a vertical tangency
    // point of this originator.
    Originator_iterator  org = p.get_originator(_curve);
    
    CGAL_assertion (org != p.originators_end());    
    CGAL_assertion (_inc_to_right != cv._inc_to_right);
    
    if (! p.is_exact())
    {
      CGAL_assertion (org->point_bound().point_type ==
                      Bez_point_bound::VERTICAL_TANGENCY_PT);

      // Comparison based on the control polygon of the bounded vertical
      // tangency point, using the fact this polygon is y-monotone.
      const typename Bounding_traits::Control_point_vec& cp = 
        org->point_bound().bounding_polyline;
      
      if (_inc_to_right)
      {
        return (CGAL::compare(cp.front().y(), cp.back().y()));
      }
      else
      {
        return (CGAL::compare(cp.back().y(), cp.front().y()));
      }
    }
    
    // Iddo: Handle rational points (using de Casteljau derivative)?