conic_x_monotone_arc_2.h

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

// Copyright (c) 2005  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/Conic_x_monotone_arc_2.h $
// $Id: Conic_x_monotone_arc_2.h 39372 2007-07-12 15:12:35Z ophirset $
// 
//
// Author(s)     : Ron Wein <[e-mail]>

#ifndef CGAL_CONIC_X_MONOTONE_ARC_2_H
#define CGAL_CONIC_X_MONOTONE_ARC_2_H

/*! \file
 * Header file for the _Conic_x_monotone_arc_2<Conic_arc_2> class.
 */

#include <CGAL/Arr_traits_2/Conic_intersections_2.h>

#include <map>
#include <ostream>

CGAL_BEGIN_NAMESPACE

/*!
 * Representation of an x-monotone conic arc.
 * The class is templated by a representation of a general bounded conic arc.
 */

template <class Conic_arc_>
class _Conic_x_monotone_arc_2 : private Conic_arc_
{
public:

  typedef Conic_arc_                              Conic_arc_2;
  typedef _Conic_x_monotone_arc_2<Conic_arc_2>    Self;
  
  typedef typename Conic_arc_2::Alg_kernel        Alg_kernel;
  typedef typename Conic_arc_2::Algebraic         Algebraic;

  typedef typename Conic_arc_2::Point_2           Point_2;
  typedef typename Conic_arc_2::Conic_point_2     Conic_point_2;

  // Type definition for the intersection points mapping.
  typedef typename Conic_point_2::Conic_id        Conic_id;
  typedef std::pair<Conic_id, Conic_id>           Conic_pair;
  typedef std::pair<Conic_point_2, unsigned int>  Intersection_point_2;
  typedef std::list<Intersection_point_2>         Intersection_list;

  /*!
   * \struct Less functor for Conic_pair.
   */
  struct Less_conic_pair
  {
    bool operator() (const Conic_pair& cp1, const Conic_pair& cp2) const
    {
      // Compare the pairs of IDs lexicographically.
      return (cp1.first < cp2.first ||
              (cp1.first == cp2.first && cp1.second < cp2.second));
    }
  };

  typedef std::map<Conic_pair,
                   Intersection_list,
                   Less_conic_pair>               Intersection_map;
  typedef typename Intersection_map::value_type   Intersection_map_entry;
  typedef typename Intersection_map::iterator     Intersection_map_iterator;

protected:
  
  typedef Conic_arc_2                             Base;

  typedef typename Conic_arc_2::Integer           Integer;
  typedef typename Conic_arc_2::Nt_traits         Nt_traits;
  typedef typename Conic_arc_2::Rat_kernel        Rat_kernel;

  // Bit masks for the _info field (the two least significant bits are already
  // used by the base class).
  enum
  {
    IS_VERTICAL_SEGMENT = 4,
    IS_DIRECTED_RIGHT = 8,
    DEGREE_1 = 16,
    DEGREE_2 = 32,
    DEGREE_MASK = 16 + 32,
    PLUS_SQRT_DISC_ROOT = 64,
    FACING_UP = 128,
    FACING_DOWN = 256,
    FACING_MASK = 128 + 256,
    IS_SPECIAL_SEGMENT = 512
  };

  Algebraic      alg_r;      // The coefficients of the supporting conic curve:
  Algebraic      alg_s;      //
  Algebraic      alg_t;      //   r*x^2 + s*y^2 + t*xy + u*x + v*y +w = 0 ,
  Algebraic      alg_u;      //
  Algebraic      alg_v;      // converted to algebraic numbers.
  Algebraic      alg_w;      //

  Conic_id      _id;         // The ID number of the supporting conic curve.
    
public:

  /// \name Constrcution methods.
  //@{

  /*!
   * Default constructor.
   */
  _Conic_x_monotone_arc_2 () :
    Base (),
    _id ()
  {}

  /*!
   * Copy constructor.
   * \param arc The copied arc.
   */
  _Conic_x_monotone_arc_2 (const Self& arc) :
    Base (arc),
    alg_r (arc.alg_r),
    alg_s (arc.alg_s),
    alg_t (arc.alg_t),
    alg_u (arc.alg_u),
    alg_v (arc.alg_v),
    alg_w (arc.alg_w),
    _id (arc._id)
  {}

