sweep_line_2_impl.h

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

   *  outpt the subcurves induced by these 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, 
				 SweepLineGetSubCurves &tag)
  {
    SL_DEBUG(std::cout<<"handle_vertical_curve_top... (" 
	              << m_currentEvent->get_point() << ")\n";)
    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 this is the bottom point, nothing to do here
      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";)


      // the following while loop comes to handle  | 
      // in the case where a new curve begins at   |------
      // a vertical curve                          |

      // find the "position" of the curve of the status line
      StatusLineIter slIter = m_statusLine->lower_bound(vcurve);
      
      if ( slIter != m_statusLine->end() ) 
      {
	SL_DEBUG(std::cout<<"starting at curve \n";)
	SL_DEBUG((*slIter)->Print();)

	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(), 
					  vcurve->get_bottom_end()) &&
	       m_traits->curve_compare_y_at_x(
		 vcurve->get_bottom_end(), 
		 (*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(), true);
	  }
	  ++slIter;
	}   
      }

      // now we go over the list of intersection points on the vertical
      // curve in at the event and process them...
      SL_DEBUG(std::cout<<"handling the splitting now\n";)
      VerticalXPointList &pointList = 
	                    m_currentEvent->get_vertical_x_point_list();
      if ( pointList.empty() )
      {
	add_vertical_curve_to_output(out, vcurve->get_curve());
	++vciter;
	continue;
      }
    
      X_monotone_curve_2 a, b, c;
      a = vcurve->get_curve();
      SL_DEBUG(std::cout << "there are " << pointList.size() << " points\n";)
      SL_DEBUG(m_currentEvent->PrintVerticalXPoints();)
      for ( VerticalXPointListIter i = pointList.begin() ;
	    i != pointList.end(); ++i )
      {
	SL_DEBUG(std::cout<< "splitting: " << a << " at " << *i ;)
	if ( !vcurve->is_point_in_range(*i) )
	{
	  SL_DEBUG(std::cout << " not !\n";)
	  continue;
	}
	SL_DEBUG(std::cout << " yes! \n";)
	m_traits->curve_split(a, b, c, *i);
	if ( vcurve->is_source_left_to_target()) {
	  add_vertical_curve_to_output(out, b);
	  a = c;
	} else {
	  add_vertical_curve_to_output(out, c);
	  a = b;
	}
      }
      if ( vcurve->is_source_left_to_target() ) {
	add_vertical_curve_to_output(out, c);
      }
      else {
	add_vertical_curve_to_output(out, b);
      }
      ++vciter;
    }
  }


  /*! Loop over the curves to the right of the status line and handle them:
   * - if we are at the beginning of the curve, we insert it to the status 
   *   line, then we look if it intersects any of its neighbours.
   * - if we are at an intersection point between two curves, we add them
   *   to the status line and attempt to intersect them with their neighbours. 
   * - We also check to see if the two intersect again to the right of the 
   *   point.
   */
  template <class OutpoutIterator>
  void handle_right_curves(OutpoutIterator out, SweepLineGetSubCurves &tag)
  {
    SL_DEBUG(std::cout << "Handling right curves (" ;)
    SL_DEBUG(std::cout << m_currentEvent->get_point() << ")\n";)
    int numRightCurves = m_currentEvent->get_num_right_curves();
    if ( numRightCurves == 0 )
      return;
      
    m_currentPos = m_sweepLinePos;
    if ( numRightCurves == 1 )
    {
      SL_DEBUG(std::cout << " - beginning of curve " << std::endl;)
	  
      SL_DEBUG(
	    Subcurve *tmp1 = *(m_currentEvent->right_curves_begin());
	    PRINT_INSERT(tmp1);
	    )
	  
      StatusLineIter slIter = m_statusLine->insert(
	                        m_status_line_insert_hint, 
				*(m_currentEvent->right_curves_begin()));
      
      (*(m_currentEvent->right_curves_begin()))->set_hint(slIter); //xxx
      m_status_line_insert_hint = slIter; ++m_status_line_insert_hint;

      SL_DEBUG(PrintStatusLine();)

      // if this is the only curve on the status line, nothing else to do
      if ( m_statusLine->size() == 1 )
	return;

      StatusLineIter prev = slIter;
      StatusLineIter next = slIter;
      ++next;

      SubCurveList mylist;
      if ( slIter != m_statusLine->begin() )
      {
	--prev;
	
	StatusLineIter tmp = prev;
	mylist.push_back(*prev);
	while ( tmp != m_statusLine->begin() ) 
	{
	  --tmp;
	  if ( do_curves_overlap(*prev, *tmp) )
	    mylist.push_back(*tmp);
	  else 
	    break;
	}
      }
      
      if ( next != m_statusLine->end() )
      { 
	
	StatusLineIter tmp = next;
	mylist.push_back(*next);
	++tmp;
	while ( tmp != m_statusLine->end() ) 
	{
	  if ( do_curves_overlap(*next, *tmp) )
	  {
	    mylist.push_back(*tmp);
	    ++tmp;
	  }
	  else
	    break;
	}
      }
      intersect_curve_group(*(m_currentEvent->right_curves_begin()), 
			    mylist, out);
      
    } 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_currentEvent->add_curve_to_left(c, m_sweepLinePos);
	      m_currentEvent->add_curve_to_right(c);
	      X_monotone_curve_2 a,b;
	      if ( c->is_source_left_to_target() ) {
		m_traits->curve_split(c->get_last_curve(), a, b, 
				      m_currentEvent->get_point());
	      } else {
		m_traits->curve_split(c->get_last_curve(), b, a, 
				      m_currentEvent->get_point());
	      }
	      c->set_last_point(m_currentEvent->get_point());
	      c->set_last_curve(b);
	      
	      add_curve_to_output(a, c, out);
	      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;
	
	// 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, out);
      }
      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, out);
	  currentlist.push_back(*currentOne);
	} else {
	  prevlist = currentlist;
	  currentlist.clear();
	  currentlist.push_back(*currentOne);
	}
	
	intersect_curve_group(*currentOne, prevlist, out);
	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() ) {
	intersect_curve_group(*next, currentlist, out, true);
	StatusLineIter tmp = next; ++tmp;
	while ( tmp != m_statusLine->end() ) 
	{
	  if ( do_curves_overlap(*next, *tmp))
	  {
	    intersect_curve_group(*tmp, currentlist, out, true);
	    ++tmp;
	  }
	  else
	    break;
	}
      }
    }
  }
  

  template <class OutpoutIterator>
  void handle_right_curves(OutpoutIterator out, SweepLineGetPoints &tag)
  {
    SL_DEBUG(std::cout << "Handling right curves (" ;);
    SL_DEBUG(std::cout << m_currentEvent->get_point() << ")\n";);
    int numRightCurves = m_currentEvent->get_num_right_curves();
    if ( numRightCurves == 0 )
      return;
    
    m_currentPos = m_sweepLinePos;
    if ( numRightCurves == 1 )
    {
      SL_DEBUG(std::cout << " - beginning of curve " << std::endl;);

      SL_DEBUG(
	Subcurve *tmp1 = *(m_currentEvent->right_curves_begin());
	PRINT_INSERT(tmp1);
	);

      StatusLineIter slIter = m_statusLine->insert(
                                      m_status_line_insert_hint, 
				      *(m_currentEvent->right_curves_begin()));
      
      (*(m_currentEvent->right_curves_begin()))->set_hint(slIter); 
      m_status_line_insert_hint = slIter; ++m_status_line_insert_hint;
      
      SL_DEBUG(PrintStatusLine(););
      
      // if this is the only curve on the status line, nothing else to do
      if ( m_statusLine->size() == 1 )
	return;
      
      StatusLineIter prev = slIter;
      StatusLineIter next = slIter;
      ++next;

      SubCurveList mylist;
      if ( slIter != m_statusLine->begin() )
      {
	--prev;
	
	if ( CurveStartsAtCurve(*slIter, *prev) && !m_includeEndPoints) {
	  SL_DEBUG(std::cout << "Reporting point (4): " 
                             << (*slIter)->get_left_end() 
                 	     << "\n";);
	  //*out = (*slIter)->get_left_end(); ++out;
	  add_point_to_output((*slIter)->get_left_end(), out);
	  m_found_intersection = true;
	}
	StatusLineIter tmp = prev;
	mylist.push_back(*prev);
	while ( tmp != m_statusLine->begin() ) 
	{
	  --tmp;
	  if ( do_curves_overlap(*prev, *tmp) )
	    mylist.push_back(*tmp);
	  else 
	    break;
	}
      }
      
      if ( next != m_statusLine->end() )
      { 
	if ( CurveStartsAtCurve(*slIter, *next)  && !m_includeEndPoints) {
	  SL_DEBUG(std::cout << "Reporting point (5): " 
		   << (*slIter)->get_left_end() 
		   << "\n";);
	  //*out = (*slIter)->get_left_end(); ++out;
	  add_point_to_output((*slIter)->get_left_end(), out);
	  m_found_intersection = true;
	}
	StatusLineIter tmp = next;
	mylist.push_back(*next);
	++tmp;
	while ( tmp != m_statusLine->end() ) 
	{
	  if ( do_curves_overlap(*next, *tmp) )
	  {
	    mylist.push_back(*tmp);
	    ++tmp;
	  }
	  else
	    break;
	}
      }