sweep_line_2_impl.h

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

  void handle_left_curves(OutpoutIterator out, SweepLineGetPoints &tag)
  {
    SL_DEBUG(std::cout << "Handling left curve" << std::endl;)
    SL_DEBUG(m_currentEvent->Print();)
    const Point_2 &eventPoint = m_currentEvent->get_point();
    if ( !m_currentEvent->has_left_curves())
    {
      if (m_includeEndPoints || 
	  m_currentEvent->is_internal_intersection_point())
      {
	SL_DEBUG(std::cout << "Reporting point (2): " << eventPoint << "\n";)
	  //*out = eventPoint; ++out;    
	add_point_to_output(eventPoint, out);
	m_found_intersection = true;
      }
      return;
    }

    // delete the curve from the status line
    EventCurveIter leftCurveIter = m_currentEvent->left_curves_begin();
    m_currentPos = m_prevPos;
    m_use_hint_for_erase = false;
    while ( leftCurveIter != m_currentEvent->left_curves_end() )
    {
      // before deleting check new neighbors that will become after deletion
      remove_curve_from_status_line(*leftCurveIter);
      m_use_hint_for_erase = true;
      PRINT_ERASE((*leftCurveIter));
      m_currentPos = m_prevPos;
      Subcurve *leftCurve = *leftCurveIter; 
      leftCurve->set_last_point(eventPoint);
      ++leftCurveIter;
    }

    if ( m_includeEndPoints || 
	 m_currentEvent->is_internal_intersection_point() )
    {	
      SL_DEBUG(std::cout << "Reporting point (3): " << eventPoint << "\n";)
      //*out = eventPoint; ++out;
      add_point_to_output(eventPoint, out);
      m_found_intersection = true;
    }
  }

  
#ifndef NDEBUG
  void PrintEventQueue();
  void PrintSubCurves();
  void PrintStatusLine();
  void PrintVerticals();
#endif

protected:
  /*! a pointer to a traits object */
  Traits *m_traits;

  /*! an indication to whether the traits should be deleted in the distructor
   */
  bool m_traitsOwner;

  /*! if false, overlapping subcurves are reported only one. 
    Otherwise, they are reported as many times as they appeard. */
  bool m_overlapping;

  /*! if true, end points are reported as intersection points */
  bool m_includeEndPoints;

  /*! this is true when get_intersection_points() is called */
  bool m_stop_at_first_int;

  /*! used to hold all event, processed or not, so that they can 
`     all be deleted at the end */
  EventPtrContainer m_events; 

  /*! the queue of events (intersection points) to handle */
  EventQueue *m_queue;

  /*! The subcurves, as created on the fly */
  SubCurveList m_subCurves;

  /*! The status line */
  StatusLine *m_statusLine;

  /*! a struct that holds params associated with the curve compare functor */
  CompareParams *m_comp_param;

  /*! A reference point that is used for comapring curves. It is used
      when inserting/erasing curves from the status line. */
  Point_2 m_currentPos;

  /*! A reference point that is used for comapring curves */
  Point_2 m_prevPos;

  /*! The current position (in X) of the sweep line */
  Point_2 m_sweepLinePos;

  /*! if non x-monotone are specified, this hold the x-monotone 
    curves created when splitting them into x-monotone curves. */
  std::vector<X_monotone_curve_2> m_xcurves;

  /*! a pointer to the current event */
  Event *m_currentEvent;

  /*! a queue that holds all the events that have the same x coordinate as 
      the status line. */
  EventList m_miniq;

  /*! a list of vertical curves at the x coordinate of the current event 
      point.*/
  SubCurveList m_verticals;
  CurveList m_verticalSubCurves;

  /*! when an intersection point is found this is turned to true */
  bool m_found_intersection;

  /*! An iterator of the  status line that is used as a hint for inserts. */
  StatusLineIter m_status_line_insert_hint;

  /*! A an indication wether the hint can be used to erase from the status
    line */
  bool m_use_hint_for_erase;
  SubCurveList m_tmpOut;
  Point_2 m_lastReportedPoint;
  bool is_first_point;

  /*! a counter the is used to assign unique ids to the curves. */
  int m_curveId;

#ifndef NDEBUG
  int m_eventId;
