conic_arc_2_core.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 2,297 行 · 第 1/5 页

// Copyright (c) 1999  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.
//
// $Source: /CVSROOT/CGAL/Packages/Arrangement/include/CGAL/Arrangement_2/Conic_arc_2_core.h,v $
// $Revision: 1.2 $ $Date: 2004/05/27 11:52:28 $
// $Name:  $
//
// Author(s)     : Ron Wein <[e-mail]>

#ifndef CGAL_CONIC_ARC_2_CORE_H
#define CGAL_CONIC_ARC_2_CORE_H

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Conic_2.h>
#include <CGAL/predicates_on_points_2.h>
#include <CGAL/Bbox_2.h>
#include <CGAL/Arrangement_2/Conic_arc_2_eq_core.h>

#include <list>
#include <ostream>

#define CGAL_CONIC_ARC_USE_CACHING

CGAL_BEGIN_NAMESPACE

/*!
 * A class that stores additional information with the point's coordinates:
 * Namely the conic IDs of the generating curves.
 */
template <class Kernel_>
class Point_ex_2 : public Kernel_::Point_2
{
public:

  typedef Kernel_                       Kernel;
  typedef typename Kernel::Point_2      Base;
  typedef Point_ex_2<Kernel>            Self;
    
  typedef typename Kernel::FT           CoNT;
 
private:

  int    _id1;       // The ID of the first generating conic (or 0).
  int    _id2;       // The ID of the second generating conic (or 0).

 public:

  // Constructors.
  Point_ex_2 () :
    Base(),
    _id1(0),
    _id2(0)
  {}

  Point_ex_2 (const CoNT& hx, const CoNT& hy, const CoNT& hz) :
    Base(hx,hy,hz),
    _id1(0),
    _id2(0)
  {}

  Point_ex_2 (const CoNT& hx, const CoNT& hy,
	      const int& id1 = 0, const int& id2 = 0) :
    Base(hx,hy),
    _id1(id1),
    _id2(id2)
  {}

  Point_ex_2 (const Base& p) :
    Base(p),
    _id1(0),
    _id2(0)
  {}

  Point_ex_2 (const Base& p,
	      const int& id1, const int& id2 = 0) :
    Base(p),
    _id1(id1),
    _id2(id2)
  {}

  // Set the generating conic IDs.
  void set_generating_conics (const int& id1,
			      const int& id2 = 0)
  {
    _id1 = id1;
    _id2 = id2;

    return;
  }

  // Check if the given conic generates the point.
  bool is_generating_conic_id (const int& id) const
  {
    return (id != 0 &&
	    (id == _id1 || id == _id2));
  }

  // Check whether two points are equal.
  bool equals (const Self& p) const
  {
    // If the two points are the same:
    if (this == &p)
      return (true);

    // Use the parent's equality operator.
    return ((*this) == p);
  }
  
  // Compare the x coordinates.
  Comparison_result compare_x (const Self& p) const
  {
    return (CGAL_NTS compare(x(), p.x()));
  }

  // Compare the y coordinates.
  Comparison_result compare_y (const Self& p) const
  {
    return (CGAL_NTS compare(y(), p.y()));
  }

  // Compare two points lexicographically.
  Comparison_result compare_lex_xy (const Self& p) const
  {
    Comparison_result   res = this->compare_x (p);

    if (res != EQUAL)
      return (res);
    
    return (this->compare_y (p));
  }
};

/*!
 * Representation of a conic arc -- a bounded segment that lies on a conic
 * curve, the loci of all points satisfying the equation:
 *   r*x^2 + s*y^2 + t*xy + u*x + v*y +w = 0
 *
 * The class is templated with two parameters: 
 * CfNT_ is a number type for representing the conic coefficients (integers).
 * Kernel_ is a geometric kernel, where Kernel_::FT is the number type for the
 * coordinates of points (which are algebraic numbers).
 */

static int _conics_count = 0;

template <class CfNT_, class Kernel_> class Arr_conic_traits_2;

template <class CfNT_, class Kernel_>
class Conic_arc_2
{
protected:
  typedef Conic_arc_2<CfNT_, Kernel_>  Self;
        
public:
  typedef CfNT_                        CfNT;
  typedef Kernel_                      Kernel;
  typedef typename Kernel::FT          CoNT;
    
  typedef Point_ex_2<Kernel>           Point_2;
  typedef Segment_2<Kernel>            Segment_2;
  typedef Circle_2<Kernel>             Circle_2;
  
 protected:

  friend class Arr_conic_traits_2<CfNT, Kernel>;