  /*!
   * Construct an x-monotone arc from a conic arc.
   * \param arc The given (base) arc.
   * \pre The given arc is x-monotone.
   */
  _Conic_x_monotone_arc_2 (const Base& arc) :
    Base (arc),
    _id ()
  {
    CGAL_precondition (arc.is_valid() && arc.is_x_monotone());

    _set ();
  }

  /*!
   * Construct an x-monotone arc from a conic arc.
   * \param arc The given (base) arc.
   * \param id The ID of the base arc.
   */
  _Conic_x_monotone_arc_2 (const Base& arc,
                           const Conic_id& id) :
    Base (arc),
    _id (id)
  {
    CGAL_precondition (arc.is_valid() && id.is_valid());

    _set ();
  }

  /*!
   * Construct an x-monotone sub-arc from a conic arc.
   * \param arc The given (base) arc.
   * \param source The source point.
   * \param target The target point.
   * \param id The ID of the base arc.
   */
  _Conic_x_monotone_arc_2 (const Base& arc,
                           const Point_2& source, const Point_2& target,
                           const Conic_id& id) :
    Base (arc),
    _id (id)
  {
    CGAL_precondition (arc.is_valid() && id.is_valid());

    // Set the two endpoints.
    this->_source = source;
    this->_target = target;

    _set();
  }

  /*!
   * Construct a special segment connecting to given endpoints (for the usage
   * of the landmarks point-location strategy).
   * \param source The source point.
   * \param target The target point.
   */
  _Conic_x_monotone_arc_2 (const Point_2& source, const Point_2& target) :
    Base()
  {
    // Set the basic properties and clear the _info bits.
    this->_source = source;
    this->_target = target;
    this->_orient = COLLINEAR;
    this->_info = 0;
 
    // Check if the arc is directed right (the target is lexicographically
    // greater than the source point), or to the left.
    Alg_kernel         ker;
    Comparison_result  dir_res = ker.compare_xy_2_object() (this->_source,
                                                            this->_target);

    CGAL_precondition (dir_res != EQUAL);
    if (dir_res == EQUAL)
      // Invalid arc:
      return;

    this->_info = (Conic_arc_2::IS_VALID | DEGREE_1);
    if (dir_res == SMALLER)
      this->_info = (this->_info | IS_DIRECTED_RIGHT);

    // Compose the equation of the underlying line.
    const Algebraic        x1 = source.x(), y1 = source.y();
    const Algebraic        x2 = target.x(), y2 = target.y();

    // The supporting line is A*x + B*y + C = 0, where:
    //
    //  A = y2 - y1,    B = x1 - x2,    C = x2*y1 - x1*y2 
    //
    // We use the extra data field to store the equation of this line.
    this->_extra_data_P = new typename Base::Extra_data;
    this->_extra_data_P->a = y2 - y1;
    this->_extra_data_P->b = x1 - x2;
    this->_extra_data_P->c = x2*y1 - x1*y2;
    this->_extra_data_P->side = ZERO;

    // Check if the segment is vertical.
    if (CGAL::sign (this->_extra_data_P->b) == ZERO)
      this->_info = (this->_info | IS_VERTICAL_SEGMENT);

    // Mark that this is a special segment.
    this->_info = (this->_info | IS_SPECIAL_SEGMENT);

    return;
  }

