circle_segment_2.h

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

  /*!
   * Get the supporting line. 
   * \pre The arc is linear (a line segment).
   */
  Line_2 supporting_line () const
  {
    CGAL_precondition (is_linear());

    return (Line_2 (a(), b(), c()));
  }

  /*!
   * Get the supporting circle. 
   * \pre The arc is circular.
   */
  Circle_2 supporting_circle () const
  {
    CGAL_precondition (is_circular());

    typename Kernel::Point_2  center (x0(), y0());
    return (Circle_2 (center , sqr_r(), orientation()));
  }

  /*! Get the source point. */
  inline const Point_2& source () const
  {
    return (_source);
  }

  /*! Get the target point. */
  inline const Point_2& target () const
  {
    return (_target);
  }

  /*! Get the left endpoint of the arc. */
  inline const Point_2& left () const
  {
    return (((_info & IS_DIRECTED_RIGHT_MASK) != 0) ? _source : _target);
  }

  /*! Get the right endpoint of the arc. */
  inline const Point_2& right () const
  {
    return (((_info & IS_DIRECTED_RIGHT_MASK) != 0) ? _target : _source);
  }

  /*!
   * Check whether the given point is in the x-range of the arc.
   */
  bool is_in_x_range (const Point_2& p) const
  {
    Comparison_result    res = CGAL::compare (p.x(), left().x());

    if (res == SMALLER)
      return (false);
    else if (res == EQUAL)
      return (true);

    return (CGAL::compare (p.x(), right().x()) != LARGER);
  }

  /*! Check if the arc is a vertical segment. */
  inline bool is_vertical () const
  {
    return ((_info & IS_VERTICAL_SEGMENT_MASK) != 0);
  }

  /*! Get the orientation of the arc. */ 
  inline Orientation orientation() const
  {
    unsigned int   _or = (_info & ORIENTATION_MASK);

    if (_or == COUNTERCLOCKWISE_CODE)
      return (CGAL::COUNTERCLOCKWISE);
    else if (_or == CLOCKWISE_CODE)
      return (CGAL::CLOCKWISE);

    CGAL_assertion (_or == 0);
    return (CGAL::COLLINEAR);
  }

  /*!
   * Check the position of a given point with respect to the arc.
   */
  Comparison_result point_position (const Point_2& p) const
  {
    if (is_linear())
      return (_line_point_position (p));
    else
      return (_circ_point_position (p));
  }


  /*!
   * Compare the two arcs to the right of their intersection point.
   */
  Comparison_result compare_to_right (const Self& cv, const Point_2& p) const
  {
    if (is_linear())
    {
      if (cv.is_linear())
        return (_lines_compare_to_right (cv, p));
      
      Comparison_result   res = cv._circ_line_compare_to_right (*this, p);
      
      if (res != EQUAL)
        res = (res == SMALLER) ? LARGER : SMALLER;

      return (res);
    }
    else
    {
      if (cv.is_linear())
        return (_circ_line_compare_to_right (cv, p));

      return (_circs_compare_to_right (cv, p));
    }
  }

  /*!
   * Compare the two arcs to the left of their intersection point.
   */
  Comparison_result compare_to_left (const Self& cv, const Point_2& p) const
  {
    if (is_linear())
    {
      if (cv.is_linear())
        return (_lines_compare_to_left (cv, p));
      
      Comparison_result   res = cv._circ_line_compare_to_left (*this, p);
      
      if (res != EQUAL)
        res = (res == SMALLER) ? LARGER : SMALLER;

      return (res);
    }
    else
    {
      if (cv.is_linear())
        return (_circ_line_compare_to_left (cv, p));

      return (_circs_compare_to_left (cv, p));
    }
  }

  /*!
   * Check whether the two arcs have the same supporting curve.
   */
  bool has_same_supporting_curve (const Self& cv) const
  {
    // Check if the curve indices are the same.
    if (_index() != 0 && _index() == cv._index())
      return (true);

    // Make sure that the supporting curves are of the same type.
    if (is_linear() && ! cv.is_linear())
      return (false);

    if (! is_linear() && cv.is_linear())
      return (false);

    // Compare the curve coefficients.
    if (! is_linear())
    {
      // The two circles must have the same center and the same radius.
      return (CGAL::compare (x0(), cv.x0()) == EQUAL &&
              CGAL::compare (y0(), cv.y0()) == EQUAL &&
              CGAL::compare (sqr_r(), cv.sqr_r()) == EQUAL);
    }

    // Compare the line equations: Note that these may be scaled.
    NT    fact1;
    NT    fact2;

    if (is_vertical())
    {
      if (! cv.is_vertical())
        return (false);

      fact1 = a();
      fact2 = cv.a();
    }
    else
    {
      fact1 = b();
      fact2 = cv.b();
    }

    return (CGAL::compare (fact2*a(), fact1*cv.a()) == EQUAL &&
            CGAL::compare (fact2*b(), fact1*cv.b()) == EQUAL &&
            CGAL::compare (fact2*c(), fact1*cv.c()) == EQUAL);
  }

  /*!
   * Check if the two curves are equal.
   */
  bool equals (const Self& cv) const
  {
    if (! this->has_same_supporting_curve (cv))
      return (false);

    if (is_linear())
    {
      // In case of line segments we can swap the source and target:
      return ((_source.equals (cv._source) && _target.equals (cv._target)) ||
              (_source.equals (cv._target) && _target.equals (cv._source)));
    }

    // Once again, opposite circular arcs are considered to be equal:
    return ((orientation() == cv.orientation() &&
             _source.equals (cv._source) && _target.equals (cv._target)) ||
            (orientation() != cv.orientation() &&
             _source.equals (cv._target) && _target.equals (cv._source)));
  }

  /*!
   * Split the curve at a given point into two sub-arcs.
   */
  void split (const Point_2& p, Self& c1, Self& c2) const
  {
    // Copy the properties of this arc to the sub-arcs.
    c1 = *this;
    c2 = *this;

    // Change the endpoint, such that c1 lies to the right of c2:
    if (is_directed_right())
    {
      c1._target = p;
      c2._source = p;
    }
    else
    {
      c1._source = p;
      c2._target = p;
    }

    return;
  }

  /*!
   * Compute the intersections between the two arcs or segments.
   */
  template <class OutputIterator>
  OutputIterator intersect (const Self& cv, OutputIterator oi,
                            Intersection_map *inter_map = NULL) const
  {
    // First check whether the two arcs have the same supporting curve.
    if (has_same_supporting_curve (cv))
    {
      // Check for overlaps between the two arcs.
      Self    overlap;

      if (_compute_overlap (cv, overlap))
      {
        // There can be just a single overlap between two x-monotone arcs:
        *oi = CGAL::make_object (overlap);
        ++oi;
        return (oi);
      }

      // In case there is not overlap and the supporting curves are the same,
      // there cannot be any intersection points, unless the two arcs share
      // a common end point.
      // Note that in this case we do not define the multiplicity of the
      // intersection points we report.
      unsigned int  mult = 0;
      if (left().equals (cv.left()))
      {
        *oi = CGAL::make_object (std::make_pair (left(), mult));
        ++oi;
      }

      if (right().equals (cv.right()))
      {
        *oi = CGAL::make_object (std::make_pair (right(), mult));
        ++oi;
      }

      return (oi);
    }

    // Before computing the intersection points between the two supporting
    // curves, check if their intersection has already been computed and
    // cached.
    Curve_id_pair                id_pair;
    Intersection_map_iterator    map_iter;
    Intersection_list            inter_list;
    bool                         invalid_ids = false;

    if (inter_map != NULL && _index() != 0 && cv._index() != 0)
    {
      if (_index() < cv._index())
        id_pair = Curve_id_pair (_index(), cv._index());
      else
        id_pair = Curve_id_pair (cv._index(), _index());
      
      map_iter = inter_map->find (id_pair);
    }
    else
    {
      // In case one of the IDs is invalid, we do not look in the map neither
      // we cache the results.
      if (inter_map != NULL)
        map_iter = inter_map->end();
      invalid_ids = true;
    }

    if (inter_map == NULL || map_iter == inter_map->end())
    {
      // Compute the intersections points between the two supporting curves.
      if (is_linear())
      {
        if (cv.is_linear())
          _lines_intersect (cv, inter_list);
        else
          cv._circ_line_intersect (*this, inter_list);
      }
      else
      {
        if (cv.is_linear())
          _circ_line_intersect (cv, inter_list);
        else
          _circs_intersect (cv, inter_list);
      }

      // Cache the result.
      if (! invalid_ids)
        (*inter_map)[id_pair] = inter_list;
    }
    else
    {
      // Obtain the precomputed intersection points from the map.
      inter_list = (*map_iter).second;
    }

    // Report only the intersection points that lie on both arcs.
    typename Intersection_list::const_iterator   iter;

    for (iter = inter_list.begin(); iter != inter_list.end(); ++iter)
    {
      if (this->_is_between_endpoints (iter->first) &&
          cv._is_between_endpoints (iter->first))
      {
        *oi = CGAL::make_object (*iter);
        ++oi;
      }
    }

    return (oi);
  }

  /*!
   * Check whether it is possible to merge our arc with the given arc.
   */
  bool can_merge_with (const Self& cv) const
  {
    // In order to merge the two arcs, they should have the same supporting
    // curve.
    if (! this->has_same_supporting_curve (cv))
      return (false);

    // Check if the left endpoint of one curve is the right endpoint of the
    // other.
    return (right().equals (cv.left()) ||
            left().equals (cv.right()));
  }

  /*!
   * Merge our arc with the given arc.
   * \pre The two arcs are mergeable.
   */
  void merge (const Self& cv)
  {
    CGAL_precondition (this->can_merge_with (cv));

    // Check if we should extend the arc to the left or to the right.
    if (right().equals (cv.left()))
    {
      // Extend the arc to the right.
      if (is_directed_right())
        this->_target = cv.right();
      else
        this->_source = cv.right();
    }
    else
    {
      CGAL_precondition (left().equals (cv.right()));

      // Extend the arc to the left.
      if (is_directed_right())
        this->_source = cv.left();
      else
        this->_target = cv.left();
    }

    return;
  }


  /*! return true iff the arc is directed right lexicoraphically. */
  bool is_directed_right() const
  {
    return ((_info & IS_DIRECTED_RIGHT_MASK) != 0);
  }


  /*! construct an opposite arc. */
  Self construct_opposite() const
  {
    Self opp_cv;
    opp_cv._first = this->_first;
    opp_cv._second = this-> _second;
    opp_cv._third = this-> _third;
    opp_cv._source = this->_target;
    opp_cv._target = this->_source;

    // Take care of the information bits: We flip the orientation bits and
    // the bits that marks the direction.
    if (is_linear())
      opp_cv._info = (this->_info ^ IS_DIRECTED_RIGHT_MASK);
    else
      opp_cv._info = (this->_info ^ IS_DIRECTED_RIGHT_MASK ^ ORIENTATION_MASK);

    return (opp_cv);
  }

  Bbox_2 bbox() const
  {
    double x_min = to_double(left().x());
    double x_max = to_double(right().x());   
    double y_min = to_double(left().y()); 
    double y_max = to_double(right().y());
    if(y_min > y_max)
      std::swap(y_min, y_max);
    if(is_circular())
    {
      const Circle_2& circ = this->supporting_circle();
      if(_is_upper())
      {
        y_max = to_double(circ.center().y())+ 
                std::sqrt(to_double(circ.squared_radius()));
      }
      else
      {
        y_min = to_double(circ.center().y()) - 
                std::sqrt(to_double(circ.squared_radius()));
      }
    }

    
    return Bbox_2(x_min, y_min, x_max, y_max);
  }

protected:

  /*! Get the curve index. */
  inline unsigned int _index () const
  {
    return (_info >> INDEX_SHIFT_BITS);
  }