bezier_point_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_point_2.h $
// $Id: Bezier_point_2.h 39308 2007-07-05 10:22:22Z golubevs $
// 
//
// Author(s)     : Ron Wein     <[e-mail]>
//                 Iddo Hanniel <[e-mail]>

#ifndef CGAL_BEZIER_POINT_2_H
#define CGAL_BEZIER_POINT_2_H

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

#include <CGAL/Arr_traits_2/Bezier_curve_2.h>
#include <CGAL/Arr_traits_2/Bezier_cache.h>
#include <CGAL/Handle_for.h>
#include <list>
#include <ostream>

CGAL_BEGIN_NAMESPACE

/*! \class _Bezier_point_2
 * Representation of a point on a Bezier curve. The point has algebraic
 * coefficients, with an additional list of originator. An originator is a
 * pair of the form <B(t), t0>, meaning that this point is obtained by
 * computing B(t0) on the curve B(t).
 */

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

template <class RatKernel_, class AlgKernel_, class NtTraits_,
          class BoundingTraits_>
class _Bezier_point_2_rep
{
  friend class _Bezier_point_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::Rational            Rational;
  typedef typename Nt_traits::Algebraic           Algebraic;

  typedef typename Bounding_traits::Bez_point_bound   Bez_point_bound;
  typedef typename Bounding_traits::Bez_point_bbox    Bez_point_bbox;

  typedef _Bezier_point_2_rep<Rat_kernel,
                              Alg_kernel,
                              Nt_traits,
                              Bounding_traits>    Self; 

private:

  typedef _Bezier_curve_2<Rat_kernel,
                          Alg_kernel,
                          Nt_traits,
                          Bounding_traits>        Curve_2;

  typedef _Bezier_cache<Nt_traits>                Bezier_cache;

  /*! \class Originator
   * Stores information on the original curve the Bezier point came from.
   */
  class Originator
  {
  private:

    Curve_2             _curve;     /*! The originating curve. */
    Bez_point_bound     _bpb;       /*! Bounding information for the
                                        point: bouding control polygon,
                                        point type, etc. */
    Algebraic          *p_t;        /*! The algebraic parameter for the
                                        point (if available). */

  public:

    /*! Constructor, given an exact algebraic representation. */
    Originator(const Curve_2& c, const Algebraic& t) :
      _curve(c),
      p_t (NULL)
    {
      set_parameter (t);
    }

    /*! Constructor with bounding information and no exact representation. */
    Originator (const Curve_2& c, const Bez_point_bound& bpb) :
      _curve (c),
      _bpb (bpb),
      p_t (NULL)
    {}

    /*! Copy constructor. */
    Originator (const Originator& other) :
      _curve (other._curve),
      _bpb (other._bpb),
      p_t (NULL)
    {
      // Deep copy of lazy instantiation
      if (other.p_t != NULL)
        p_t = new Algebraic (*(other.p_t));
    }

    /*! Destructor. */
    ~Originator() 
    {
      if (p_t != NULL)
        delete p_t;
    }

    /*! Assignment operator. */
    Originator& operator= (const Originator& other)
    {
      // Avoid self assignments.
      if (this == &other)
        return (*this);
                                                
      // Free memory, if necessary.
      if (p_t != NULL)
        delete p_t;
      p_t = NULL;

      // Copy the data members.
      _curve = other._curve;
      _bpb = other._bpb;

      // Deep copy of lazy instantiation
      if (other.p_t != NULL)
        p_t = new Algebraic (*(other.p_t));

      return (*this);
    }

    /*! Get the originating curve. */
    const Curve_2& curve () const
    {
      return (_curve);
    }

    /*! Get the bounding information. */
    const Bez_point_bound& point_bound () const
    {
      return (_bpb);
    }

    /*! Update the bounding information. */
    void update_point_bound (const Bez_point_bound& bpb)
    {
      _bpb = bpb;
      return;
    }

    /*! Check if the algberaic parameter is available. */
    bool has_parameter () const
    {
      return (p_t != NULL);
    }

    /*! 
     * Get the algebraic parameter.
     * \pre The parameter value is available.
     */
    const Algebraic& parameter () const
    {
      CGAL_precondition (p_t != NULL);
      return (*p_t);
    }

    /*!
     * Set the parameter value. 
     * \pre The parameter value is not yet set.
     */
    void set_parameter (const Algebraic& t)
    {
      CGAL_precondition (p_t == NULL);
      
      p_t = new Algebraic (t);

      // Update the Bez_point_bound, probably by converting t to
      // an interval of doubles and setting _bpb accordingly.
      Nt_traits                         nt_traits;
      const std::pair<double, double>&  t_bnd = nt_traits.double_interval (t);

      _bpb.t_min = t_bnd.first;
      _bpb.t_max = t_bnd.second;

      return;
    }
  };

  /*! \struct Subcurve
   * Auxilary structure for the vertical_position() function.
   */
  typedef typename Bounding_traits::Control_point_vec   Control_point_vec;
  typedef typename Bounding_traits::NT                  BoundNT;

  struct Subcurve
  {
    Control_point_vec   cp;
    BoundNT             l;
    BoundNT             r;

    /*! Constructor. */
    Subcurve (const Control_point_vec& _cp,
              const BoundNT& _l, 
              const BoundNT& _r) :
      cp (_cp),
      l (_l),
      r (_r)
    {} 
  };

