sweep_line_event.h

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

      m_rightCurves->insert(iter, curve);
    }
  }
  

  /*! Returns an iterator to the first curve to the left of the event */
  SubCurveIter left_curves_begin() {
    return m_leftCurves->begin();
  }

  /*! Returns an iterator to the one past the last curve to the left 
      of the event */
  SubCurveIter left_curves_end() {
    return m_leftCurves->end();
  }

  /*! Returns an iterator to the first curve to the right of the event */
  SubCurveIter right_curves_begin() {
    return m_rightCurves->begin();
  }

  /*! Returns an iterator to the one past the last curve to the right 
      of the event */
  SubCurveIter right_curves_end() {
    return m_rightCurves->end();
  }

  /*! Returns the number of intersecting curves that are defined
      to the right of the event point. */
  int get_num_right_curves() {
    return m_rightCurves->size();
  }

  /*! Returns the number of intersecting curves that are defined
      to the left of the event point. */
  int get_num_left_curves() {
    return m_leftCurves->size();
  }

  /*! Returns true if at least one intersecting curve is defined to 
      the left of the point. */
  bool has_left_curves() {
    return !m_leftCurves->empty();
  }

  /*! Returns the actual point of the event */
  const Point_2 &get_point() {
    return m_point;
  }

  /*! 
    @return returns true if at least one of the curves passign 
    through the event is vertical.
  */
  bool does_contain_vertical_curve() const {
    return !m_verticalCurves.empty();
  }


  /*!returns the list of vertical curves passing through the event point.
    @return a reference to the list of curves.
  */
  VerticalCurveList &get_vertical_curves() {
    return m_verticalCurves;
  }


  /*! Insert a new intersection point on any of the vertical curves.
   *  The list of points is sorted by their y values.              <br>
   *  If the requireSort flag is true, the appripriate place in the list 
   *  is searched for. If not, the point is assumed to have the largest y 
   *  value, and is inserted at the end of the list.               <br>
   *  If the pioint already exists, the point is not inserted again.
   *  @param p a reference to the point
   *  @param requireSort false if the point is to be added at the end
   *  of the list.
   *  
   */
  void add_vertical_curve_x_point(const Point_2 &p, bool requireSort=false) 
  {
    m_verticalCurveXPoints->insert(p);
  }
	  /*
    if ( m_verticalCurveXPoints.empty() ) 
    {
      m_verticalCurveXPoints.push_back(p); 
      return;
    }

    if ( !requireSort ) 
    {
      if (!m_traits->point_equal(p, m_verticalCurveXPoints.back())) {
	m_verticalCurveXPoints.push_back(p);
      }
    } else
    {
      VerticalXPointSetIter iter = m_verticalCurveXPoints.begin();
      while ( iter != m_verticalCurveXPoints.end() )
      {
	if ( m_traits->compare_xy(*iter, p) == SMALLER )
	  ++iter; 
	else
	  break;
      }
      if ( iter == m_verticalCurveXPoints.end() )
	m_verticalCurveXPoints.push_back(p);
      else if (!m_traits->point_equal(p, *iter)) {
	m_verticalCurveXPoints.insert(iter, p);
      }
    }
  }
  */

  /*! 
   *  Returns a referece to the list of intersection points on the 
   * vertical curves passign through the event. If no vertical curves 
   * pass through the event or no intersection curves exist, the list 
   * will be empty.
   * @return a reference to the list of points.
   */
  VerticalXPointSet &get_vertical_x_point_list() {
    return *m_verticalCurveXPoints;
  }

  /*! Mark the event as an intersection point at an interior of a curve.
   */
  void mark_internal_intersection_point() {
    m_isInternalIntersectionPoint = true;
  }

  /*!
    @return returns true if the event is an intersection point at the 
    interior of at least one of the curves passing throuogh the event 
    point.
   */
  bool is_internal_intersection_point() const {
    return m_isInternalIntersectionPoint;
  }

  /*! 
    @return true if the any two curves in the event overlap, false otherwise.
  */
  bool does_contain_overlap() const {
    return m_containsOverlap;
  }

#ifndef NDEBUG
  void Print();
  void PrintVerticalXPoints();
#endif
 
