bezier_x_monotone_2.h

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

    
    // 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::NEGATIVE) ? LARGER : SMALLER);
    else
      return ((sign_der == CGAL::POSITIVE) ? 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; note that we swap the order of the curves
  // to obtain their position to the left.
  Comparison_result   slope_res = cv._compare_slopes (*this, p);
  
  if (slope_res != EQUAL)
    return (slope_res);
  
  // Compare the two subcurves by choosing some point to the left of p
  // and compareing the vertical position there.
  Comparison_result   left_res;
  
  if (left().compare_x (cv.left(), cache) != SMALLER)
  {
    left_res = _compare_to_side (cv, p,
                                 false,          // Compare to p's left.
                                 cache);
  }
  else
  {
    left_res = cv._compare_to_side (*this, p,
                                    false,       // Compare to p's left.
                                    cache);
    left_res = CGAL::opposite (left_res);
  }
  
  return (left_res);
}

// ---------------------------------------------------------------------------
// Check whether the two subcurves are equal (have the same graph).
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
bool _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::equals
        (const Self& cv,
         Bezier_cache& cache) const
{
  // Check if the two subcurve have overlapping supporting curves.
  if (! _curve.is_same (cv._curve))
  {
    // Ron: For the time being, we do not deal with this case ...
    /*
    if (! _curve.has_same_support (cv._curve))
      return (false);
    
    // Mark that the two curves overlap.
    const Curve_id               id1 = _curve.id();
    const Curve_id               id2 = cv._curve.id();
    Curve_pair                   curve_pair;
    
    if (id1 < id2)
      curve_pair = Curve_pair (id1, id2);
    else
      curve_pair = Curve_pair (id2, id1);
    
    if (inter_map.find (curve_pair) == inter_map.end())
    {
      Intersection_info&  info = inter_map[curve_pair];
      info.second = true;
    }
    */
  }

  // Check for equality of the endpoints.
  return (left().equals (cv.left(), cache) &&
          right().equals (cv.right(), cache));
}

// ---------------------------------------------------------------------------
// Split the subcurve into two at a given split point.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
void _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::split
        (const Point_2& p,
         Self& c1, Self& c2) const
{
  CGAL_precondition (p.get_originator(_curve) != p.originators_end());

  // Duplicate the curve.
  c1 = c2 = *this;
    
  // Perform the split.
  if (_dir_right)
  {
    c1._pt = p;      
    c2._ps = p;
  }
  else
  {
    c1._ps = p;
    c2._pt = p;
  }
  
  return;
}

// ---------------------------------------------------------------------------
// Check if the two subcurves are mergeable.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
bool _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::can_merge_with
        (const Self& cv) const
{
  // Note that we only allow merging subcurves of the same originating
  // Bezier curve (overlapping curves will not do in this case).
  return (_curve.is_same (cv._curve) &&
          (right().is_same (cv.left()) || left().is_same (cv.right())));
  
  return (false);
}

// ---------------------------------------------------------------------------
// Merge the current arc with the given arc.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
typename _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::Self
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::merge
        (const Self& cv) const
{
  CGAL_precondition (_curve.is_same (cv._curve));
  
  Self    res = cv;
  
  if (right().is_same (cv.left()))
  {
    // Extend the subcurve to the right.
    if (_dir_right)
    {
      res._pt = cv.right();
    }
    else
    {
      res._ps = cv.right();
    }
  }
  else
  {
    CGAL_precondition (left().is_same (cv.right()));
    
    // Extend the subcurve to the left.
    if (_dir_right)
    {
      res._ps = cv.left();
    }
    else
    {
      res._pt = cv.left();
    }
  }

  return (res);
}

// ---------------------------------------------------------------------------
// Check if the given t-value is in the range of the subcurve.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
bool _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::_is_in_range
        (const Algebraic& t,
         Bezier_cache& cache) const
{
  // First try to use the approximate representation of the endpoints.
  Originator_iterator  s_org = _ps.get_originator (_curve);
  CGAL_assertion (s_org != _ps.originators_end());

  Originator_iterator  t_org = _pt.get_originator (_curve);
  CGAL_assertion (t_org != _pt.originators_end());

  bool  p_lt_ps = (CGAL::compare (t,
                                  Algebraic (s_org->point_bound().t_min)) == 
                   SMALLER);
  bool  p_gt_ps = (CGAL::compare (t,
                                  Algebraic (s_org->point_bound().t_max)) ==
                   LARGER);
  bool  p_lt_pt = (CGAL::compare (t,
                                  Algebraic (t_org->point_bound().t_min)) ==
                   SMALLER);
  bool  p_gt_pt = (CGAL::compare (t,
                                  Algebraic (t_org->point_bound().t_max)) ==
                   LARGER);

  if ((p_gt_ps && p_lt_pt) || (p_lt_ps && p_gt_pt))
  {
    // The point p is definately in the x-range of the subcurve, as its
    // parameter is between the source and target parameters.
    return (true);
  }
  
  if ((p_lt_ps && p_lt_pt) || (p_gt_ps && p_gt_pt))
  {
    // The point p is definately not in the x-range of the subcurve,
    // as its parameter is smaller than both source and target parameter
    // (or greater than both of them).
    return (false);
  }
  
  // Obtain the exact t-range of the curve and peform an exact comparison.
  std::pair<Algebraic, Algebraic> range = _t_range (cache);
  const Algebraic&                t_src = range.first;
  const Algebraic&                t_trg = range.second;
  
  const Comparison_result  res1 = CGAL::compare (t, t_src);
  const Comparison_result  res2 = CGAL::compare (t, t_trg);
  
  return (res1 == EQUAL || res2 == EQUAL || res1 != res2);
}

