circle_segment_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/Circle_segment_2.h $
// $Id: Circle_segment_2.h 39311 2007-07-05 12:44:29Z golubevs $
// 
//
// Author(s)     : Ron Wein        <[e-mail]>
//                 Baruch Zukerman <[e-mail]>

#ifndef CGAL_CIRCULAR_ARC_2_H
#define CGAL_CIRCULAR_ARC_2_H

/*! \file
 * Header file for the _Circle_segment_2<Kernel, Filter> class.
 */
#include <CGAL/Arr_traits_2/One_root_number.h>
#include <CGAL/Bbox_2.h>
#include <CGAL/Handle_for.h>
#include <list>
#include <map>
#include <ostream>

CGAL_BEGIN_NAMESPACE

// Forward declaration:
template <class NumberType_, bool Filter_> class _One_root_point_2;

/*! \class
 * Representation of a point whose coordinates are one-root numbers.
 */
template <class NumberType_, bool Filter_>
class _One_root_point_2_rep //: public Ref_counted
{
  friend class _One_root_point_2<NumberType_, Filter_>;

public:

  typedef NumberType_                             NT;
  typedef _One_root_point_2_rep<NT, Filter_>      Self;
  typedef _One_root_number<NT, Filter_>           CoordNT;

private:

  CoordNT       _x;            // The coordinates.
  CoordNT       _y;

public:

  /*! Default constructor. */
  _One_root_point_2_rep () :
    _x (0),
    _y (0)
  {}

  /*! Constructor of a point with rational coefficients. */
  _One_root_point_2_rep (const NT& x, const NT& y) :
    _x (x),
    _y (y)
  {}

  /*! Constructor of a point with one-root coefficients. */
  _One_root_point_2_rep (const CoordNT& x, const CoordNT& y) :
    _x (x),
    _y (y)
  {}
};

/*! \class
 * A handle for a point whose coordinates are one-root numbers.
 */
template <class NumberType_, bool Filter_>
class _One_root_point_2 :
  public Handle_for<_One_root_point_2_rep<NumberType_, Filter_> >
{
public:

  typedef NumberType_                           NT;
  typedef _One_root_point_2<NT, Filter_>        Self;

private:

  typedef _One_root_point_2_rep<NT, Filter_>    Point_rep;
  typedef Handle_for<Point_rep>                 Point_handle;

public:

  typedef typename Point_rep::CoordNT           CoordNT;

  /*! Default constructor. */
  _One_root_point_2 () :
    Point_handle (Point_rep())
  {}

  /*! Copy constructor. */
  _One_root_point_2 (const Self& p) :
    Point_handle (p)
  {}

  /*! Constructor of a point with rational coefficients. */
  _One_root_point_2 (const NT& x, const NT& y) :
    Point_handle (Point_rep (x, y))
  {}

  /*! Constructor of a point with one-root coefficients. */
  _One_root_point_2 (const CoordNT& x, const CoordNT& y) :
    Point_handle (Point_rep (x, y))
  {}

  /*! Get the x-coordinate. */
  const CoordNT& x () const
  {
    return (this->ptr()->_x);
  }

  /*! Get the y-coordinate. */
  const CoordNT& y () const
  {
    return (this->ptr()->_y);
  }

  /*! Check for equality. */
  bool equals (const Self& p) const
  {
    if (this->identical (p))
      return (true);

    return (CGAL::compare (this->ptr()->_x, p.ptr()->_x) == EQUAL &&
            CGAL::compare (this->ptr()->_y, p.ptr()->_y) == EQUAL);
  }
/*
  bool operator != (const Self& p) const
  {
    return !equals(p);
  }
*/
  /*! Set the point coordinates. */
  void set (const NT& x, const NT& y)
  {
    this->copy_on_write();
    this->ptr()->_x = CoordNT (x);
    this->ptr()->_y = CoordNT (y);
    return;
  }

  /*! Set the point coordinates. */
  void set (const CoordNT& x, const CoordNT& y)
  {
    this->copy_on_write();
    this->ptr()->_x = x;
    this->ptr()->_y = y;
    return;
  }
};

/*!
 * Exporter for conic arcs.
 */
template <class NT, bool Filter>
std::ostream&
operator<< (std::ostream& os,
            const _One_root_point_2<NT, Filter>& p)
{
  os << CGAL::to_double(p.x()) << ' ' << CGAL::to_double(p.y());
  return (os);
}

