bezier_x_monotone_2.h

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

    {
      *oi = CGAL::make_object (*ip_it);
      ++oi;
    }
    return (oi);
  }

  /*!
   * Split the subcurve into two at a given split point.
   * \param p The split point.
   * \param c1 Output: The first resulting arc, lying to the left of p.
   * \param c2 Output: The first resulting arc, lying to the right of p.
   * \pre p lies in the interior of the subcurve (not one of its endpoints).
   */
  void split (const Point_2& p,
              Self& c1, Self& c2) const;

  /*!
   * Check if the two subcurves are mergeable.
   * \param cv The other subcurve.
   * \return Whether the two subcurves can be merged.
   */
  bool can_merge_with (const Self& cv) const;

  /*!
   * Merge the current arc with the given arc.
   * \param cv The other subcurve.
   * \pre The two arcs are mergeable.
   * \return The merged arc.
   */
  Self merge (const Self& cv) const;

  /*!
   * Flip the subcurve (swap its source and target points).
   * \return The flipped subcurve.
   */
  Self flip () const
  {
    // TODO: Is this "legal"? Should we touch the Bezier curve instead
    // so that _trg > _src in all cases?
    Self  cv = *this;

    cv._ps = this->_pt;
    cv._pt = this->_ps;
    cv._dir_right = ! this->_dir_right;

    return (cv);
  }

private:

  /*!
   * Check if the given t-value is in the range of the subcurve.
   * \param t The parameter value.
   * \param cache Caches the vertical tangency points and intersection points.
   * \return If t in the parameter-range of the subcurve.
   */
  bool _is_in_range (const Algebraic& t,
                     Bezier_cache& cache) const;

  /*!
   * Check if the given point lies in the range of this x-monotone subcurve.
   * \param p The point, which lies on the supporting Bezier curve.
   * \param is_certain Output: Is the answer we provide is certain.
   * \return Whether p is on the x-monotone subcurve.
   */
  bool _is_in_range (const Point_2& p, bool& is_certain) const;

  /*!
   * Compute a y-coordinate of a point on the x-monotone subcurve with a
   * given x-coordinate.
   * \param x0 The given x-coodinate.
   * \param cache Caches the vertical tangency points and intersection points.
   * \return The y-coordinate.
   */
  Algebraic _get_y (const Rational& x0,
                    Bezier_cache& cache) const;

  /*!
   * Compare the slopes of the subcurve with another given Bezier subcurve at
   * their given intersection point.
   * \param cv The other subcurve.
   * \param p The intersection point.
   * \pre p lies of both subcurves.
   * \pre Neither of the subcurves is a vertical segment.
   * \return SMALLER if (*this) slope is less than cv's;
   *         EQUAL if the two slopes are equal;
   *         LARGER if (*this) slope is greater than cv's.
   */
  Comparison_result _compare_slopes (const Self& cv,
                                     const Point_2& p) const;

  /*!
   * Get the range of t-value over which the subcurve is defined.
   * \param cache Caches the vertical tangency points and intersection points.
   * \return A pair comprised of the t-value for the source point and the
   *         t-value for the target point.
   */
  std::pair<Algebraic, Algebraic> _t_range (Bezier_cache& cache) const;

  /*!
   * Compare the relative y-position of two x-monotone subcurve to the right
   * (or to the left) of their intersection point, whose multiplicity is
   * greater than 1.
   * \param cv The other subcurve.
   * \param p The query point.
   * \param to_right Should we compare to p's right or to p's left.
   * \param cache Caches the vertical tangency points and intersection points.
   * \pre The x-coordinate of the right endpoint of *this is smaller than
   *      (or equal to) the x-coordinate of the right endpoint of cv.
   * \pre p is the common left endpoint of both subcurves.
   * \pre Neither of the subcurves is a vertical segment.
   * \return SMALLER if (*this) lies below cv to the right of p;
   *         EQUAL in case of an overlap (should not happen);
   *         LARGER if (*this) lies above cv to the right of p.
   */
  Comparison_result _compare_to_side (const Self& cv,
                                      const Point_2& p,
                                      bool to_right,
                                      Bezier_cache& cache) const;

  /*!
   * Approximate the intersection points between the two given curves.
   * \param B1 The first Bezier curve.
   * \param B2 The second Bezier curve.
   * \param inter_pts Output: An output list of intersection points.
   * \return Whether all intersection points where successfully approximated.
   */
  bool _approximate_intersection_points (const Curve_2& B1,
                                         const Curve_2& B2,
                                         std::list<Point_2>& inter_pts) const;

  /*!
   * Compute the intersections with the given subcurve.
   * \param cv The other subcurve.
   * \param inter_map Caches the bounded intersection points.
   * \param cache Caches the vertical tangency points and intersection points.
   * \param ipts Output: A vector of intersection points + multiplicities.
   * \param ovlp_cv Output: An overlapping subcurve (if exists).
   * \return Whether an overlap has occured.
   */
  bool _intersect (const Self& cv,
                   Intersection_map& inter_map,
                   Bezier_cache& cache,
                   std::vector<Intersection_point_2>& ipts,
                   Self& ovlp_cv) const;

  /*!
   * Compute the exact vertical position of the given point with respect to
   * the x-monotone curve.
   * \param p The point.
   * \param force_exact Sould we force an exact result.
   * \return SMALLER if the point is below the arc;
   *         LARGER if the point is above the arc;
   *         EQUAL if p lies on the arc.
   */
  Comparison_result _exact_vertical_position (const Point_2& p,
                                              bool force_exact) const;

};