protected:

  /*! Whenever a new curve is added to the event at the initialization 
   * stage, the right most end point to the left of the event point is 
   * updated.
   * Precondition: the event is either the source or destination of the curve.
   * @param curve a pointer to a new curve added to the event.
   */
  void update_rightmost_point(SubCurve *curve)
  {
    if ( curve->is_source_left_to_target())
    {
      if ( curve->is_target(m_point) )
	if ( m_traits->compare_x(curve->get_source(), 
				 m_rightmostPointToLeft) == LARGER )
	  m_rightmostPointToLeft = curve->get_source();
    } else
    {
      if ( curve->is_source(m_point) )
	if ( m_traits->compare_x(curve->get_target(), 
				 m_rightmostPointToLeft) == LARGER )
	  m_rightmostPointToLeft = curve->get_target();
    }
  }




  


  /*! The point of the event */
  Point_2 m_point;

  /*! A pointer to a traits class */
  Traits *m_traits;

  /*! A list of curves on the left side of the event, sorted by their y value
      to the left of the point */
  SubcurveContainer *m_leftCurves;

  /*! A list of curves on the right side of the event, sorted by their y value
      to the right of the point */
  SubcurveContainer *m_rightCurves;

  /*! The rightmost curve end point that is to the left of the event
      point. This point is used as a reference point when curves are compared
      to the left of the event point. 
  */
  Point_2 m_rightmostPointToLeft;

  /*! An indication whether this event has been initialized. The event is
      initialized after the first curve has been added to the left of the 
      event. 
  */
  bool m_isInitialized;

  /*! a list of vertical curves going through this event */
  VerticalCurveList m_verticalCurves; 

  /*! a list of intersection points on the vertical curves */
  VerticalXPointSet* m_verticalCurveXPoints;

  /*! a flag that inidcates whether the event is an "interior" intersection 
      point, or just an end point of all curves passing through it.
  */
  bool m_isInternalIntersectionPoint;

  /*! true if any two curves passing through the event overlap. */
  bool m_containsOverlap;

  const Point_2 &largest_point(const Point_2 &p1, const Point_2 &p2)
  {
    if ( m_traits->compare_x(p1, p2) == LARGER )
      return p1;
    return p2;
  }

#ifndef NDEBUG
public:
  int id;
#endif
  
};





#ifndef NDEBUG
template<class SweepLineTraits_2, class CurveWrap>
void 
Sweep_line_event<SweepLineTraits_2, CurveWrap>::
Print() 
{
  std::cout << "\tEvent id: " << id << "\n" ;
  std::cout << "\t" << m_point << "\n" ;
  std::cout << "\tLeft curves: \n" ;
  for ( SubCurveIter iter = m_leftCurves->begin() ;
	iter != m_leftCurves->end() ; ++iter )
  {
    std::cout << "\t";
    (*iter)->Print();
    std::cout << "\n";
  }
  std::cout << std::endl;
  std::cout << "\tRight curves: \n" ;
  for ( SubCurveIter iter1 = m_rightCurves->begin() ;
	iter1 != m_rightCurves->end() ; ++iter1 )
  {
    std::cout << "\t";
    (*iter1)->Print();
    std::cout << "\n";
  }
  std::cout <<"\tVertical curves: \n" ;
  for( VerticalCurveListIter iter2 = m_verticalCurves.begin() ; 
       iter2 != m_verticalCurves.end() ; 
       ++iter2)
  {
    std::cout<<"\t";
    (*iter2)->Print();
    std::cout<<"\n";
  }
  std::cout << std::endl;
}

template<class SweepLineTraits_2, class CurveWrap>
void 
Sweep_line_event<SweepLineTraits_2, CurveWrap>::
PrintVerticalXPoints()
{
  std::cout << "Vertical intersection points for " << m_point << ":\n";
  typename std::list<Point_2>::iterator iter = m_verticalCurveXPoints->begin();
  while ( iter != m_verticalCurveXPoints->end() )
  {
    std::cout << "\t" << *iter << "\n";
    ++iter;
  }
}
 
#endif // NDEBUG

CGAL_END_NAMESPACE

#endif // CGAL_SWEEP_LINE_EVENT_H