/*
template <class NT, bool Filter>
std::istream & operator >> (std::istream & is, 
                            _One_root_point_2<NT, Filter>& p)
{
  typename _One_root_point_2<NT, Filter>::CoordNT ort1,ort2;
  is >> ort1 >> ort2;
  p=_One_root_point_2<NT, Filter>(ort1,ort2);
  return is;
}
*/

/*! \class
 * Representation of a circle, a circular arc or a line segment.
 */
template <class Kernel_, bool Filter_>
class _Circle_segment_2
{
public:

  typedef Kernel_                                          Kernel;
  typedef typename Kernel::FT                              NT;
  typedef _One_root_point_2<NT, Filter_>                   Point_2;
  typedef typename Kernel::Circle_2                        Circle_2;
  typedef typename Kernel::Segment_2                       Segment_2;
  typedef typename Kernel::Line_2                          Line_2;

private:

  typedef typename Point_2::CoordNT                        CoordNT;

  // Data members:
  Line_2        _line;        // The supporting line (for line segments).
  Circle_2      _circ;        // The supporting circle (for circular arcs).
  bool          _is_full;     // Whether we have a full circle.
  bool          _has_radius;  // Is the radius (not just the squared radius)
                              // explicitly specified).
  NT            _radius;      // The radius, in case it is specified.
  Point_2       _source;      // The source point.
  Point_2       _target;      // The target point.
  Orientation   _orient;      // The orientation (COLLINEAR for line segments).

public:

  /*! Default constructor. */
  _Circle_segment_2 () :
    _is_full (false),
    _has_radius (false),
    _orient (COLLINEAR)
  {}

  /*!
   * Constructor from a line segment.
   * \param seg The segment.
   */
  _Circle_segment_2 (const Segment_2& seg) :
    _line (seg),
    _is_full (false),
    _has_radius (false),
    _source (seg.source().x(), seg.source().y()),
    _target (seg.target().x(), seg.target().y()),
    _orient (COLLINEAR)
  {}

  /*!
  * Constructor from of a line segment.
   * \param ps The source point.
   * \param pt The target point.
   */
  _Circle_segment_2 (const typename Kernel::Point_2& ps,
                     const typename Kernel::Point_2& pt) :
    _line (ps, pt),
    _is_full (false),
    _has_radius (false),
    _source (ps.x(), ps.y()),
    _target (pt.x(), pt.y()),
    _orient (COLLINEAR)
  {}

  /*!
   * Constructor of a segment, given a supporting line and two endpoints,
   * which need not necessarily have rational coordinates.
   * \param line The supporting line.
   * \param source The source point.
   * \param target The target point.
   * \pre Both endpoints lie on the supporting line.
   */
  _Circle_segment_2 (const Line_2& line,
                     const Point_2& source, const Point_2& target) :
    _line (line),
    _is_full (false),
    _has_radius (false),
    _source (source),
    _target (target),
    _orient (COLLINEAR)
  {
    CGAL_precondition (CGAL::compare (source.x()*line.a() + line.c(),
                                      -source.y()*line.b()) == EQUAL);

    CGAL_precondition (CGAL::compare (target.x()*line.a() + line.c(),
                                      -target.y()*line.b()) == EQUAL);
  }

  /*!
   * Constructor from a circle.
   * \param circ The circle.
   */
  _Circle_segment_2 (const Circle_2& circ) :
    _circ (circ),
    _is_full (true),
    _has_radius (false),
    _orient (circ.orientation())
  {
    CGAL_assertion (_orient != COLLINEAR);
  }

  /*!
   * Constructor from a circle.
   * \param c The circle center.
   * \param r The radius.
   * \param orient The orientation of the circle.
   */
  _Circle_segment_2 (const typename Kernel::Point_2& c,
                     const NT& r,
                     Orientation orient = COUNTERCLOCKWISE) :
    _circ (c, r*r, orient),
    _is_full (true),
    _has_radius (true),
    _radius (r),
    _orient (orient)
  {
    CGAL_assertion (orient != COLLINEAR);
  }

  /*!
   * Constructor of a circular arc, given a supporting circle and two
   * endpoints, which need not necessarily have rational coordinates.
   * The orientation of the circle determines the orientation of the arc.
   * \param circ The supporting circle.
   * \param source The source point.
   * \param target The target point.
   * \pre Both endpoints lie on the supporting circle.
   */
  _Circle_segment_2 (const Circle_2& circ,
                     const Point_2& source, const Point_2& target) :
    _circ (circ),
    _is_full (false),
    _has_radius (false),
    _source (source),
    _target (target),
    _orient (circ.orientation())
  {
    CGAL_assertion (_orient != COLLINEAR);

    CGAL_precondition
      (CGAL::compare (CGAL::square (source.x() - circ.center().x()),
                      circ.squared_radius() -
                      CGAL::square (source.y() - circ.center().y())) == EQUAL);

    CGAL_precondition
      (CGAL::compare (CGAL::square (target.x() - circ.center().x()),
                      circ.squared_radius() -
                      CGAL::square (target.y() - circ.center().y())) == EQUAL);
  }

