bezier_point_2.h

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

  typedef typename Bpt_rep::Rat_point_2           Rat_point_2;
  typedef typename Bpt_rep::Alg_point_2           Alg_point_2;
  typedef typename Bpt_rep::Rational              Rational;
  typedef typename Bpt_rep::Algebraic             Algebraic;
  typedef typename Bpt_rep::Curve_2               Curve_2;
  typedef typename Bpt_rep::Originator            Originator;
  typedef typename Bpt_rep::Bezier_cache          Bezier_cache;

  typedef typename Bpt_rep::Orig_const_iter       Originator_iterator;
  typedef typename Bpt_rep::Bez_point_bound       Bez_point_bound;
  typedef typename Bpt_rep::Bez_point_bbox        Bez_point_bbox;

  /*!
   * Default constructor.
   */
  _Bezier_point_2 () :
    Bpt_handle (Bpt_rep())
  {}

  /*!
   * Copy constructor.
   */
  _Bezier_point_2 (const Self& bpt) :
    Bpt_handle (bpt)
  {}

  /*!
   * Constructor with coordinates.
   */
  _Bezier_point_2 (const Algebraic& x, const Algebraic& y) :
    Bpt_handle (Bpt_rep (x, y))
  {}

  /*!
   * Constructor given an originating curve and a rational t0 value.
   * \pre t0 must be between 0 and 1.
   */
  _Bezier_point_2 (const Curve_2& B, const Rational& t0) :
    Bpt_handle (Bpt_rep (B, t0))
  {}

  /*!
   * Constructor given an originating curve and an algebraic t0 value.
   * \pre t0 must be between 0 and 1.
   */
  _Bezier_point_2 (const Curve_2& B, const Algebraic& t0) :
    Bpt_handle (Bpt_rep (B, t0))
  {}

  /*!
   * Assignment operator.
   */
  Self& operator= (const Self& pt)
  {
    if (this == &pt || this->identical (pt))
      return (*this);

    Bpt_handle::operator= (pt);
    return (*this);
  }

  /*!
   * Check if the two handles refer to the same object.
   */
  bool is_same (const Self& pt) const
  {
    return (this->identical (pt));
  }

  /*!
   * Check if the point is computed in an exact manner.
   */
  bool is_exact () const
  {
    return (_rep().is_exact());
  }

  /*!
   * Check if the point has rational coordinates.
   */
  bool is_rational () const
  {
    return (_rep().is_rational());
  }

  /*!
   * Get the x-coordinate.
   * \pre The point is exactly computed.
   */
  const Algebraic& x () const
  {
    CGAL_precondition (_rep().is_exact());
    return (*(_rep().p_alg_x));
  }

  /*!
   * Get the y-coordinate.
   * \pre The point is exactly computed.
   */
  const Algebraic& y () const
  {
    CGAL_precondition (_rep().is_exact());
    return (*(_rep().p_alg_y));
  }

  /*!
   * Get the approximate coordinates.
   */
  std::pair<double, double> approximate () const
  {
    double      x, y;

    if (is_exact())
    {
      x = CGAL::to_double (*(_rep().p_alg_x));
      y = CGAL::to_double (*(_rep().p_alg_y));
    }
    else
    {
      x = CGAL::to_double ((_rep()._bbox.min_x + _rep()._bbox.max_x) / 2);
      y = CGAL::to_double ((_rep()._bbox.min_y + _rep()._bbox.max_y) / 2);
    }

    return (std::make_pair (x, y));
  }

  /*!
   * Convert to a rational point.
   * \pre The point has rational coordinates.
   */
  operator Rat_point_2 () const
  {
    CGAL_precondition (_rep().is_rational());
    
    return (Rat_point_2 (*(_rep().p_rat_x), *(_rep().p_rat_y)));
  }

  /*!
   * Refine the representation of the point.
   * \return Whether a refinement was possible.
   */
  bool refine () const
  {
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());
    
    return (rep._refine());
  }

  /*!
   * Compute the exact coordinates of the point.
   */
  void make_exact (Bezier_cache& cache) const
  {
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());

    rep._make_exact (cache);
    return;
  }

  /*!
   * Compare the x-coordinate with the coordinate of the given point.
   * \param pt The other point.
   * \param cache A cache for the vertical tangency points and the
   *              intersection points.
   * \return The comparison result;
   */
  Comparison_result compare_x (const Self& pt,
                               Bezier_cache& cache) const 
  {
    if (this->identical (pt))
      return (EQUAL);

    // Const cast since we are modifying the reps.
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());
    Bpt_rep&             rep_pt = const_cast<Bpt_rep&> (pt._rep());

    return (rep.compare_x (rep_pt, cache));
  }

  /*!
   * Compare the the two points xy-lexicographically.
   * \param pt The other point.
   * \param cache A cache for the vertical tangency points and the
   *              intersection points.
   * \return The comparison result;
   */
  Comparison_result compare_xy (const Self& pt,
                                Bezier_cache& cache) const 
  {
    if (this->identical (pt))
      return EQUAL;

    Self&                p1 = const_cast<Self&> (*this);
    Self&                p2 = const_cast<Self&> (pt);
    Comparison_result    res = p1._rep().compare_xy (p2._rep(), cache);

    if (res == EQUAL)
    {
      // If we find that two points are equal, we merge their lists of
      // originators and make them refer to the same representation.
      p1.merge_originators (p2);
      p2 = p1;

      CGAL_assertion (this->identical (pt));
    }
      
    return (res);
  }

  /*!
   * Determine if the two points are equal. 
   */
  bool equals (const Self& pt,
               Bezier_cache& cache) const
  {
    return (this->compare_xy (pt, cache) == EQUAL);
  }

  /*!
   * Determines the vertical position of the point with respect to an
   * x-monotone subcurve, given by its control polygon.
   * \param cp The control polygon of the subcurve.
   * \param t_min Defines the smallest parameter value of the subcurve. 
   * \param t_max Defines the largest parameter value of the subcurve. 
   * \return SMALLER if the point is located below the curve;
   *         LARGER if the point is located above the curve;
   *         EQUAL if we cannot determine its precise position.
   */
  Comparison_result vertical_position
      (const typename Bounding_traits::Control_point_vec& cp,
       const typename Bounding_traits::NT& t_min,
       const typename Bounding_traits::NT& t_max) const
  {
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());
    return (rep.vertical_position(cp, t_min, t_max));
  }

  /*!
   * Get the originator of the point that is associates with the given curve.
   * \param B The Bezier curve.
   * \return An iterator pointing to the requested originator;
   *         or originators_end() if B is not an originator of the point.
   */
  // Iddo: this is a bit const-problematic since it should return
  //       const_iterator, currently Originator_iterator is typedefed to a
  //       const_iterator.
  //       (TODO - Originator_const_iterator and Originator_iterator)
  Originator_iterator get_originator(const Curve_2& B) const
  {
    // Scan the list of originators and look for B.
    typename Bpt_rep::Orig_const_iter     it = _rep()._origs.begin();
    typename Bpt_rep::Orig_const_iter     end = _rep()._origs.end();

    while (it != end)
    {
      if (B.is_same (it->curve()))
        break;
      ++it;
    }

    return it;
  }

  /*!
   * Get the range of originators.
   */
  Originator_iterator originators_begin () const
  {
    return (_rep()._origs.begin());
  }

  Originator_iterator originators_end () const
  {
    return (_rep()._origs.end());
  }

  /*!
   * Add an orinigator to the point.
   */
  void add_originator (const Originator& o) const
  {
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());

    rep._origs.push_back (o);
    return;
  }

  /*!
   * Add the originators of the given point.
   */
  void merge_originators (const Self& pt) const
  {
    Bpt_rep&             rep = const_cast<Bpt_rep&> (_rep());
    Originator_iterator  org_it = pt.originators_begin();

    while (org_it != pt.originators_end())
    {
      rep._origs.push_back (typename Bpt_rep::Originator (*org_it));
      ++org_it;
    }

    return;
  }

  // Iddo: workaround the ctr problems
  /*! Set the bounding box for the point. */
  void set_bbox (const Bez_point_bbox& bbox)
  {
    _rep()._bbox = bbox;
  }

  /*! Get the bounding box of the point. */
  void get_bbox (typename Bounding_traits::NT& min_x, 
                 typename Bounding_traits::NT& min_y, 
                 typename Bounding_traits::NT& max_x, 
                 typename Bounding_traits::NT& max_y) const
  {
    min_x = _rep()._bbox.min_x;
    min_y = _rep()._bbox.min_y;
    max_x = _rep()._bbox.max_x;
    max_y = _rep()._bbox.max_y;
  }

