sweep_line_2_impl.h

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

      intersect_curve_group(*(m_currentEvent->right_curves_begin()), mylist);
      
    } else
    {
      /* this block takes care of 
      //
      //           /
      //          /
      //       --------
      //          \
      //           \
      */
      int numLeftCurves = m_currentEvent->get_num_left_curves();
      if ( numLeftCurves == 0 ) {
	
	SL_DEBUG(std::cout << " - handling special case " << std::endl;);
	StatusLineIter slIter;
	EventCurveIter currentOne = m_currentEvent->right_curves_begin();
	while ( currentOne != m_currentEvent->right_curves_end() ) {
	  slIter = m_statusLine->lower_bound(*currentOne);
	  if ( slIter != m_statusLine->end() ) {
	    Subcurve *c = *slIter;
	    if ( CurveStartsAtCurve(*currentOne, c) && !m_includeEndPoints) {
	      SL_DEBUG(std::cout << "Reporting point (8): "
                                 << (*currentOne)->get_left_end()
		                 << "\n";);
	      //*out = (*currentOne)->get_left_end(); ++out;
	      add_point_to_output((*currentOne)->get_left_end(), out);
	      m_found_intersection = true;
	      break;
	    }
	  }
	  currentOne++;
	}
      }
      // end block ..
      
      
      SubCurveList mylist;
      SubCurveList prevlist;
      SubCurveList currentlist;
      
      
      SL_DEBUG(std::cout << " - intersection point " << std::endl;);
      EventCurveIter firstOne = m_currentEvent->right_curves_begin();
      EventCurveIter lastOne = m_currentEvent->right_curves_end(); --lastOne;
      EventCurveIter rightCurveEnd = m_currentEvent->right_curves_end();
      
      PRINT_INSERT(*firstOne);
      
      StatusLineIter slIter = m_statusLine->insert(m_status_line_insert_hint, 
						   *firstOne);
      (*firstOne)->set_hint(slIter);
      
      SL_DEBUG(PrintStatusLine(););
      if ( slIter != m_statusLine->begin() )
      { 
	StatusLineIter prev = slIter; --prev;
	
	if ( CurveStartsAtCurve(*slIter, *prev) && !m_includeEndPoints) {
	  SL_DEBUG(std::cout << "Reporting point (6): " 
		   << (*slIter)->get_left_end() 
		   << "\n";);
	  //*out = (*slIter)->get_left_end(); ++out;
	  add_point_to_output((*slIter)->get_left_end(), out);
	  m_found_intersection = true;
	}
	
	// find all curves that are overlapping with the prev curve
	StatusLineIter tmp = prev;
	prevlist.push_back(*prev);
	while ( tmp != m_statusLine->begin() ) 
	{
	  --tmp;
	  if ( do_curves_overlap(*prev, *tmp))
	    prevlist.push_back(*tmp);
	  else
	    break;
	}
	
	intersect_curve_group(*slIter, prevlist);
      }
      currentlist.push_back(*firstOne);
      
      EventCurveIter currentOne = firstOne; ++currentOne;
      EventCurveIter prevOne = firstOne;
      
      while ( currentOne != rightCurveEnd )
      {
	m_currentPos = m_sweepLinePos;
	PRINT_INSERT(*currentOne);
	++slIter;
	slIter = m_statusLine->insert(slIter, *currentOne);
	(*currentOne)->set_hint(slIter);
	
	SL_DEBUG(PrintStatusLine(););
	if ( do_curves_overlap(*currentOne, *prevOne))
	{
	  intersect_curve_group(*currentOne, currentlist);
	  currentlist.push_back(*currentOne);
	} else {
	  prevlist = currentlist;
	  currentlist.clear();
	  currentlist.push_back(*currentOne);
	}
	
	intersect_curve_group(*currentOne, prevlist);
	prevOne = currentOne;
	++currentOne;
      }
      m_status_line_insert_hint = slIter; ++m_status_line_insert_hint;
      
      lastOne = currentOne; --lastOne;
      m_currentPos = m_sweepLinePos;
      PRINT_INSERT(*lastOne);
      
      SL_DEBUG(PrintStatusLine(););
      StatusLineIter next = slIter; ++next;
      if ( next != m_statusLine->end() ) {
	
	if ( CurveStartsAtCurve(*slIter, *next)  && !m_includeEndPoints) {
	  SL_DEBUG(std::cout << "Reporting point (7): " 
                             << (*slIter)->get_left_end() 
  		             << "\n";);
	  //*out = (*slIter)->get_left_end(); ++out;
	  add_point_to_output((*slIter)->get_left_end(), out);
	  m_found_intersection = true;
	}
	
	intersect_curve_group(*next, currentlist);
	StatusLineIter tmp = next; ++tmp;
	while ( tmp != m_statusLine->end() ) 
	{
	  if ( do_curves_overlap(*next, *tmp))
	  {
	    intersect_curve_group(*tmp, currentlist);
	    ++tmp;
	  }
	  else
	    break;
	}
      }
    }
  }
  


  // utility methods 
  bool intersect(Subcurve *c1, Subcurve *c2);
  void intersect_curve_group(Subcurve *c1, SubCurveList &mylist);


  // reverse = false ==> we check if the curve starts at the list of curves
  // reverse = true ==> we check if any of the curves in the list start at 
  // the single curve
  template <class OutpoutIterator>
  void intersect_curve_group(Subcurve *c1, SubCurveList &mylist,
			   OutpoutIterator out, bool reverse=false)
  {
    m_tmpOut.clear();
    SL_DEBUG(std::cout << "intersect_curve_group (with out)\n";)
    SL_DEBUG(std::cout << "intersecting with " << mylist.size()
             << " curves\n";)
    SubCurveListIter i = mylist.begin();
    while ( i != mylist.end())
    {
      bool flag;
      if ( reverse ) {
	flag = CurveStartsAtCurve(*i, c1);
	if ( flag && (c1->get_last_point() != m_currentEvent->get_point()) ) {
	  SL_DEBUG(std::cout << "CurveStartsAtCurve 3 \n";)
	  m_currentEvent->add_curve_to_right(c1);
	  m_currentEvent->add_curve_to_left(c1, m_prevPos);
	  X_monotone_curve_2 a,b;
	  SL_DEBUG(std::cout << "splitting " << (c1)->get_last_curve() 
                             << " at " 
		             << m_currentEvent->get_point() << "\n";)
	  if ( (c1)->is_source_left_to_target() ) 
	    m_traits->curve_split((c1)->get_last_curve(), a, b, 
				  m_currentEvent->get_point());
	  else
	    m_traits->curve_split((c1)->get_last_curve(), b, a, 
				  m_currentEvent->get_point());
	  (c1)->set_last_point(m_currentEvent->get_point());
	  (c1)->set_last_curve(b); 
	  (c1)->set_last_subcurve(a); 
	  m_tmpOut.push_back(c1);
	}
      }
      else
      {
	flag = CurveStartsAtCurve(c1, *i);
	if ( flag && ((*i)->get_last_point() != m_currentEvent->get_point())) {
	  
	  SL_DEBUG(std::cout << "CurveStartsAtCurve 3 \n";)
	  m_currentEvent->add_curve_to_right(*i);
	  m_currentEvent->add_curve_to_left(*i, m_prevPos);
	  X_monotone_curve_2 a,b;
	  SL_DEBUG(std::cout << "splitting " << (*i)->get_last_curve() 
                             << " at " 
		             << m_currentEvent->get_point() << "\n";)
	  if ( (*i)->is_source_left_to_target() ) 
	    m_traits->curve_split((*i)->get_last_curve(), a, b, 
				  m_currentEvent->get_point());
	  else
	    m_traits->curve_split((*i)->get_last_curve(), b, a, 
				  m_currentEvent->get_point());
	  (*i)->set_last_point(m_currentEvent->get_point());
	  (*i)->set_last_curve(b); 
	  (*i)->set_last_subcurve(a); 
	  m_tmpOut.push_back(*i);
	  
	}
      }
      
      intersect(c1, *i);
      ++i;
    }
    
    for ( SubCurveListIter iter = m_tmpOut.begin() ; iter != m_tmpOut.end();
	  ++iter) {
      add_curve_to_output((*iter)->get_last_subcurve(), *iter, out);
    }
  }

  void remove_curve_from_status_line(Subcurve *leftCurve);

  bool is_internal_x_point(const Point_2 &p);
  bool handle_vertical_curve_x_at_end(Subcurve *vcurve, Subcurve *curve, 
				      Event *topEndEvent,
				      SweepLineGetSubCurves tag);
  bool handle_vertical_curve_x_at_end(Subcurve *vcurve, Subcurve *curve, 
				      Event *topEndEvent, 
				      SweepLineGetPoints tag);


  bool do_curves_overlap(Subcurve *c1, Subcurve *c2);
  bool similar_curves(const X_monotone_curve_2 &a, 
		      const X_monotone_curve_2 &b);
  bool vertical_subcurve_exists(const X_monotone_curve_2 &a);


  /*! Adds a new curve to the output list. If the overlapping flag is false,
      each unique curve is reported only once.

      @param out an iterator to the output container
      @param cv the curve to be added
  */
  template <class OutpoutIterator>
  void add_curve_to_output(const X_monotone_curve_2 &cv, Subcurve *curve, 
                           OutpoutIterator out)
  {
    static Subcurve *prevCurve = 0;
    static X_monotone_curve_2 prevXCv;

    if ( m_overlapping ) {
      *out = cv;
      ++out;
    } else {
      if ( prevCurve && similar_curves(cv, prevXCv)) {
	SL_DEBUG(std::cout << " curve already reported... " << std::endl;)
	return;
      }
      prevCurve = curve;
      prevXCv = cv;
      *out = cv;
      ++out;
    }
  }
  template <class OutpoutIterator>
  void add_point_to_output(const Point_2 p, OutpoutIterator out) {

    SL_DEBUG(std::cout << "Reporting point " << p;)
    if ( is_first_point ) {
      is_first_point = false;
      *out = p;
      m_lastReportedPoint = p;
      ++out;
      SL_DEBUG(std::cout << " YES - first time\n";)
    } else {
      if ( m_lastReportedPoint != p ) {
	*out = p;
	++out;
	m_lastReportedPoint = p;
	SL_DEBUG(std::cout << " YES\n";)
      } else {
	SL_DEBUG(std::cout << " NO\n";)
      }
    }
  }


  template <class OutpoutIterator>
  void add_vertical_curve_to_output(OutpoutIterator out, 
				const X_monotone_curve_2 &cv)
  {
    if ( m_overlapping ) {
      *out = cv;
      ++out;
    } else {
      if ( vertical_subcurve_exists(cv)) {
	SL_DEBUG(std::cout << " curve already reported... " << std::endl;)
	return;
      }
      m_verticalSubCurves.push_back(cv);
      *out = cv;
      ++out;
    }
  }

  /*! 
   * Returns true if the point is in the interior of the curve.
   * Returns false if the point is outside the range of the curve or
   * if the point is either the source or the target of the curve.
   * @return true if the point is int he interior of the curve.
   */
  bool is_point_in_curve_interior(const X_monotone_curve_2 &c, 
				  const Point_2 &p)
  {
    if (! m_traits->point_in_x_range(c,p) || 
	m_traits->curve_compare_y_at_x(p, c) != EQUAL)
      return false;
    if ( is_end_point(p) )
      return false;
    return true;
  }


  //
  // a second implementation for the get_intersection_points functionality
  //

  /*!
   *  Handle a vertical curve when the event being processed is the top end 
   *  of the curve. In this situation, the event contains a list of
   *  intersection points on the vertical curve. We go through this list and
   *  output the intersection points.
   *  If the curve is not vertical, returns without doing anything.
   * 
   *  @param out an iterator to the output
   *  @param tag a tag that indicates the version of the method
   */
  template <class OutpoutIterator>
  void handle_vertical_curve_top(OutpoutIterator out, 
			      SweepLineGetPoints &tag)
  {
    SL_DEBUG(std::cout<<"handle_vertical_curve_top... ";)
    if ( !m_currentEvent->does_contain_vertical_curve() )
    {
      SL_DEBUG(std::cout<<"exiting\n ";)
      return;
    }
    SL_DEBUG(std::cout<<"\n ";)

    VerticalCurveList &vcurves = m_currentEvent->get_vertical_curves();
    VerticalCurveListIter vciter = vcurves.begin();

    while ( vciter != vcurves.end() )
    {
      Subcurve *vcurve = *vciter; 
      const Point_2 &topPoint = m_currentEvent->get_point();
      if ( vcurve->is_bottom_end(topPoint)) {
	SL_DEBUG(std::cout<<"this is the bottom. skipping.\n";)
	++vciter;
	continue;
      }

      SL_DEBUG(std::cout<<"handling top point of vertical curve\n";)
      StatusLineIter slIter = m_statusLine->lower_bound(vcurve);
      if ( slIter != m_statusLine->end() )
      {
	SL_DEBUG(std::cout<<"starting at curve \n";)
	SL_DEBUG((*slIter)->Print();)
	  
        const Point_2 &bottomPoint = vcurve->get_bottom_end();

	while (slIter != m_statusLine->end() &&
	       m_traits->point_in_x_range((*slIter)->get_curve(),
                                          topPoint) &&
	       m_traits->curve_compare_y_at_x(topPoint,
                                              (*slIter)->get_curve()) ==
               LARGER &&
	       m_traits->point_in_x_range((*slIter)->get_curve(), 
                                          bottomPoint) && 
	       m_traits->curve_compare_y_at_x(bottomPoint,
                                              (*slIter)->get_curve()) ==
               SMALLER)
	{
	  SL_DEBUG(std::cout<<"checking \n";)
	  SL_DEBUG((*slIter)->Print();) 
	  if ( m_traits->compare_x((*slIter)->get_left_end(),topPoint) 
	                                                       == EQUAL)
	  {
	    m_currentEvent->add_vertical_curve_x_point(
	                                    (*slIter)->get_left_end());
	    // if this point was not an event, we need to report the point
	    // test40/42
	    if ( !m_includeEndPoints && 
		 !is_internal_x_point((*slIter)->get_left_end())) {
	      SL_DEBUG(std::cout << "Reporting point (1): " 
                                 << (*slIter)->get_left_end() << "\n";)
	      //*out = (*slIter)->get_left_end(); ++out;
	      add_point_to_output((*slIter)->get_left_end(), out);
	      m_found_intersection = true;
	    }
	  }
	  ++slIter;
	}   
      }
      ++vciter;
    }
  }
  /*! For each left-curve, if it is the "last" subcurve, i.e., the 
   * event point is the right-edge of the original curve, the 
   * last sub curve is created and added to the result. Otherwise
   * the curve is added as is to the result.
   */
  template <class OutpoutIterator>