bezier_curve_2.h

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

// Copyright (c) 2006  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Arrangement_2/include/CGAL/Arr_traits_2/Bezier_curve_2.h $
// $Id: Bezier_curve_2.h 39700 2007-08-06 09:26:35Z golubevs $
// 
//
// Author(s)     : Ron Wein     <[e-mail]>
//                 Iddo Hanniel <[e-mail]>

#ifndef CGAL_BEZIER_CURVE_2_H
#define CGAL_BEZIER_CURVE_2_H

/*! \file
 * Header file for the _Bezier_curve_2 class.
 */

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Handle_for.h>
#include <CGAL/Arr_traits_2/de_Casteljau_2.h>
#include <CGAL/Sweep_line_2_algorithms.h>

#include <algorithm>
#include <deque>
#include <vector>
#include <list>
#include <ostream>

CGAL_BEGIN_NAMESPACE

/*! \class _Bezier_curve_2
 * Representation of a Bezier curve, specified by (n+1) control points
 * p_0, ... , p_n that define the curve (X(t), Y(t)) for 0 <= t <= 1,
 * where X(t) and Y(t) are polynomials of degree n.
 *
 * The class is templated with three parameters: 
 * Rat_kernel A geometric kernel, where Alg_kernel::FT is the number type
 *            for the coordinates of control points (and subsequently also for
 *            the polynomial coefficients). This number type must be the same
 *            as Nt_traits::Rational.
 * Alg_kernel A geometric kernel, where Alg_kernel::FT is a number type
 *            for representing algebraic numbers. This number type must be the
 *            same as Nt_traits::Algebraic.
 * Nt_traits A traits class that defines the Integer, Rational and Algebraic
 *           number-types, as well as the Polynomial class (a polynomial with
 *           integer coefficients) and enables performing various operations
 *           on objects of these types.
 * Bounding_traits A traits class for filtering the exact computations.
 */

// Forward declaration:
template <class RatKernel_, class AlgKernel_, class NtTraits_,
          class BoundingTraits_>
class _Bezier_curve_2;

template <class RatKernel_, class AlgKernel_, class NtTraits_,
          class BoundingTraits_>
class _Bezier_curve_2_rep
{
  friend class _Bezier_curve_2<RatKernel_, AlgKernel_, NtTraits_,
                               BoundingTraits_>;

public:

  typedef RatKernel_                              Rat_kernel;
  typedef AlgKernel_                              Alg_kernel;
  typedef NtTraits_                               Nt_traits;
  typedef BoundingTraits_                         Bounding_traits;

  typedef typename Rat_kernel::Point_2            Rat_point_2;
  typedef typename Alg_kernel::Point_2            Alg_point_2;
  
  typedef typename Nt_traits::Integer             Integer;
  typedef typename Nt_traits::Rational            Rational;
  typedef typename Nt_traits::Algebraic           Algebraic;
  typedef typename Nt_traits::Polynomial          Polynomial;

private:

  typedef std::deque<Rat_point_2>                   Control_point_vec;

  Control_point_vec   _ctrl_pts;    // The control points (we prefer deque to
                                    // a vector, as it enables push_front()).
  Bbox_2              _bbox;        // A bounding box for the curve.

  /// \name Lazily-evaluated values of the polynomials B(t) = (X(t), Y(t)).
  //@{
 
  // X(t) is given by *p_polyX(t) / _normX:
  mutable Polynomial        *p_polyX;       // The polynomial for x.
  mutable Integer           *p_normX;       // Normalizing factor for y.

  // Y(t) is given by _polyY(t) / _normY:
  mutable Polynomial        *p_polyY;       // The polynomial for y.
  mutable Integer           *p_normY;       // Normalizing factor for y.
  //@}

public:

  /*! Default constructor. */
  _Bezier_curve_2_rep () : 
    p_polyX(NULL),
    p_normX(NULL),
    p_polyY(NULL),
    p_normY(NULL) 
  {}

  /*! Copy constructor (isn't really used). */
  _Bezier_curve_2_rep (const _Bezier_curve_2_rep& other) :
    _ctrl_pts(other._ctrl_pts),
    _bbox(other._bbox),
    p_polyX(NULL),
    p_normX(NULL),
    p_polyY(NULL),
    p_normY(NULL)
  {
    if (other.p_polyX != NULL)
      p_polyX = new Polynomial(*(other.p_polyX));
    if (other.p_polyY != NULL)
      p_polyY = new Polynomial(*(other.p_polyY));
    if (other.p_normX != NULL)
      p_normX = new Integer(*(other.p_normX));
    if (other.p_normY != NULL)
      p_normY = new Integer(*(other.p_normY));
  }