#endif

  bool CurveStartsAtCurve(Subcurve *one, Subcurve *two)
  {
    SL_DEBUG(std::cout << "CurveStartsAtCurve: \n";)
    SL_DEBUG(std::cout << one->get_curve() << "\n" << two->get_curve() 
                       << "\n";)

    if ( m_traits->point_equal(one->get_left_end(),two->get_left_end()))
      return false;

    if ( !m_traits->point_equal(one->get_left_end(),
				m_currentEvent->get_point()) )
      return false;
    if ( m_traits->curve_compare_y_at_x(one->get_left_end(), 
					two->get_curve()) == EQUAL )
      return true;
    return false;
  }

};

template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
~Sweep_line_2_impl() 
{
  if ( m_traitsOwner ) delete m_traits;

  for ( SubCurveListIter sci = m_subCurves.begin() ; 
	sci != m_subCurves.end() ; ++sci)
  {
    delete *sci;
  }

  for ( EventPtrContainerIter ei = m_events.begin();
	ei != m_events.end() ; ++ei)
  {
    delete *ei;
  }
  delete m_queue;
  delete m_statusLine;
  delete m_comp_param;
}



/*! initializes the data structures to work with:
 *  - x-monotonize the inf\put curves
 *  - for each end point of each curve create an event
 *  - initialize the event queue
 *  -
 */
template <class CurveInputIterator,  class SweepLineTraits_2,
          class SweepEvent, class CurveWrap>
inline void 
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
init(CurveInputIterator begin, CurveInputIterator end)
{
  PointLess pred(m_traits);
  m_queue = new EventQueue(pred);
  m_comp_param = new CompareParams(m_traits);
  StatusLineCurveLess slcurveless(m_comp_param);
  m_statusLine = new StatusLine(slcurveless);
  m_status_line_insert_hint = m_statusLine->begin();

#ifndef NDEBUG
  m_eventId = 0;
#endif
  m_curveId = 0;

  int count = 0;
  CurveInputIterator iter;
  for ( iter = begin ; iter != end ; ++iter)
  {
    std::list<X_monotone_curve_2> xcurves;
    m_traits->curve_make_x_monotone(*iter, std::back_inserter(xcurves));
    SL_DEBUG(
             std::cout << "curve " << *iter << " was split into " 
             << xcurves.size() << " curves." << std::endl;
             )

    for (typename std::list<X_monotone_curve_2>::iterator i = xcurves.begin();
         i != xcurves.end() ; ++i )
    {
      m_xcurves.push_back(*i);
      init_curve(m_xcurves[count]);
      count++;
    }
  }
}



/*! Given an x-monotone curve, create events for each end (if 
 *  one doesn't exist already). 
 *  For each curve create a Subcurve instance.
 */
template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline void 
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
init_curve(X_monotone_curve_2 &curve)
{
  const Point_2 &source = m_traits->curve_source(curve);
  const Point_2 &target = m_traits->curve_target(curve);
  Event *e = 0;
  
  Subcurve *subCv = new Subcurve(m_curveId++, curve, &m_currentPos, m_traits);
  m_subCurves.push_back(subCv);
  
  // handle the source point
  EventQueueIter eventIter = m_queue->find(&source); 
  if ( eventIter != m_queue->end() )  // check if the event already in the event queue
  {
    SL_DEBUG(std::cout << "event " << source << " already exists\n";)
    e = eventIter->second;
  }
  else  // the event is not in the event-queue
  {
    e = new Event(source, m_traits); 
#ifndef NDEBUG
    e->id = m_eventId++;
#endif
    m_events.push_back(e);
    m_queue->insert(EventQueueValueType(&(e->get_point()), e));
  }
  e->add_curve(subCv);
  PRINT_NEW_EVENT(source, e);
    
  // handle the target point
  eventIter = m_queue->find(&target);
  if ( eventIter != m_queue->end() )
  {
    SL_DEBUG(std::cout << "event " << target << " already exists\n";)
    e = eventIter->second;
  }
  else 
  {
    e = new Event(target, m_traits); 
#ifndef NDEBUG
    e->id = m_eventId++;
#endif
    m_events.push_back(e);
    m_queue->insert(EventQueueValueType(&(e->get_point()), e));
  }
  e->add_curve(subCv);
  PRINT_NEW_EVENT(target, e);
}




/*!
 * Handles the degenerate case of vertical curves. Most of the cases
 * that occur with vertical curves are handled by this method and 
 * handle_vertical_curve_top method.
 * When the current event is the bottom end of a vertical curve, we look
 * for intersection points between the vertical curve and any curve
 * in the status line that in the y-range that is defined by the bottom 
 * and top ends of the vertical curve. When those are found, we create
 * new events, unless ones already exist, in which case we update the events.
 * 
 * @param tag a tag that indicates the version of this method
 * \sa handle_vertical_curve_top
 */