// ---------------------------------------------------------------------------
// Check if the given point lies in the range of this x-monotone subcurve.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
bool _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::_is_in_range
        (const Point_2& p,
         bool& is_certain) const
{
  is_certain = true;
  
  // Check the easy case that p is one of the subcurve endpoints.
  if (p.is_same(_ps) || p.is_same(_pt))
    return true;

  // Compare the parameter of p with the parameters of the endpoints.
  Originator_iterator  p_org = p.get_originator (_curve);
  CGAL_assertion (p_org != p.originators_end());
  
  Originator_iterator  s_org = _ps.get_originator (_curve);
  CGAL_assertion (s_org != _ps.originators_end());
  
  Originator_iterator  t_org = _pt.get_originator (_curve);
  CGAL_assertion (t_org != _pt.originators_end());
  
  bool      can_refine_p = ! p.is_exact();
  bool      can_refine_s = ! _ps.is_exact();
  bool      can_refine_t = ! _pt.is_exact();
  
  while (can_refine_p || can_refine_s || can_refine_t)
  {
    bool  p_lt_ps = (CGAL::compare (p_org->point_bound().t_max,
                                    s_org->point_bound().t_min) == SMALLER);
    bool  p_gt_ps = (CGAL::compare (p_org->point_bound().t_min,
                                    s_org->point_bound().t_max) == LARGER);
    bool  p_lt_pt = (CGAL::compare (p_org->point_bound().t_max,
                                    t_org->point_bound().t_min) == SMALLER);
    bool  p_gt_pt = (CGAL::compare (p_org->point_bound().t_min,
                                    t_org->point_bound().t_max) == LARGER);

    if ((p_gt_ps && p_lt_pt) || (p_lt_ps && p_gt_pt))
    {
      // The point p is definately in the x-range of the subcurve, as its
      // parameter is between the source and target parameters.
      return (true);
    }

    if ((p_lt_ps && p_lt_pt) || (p_gt_ps && p_gt_pt))
    {
      // The point p is definately not in the x-range of the subcurve,
      // as its parameter is smaller than both source and target parameter
      // (or greater than both of them).
      return (false);
    }
    
    // Try to refine the points.
    if (can_refine_p)
      can_refine_p = p.refine();
    
    if (can_refine_s)
      can_refine_s = _ps.refine();
    
    if (can_refine_t)
      can_refine_t = _pt.refine();
  }

  // If we reached here, we do not have a certain answer.
  is_certain = false;
  return (false);
}

// ---------------------------------------------------------------------------
// Compute a y-coordinate of a point on the x-monotone subcurve with a
// given x-coordinate.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
typename _Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::Algebraic
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::_get_y
        (const Rational& x0,
         Bezier_cache& cache) const
{
  // Obtain the t-values for with the x-coordinates of the supporting
  // curve equal x0.
  std::list<Algebraic>  t_vals;
  
  _curve.get_t_at_x (x0, std::back_inserter(t_vals));
  
  // Find a t-value that is in the range of the current curve.
  Nt_traits                                nt_traits;
  typename std::list<Algebraic>::iterator  t_iter;
  std::pair<Algebraic, Algebraic>          t_range = _t_range (cache);
  const Algebraic&                         t_src = t_range.first;
  const Algebraic&                         t_trg = t_range.second;
  Comparison_result                        res1, res2;
  
  for (t_iter = t_vals.begin(); t_iter != t_vals.end(); ++t_iter)
  {
    res1 = CGAL::compare (*t_iter, t_src);
    
    if (res1 == EQUAL)
    {
      // Return the y-coordinate of the source point:
      return (_ps.y());
    }
    
    res2 = CGAL::compare (*t_iter, t_trg);
    
    if (res2 == EQUAL)
    {
      // Return the y-coordinate of the source point:
      return (_pt.y());
    }

    if (res1 != res2)
    {
      // We found a t-value in the range of our x-monotone subcurve.
      // Use this value to compute the y-coordinate.
      return (nt_traits.evaluate_at (_curve.y_polynomial(), *t_iter) /
              nt_traits.convert (_curve.y_norm()));
    }
  }
  
  // If we reached here, x0 is not in the x-range of our subcurve.
  CGAL_assertion (false);
  return (0);
}

// ---------------------------------------------------------------------------
// Compare the slopes of the subcurve with another given Bezier subcurve at
// their given intersection point.
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
Comparison_result
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::_compare_slopes
        (const Self& cv,
         const Point_2& p) const
{
  // Get the originators of p.
  Originator_iterator     org1 = p.get_originator (_curve);
  CGAL_assertion (org1 != p.originators_end());

  Originator_iterator     org2 = p.get_originator (cv._curve);
  CGAL_assertion (org2 != p.originators_end());
  
  // If the point is only approximated, we can carry out a comparison using
  // an approximate number type.
  if (! p.is_exact())
  {
    // If the point is inexact, we assume it is a bounded intersection
    // point of two curves, and therefore the bounding angle these curves
    // span do not overlap.
    const Bez_point_bound&  bound1 = org1->point_bound();
    const Bez_point_bound&  bound2 = org2->point_bound();
    Bounding_traits         bound_tr;
    
    return (bound_tr.compare_slopes_of_bounded_intersection_point (bound1,