conic_arc_2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 2,200 行 · 第 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.h,v $
// $Revision: 1.16 $ $Date: 2004/09/27 10:39:26 $
// $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.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(this->x(), p.x()));
  }

  // Compare the y coordinates.
  Comparison_result compare_y (const Self& p) const
  {
    return (CGAL_NTS compare(this->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: 
 * Int_kernel_ is a kernel that provides the input points or coefficients.
 *             Int_kernel_::FT must be of an integral type (e.g. CORE:BigInt).
 * Alg_kernel_ is a geometric kernel, where Kernel_::FT is the number type
 *             for the coordinates of points, which are algebraic numbers
 *             (preferably it is CORE::Expr).
 */

static int _conics_count = 0;

template <class Int_kernel_, class Alg_kernel_> class Arr_conic_traits_2;

template <class Int_kernel_, class Alg_kernel_>
class Conic_arc_2
{
protected:
  typedef Conic_arc_2<Int_kernel_, Alg_kernel_>  Self;
        
public:

  typedef Int_kernel_                  Int_kernel;
  typedef Alg_kernel_                  Alg_kernel;

  // Define objects from the integral kernel.
  typedef typename Int_kernel::FT        CfNT;
  typedef typename Int_kernel::Point_2   Int_point_2;
  typedef typename Int_kernel::Segment_2 Int_segment_2;
  typedef typename Int_kernel::Line_2    Int_line_2;
  typedef typename Int_kernel::Circle_2  Int_circle_2;

  // Define objects from the algebraic kernel.
  typedef typename Alg_kernel::FT        CoNT;   
  typedef Point_ex_2<Alg_kernel>         Point_2;
  
 protected:

  friend class Arr_conic_traits_2<Int_kernel, Alg_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_VERTICAL_SEGMENT = 128,
    IS_VALID = 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 arc a vertical segment.
                            // Bit 8     - Is the arc valid.

  // 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;
  };

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

  Hyperbolic_arc_data *_hyper_P;

  // 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),
    _hyper_P(NULL)
  {
    _info = (arc._info & DEGREE_MASK) | 
      X_MON_UNDEFINED;

    // Copy the hyperbolic or circular data, if necessary.
    if (arc._hyper_P != NULL)
      _hyper_P = new Hyperbolic_arc_data (*(arc._hyper_P));
    else
      _hyper_P = NULL;

    // Mark whether this is a vertical segment.
    if ((arc._info & IS_VERTICAL_SEGMENT) != 0)
    {
      _info = _info | IS_VERTICAL_SEGMENT;
    }

    // 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 (_orient != CGAL::COLLINEAR)
      {
        bool    legal_facing = _set_facing();

        CGAL_assertion (legal_facing);

        if (! legal_facing)
            // Invalid arc:
            return;
      }
    }
    else
    {
      _info = (_info & ~X_MON_UNDEFINED);
    }

    // Mark the arc as valid.
    _info = (_info | IS_VALID);
  }

 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),
    _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),
    _hyper_P(NULL)
  {
    // Copy the hyperbolic or circular data, if necessary.
    if (arc._hyper_P != NULL)
      _hyper_P = new Hyperbolic_arc_data (*(arc._hyper_P));
    else
      _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 r,s,t,u,v,w The coefficients of the supporting conic curve.
   * \param orient The orientation of the arc.
   * \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),
    _hyper_P(NULL)
  {
    // Make sure the conic contains the two end-points on its boundary.
    const bool    source_on_boundary = _conic_has_on_boundary(source);
    CGAL_precondition(source_on_boundary);

    const bool    target_on_boundary = _conic_has_on_boundary(target);
    CGAL_precondition(target_on_boundary);

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

    if (! (source_on_boundary && target_on_boundary && 
           source_not_equals_target))
    {
      // In this case, the arc is invalid.
      return;
    }

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

  /*! 
   * Construct a conic arc which lies on the conic curve:
   *   C: r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0 ,
   * and whose endpoints are given by the intersections of C with a given line,
   * such that the arc lies on the positive half-plane defined by l.
   * \param r,s,t,u,v,w The coefficients of the supporting conic curve.
   * \param l The intersecting line.
   * \pre The line must have two intersection points with the conic curve.
   */
  Conic_arc_2 (const CfNT& r, const CfNT& s, const CfNT& t,
               const CfNT& u, const CfNT& v, const CfNT& w,
               const Int_line_2& l) :
    _r(r), _s(s), _t(t), _u(u), _v(v), _w(w),
    _info(X_MON_UNDEFINED),
    _hyper_P(NULL)
  {
    // Make sure that the curve is of degree 2.
    const bool      has_degree_2 = (CGAL_NTS compare(r, 0) != EQUAL || 
                                    CGAL_NTS compare(s, 0) != EQUAL ||
                                    CGAL_NTS compare(t, 0) != EQUAL);

    CGAL_precondition (has_degree_2);

    if (! has_degree_2)
      // In this case, the arc is invalid.
      return;

    // Find the intersection points with the line l: a*x + b*y + c = 0.
    const CfNT   a = l.a();
    const CfNT   b = l.b();
    const CfNT   c = l.c();
    Point_2      pmid;
    bool         found_two_intersection_points;

    if (CGAL_NTS compare(b, 0) != EQUAL)
    {
      // Find the x-coordinates of the intersection points of the conic curve
      // and the line y = -(a*x + c) / b:
      CoNT      xs[2];
      int       n_xs;

      n_xs = solve_quadratic_eq<CfNT,CoNT> (b*b*r + a*(a*s - b*t),
                                            2*a*c*s - b*(c*t + a*v + b*u),
                                            s*c*c + b*(b*w - c*v),