private:

  /*! Get the representation (const version). */
  inline const Bpt_rep& _rep () const
  {
    return (*(this->ptr()));
  }

  /*! Get the representation (non-const version). */
  inline Bpt_rep& _rep ()
  {
    return (*(this->ptr()));
  }

};

/*!
 * Exporter for Bezier points.
 */
template <class Rat_kernel, class Alg_kernel, class Nt_traits, 
          class Bounding_traits>
std::ostream& 
operator<< (std::ostream& os, 
            const _Bezier_point_2<Rat_kernel, Alg_kernel, Nt_traits,
                                  Bounding_traits> & pt)
{
  if (pt.is_exact())
  {
    os << CGAL::to_double (pt.x()) << ' ' << CGAL::to_double (pt.y());
  }
  else
  {
    typename Bounding_traits::NT   min_x, min_y, max_x, max_y;
    
    pt.get_bbox(min_x, min_y, max_x, max_y);
    os << '~' << CGAL::to_double ((min_x + max_x) / 2) 
       << " ~" << CGAL::to_double ((min_y + max_y) / 2);
  }

  return (os);
}

// ---------------------------------------------------------------------------
// Constructor given an originating curve and a rational t0 value.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
_Bezier_point_2_rep<RatKer, AlgKer, NtTrt, BndTrt>::_Bezier_point_2_rep
        (const Curve_2& B, const Rational& t0)
{
  // Insert an originator of a rational point.
  // Note that this constructor also takes care of the Bez_bound
  // for the originator.
  _origs.push_back (Originator(B, t0));

  // Evaluate the point coordinates.
  const Rat_point_2&  p = B (t0);
  Nt_traits           nt_traits;

  p_rat_x = new Rational (p.x());
  p_alg_x = new Algebraic (nt_traits.convert (*p_rat_x));
  p_rat_y = new Rational (p.y());
  p_alg_y = new Algebraic (nt_traits.convert (*p_rat_y));

  // Also set the bounding box for this point, by converting x, y
  // to two ranges of doubles.
  const std::pair<double, double>&  x_bnd = 
                                        nt_traits.double_interval (*p_alg_x);
  const std::pair<double, double>&  y_bnd = 
                                        nt_traits.double_interval (*p_alg_y);

  _bbox.min_x = x_bnd.first;
  _bbox.max_x = x_bnd.second;
  _bbox.min_y = y_bnd.first;
  _bbox.max_y = y_bnd.second;
}