  /*!
   * Constructor from a given range of control points.
   * \param pts_begin An iterator pointing to the first point in the range.
   * \param pts_end A past-the-end iterator for the range.
   *        The value-type of the input iterators must be Rat_kernel::Point_2.
   * \pre There must be at least 2 control points, and the polyline defined
   *      by these points may not be self intersecting.
   */
  template <class InputIterator>
  _Bezier_curve_2_rep (InputIterator pts_begin, InputIterator pts_end) :
    p_polyX(NULL),
    p_normX(NULL),
    p_polyY(NULL),
    p_normY(NULL)
  {
    // Make sure that the control polyline is not self-intersecting.
    CGAL_expensive_precondition_code (
      Rat_kernel        ker;
      InputIterator     pt_curr = pts_begin;
      InputIterator     pt_next = pt_curr;
      std::list<typename Rat_kernel::Segment_2>  segs;

      ++pt_next;
      while (pt_next != pts_end)
      {
        segs.push_back (ker.construct_segment_2_object() (*pt_curr, *pt_next));
        pt_curr = pt_next;
        ++pt_next;
      }
    );
    CGAL_expensive_precondition_msg
        (! do_curves_intersect (segs.begin(), segs.end()),
         "The control polyline may be be self-intersecting.");

    // Copy the control points and compute their bounding box.
    const int   pts_size = std::distance (pts_begin, pts_end);
    double      x, y;
    double      x_min = 0, x_max = 0;
    double      y_min = 0, y_max = 0;
    int         k;

    CGAL_precondition_msg (pts_size > 1,
                           "There must be at least 2 control points.");

    _ctrl_pts.resize (pts_size);
    
    for (k = 0; pts_begin != pts_end; ++pts_begin, k++)
    {
      // Copy the current control point.
      _ctrl_pts[k] = *pts_begin;

      // Update the bounding box, if necessary.
      x = CGAL::to_double (pts_begin->x());
      y = CGAL::to_double (pts_begin->y());

      if (k == 0)
      {
        x_min = x_max = x;
        y_min = y_max = y;
      }
      else
      {
        if (x < x_min)
          x_min = x;
        else if (x > x_max)
          x_max = x;

        if (y < y_min)
          y_min = y;
        else if (y > y_max)
          y_max = y;
      }
    }

    // Construct the bounding box.
    _bbox = Bbox_2 (x_min, y_min, x_max, y_max);
  }

  /*! Destructor. */
  ~_Bezier_curve_2_rep ()
  {
    if (p_polyX != NULL) 
      delete p_polyX;
    if (p_normX != NULL) 
      delete p_normX;
    if (p_polyY != NULL) 
      delete p_polyY;
    if (p_normY != NULL) 
      delete p_normY;
  }

  /// \name Access the polynomials (lazily evaluated).
  //@{

  /*! Check if the polynomials are already constructed. */
  bool has_polynomials () const
  {
    return (p_polyX != NULL && p_normX != NULL &&
            p_polyY != NULL && p_normY != NULL);
  }

  /*! Get the polynomial X(t). */
  const Polynomial& x_polynomial () const 
  {
    if (p_polyX == NULL)
      _construct_polynomials ();
    
    return (*p_polyX);
  }

  /*! Get the normalizing factor for X(t). */
  const Integer& x_norm () const 
  {
    if (p_normX == NULL)
      _construct_polynomials ();
    
    return (*p_normX);
  }

  /*! Get the polynomial Y(t). */
  const Polynomial& y_polynomial () const 
  {
    if (p_polyY == NULL)
      _construct_polynomials ();

    return (*p_polyY);
  }

  /*! Get the normalizing factor for Y(t). */
  const Integer& y_norm () const 
  {
    if (p_normY == NULL)
      _construct_polynomials ();
    
    return (*p_normY);
  }
  //@}

private:

  /*!
   * Construct the representation of X(t) and Y(t).
   * The function is declared as "const" as it changes only mutable members.
   */
  void _construct_polynomials () const;

  /*!
   * Compute the value of n! / (j! k! (n-k-j)!).
   */
  Integer _choose (int n, int j, int k) const;

};

template <class RatKernel_, class AlgKernel_, class NtTraits_,
          class BoundingTraits_>