  typedef std::list<Originator>                   Orig_list;
  typedef typename Orig_list::const_iterator      Orig_const_iter;
  typedef typename Orig_list::iterator            Orig_iter;

  Algebraic        *p_alg_x;   /*! The exact x-coordinate (if known). */
  Rational         *p_rat_x;   /*! The x-coordinate, in case it is rational. */
  Algebraic        *p_alg_y;   /*! The exact y-coordinate (if known). */
  Rational         *p_rat_y;   /*! The y-coordinate, in case it is rational. */
  Orig_list        _origs;     /*! The list of originators. */
  Bez_point_bbox   _bbox;      /*! A bounding box. */

public:

  /*! Default constructor. */
  _Bezier_point_2_rep () :
    p_alg_x (NULL),
    p_rat_x (NULL),
    p_alg_y (NULL),
    p_rat_y (NULL)
  {}

  /*! Copy constructor. */
  _Bezier_point_2_rep (const Self& pt) :
    p_alg_x (NULL),
    p_rat_x (NULL),
    p_alg_y (NULL),
    p_rat_y (NULL),
    _origs (pt._origs),
    _bbox (pt._bbox)
  {
    if (pt.p_alg_x != NULL)
      p_alg_x = new Algebraic (*(pt.p_alg_x));
    if (pt.p_rat_x != NULL)
      p_rat_x = new Rational (*(pt.p_rat_x));
    if (pt.p_alg_y != NULL)
      p_alg_y = new Algebraic (*(pt.p_alg_y));
    if (pt.p_rat_y != NULL)
      p_rat_y = new Rational (*(pt.p_rat_y));
  }

  /*!
   * Constructor with algebraic coordinates.
   * \param x The exact x-coordinate.
   * \param y The exact y-coordinate.
   */
  _Bezier_point_2_rep (const Algebraic& x, const Algebraic& y) : 
    p_rat_x (NULL),
    p_rat_y (NULL)
  {
    p_alg_x = new Algebraic (x);
    p_alg_y = new Algebraic (y);

    // Initialize the bounding box.
    Nt_traits                         nt_traits;
    const std::pair<double, double>&  x_bnd = 
                                        nt_traits.double_interval (x);
    const std::pair<double, double>&  y_bnd = 
                                        nt_traits.double_interval (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 a rational t0 value.
   * \pre t0 must be between 0 and 1.
   */
  _Bezier_point_2_rep (const Curve_2& B, const Rational& t0);

  /*!
   * Constructor given an originating curve and an algebraic t0 value.
   * \pre t0 must be between 0 and 1.
   */
  _Bezier_point_2_rep (const Curve_2& B, const Algebraic& t0);

  /*! Destructor. */
  ~_Bezier_point_2_rep ()
  {
    if (p_rat_x != NULL)
      delete p_rat_x;
    if (p_alg_x != NULL)
      delete p_alg_x;
    if (p_rat_y != NULL)
      delete p_rat_y;
    if (p_alg_y != NULL)
      delete p_alg_y;
  }

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

    if (p_rat_x != NULL)
      delete p_rat_x;
    if (p_alg_x != NULL)
      delete p_alg_x;
    if (p_rat_y != NULL)
      delete p_rat_y;
    if (p_alg_y != NULL)
      delete p_alg_y;
    p_alg_x = p_rat_x = p_alg_y = p_rat_y = NULL;


    if (pt.p_alg_x != NULL)
      p_alg_x = new Algebraic (*(pt.p_alg_x));
    if (pt.p_rat_x != NULL)
      p_rat_x = new Rational (*(pt.p_rat_x));
    if (pt.p_alg_y != NULL)
      p_alg_y = new Algebraic (*(pt.p_alg_y));
    if (pt.p_rat_y != NULL)
      p_rat_y = new Rational (*(pt.p_rat_y));
  
    _origs = pt._origs;
    _bbox = pt._bbox;

    return (*this);
  }

  /*! Check if the point is exactly computed. */
  inline bool is_exact () const
  {
    return (p_alg_x != NULL && p_alg_y != NULL);
  }

  /*! Check if the point has rational coordinates. */
  inline bool is_rational () const
  {
    return (p_rat_x != NULL && p_rat_y != NULL);
  }

  /*!
   * 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 (Self& pt,
                               Bezier_cache& cache);

  /*!
   * Compare the two point 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 (Self& pt,
                                Bezier_cache& cache);

  /*!
   * 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 Control_point_vec& cp,
                                       const BoundNT& t_min,
                                       const BoundNT& t_max);

private:

  /*!
   * Refine the bounds of the point.
   * \return Whether it was possible to further refine the point.
   */
  bool _refine ();

  /*!
   * Compute the exact representation of the point.
   * \param cache A cache for the vertical tangency points and the
   *              intersection points.
   */
  void _make_exact (Bezier_cache& cache);
};

template <class RatKernel_, class AlgKernel_, class NtTraits_, 
          class BoundingTraits_>
class _Bezier_point_2 :
  public Handle_for<_Bezier_point_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_point_2<Rat_kernel,
                          Alg_kernel,
                          Nt_traits,
                          Bounding_traits>        Self;

private:

  typedef _Bezier_point_2_rep<Rat_kernel,
                              Alg_kernel,
                              Nt_traits,
                              Bounding_traits>    Bpt_rep;
  typedef Handle_for<Bpt_rep>                     Bpt_handle;

public: