circle_segment_2.h

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

  /*!
   * Get the orientation of the curve. 
   * \return COLLINEAR in case of a line segment,
   *         CLOCKWISE or COUNTERCLOCKWISE for circular curves.
   */
  inline Orientation orientation () const
  {
    return (_orient);
  }

  /*! Check if the arc is linear. */
  inline bool is_linear () const
  {
    return (_orient == COLLINEAR);
  }

  /*! Check if the arc is circular. */
  inline bool is_circular () const
  {
    return (_orient != COLLINEAR);
  }

  /*!
   * Get the supporting line.
   * \pre The curve orientation is COLLINEAR.
   */
  const Line_2& supporting_line () const
  {
    CGAL_precondition (_orient == COLLINEAR);
    return (_line);
  }

  /*!
   * Get the supporting circle.
   * \pre The curve orientation is not COLLINEAR.
   */
  const Circle_2& supporting_circle () const
  {
    CGAL_precondition (_orient != COLLINEAR);
    return (_circ);
  }

  /*! Check if the curve is a full circle. */
  bool is_full () const
  {
    return (_is_full);
  }

  /*!
   * Get the source point.
   * \pre The curve is not a full circle.
   */
  const Point_2& source () const
  {
    CGAL_precondition (! _is_full);
    return (_source);
  }

  /*!
   * Get the target point.
   * \pre The curve is not a full circle.
   */
  const Point_2& target () const
  {
    CGAL_precondition (! _is_full);
    return (_target);
  }

  /*!
   * Get the vertical tangency points the arc contains.
   * \param vpts Output: The vertical tagnecy points.
   * \pre The curve is circular.
   * \return The number of points (0, 1, or 2).
   */
  unsigned int vertical_tangency_points (Point_2 *vpts) const
  {
    CGAL_precondition (_orient != COLLINEAR);
    unsigned int  n_vpts = 0;

    if (_is_full)
    {
      // In case of a full circle, create both vertical tangency points:
      const NT&     x0 = _circ.center().x();
      const NT&     y0 = _circ.center().y();
      CoordNT       xv_left;
      CoordNT       xv_right;

      if (_has_radius)
      {
        // In case the radius is explicitly given:
        xv_left = CoordNT (x0 - _radius);
        xv_right = CoordNT (x0 + _radius);
      }
      else
      {
        // In case only the squared root is given:
        xv_left = CoordNT (x0, -1, _circ.squared_radius());
        xv_right = CoordNT (x0, 1, _circ.squared_radius());
      }

      vpts[0] = Point_2 (xv_left, y0);
      vpts[1] = Point_2 (xv_right, y0);
      return (2);
    }

    if (_orient == COUNTERCLOCKWISE)
    {
      // Compute the vertical tangency points for the arc:
      n_vpts = _ccw_vertical_tangency_points (_source, _target, vpts);
    }
    else
    {
      // Compute the vertical tangency points for the opposite arc:
      n_vpts = _ccw_vertical_tangency_points (_target, _source, vpts);

      // Swap their order, if necessary.
      if (n_vpts == 2)
      {
        Point_2   temp = vpts[0];
        vpts[0] = vpts[1];
        vpts[1] = temp;
      }
    }

    return (n_vpts);
  }

private:

  /*!
   * Get the vertical tangency points the arc contains, assuming it is
   * counterclockwise oreinted.
   * \param vpts Output: The vertical tagnecy points.
   * \return The number of points (0, 1, or 2).
   */
  unsigned int _ccw_vertical_tangency_points (const Point_2& src,
                                              const Point_2& trg,
                                              Point_2 *vpts) const
  {
    unsigned int  n_vpts = 0;
    const NT&     x0 = _circ.center().x();
    const NT&     y0 = _circ.center().y();
    int           qs = _quart_index (src);
    int           qt = _quart_index (trg);
  
    if (qs == qt)
    {
      if ((qs == 0 || qs == 1) && CGAL::compare (src.x(), trg.x()) == LARGER)
        // We have an x-monotone arc lying on the upper half of the circle:
        return (0);
      
      if ((qs == 2 || qs == 3) && CGAL::compare (src.x(), trg.x()) == SMALLER)
        // We have an x-monotone arc lying on the lower half of the circle:
        return (0);
    }

    // Make sure the target quarter is larger than the source quarter, by 
    // adding 4 to its index, if necessary.
    if (qt <= qs)
      qt += 4;

    // Start traversing the quarter-planes and collect the vertical tangency
    // points we encounter.
    while (qs < qt)
    {
      if ((qs % 4) == 1)
      {
        // We collect the left tangency point when going from Q[1] to Q[2]:
        if (CGAL::compare (x0, trg.x()) != LARGER ||
            CGAL::compare (y0, trg.y()) != EQUAL)
        {
          if (_has_radius)
            vpts[n_vpts] = Point_2 (CoordNT (x0 - _radius), y0);
          else
            vpts[n_vpts] = Point_2 (CoordNT (x0, -1, _circ.squared_radius()),
                                             y0);

          n_vpts++;
        }
      }
      else if ((qs % 4) == 3)
      {
        // We collect the right tangency point when going from Q[3] to Q[0]:
        if (CGAL::compare (x0, trg.x()) != SMALLER ||
            CGAL::compare (y0, trg.y()) != EQUAL)
        {
          if (_has_radius)
            vpts[n_vpts] = Point_2 (CoordNT (x0 + _radius), y0);
          else
            vpts[n_vpts] = Point_2 (CoordNT (x0, 1, _circ.squared_radius()),
                                             y0);
          n_vpts++;
        }
      }

      qs++;
    }

    return (n_vpts);
  }

  /*!
   * Get the index of the quarter-plane containing the given point,
   * where the circle center is considered to be the origin.
   */
  int _quart_index (const Point_2& p) const
  {
    // The plane looks like:
    //
    //      Q[1] :  |   Q[0]:
    //      x <= 0  |   x >  0
    //      y >  0  |   y >= 0
    //    ----------+-----------
    //      Q[2] :  |   Q[3]:
    //      x <  0  |   x >= 0
    //      y <= 0  |   y <  0
    //
    const CGAL::Sign   sign_x = CGAL::sign (p.x() - _circ.center().x());
    const CGAL::Sign   sign_y = CGAL::sign (p.y() - _circ.center().y());

    if (sign_x == POSITIVE)
    {
      return ((sign_y == NEGATIVE) ? 3 : 0);
    }
    else if (sign_x == NEGATIVE)
    {
      return ((sign_y == POSITIVE) ? 1 : 2);
    }

    CGAL_assertion (sign_y != ZERO);
    return ((sign_y == POSITIVE) ? 1 : 3);
  }
};

/*!
 * Exporter for line segments and circular arcs.
 */
template <class Kernel, bool Filter>
std::ostream& 
operator<< (std::ostream& os, 
            const _Circle_segment_2<Kernel, Filter>& c)
{
  if (c.orientation() == COLLINEAR)
  {
    os<< "segment: " << c.source() << " -> " << c.target() << std::endl;
  }
  else
  {
    if(!c.is_full())
    {
      os << "circular arc: " << c.supporting_circle() << ' '
         << c.source() << " -> " << c.target() << std::endl;
    }
    else
    {
      os << "circular arc: " << c.supporting_circle()<<std::endl;
    }
  }

  return (os);
}

/*! \class
 * Representation of an x-monotone circular arc.
 */
template <class Kernel_, bool Filter_>
class _X_monotone_circle_segment_2
{
public:

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

  // Type definition for the intersection points mapping.
  typedef std::pair<unsigned int, unsigned int>   Curve_id_pair;
  typedef std::pair<Point_2, unsigned int>        Intersection_point_2;
  typedef std::list<Intersection_point_2>         Intersection_list;

  /*!
   * \struct Less functor for Curve_id_pair.
   */
  struct Less_id_pair
  {
    bool operator() (const Curve_id_pair& ip1, const Curve_id_pair& ip2) const
    {
      // Compare the pairs of IDs lexicographically.
      return (ip1.first < ip2.first ||
              (ip1.first == ip2.first && ip1.second < ip2.second));
    }
  };

  typedef std::map<Curve_id_pair,
                   Intersection_list,
                   Less_id_pair>                  Intersection_map;
  typedef typename Intersection_map::value_type   Intersection_map_entry;
  typedef typename Intersection_map::iterator     Intersection_map_iterator;

protected:

  NT           _first;       // The x-coordinate of the circle center.
                             // Or: the coefficient of x in the line equation.

  NT           _second;      // The y-coordinate of the circle center.
                             // Or: the coefficient of y in the line equation.

  NT           _third;       // The squared radius of the supporting circle.
                             // Or: the free coefficient in the line equation.
  
  Point_2      _source;      // The source point.
  Point_2      _target;      // The target point.

  enum {
    IS_DIRECTED_RIGHT_MASK = 1,
    IS_VERTICAL_SEGMENT_MASK = 2,
    COUNTERCLOCKWISE_CODE = 4,
    CLOCKWISE_CODE = 8,
    ORIENTATION_MASK = 4 + 8,
    INDEX_SHIFT_BITS = 4
  };

  unsigned int _info;        // A bit vector, where:
                             // Bit 0 (the LSB): marks if the arc is directed
                             //                  from left to right.
                             // Bit 1: marks if the arc is a vertical segment.
                             // Bits 2-3: mark the orientation.
                             // The rest of the bits represent the curve index.

public:

  /*!
   * Default constructor.
   */
  _X_monotone_circle_segment_2 () :
    _first(), 
    _second(),
    _third(),
    _source(), _target(),
    _info (0)
  {}

  /*!
   * Construct an arc from a line segment.
   * \param line The supporting line.
   * \param source The source point.
   * \param target The target point.
   */
  _X_monotone_circle_segment_2 (const Line_2& line,
                                const Point_2& source, const Point_2& target,
                                unsigned int index = 0) :
    _first (line.a()),
    _second (line.b()),
    _third (line.c()),
    _source (source), 
    _target(target),
    _info (index << INDEX_SHIFT_BITS)
  {
    // Check if the segment is directed left or right:
    Comparison_result   res = CGAL::compare (source.x(), target.x());

    if (res == EQUAL)
    {
      CGAL_precondition (CGAL::sign(_second) == ZERO);

      // We have a vertical segment - compare the points by their
      // y-coordinates:
      _info = (_info | IS_VERTICAL_SEGMENT_MASK);
      res = CGAL::compare (source.y(), target.y());
    }

    CGAL_precondition (res != EQUAL);
    if (res == SMALLER)
      _info = (_info | IS_DIRECTED_RIGHT_MASK);
  }

  /*!
   * Construct a segment arc from two kernel points
   * \param source the source point.
   * \ param target the target point.
   * \pre source and target are not equal.
   */
  _X_monotone_circle_segment_2 (const typename Kernel::Point_2& source,
                                const typename Kernel::Point_2& target) :
    _source(source.x(), source.y()),
    _target(target.x(), target.y()),
    _info (0)
  {
    Line_2 line(source, target);
    _first  = line.a();
    _second = line.b();
    _third  = line.c();
    
    // Check if the segment is directed left or right:
    Comparison_result   res = CGAL::compare (source.x(), target.x());

    if (res == EQUAL)
    {
      CGAL_precondition (CGAL::sign(_second) == ZERO);

      // We have a vertical segment - compare the points by their
      // y-coordinates:
      _info = (_info | IS_VERTICAL_SEGMENT_MASK);
      res = CGAL::compare (source.y(), target.y());
    }

    CGAL_precondition (res != EQUAL);
    if (res == SMALLER)
      _info = (_info | IS_DIRECTED_RIGHT_MASK);
  }
     

  /*! 
   * Construct a circular arc.
   * \param line The supporting line.
   * \param source The source point.
   * \param target The target point.
   * \param orient The orientation of the arc.
   */
  _X_monotone_circle_segment_2 (const Circle_2& circ,
                                const Point_2& source, const Point_2& target,
                                Orientation orient,
                                unsigned int index = 0) :
    _first (circ.center().x()),
    _second (circ.center().y()),
    _third (circ.squared_radius()),
    _source (source), 
    _target(target),
    _info (index << INDEX_SHIFT_BITS)
  {
    // Check if the segment is directed left or right:
    Comparison_result   res = CGAL::compare (source.x(), target.x());

    CGAL_precondition (res != EQUAL);
    if (res == SMALLER)
      _info = (_info | IS_DIRECTED_RIGHT_MASK);

    // Set the orientation.
    CGAL_precondition (orient != COLLINEAR);
    if (orient == COUNTERCLOCKWISE)
      _info = (_info | COUNTERCLOCKWISE_CODE);
    else
      _info = (_info | CLOCKWISE_CODE);
  }

  /*! Check if the arc is linear. */
  inline bool is_linear () const
  {
    return ((_info & ORIENTATION_MASK) == 0);
  }

  /*! Check if the arc is circular. */
  inline bool is_circular () const
  {
    return ((_info & ORIENTATION_MASK) != 0);
  }