bezier_x_monotone_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_x_monotone_2.h $
// $Id: Bezier_x_monotone_2.h 39701 2007-08-06 09:26:46Z golubevs $
// 
//
// Author(s)     : Ron Wein     <[e-mail]>
//                 Iddo Hanniel <[e-mail]>

#ifndef CGAL_BEZIER_X_MONOTONE_2_H
#define CGAL_BEZIER_X_MONOTONE_2_H

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

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

CGAL_BEGIN_NAMESPACE

/*! \class
 * Representation of an x-monotone Bezier subcurve, specified by a Bezier curve
 * and two end points.
 */
template <class Rat_kernel_, class Alg_kernel_, class Nt_traits_,
          class Bounding_traits_>
class _Bezier_x_monotone_2
{
public:

  typedef Rat_kernel_                             Rat_kernel;
  typedef Alg_kernel_                             Alg_kernel;
  typedef Nt_traits_                              Nt_traits;
  typedef Bounding_traits_                        Bounding_traits;
  typedef _Bezier_curve_2<Rat_kernel,
                          Alg_kernel,
                          Nt_traits,
                          Bounding_traits>              Curve_2;
  typedef _Bezier_point_2<Rat_kernel,
                          Alg_kernel,
                          Nt_traits,
                          Bounding_traits>              Point_2;
  typedef _Bezier_x_monotone_2<Rat_kernel,
                               Alg_kernel,
                               Nt_traits,
                               Bounding_traits>         Self;

  typedef _Bezier_cache<Nt_traits>                      Bezier_cache;

private:

  typedef typename Alg_kernel::Point_2            Alg_point_2;
  typedef typename Rat_kernel::Point_2            Rat_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;

  typedef typename Point_2::Originator               Originator;
  typedef typename Point_2::Originator_iterator      Originator_iterator;
  typedef typename Bounding_traits::Bez_point_bound  Bez_point_bound;
  typedef typename Bounding_traits::Bez_point_bbox   Bez_point_bbox;

  // Type definition for the vertical tangency-point mapping.
  typedef typename Bezier_cache::Curve_id                 Curve_id;
  typedef std::pair<Curve_id, Curve_id>                   Curve_pair;
  typedef typename Bezier_cache::Vertical_tangency_list   Vert_tang_list;
  typedef typename Bezier_cache::Vertical_tangency_iter   Vert_tang_iter;

  // Type definition for the intersection-point mapping.
  typedef typename Bezier_cache::Intersection_list        Intersect_list;
  typedef typename Bezier_cache::Intersection_iter        Intersect_iter;

  // Representation of an intersection point with its multiplicity:
  typedef std::pair<Point_2, unsigned int>                Intersection_point_2;

  /*! \class Less_intersection_point
   * Comparison functor for intersection points.
   */
  class Less_intersection_point
  {
  private:
    Bezier_cache    *p_cache;
    
  public:

    Less_intersection_point (Bezier_cache& cache) :
      p_cache (&cache)
    {}

    bool operator() (const Intersection_point_2& ip1,
                     const Intersection_point_2& ip2) const
    {
      return (ip1.first.compare_xy (ip2.first, *p_cache) == SMALLER);
    }
  };

  // Type definition for the bounded intersection-point mapping.
  typedef std::list<Point_2>                          Intersection_list;

  /*! \struct
   * An auxiliary functor for comparing pair of curve IDs.
   */
  struct Less_curve_pair
  {
    bool operator() (const Curve_pair& cp1, const Curve_pair& cp2) const
    {
      // Compare the pairs of IDs lexicographically.
      return (cp1.first < cp2.first ||
              (cp1.first == cp2.first && cp1.second < cp2.second));
    }
  };

  /*! \struct Subcurve
   * For the usage of the _exact_vertical_position() function.
   */
  struct Subcurve
  {
    std::list<Rat_point_2>    control_points;
    Rational                  t_min;
    Rational                  t_max;

    /*! Get the rational bounding box of the subcurve. */
    void bbox (Rational& x_min, Rational& y_min,
               Rational& x_max, Rational& y_max) const
    {
      typename std::list<Rat_point_2>::const_iterator  pit =
        control_points.begin();

      CGAL_assertion (pit != control_points.end());

      x_min = x_max = pit->x();
      y_min = y_max = pit->y();

      for (++pit; pit != control_points.end(); ++pit)
      {
        if (CGAL::compare (x_min, pit->x()) == LARGER)
          x_min = pit->x();
        else if (CGAL::compare (x_max, pit->x()) == SMALLER)
          x_max = pit->x();

        if (CGAL::compare (y_min, pit->y()) == LARGER)
          y_min = pit->y();
        else if (CGAL::compare (y_max, pit->y()) == SMALLER)
          y_max = pit->y();
      }

      return;
    }
  };

public:

  typedef std::map<Curve_pair,
                   Intersection_list,
                   Less_curve_pair>               Intersection_map;
  typedef typename Intersection_map::value_type   Intersection_map_entry;
  typedef typename Intersection_map::iterator     Intersection_map_iterator;

private:

  // Data members:
  Curve_2     _curve;         /*! The supporting Bezier curve. */
  Point_2     _ps;            /*! The source point. */
  Point_2     _pt;            /*! The target point. */
  bool        _dir_right;     /*! Is the subcurve directed right (or left). */
  bool        _inc_to_right;  /*! Does the parameter value increase when
                                  traversing the subcurve from left to
                                  right. */
  bool        _is_vert;       /*! Is the subcurve a vertical segment. */

public:

  /*! Default constructor. */
  _Bezier_x_monotone_2 () :
    _dir_right (false),
    _is_vert (false)
  {}

  /*!
   * Constructor given two endpoints.
   * \param B The supporting Bezier curve.
   * \param ps The source point.
   * \param pt The target point.
   * \param cache Caches the vertical tangency points and intersection points.
   * \pre B should be an originator of both ps and pt.
   */
  _Bezier_x_monotone_2 (const Curve_2& B,
                        const Point_2& ps, const Point_2& pt,
                        Bezier_cache& cache);

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

  /*!
   * Get the source point.
   */
  const Point_2& source () const
  {
    return (_ps);
  }

  /*!
   * Get the target point.
   */
  const Point_2& target () const
  {
    return (_pt);
  }

  /*!
   * Get the left endpoint (the lexicographically smaller one).
   */
  const Point_2& left () const
  {
    return (_dir_right ? _ps : _pt);
  }

  /*!
   * Get the right endpoint (the lexicographically larger one).
   */
  const Point_2& right () const
  {
    return (_dir_right ? _pt : _ps);
  }

  /*!
   * Check if the subcurve is a vertical segment.
   */
  bool is_vertical () const
  {
    return (_is_vert);
  }

  /*!
   * Check if the subcurve is directed from left to right.
   */
  bool is_directed_right () const
  {
    return (_dir_right);
  }

  /*!
   * Get the approximate parameter range defining the curve.
   * \return A pair of t_src and t_trg, where B(t_src) is the source point
   *         and B(t_trg) is the target point.
   */
  std::pair<double, double> parameter_range () const;

  /*!
   * Get the relative position of the query point with respect to the subcurve.
   * \param p The query point.
   * \param cache Caches the vertical tangency points and intersection points.
   * \pre p is in the x-range of the arc.
   * \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 point_position (const Point_2& p,
                                    Bezier_cache& cache) const;

  /*!
   * Compare the relative y-position of two x-monotone subcurve to the right
   * of their intersection point.
   * \param cv The other subcurve.
   * \param p The intersection point.
   * \param cache Caches the vertical tangency points and intersection points.
   * \pre p is the common left endpoint of both subcurves.
   * \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_right (const Self& cv,
                                      const Point_2& p,
                                      Bezier_cache& cache) const;

  /*!
   * Compare the relative y-position of two x-monotone subcurve to the left
   * of their intersection point.
   * \param cv The other subcurve.
   * \param p The intersection point.
   * \param cache Caches the vertical tangency points and intersection points.
   * \pre p is the common right endpoint of both subcurves.
   * \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_left (const Self& cv,
                                     const Point_2& p,
                                     Bezier_cache& cache) const;

  /*!
   * Check whether the two subcurves are equal (have the same graph).
   * \param cv The other subcurve.
   * \param cache Caches the vertical tangency points and intersection points.
   * \return (true) if the two subcurves have the same graph;
   *         (false) otherwise.
   */
  bool equals (const Self& cv,
               Bezier_cache& cache) 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 oi The output iterator.
   * \return The past-the-end iterator.
   */
  template<class OutputIterator>
  OutputIterator intersect (const Self& cv,
                            Intersection_map& inter_map,
                            Bezier_cache& cache,
                            OutputIterator oi) const
  {
    // In case we have two x-monotone subcurves of the same Bezier curve,
    // the only intersections that may occur are common endpoints.
    if (_curve.is_same (cv._curve))
    {
      if (left().is_same (cv.left()) || left().is_same (cv.right()))
      {
        *oi = CGAL::make_object (Intersection_point_2 (left(), 0));
        ++oi;
      }

      if (right().is_same (cv.left()) || right().is_same (cv.right()))
      {
        *oi = CGAL::make_object (Intersection_point_2 (right(), 0));
        ++oi;
      }

      return (oi);
    }
   
    // Compute the intersections of the two sucurves. Note that for caching
    // purposes we always apply the _intersect() function on the subcurve whose
    // curve ID is smaller.
    std::vector<Intersection_point_2>   ipts;
    Self                                ovlp_cv;
    bool                                do_ovlp;

    CGAL_assertion (_curve.id() != cv._curve.id());
    if (_curve.id() < cv._curve.id())
      do_ovlp = _intersect (cv, inter_map, cache, ipts, ovlp_cv);
    else
      do_ovlp = cv._intersect (*this, inter_map, cache, ipts, ovlp_cv);

    // In case of overlap, just report the overlapping subcurve.
    if (do_ovlp)
    {
      *oi = CGAL::make_object (ovlp_cv);
      ++oi;
      return (oi);
    }

    // If we have a set of intersection points, sort them in ascending
    // xy-lexicorgraphical order, and insert them to the output iterator.
    typename std::vector<Intersection_point_2>::const_iterator  ip_it;

    std::sort (ipts.begin(), ipts.end(), Less_intersection_point (cache));
    for (ip_it = ipts.begin(); ip_it != ipts.end(); ++ip_it)