  /*!
   * Constructor of a circular arc, given a supporting circle and two
   * endpoints, which need not necessarily have rational coordinates.
   * \param c The circle center.
   * \param r The radius.
   * \param orient The orientation of the circle.
   * \param source The source point.
   * \param target The target point.
   * \pre Both endpoints lie on the supporting circle.
   */
  _Circle_segment_2 (const typename Kernel::Point_2& c,
                     const NT& r, Orientation orient,
                     const Point_2& source, const Point_2& target) :
    _circ (c, r*r, orient),
    _is_full (false),
    _has_radius (true),
    _radius (r),
    _source (source),
    _target (target),
    _orient (orient)
  {
    CGAL_assertion (orient != COLLINEAR);

    CGAL_precondition
      (CGAL::compare (CGAL::square (source.x() - c.x()),
                      CGAL::square (r) -
                      CGAL::square (source.y() - c.y())) == EQUAL);

    CGAL_precondition
      (CGAL::compare (CGAL::square (target.x() - c.x()),
                      CGAL::square (r) -
                      CGAL::square (target.y() - c.y())) == EQUAL);
  }

  /*!
   * Constructor of a circular arc, from the given three points, in case of
   * three collinear points, a segment will be constructed.            
   * \param p1 The arc source.
   * \param p2 A point in the interior of the arc.
   * \param p3 The arc target.
   * \pre p1 and p3 are not equal.
   */
   _Circle_segment_2 (const typename Kernel::Point_2& p1,
                      const typename Kernel::Point_2& p2,
                      const typename Kernel::Point_2& p3) :
     _is_full(false),
     _has_radius(false),
     _source(p1.x(), p1.y()),
     _target(p3.x(), p3.y())
  {
    // Set the source and target.
    NT          x1 = p1.x();
    NT          y1 = p1.y();
    NT          x2 = p2.x();
    NT          y2 = p2.y();
    NT          x3 = p3.x();
    NT          y3 = p3.y();

  
    // Make sure that the source and the taget are not the same.
    CGAL_precondition (Kernel().compare_xy_2_object() (p1, p3) != EQUAL);

    // Compute the lines: A1*x + B1*y + C1 = 0,
    //               and: A2*x + B2*y + C2 = 0,
    // where:
    const NT  _two  = 2;

    const NT  A1 = _two*(x1 - x2);
    const NT  B1 = _two*(y1 - y2);
    const NT  C1 = CGAL::square(y2) - CGAL::square(y1) + 
                   CGAL::square(x2) - CGAL::square(x1);

    const NT  A2 = _two*(x2 - x3);
    const NT  B2 = _two*(y2 - y3);
    const NT  C2 = CGAL::square(y3) - CGAL::square(y2) +
                   CGAL::square(x3) - CGAL::square(x2);

    // Compute the coordinates of the intersection point between the
    // two lines, given by (Nx / D, Ny / D), where:
    const NT  Nx = B1*C2 - B2*C1;
    const NT  Ny = A2*C1 - A1*C2;
    const NT  D = A1*B2 - A2*B1;

    // Make sure the three points are not collinear.
    const bool  points_collinear = (CGAL::sign (D) == ZERO);

    if (points_collinear)
    {
      _line  = Line_2(p1, p3);
      _orient = COLLINEAR;
      return;
    }

    // The equation of the underlying circle is given by:
    
    NT x_center = Nx / D;
    NT y_center = Ny / D;

    typename Kernel::Point_2 circ_center(x_center, y_center);


    
    NT sqr_rad = (CGAL::square(D*x2 - Nx) + CGAL::square(D*y2 - Ny)) / 
                 CGAL::square(D);

    // Determine the orientation: If the mid-point forms a left-turn with
    // the source and the target points, the orientation is positive (going
    // counterclockwise).
    // Otherwise, it is negative (going clockwise).
    Kernel                         ker;
    typename Kernel::Orientation_2 orient_f = ker.orientation_2_object();
 
    if (orient_f(p1, p2, p3) == LEFT_TURN)
      _orient = COUNTERCLOCKWISE;
    else
      _orient = CLOCKWISE;

     _circ = Circle_2(circ_center, sqr_rad, _orient);
  }