/*!
 * Exporter for Bezier curves.
 */
template <class Rat_kernel, class Alg_kernel, class Nt_traits, 
          class Bounding_traits>
std::ostream& 
operator<< (std::ostream& os, 
            const _Bezier_x_monotone_2<Rat_kernel, Alg_kernel, Nt_traits, 
                                       Bounding_traits>& cv)
{
  os << cv.supporting_curve()
     << " | " << cv.source() 
     << " --> " << cv.target();

  return (os);
}

// ---------------------------------------------------------------------------
// Constructor given two endpoints.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::_Bezier_x_monotone_2
        (const Curve_2& B,
         const Point_2& ps, const Point_2& pt,
         Bezier_cache& cache) :
  _curve (B),
  _ps (ps),
  _pt (pt),
  _is_vert (false)
{
  // Get the originators of the point that correspond to the curve B.
  Originator_iterator   ps_org = ps.get_originator(B);
  CGAL_precondition (ps_org != ps.originators_end()); 
  
  Originator_iterator   pt_org = pt.get_originator(B);
  CGAL_precondition (pt_org != pt.originators_end());
  
  // Check if the subcurve is directed left or right.
  const Comparison_result    res = _ps.compare_x (_pt, cache);
  // Iddo: TODO - alternative check if the original curve is vertical,
  //       a check that can work on intervals.
  
  if (res == EQUAL)
  {
    // We have a vertical segment. Check if the source is below the target.
    _is_vert = true;
    // Iddo: TODO change the check to use compare_xy (or point bbox).
    _dir_right = (CGAL::compare (_ps.y(), _pt.y()) == SMALLER);
  }
  else
  {
    _dir_right = (res == SMALLER);
  }
  
  // Check if the value of the parameter t increases when we traverse the
  // curve from left to right: If the curve is directed to the right, we
  // check if t_src < t_trg, otherwise we check whether t_src > t_trg.
  Comparison_result      t_res;
  
  if (CGAL::compare (ps_org->point_bound().t_max,
                     pt_org->point_bound().t_min) == SMALLER ||
      CGAL::compare (ps_org->point_bound().t_min,
                     pt_org->point_bound().t_max) == LARGER)
  {
    // Perform the comparison assuming that the possible parameter
    // values do not overlap.
    t_res = CGAL::compare (ps_org->point_bound().t_min, 
                           pt_org->point_bound().t_min);
  }
  else
  {
    // In this case both exact parameter values must be known.
    // We use them to perform an exact comparison.
    CGAL_assertion (ps_org->has_parameter() && pt_org->has_parameter());
    
    t_res = CGAL::compare (ps_org->parameter(), pt_org->parameter());
  }
  
  CGAL_precondition (t_res != EQUAL);
  
  if (_dir_right)
    _inc_to_right = (t_res == SMALLER);
  else
    _inc_to_right = (t_res == LARGER);
}

// ---------------------------------------------------------------------------
// Get the approximate parameter range defining the curve.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
  std::pair<double, double> 
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::parameter_range () 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());

  double  t_src = (CGAL::to_double (s_org->point_bound().t_min) +
                   CGAL::to_double (s_org->point_bound().t_max)) / 2;
  double  t_trg = (CGAL::to_double (t_org->point_bound().t_min) +
                   CGAL::to_double (t_org->point_bound().t_max)) / 2;

  return (std::make_pair (t_src, t_trg));
}

// ---------------------------------------------------------------------------
// Get the relative position of the query point with respect to the subcurve.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
Comparison_result
_Bezier_x_monotone_2<RatKer, AlgKer, NtTrt, BndTrt>::point_position
    (const Point_2& p,
     Bezier_cache& cache) const
{
  // First check whether p has the same x-coordinate as one of the endpoints.
  const Comparison_result  res1 = p.compare_x (_ps, cache);
  
  if (res1 == EQUAL)
  {
    // In this case both points must be exact.
    CGAL_assertion (p.is_exact() && _ps.is_exact());

    // If both point are rational, compare their rational y-coordinates.
    if (p.is_rational() && _ps.is_rational())
    {
      const Rat_point_2&  rat_p = (Rat_point_2) p;
      const Rat_point_2&  rat_ps = (Rat_point_2) _ps;

      return (CGAL::compare (rat_p.y(), rat_ps.y()));
    }

    // Compare the algebraic y-coordinates.
    return (CGAL::compare (p.y(), _ps.y()));
  }
  
  const Comparison_result  res2 = p.compare_x (_pt, cache);
  
  if (res2 == EQUAL)
  {
    // In this case both points must be exact.
    CGAL_assertion (p.is_exact() && _pt.is_exact());

    // If both point are rational, compare their rational y-coordinates.
    if (p.is_rational() && _pt.is_rational())
    {
      const Rat_point_2&  rat_p = (Rat_point_2) p;
      const Rat_point_2&  rat_pt = (Rat_point_2) _pt;

      return (CGAL::compare (rat_p.y(), rat_pt.y()));
    }

    // Compare the algebraic y-coordinates.
    return (CGAL::compare (p.y(), _pt.y()));
  }
  
  // Make sure that p is in the x-range of our subcurve.
  CGAL_precondition (res1 != res2);
  
  // Check for the case when curve is an originator of the point.
  Originator_iterator   p_org = p.get_originator(_curve);
 
  if (p_org != p.originators_end())
  {
    Originator_iterator      ps_org = _ps.get_originator(_curve);
    CGAL_assertion (ps_org != _ps.originators_end());
  
    Originator_iterator      pt_org = _pt.get_originator(_curve);
    CGAL_assertion (pt_org != _pt.originators_end());

    // Check if the point is in the parameter range of this subcurve.
    // First try an approximate check of the parameter bounds.
    bool  correct_res;
    bool  in_range = false;

    in_range = _is_in_range (p, correct_res);

    if (! correct_res)
    {
      // Perform the comparsion in an exact manner.
      if (! p.is_exact())
        p.make_exact (cache);

      CGAL_assertion (p_org->has_parameter());

      in_range = _is_in_range (p_org->parameter(), cache);
    }

    if (in_range)
      return (EQUAL);
  }
  
  // Call the vertical-position function that uses the bounding-boxes
  // to evaluate the comparsion result.
  typename Bounding_traits::Control_point_vec cp;

  std::copy (_curve.control_points_begin(), _curve.control_points_end(),
             std::back_inserter(cp));

  Originator_iterator           ps_org = _ps.get_originator(_curve);
  CGAL_assertion (ps_org != _ps.originators_end());
  
  Originator_iterator           pt_org = _pt.get_originator(_curve);
  CGAL_assertion (pt_org != _pt.originators_end());
  
  Comparison_result             res_bound = EQUAL;
  typename Bounding_traits::NT  x_min, y_min, x_max, y_max;
  bool                          can_refine;

  p.get_bbox (x_min, y_min, x_max, y_max);

  if (CGAL::compare (ps_org->point_bound().t_max,
                     pt_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_max)
    // 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).