// ---------------------------------------------------------------------------
// Constructor given an originating curve and an algebraic t0 value.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
_Bezier_point_2_rep<RatKer, AlgKer, NtTrt, BndTrt>::_Bezier_point_2_rep
        (const Curve_2& B, const Algebraic& t0) :
  p_rat_x (NULL),
  p_rat_y (NULL)
{
  // Create the originator pair <B(t), t0>.
  // Note that this constructor also takes care of the Bez_bound
  // for the originator.
  _origs.push_back (Originator (B, t0));

  // Set the point coordinates.
  const Alg_point_2   p = B (t0);
  
  p_alg_x = new Algebraic (p.x());
  p_alg_y = new Algebraic (p.y());
  
  // Also set the bounding box for this point, by converting x, y
  // to two ranges of doubles.
  Nt_traits                         nt_traits;
  const std::pair<double, double>&  x_bnd = 
                                        nt_traits.double_interval (*p_alg_x);
  const std::pair<double, double>&  y_bnd = 
                                        nt_traits.double_interval (*p_alg_y);

  _bbox.min_x = x_bnd.first;
  _bbox.max_x = x_bnd.second;
  _bbox.min_y = y_bnd.first;
  _bbox.max_y = y_bnd.second;
}

// ---------------------------------------------------------------------------
// Compare the x-coordinate to this of the given point.
//
template <class RatKer, class AlgKer, class NtTrt, class BndTrt>
Comparison_result
_Bezier_point_2_rep<RatKer, AlgKer, NtTrt, BndTrt>::compare_x
         (Self& pt,
          Bezier_cache& cache)
{
  // Handle rational points first.
  if (is_rational() && pt.is_rational())
  {
    return (CGAL::compare(*p_rat_x, *(pt.p_rat_x)));
  }