  enum
  {
    DEGREE_0 = 0,
    DEGREE_1 = 1,
    DEGREE_2 = 2,
    DEGREE_MASK = 1 + 2,
    FULL_CONIC = 4,
    X_MONOTONE = 8,
    X_MON_UNDEFINED = 8 + 16,
    FACING_UP = 32,
    FACING_DOWN = 64,
    FACING_MASK = 32 + 64,
    IS_CIRCLE = 128,
    IS_HYPERBOLA = 256
  };

  CfNT     _r;              //
  CfNT     _s;              // The coefficeint of the underlying conic curve:
  CfNT     _t;              //
  CfNT     _u;              //
  CfNT     _v;              // r*x^2 + s*y^2 + t*xy + u*x + v*y +w = 0
  CfNT     _w;              //

  Orientation _orient;      // The orientation of the conic.

  int         _conic_id;    // The id of the conic.
  Point_2     _source;      // The source of the arc. 
  Point_2     _target;      // The target of the arc.
  int         _info;        // A bit array with extra information:
                            // Bit 0 & 1 - The degree of the conic 
                            //             (either 1 or 2).
                            // Bit 2     - Whether the arc is a full conic.
                            // Bit 3 & 4 - Whether the arc is x-monotone
                            //             (00, 01 or 11 - undefined).
                            // Bit 5 & 6 - Indicate whether the arc is
                            //             facing upwards or downwards (for
                            //             x-monotone curves of degree 2).
                            // Bit 7     - Is the underlying curve a circle.
                            // Bit 8     - Is the underlying curve a hyperbola.

  // For arcs whose base is a hyperbola we store the axis (a*x + b*y + c = 0)
  // which separates the two bracnes of the hyperbola. We also store the side
  // (-1 or 1) that the arc occupies.
  struct Hyperbolic_arc_data
  {
    CoNT     a;
    CoNT     b;
    CoNT     c;
    int      side;
  };

  // In case of a circle, is is convinient to store its center and radius.
  struct Circular_arc_data
  {
    CoNT       x0;
    CoNT       y0;
    CoNT       r;
  };

#ifdef CGAL_CONIC_ARC_USE_CACHING
  struct Intersections
  {
    int     id1;
    int     id2;
    int     n_points;
    Point_2 ps[4];
  };
#endif

  union
  {
    Hyperbolic_arc_data *hyper_P;
    Circular_arc_data   *circ_P;
  } _data;

  // Produce a unique id for a new conic. 
  int _get_new_conic_id ()
  {
    _conics_count++;
    return (_conics_count);
  }

  /*!
   * Protected constructor: Construct an arc which is a segment of the given
   * conic arc, with a new source and target points.
   * \param The copied arc.
   * \param source The new source point.
   * \param target The new target point.
   */
  Conic_arc_2 (const Self & arc,
	       const Point_2& source, const Point_2 & target) :
    _r(arc._r), _s(arc._s), _t(arc._t), _u(arc._u), _v(arc._v), _w(arc._w),
    _orient(arc._orient),
    _conic_id(arc._conic_id),
    _source(source),
    _target(target)
  {
    _info = (arc._info & DEGREE_MASK) | 
      X_MON_UNDEFINED;

    // Check whether the conic is x-monotone.
    if (is_x_monotone())
    {
      _info = (_info & ~X_MON_UNDEFINED) | X_MONOTONE;

      // Check whether the facing information is set for the orginating arc.
      // If it is, just copy it - otherwise calculate it if the degree is 2.
      Comparison_result facing_res = arc.facing();

      if (facing_res != EQUAL)
	_info = _info | (facing_res == LARGER ? FACING_UP : FACING_DOWN);
      else if ((_info & DEGREE_MASK) == DEGREE_2)
	_set_facing();
    }
    else
    {
      _info = (_info & ~X_MON_UNDEFINED);
    }

    // Copy the hyperbolic or circular data, if necessary.
    if ((arc._info & IS_HYPERBOLA) != 0)
    {
      _info = _info | IS_HYPERBOLA;
      _data.hyper_P = new Hyperbolic_arc_data (*(arc._data.hyper_P));
    }
    else if ((arc._info & IS_CIRCLE) != 0)
    {
      _info = _info | IS_CIRCLE;
      _data.circ_P = new Circular_arc_data (*(arc._data.circ_P));
    }
    else
    {
      _data.hyper_P = NULL;
    }
  }

 public:

  /*!
   * Default constructor.
   */
  Conic_arc_2 () :
    _r(0), _s(0), _t(0), _u(0), _v(0), _w(0),
    _orient(CGAL::COLLINEAR),
    _conic_id(0),
    _info(X_MON_UNDEFINED)
  {
    _data.hyper_P = NULL;
  }

  /*!
   * Copy constructor.
   * \param arc The copied arc.
   */
  Conic_arc_2 (const Self & arc) :
    _r(arc._r), _s(arc._s), _t(arc._t), _u(arc._u), _v(arc._v), _w(arc._w),
    _orient(arc._orient),
    _conic_id(arc._conic_id),
    _source(arc._source),
    _target(arc._target),
    _info(arc._info)
  {
    // Copy the hyperbolic or circular data, if necessary.
    if ((arc._info & IS_HYPERBOLA) != 0)
    {
      _data.hyper_P = new Hyperbolic_arc_data (*(arc._data.hyper_P));
    }
    else if ((arc._info & IS_CIRCLE) != 0)
    {
      _data.circ_P = new Circular_arc_data (*(arc._data.circ_P));
    }
    else
    {
      _data.hyper_P = NULL;
    }
  }

  /*! 
   * Construct a conic arc which lies on the conic:
   *   C: r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0
   * \param orient The orientation of the arc (clockwise or couterclockwise).
   * \param source The source point.
   * \param target The target point.
   * \pre The source and the target must be on the conic boundary and must
   * not be the same.
   */
  Conic_arc_2 (const CfNT& r, const CfNT& s, const CfNT& t,
	       const CfNT& u, const CfNT& v, const CfNT& w,
	       const Orientation& orient,
	       const Point_2& source, const Point_2& target) :
    _r(r), _s(s), _t(t), _u(u), _v(v), _w(w),
    _source(source),
    _target(target),
    _info(X_MON_UNDEFINED)
  {
    // Make sure the conic contains the two end-points on its boundary.
    CGAL_precondition(_conic_has_on_boundary(source));
    CGAL_precondition(_conic_has_on_boundary(target));

    // Make sure that the source and the taget are not the same.
    CGAL_precondition(source != target);      

    // Set the arc properties (no need to compute the orientation).
    _orient = orient;
    _set (false);
  }

  /*! 
   * Construct a conic arc which is the full conic:
   *   C: r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0
   * \pre The conic C must be an ellipse (so 4rs - t^2 > 0).
   */
  Conic_arc_2 (const CfNT& r, const CfNT& s, const CfNT& t,
	       const CfNT& u, const CfNT& v, const CfNT& w) :
    _r(r), _s(s), _t(t), _u(u), _v(v), _w(w)
  {
    // Make sure the given curve is an ellipse.
    CGAL_precondition(CGAL_NTS compare(4*r*s - t*t, CfNT(0)) == LARGER);
        
    // Set the arc to be the full conic (and compute the orientation).
    _set_full (true);
  }

  /*!
   * Construct a conic arc from the given line segment, specified by its
   * end-points (x1,y1) and (x2, y2).
   */
  Conic_arc_2 (const CfNT& x1, const CfNT& y1,
	       const CfNT& x2, const CfNT& y2) :
    _source(CoNT(x1),CoNT(y1)),
    _target(CoNT(x2),CoNT(y2))
  {
    const CfNT _zero = 0;
    const CfNT _one = 1;

    // Make sure that the source and the taget are not the same.
    CGAL_precondition(_source != _target);      

    // The supporting conic is r=s=t=0, and u*x + v*y + w = 0 should hold
    // for both the source (x1,y1) and the target (x2, y2).
    if (CGAL_NTS compare (x1, x2) == EQUAL)
    {
      // The supporting conic is a vertical line, of the form x = CONST.
      _r = _zero;    _s = _zero;    _t =  _zero;
      _u = _one;
      _v = _zero;
      _w = -x1;
    }
    else
    {
      // The supporting line is A*x + B*y + C = 0, where:
      //
      //  A = y2 - y1,    B = x1 - x2,    C = x2*y1 - x1*y2 
      //
      _r = _zero;    _s = _zero;    _t =  _zero;
      _u = y2 - y1;
      _v = x1 - x2;
      _w = x2*y1 - x1*y2;
    }

    // The orientation is zero in case of a linear object.
    _orient = CGAL::COLLINEAR;

    // Set the arc properties (no need to compute the orientation).
    _set (false);
  }

  /*!
   * Set a circular arc that lies on the given circle:
   *   C: (x - x0)^2 + (y - y0)^2 = R^2
   * \param orient The orientation of the circle.
   * \param source The source point.
   * \param target The target point.
   * \pre The source and the target must be on the conic boundary and must
   * not be the same.
   */  
  Conic_arc_2 (const CfNT& x0, const CfNT& y0,
	       const CfNT& R,
	       const Orientation& orient,
	       const Point_2& source, const Point_2& target) :
    _source(source),
    _target(target),
    _info(X_MON_UNDEFINED)