class _Bezier_curve_2 :
  public Handle_for<_Bezier_curve_2_rep<RatKernel_,
                                        AlgKernel_,
                                        NtTraits_,
                                        BoundingTraits_> >
{
public:

  typedef RatKernel_                              Rat_kernel;
  typedef AlgKernel_                              Alg_kernel;
  typedef NtTraits_                               Nt_traits;
  typedef BoundingTraits_                         Bounding_traits;
  typedef _Bezier_curve_2<Rat_kernel,
                          Alg_kernel,
                          Nt_traits,
                          Bounding_traits>        Self;

private:

  typedef _Bezier_curve_2_rep<Rat_kernel,
                              Alg_kernel,
                              Nt_traits,
                              Bounding_traits>    Bcv_rep;
  typedef Handle_for<Bcv_rep>                     Bcv_handle;

  typedef typename Bcv_rep::Control_point_vec     Control_pt_vec;

public:

  typedef typename Bcv_rep::Rat_point_2           Rat_point_2;
  typedef typename Bcv_rep::Alg_point_2           Alg_point_2;
  
  typedef typename Bcv_rep::Integer               Integer;
  typedef typename Bcv_rep::Rational              Rational;
  typedef typename Bcv_rep::Algebraic             Algebraic;
  typedef typename Bcv_rep::Polynomial            Polynomial;

  typedef typename Control_pt_vec::const_iterator Control_point_iterator;

public:

  /*!
   * Default constructor.
   */
  _Bezier_curve_2 () :
    Bcv_handle (Bcv_rep())
  {}

  /*!
   * Copy constructor.
   */
  _Bezier_curve_2 (const Self& bc) :
    Bcv_handle (bc)
  {}

  /*!
   * Constructor from a given range of control points.
   * \param pts_begin An iterator pointing to the first point in the range.
   * \param pts_end A past-the-end iterator for the range.
   * \pre The value-type of the input iterator must be Rat_kernel::Point_2.
   * \pre There must be at least 2 control points, and the polyline defined
   *      by these points may not be self intersecting.
   */
  template <class InputIterator>
  _Bezier_curve_2 (InputIterator pts_begin, InputIterator pts_end) :
    Bcv_handle (Bcv_rep (pts_begin, pts_end))
  {}

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

    Bcv_handle::operator= (bc);
    return (*this);
  }
  
  /*!
   * Get a unique curve ID (based on the actual representation pointer).
   */
  size_t id () const
  {
    return (reinterpret_cast<size_t> (this->ptr()));
  }

  /*!
   * Get the polynomial for the x-coordinates of the curve.
   */
  const Polynomial& x_polynomial () const
  {
    return (_rep().x_polynomial());
  }

  /*!
   * Get the normalizing factor for the x-coordinates.
   */
  const Integer& x_norm () const 
  {
    return (_rep().x_norm());
  }

  /*!
   * Get the polynomial for the y-coordinates of the curve.
   */
  const Polynomial& y_polynomial () const 
  {
    return (_rep().y_polynomial());
  }

  /*!
   * Get the normalizing factor for the y-coordinates.
   */
  const Integer& y_norm () const 
  {
    return (_rep().y_norm());
  }

  /*!
   * Get the number of control points inducing the Bezier curve.
   */
  unsigned int number_of_control_points () const
  {
    return (_rep()._ctrl_pts.size());
  }

  /*!
   * Get the i'th control point.
   * \pre i must be between 0 and n - 1, where n is the number of control
   *      points.
   */
  const Rat_point_2& control_point (unsigned int i) const
  {
    CGAL_precondition (i < number_of_control_points());

    return ((_rep()._ctrl_pts)[i]);
  }

  /*!
   * Get an interator for the first control point.
   */
  Control_point_iterator control_points_begin () const
  {
    return (_rep()._ctrl_pts.begin());
  }

  /*!
   * Get a past-the-end interator for control points.
   */
  Control_point_iterator control_points_end () const
  {
    return (_rep()._ctrl_pts.end());
  }

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

  /*!
   * Compute a point of the Bezier curve given a rational t-value.
   * \param t The given t-value.
   * \return The point B(t).
   */
  Rat_point_2 operator() (const Rational& t) const;
  
  /*!
   * Compute a point of the Bezier curve given an algebraic t-value.
   * \param t The given t-value.
   * \return The point B(t).
   */
  Alg_point_2 operator() (const Algebraic& t) const;
 
  /*!
   * Sample a portion of the curve (for drawing purposes, etc.).
   * \param t_start The t-value to start with.
   * \param t_end The t-value to end at.
   * \param n_samples The required number of samples.