  /*!
   * Construct a special segment of a given line connecting to given
   * endpoints.
   * \param a, b, c The coefficients of the supporting line (ax + by + c = 0).
   * \param source The source point.
   * \param target The target point.
   */
  _Conic_x_monotone_arc_2 (const Algebraic& a,
                           const Algebraic& b,
                           const Algebraic& c,
                           const Point_2& source, const Point_2& target) :
    Base()
  {
    // Make sure the two endpoints lie on the supporting line.
    CGAL_precondition (CGAL::sign (a * source.x() +
                                   b * source.y() + c) == CGAL::ZERO);

    CGAL_precondition (CGAL::sign (a * target.x() +
                                   b * target.y() + c) == CGAL::ZERO);

    // Set the basic properties and clear the _info bits.
    this->_source = source;
    this->_target = target;
    this->_orient = COLLINEAR;
    this->_info = 0;
 
    // Check if the arc is directed right (the target is lexicographically
    // greater than the source point), or to the left.
    Alg_kernel         ker;
    Comparison_result  res = ker.compare_x_2_object() (this->_source,
                                                       this->_target);

    this->_info = (Conic_arc_2::IS_VALID | DEGREE_1);
    if (res == EQUAL)
    {
      // Mark that the segment is vertical.
      this->_info = (this->_info | IS_VERTICAL_SEGMENT);

      // Compare the endpoints lexicographically.
      res = ker.compare_y_2_object() (this->_source,
                                      this->_target);

      CGAL_precondition (res != EQUAL);
      if (res == EQUAL)
      {
        // Invalid arc:
        this->_info = 0;
        return;
      }
    }

    if (res == SMALLER)
      this->_info = (this->_info | IS_DIRECTED_RIGHT);

    // Store the coefficients of the line.
    this->_extra_data_P = new typename Base::Extra_data;
    this->_extra_data_P->a = a;
    this->_extra_data_P->b = b;
    this->_extra_data_P->c = c;
    this->_extra_data_P->side = ZERO;

    // Mark that this is a special segment.
    this->_info = (this->_info | IS_SPECIAL_SEGMENT);

    return;
  } 

  /*!
   * Assignment operator.
   * \param arc The copied arc.
   */
  const Self& operator= (const Self& arc)
  {
    CGAL_precondition (arc.is_valid());

    if (this == &arc)
      return (*this);

    // Copy the base arc.
    Base::operator= (arc);

    // Set the rest of the properties.
    alg_r = arc.alg_r;
    alg_s = arc.alg_s;
    alg_t = arc.alg_t;
    alg_u = arc.alg_u;
    alg_v = arc.alg_v;
    alg_w = arc.alg_w;

    _id = arc._id;

    return (*this);
  }
  //@}

  /// \name Accessing the arc properties.
  //@{

  /*! 
   * Get the coefficients of the underlying conic.
   */
  const Integer& r () const {return (this->_r);}
  const Integer& s () const {return (this->_s);}
  const Integer& t () const {return (this->_t);}
  const Integer& u () const {return (this->_u);}
  const Integer& v () const {return (this->_v);}
  const Integer& w () const {return (this->_w);}

  /*!
   * Get the arc's source.
   * \return The source point.
   */
  const Conic_point_2& source () const
  {
    return (this->_source);
  }

  /*!
   * Get the arc's target.
   * \return The target point.
   */
  const Conic_point_2& target () const
  {
    return (this->_target);
  }

  /*!
   * Get the orientation of the arc.
   * \return The orientation.
   */
  Orientation orientation () const
  {
    return (this->_orient);
  }

  /*!
   * Get the left endpoint of the arc.
   */
  const Conic_point_2& left () const
  {
    if ((this->_info & IS_DIRECTED_RIGHT) != 0)
      return (this->_source);
    else
      return (this->_target);
  }

  /*!
   * Get the right endpoint of the arc.
   */
  const Conic_point_2& right () const
  {
    if ((this->_info & IS_DIRECTED_RIGHT) != 0)
      return (this->_target);
    else
      return (this->_source);
  }

  /*!
   * Return true iff the conic arc is directed right iexicographically.
   */
  bool is_directed_right() const
  {
    return ((this->_info & IS_DIRECTED_RIGHT) != 0);
  }

  /*!
   * Get a bounding box for the conic arc.
   * \return The bounding box.
   */
  Bbox_2 bbox () const
  {
    return (Base::bbox());
  }
  //@}

  /// \name Predicates.
  //@{

  /*!
   * Check if the conic arc is a vertical segment.
   */
  bool is_vertical () const
  {
    return ((this->_info & IS_VERTICAL_SEGMENT) != 0);