template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline void 
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
handle_vertical_curve_bottom(SweepLineGetSubCurves &tag)
{
  SL_DEBUG(std::cout<<"\nhandle_vertical_curve_bottom... ("
                    << m_currentEvent->get_point() << ")\n";)
  if ( !m_currentEvent->does_contain_vertical_curve() )
  {
    SL_DEBUG(std::cout<<" - not vertical - exiting\n ";)
    return;
  }
  SL_DEBUG(std::cout<<"\n ";)

  VerticalCurveList &vcurves = m_currentEvent->get_vertical_curves();
  VerticalCurveListIter vciter = vcurves.begin();
  const Point_2 &currentPoint = m_currentEvent->get_point();

  SL_DEBUG(std::cout << vcurves.size() << " vertical curves in event\n";)
  while ( vciter != vcurves.end() )
  {
    Subcurve *vcurve = *vciter;
    SL_DEBUG(std::cout << "working on " << vcurve->get_curve() << "\n";)
    if ( vcurve->is_top_end(currentPoint))
    {
      vciter++;
      continue;
    }
    
    SL_DEBUG(std::cout<<"handling bottom point of vertical curve\n";)
    StatusLineIter slIter = m_statusLine->lower_bound(vcurve);
    if ( slIter == m_statusLine->end() ) {
      SL_DEBUG(std::cout<<"no curves intersecting. exiting\n";)
      vciter++;
      continue;
    }    
    
    SL_DEBUG(std::cout<<"starting at curve \n";)
    SL_DEBUG((*slIter)->Print();)
    const Point_2 &topEnd = vcurve->get_top_end();
    EventQueueIter topEndEventIter = m_queue->find(&topEnd);
    CGAL_assertion(topEndEventIter!=m_queue->end());
    Event *topEndEvent = topEndEventIter->second;

    bool lastEventCreatedHere = false;
    Event *prevEvent = 0;

    while (slIter != m_statusLine->end() &&
	   (! m_traits->point_in_x_range((*slIter)->get_curve(), 
					    topEnd) ||
	    m_traits->curve_compare_y_at_x(
	           topEnd, (*slIter)->get_curve()) != SMALLER) &&
	   (! m_traits->point_in_x_range((*slIter)->get_curve(), 
					 currentPoint) ||
	    m_traits->curve_compare_y_at_x(currentPoint,
                                           (*slIter)->get_curve()) != LARGER))
    {
      SL_DEBUG(std::cout<<"intersecting with \n";)
      SL_DEBUG((*slIter)->Print();) 
	
      if ( handle_vertical_curve_x_at_end(vcurve, *slIter, topEndEvent, tag)) {
	++slIter;
	continue;
      }
      
      // handle a curve that goes through the interior of the vertical curve
      const X_monotone_curve_2 &cv1 = vcurve->get_curve();
      const X_monotone_curve_2 &cv2 = (*slIter)->get_curve();

      Object res = m_traits->nearest_intersection_to_right(cv1, cv2,
                                                           currentPoint);
      CGAL_assertion(!res.is_empty());
      Point_2 xp;
      if (!CGAL::assign(xp, res))
        CGAL_assertion(0);
      
      EventQueueIter eqi = m_queue->find(&xp);
      Event *e = 0;
      if ( eqi == m_queue->end() )
      {
	e = new Event(xp, m_traits); 
#ifndef NDEBUG
	e->id = m_eventId++;
#endif
	m_events.push_back(e);
	
	e->add_curve_to_left(*slIter, m_sweepLinePos);
	e->add_curve_to_right(*slIter);
	PRINT_NEW_EVENT(xp, e);
	m_queue->insert(EventQueueValueType(&(e->get_point()), e));

	lastEventCreatedHere = true;

      } else {
	e = eqi->second;
	
	// the only time we need to update the event is when the event
	// is created here (which also includes overlapping curves)
	if ( e == prevEvent ) {
	  if ( lastEventCreatedHere )
	  {
	    if ( !(*slIter)->is_left_end(xp) ) 
	      e->add_curve_to_left(*slIter, m_sweepLinePos);
	    if ( !(*slIter)->is_right_end(xp) ) 
	      e->add_curve_to_right(*slIter);
	  } 
	}
	else
	  lastEventCreatedHere = false;

	SL_DEBUG(std::cout << "Updating event \n";)
	SL_DEBUG(e->Print();)
      }
      
      topEndEvent->add_vertical_curve_x_point(xp);
      ++slIter;
      prevEvent = e;
    }    
    vciter++;
  }