sweep_line_2_impl.h

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

  SL_DEBUG(std::cout<<"Done Handling vertical\n";)
}

/*!
 * Handles overlapping vertical curves. 
 * If the current event point does not contain vertical curves, nothing is
 * done here.
 * Fo the current event point, we go through the list of vertical curves 
 * defined in the same x coordinate (m_verticals). For each curve, we check 
 * if the event point is in the interior of the vertical curve. If so, 
 * the event is set to be an intersection point (between the two 
 * vertical curves). 
 * While going through the vertical curves, if we reach a curve that the 
 * event point is above the curve, we remove the curve from the list.
 * 
 * Finally, we go thorugh the vertical curves of the event. If the event 
 * point is the bottom end of a vertical curve, we add the vertical curve 
 * to the list of vertical curves (m_verticals).
 */
template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline void 
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
handle_vertical_overlap_curves()
{
  SL_DEBUG(std::cout<<"\nhandle_vertical_overlap_curves... (" 
                    << m_currentEvent->get_point() << ")";)

  if ( !m_currentEvent->does_contain_vertical_curve() ) {
    SL_DEBUG(std::cout << "no vertical - exiting\n";)
    return;
  }
  SL_DEBUG(std::cout << "\n";)
  SL_DEBUG(PrintVerticals();)

  const Point_2 &point = m_currentEvent->get_point();
  SubCurveListIter iter = m_verticals.begin();
  while ( iter != m_verticals.end() )
  {
    Subcurve *curve = *iter;
   
    if (m_traits->point_in_x_range(curve->get_curve(), point) &&
	m_traits->curve_compare_y_at_x(point, curve->get_curve()) == LARGER)
    {
      iter = m_verticals.erase(iter);

    } else if (!curve->is_end_point(point)) {

      EventQueueIter eventIter = m_queue->find(&(curve->get_top_end()));
      CGAL_assertion(eventIter!=m_queue->end());
      (eventIter->second)->add_vertical_curve_x_point(point, true);
      m_currentEvent->mark_internal_intersection_point();
      ++iter;
    } else {
      ++iter;
    }
  }

  VerticalCurveList &vcurves = m_currentEvent->get_vertical_curves();
  VerticalCurveListIter vciter = vcurves.begin();
  while ( vciter != vcurves.end() )
  {
    Subcurve *vcurve = *vciter;
    if ( vcurve->is_bottom_end(point) ) {
      m_verticals.push_back(vcurve);
    }
    ++vciter;
  }
}




/*!
 * Perform intersection between the specified curve and all curves in the 
 * given group of curves.
 */ 
template <class CurveInputIterator, class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline void
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
intersect_curve_group(Subcurve *c1, SubCurveList &mylist)
{
  m_tmpOut.clear();
  SL_DEBUG(std::cout << "intersecting with " << mylist.size() << " curves\n";)
  SubCurveListIter i = mylist.begin();
  while ( i != mylist.end())
  {

    intersect(c1, *i);
    ++i;
  }
}



/*!
 * When a curve is removed from the status line for good, its top and
 * bottom neighbors become neighbors. This method finds these cases and
 * looks for the itnersection point, if one exists.
 *
 * @param leftCurve a pointer to the curve that is about to be deleted
 * @return an iterator to the position where the curve will be removed from.
 */
template <class CurveInputIterator, class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline void
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
remove_curve_from_status_line(Subcurve *leftCurve)
{
  SL_DEBUG(std::cout << "remove_curve_from_status_line\n";)
  SL_DEBUG(PrintStatusLine();)
  SL_DEBUG(leftCurve->Print();)

  StatusLineIter sliter;
  sliter = leftCurve->get_hint(); 

  m_status_line_insert_hint = sliter; ++m_status_line_insert_hint;
  if ( !leftCurve->is_end_point(m_currentEvent->get_point())) {
    m_statusLine->erase(sliter);
    SL_DEBUG(std::cout << "remove_curve_from_status_line Done\n";)
    return;
  }

  m_currentPos = m_prevPos;
  CGAL_assertion(sliter!=m_statusLine->end());
  StatusLineIter end = m_statusLine->end(); --end;
  if ( sliter != m_statusLine->begin() && sliter != end ) 
  {
    SubCurveList mylist;
    StatusLineIter prev = sliter; --prev;
    
    // collect all curves that overlap with *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;
    }
    
    StatusLineIter next = sliter; ++next;
    
    // intersect *next with the the *prev curve and all overlaps
    tmp = next;
    intersect_curve_group(*tmp, mylist);
    // if there are curves that overlap with the *next curve, intersect
    // them with the *prev curve and all overlaps
    ++tmp;
    while ( tmp != m_statusLine->end() ) 
    {
      if ( do_curves_overlap(*next, *tmp))
      {
	intersect_curve_group(*tmp, mylist);
	++tmp;
      }
      else 
	break;
    }
  }
  m_statusLine->erase(sliter);
  SL_DEBUG(std::cout << "remove_curve_from_status_line Done\n";)
} 

/*! 
 * Finds intersection between two curves. 
 * If the two curves intersect, create a new event (or use the event that 
 * already exits in the intersection point) and insert the curves to the
 * event.
 * @param curve1 a pointer to the first curve
 * @param curve2 a pointer to the second curve
 * @return true if the two curves overlap.
*/


template <class CurveInputIterator, class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline bool 
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
intersect(Subcurve *c1, Subcurve *c2)
{
  SL_DEBUG(std::cout << "Looking for intersection between:\n\t";)
  SL_DEBUG(c1->Print();)
  SL_DEBUG(std::cout << "\t";)
  SL_DEBUG(c2->Print();)
  SL_DEBUG(std::cout << "\n";)
  SL_DEBUG(std::cout << "relative to " << m_currentEvent->get_point() << "\n";)

  if ( c1->getId() == c2->getId() ) {
    SL_DEBUG(std::cout << "same curve, returning....\n";)
    return false;
  }

  Subcurve *scv1 = c1;
  Subcurve *scv2 = c2;
  const X_monotone_curve_2 &cv1 = scv1->get_curve();
  const X_monotone_curve_2 &cv2 = scv2->get_curve();

  bool isOverlap = false;

  Object res =
    m_traits->nearest_intersection_to_right(cv1, cv2, 
                                            m_currentEvent->get_point());
  if (!res.is_empty())
  {
    Point_2 xp;
    if (!CGAL::assign(xp, res))
    {
      X_monotone_curve_2 cv;
      if (CGAL::assign(cv, res))
      {
        xp = m_traits->curve_source(cv);
        Point_2 xp1 = m_traits->curve_target(cv);
        if ( m_traits->compare_x(xp1, xp) == LARGER )
          xp = xp1;
        SL_DEBUG(std::cout << "overlap detected\n";)
          isOverlap = true;
      }
    }

    SL_DEBUG(
      std::cout << " a new event is created between:\n\t";
      scv1->Print();
      std::cout << "\t";
      scv2->Print();
      std::cout << "\trelative to ("
                << m_sweepLinePos << ")\n\t at (" 
                << xp << ")" << std::endl;
    )

    // check to see if an event at this point already exists...
    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(c1, m_sweepLinePos);
      e->add_curve_to_left(c2, m_sweepLinePos);
      
      e->add_curve_to_right(c1);
      e->add_curve_to_right(c2);
      
      PRINT_NEW_EVENT(xp, e);
      m_queue->insert(EventQueueValueType(&(e->get_point()), e));
      return isOverlap;
    } 
    else 
    {
      SL_DEBUG(std::cout << "event already exists,updating.. (" << xp <<")\n";)
      e = eqi->second;
    
      e->add_curve_to_left(c1, m_sweepLinePos);
      if ( !scv1->is_end_point(xp)) 
      { 
	      e->add_curve_to_right(c1);
      }

      e->add_curve_to_left(c2, m_sweepLinePos);
      if ( !scv2->is_end_point(xp) ) 
      {
	      e->add_curve_to_right(c2);
      }
      SL_DEBUG(e->Print();)
    }
    return isOverlap;
  } 
  SL_DEBUG(std::cout << "not found 2\n";)
  return isOverlap;
}



template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline bool
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
is_internal_x_point(const Point_2 &p)
{
  EventListIter itt = m_miniq.begin();
  while ( itt != m_miniq.end() )
  {
    if ( m_traits->point_equal(p, (*itt)->get_point())) 
    {
      if ((*itt)->is_internal_intersection_point()) {
	return true;
      }
      (*itt)->mark_internal_intersection_point(); 
                                     // this is to handle cases: |/ .
      return false;                  // (test 50/51)             |\ .
    } 
    ++itt;
  }
  CGAL_assertion(0);
  return false;
}



/*!
 * Handles the case in which a curve ont he status line passes through
 * one of the end points of the vertical curve.
 *
 * @param vcurve the vertical curve we are dealing with
 * @param curve a cerve that intersects with the vertical curve
 * @param topEndEvent the event attached to the top end of the vertical curve
 * @param tag 
 * @return returns true if the curve passed through one of the ends of the 
 *              vertical curve. Returns false otherwise.
 */
template <class CurveInputIterator,  class SweepLineTraits_2,
          class SweepEvent, class CurveWrap>
inline bool
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
handle_vertical_curve_x_at_end(Subcurve *vcurve, Subcurve *curve, 
			  Event *topEndEvent, SweepLineGetSubCurves tag)
{
  const Point_2 &topEnd = vcurve->get_top_end();
  // handle a curve that goes through the top point of the vertical curve
  if (m_traits->point_in_x_range(curve->get_curve(), topEnd) &&
      m_traits->curve_compare_y_at_x(topEnd, curve->get_curve()) == EQUAL)
  {
    if ( !curve->is_left_end(topEnd)) {
      topEndEvent->add_curve_to_left(curve, m_prevPos);
    }
    if ( ! curve->is_right_end(topEnd)) {
      topEndEvent->add_curve_to_right(curve);
    }
    return true;
  } 
  
  // handle a curve that goes through the bottom point of the vertical curve
  const Point_2 &currentPoint = m_currentEvent->get_point();
  if (m_traits->point_in_x_range((curve)->get_curve(), currentPoint) &&
      m_traits->curve_compare_y_at_x(currentPoint, (curve)->get_curve()) ==
      EQUAL)
  {
    if ( !(curve)->is_left_end(currentPoint)) {
      m_currentEvent->add_curve_to_left(curve, m_prevPos);
    }
    if ( ! (curve)->is_right_end(currentPoint)) {
      m_currentEvent->add_curve_to_right(curve);
    }
    return true;
  }
  return false;
}



template <class CurveInputIterator,  class SweepLineTraits_2,
          class SweepEvent, class CurveWrap>
inline bool
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
do_curves_overlap(Subcurve *c1, Subcurve *c2)
{
  SL_DEBUG(std::cout << "do_curves_overlap " << m_sweepLinePos << "\n" 
	             << "\t" << c1->get_curve() << "\n"
	             << "\t" << c2->get_curve() << "\n";)

  const Point_2 *p = &(c2->get_last_point());
  if ( m_traits->compare_x(c1->get_last_point(), 
			   c2->get_last_point()) == LARGER )
    p = &(c1->get_last_point());

  if ((m_traits->curves_compare_y_at_x(c1->get_curve(),
				       c2->get_curve(),
				       *p) != EQUAL))
    return false;

  if ( m_traits->curves_overlap(c1->get_curve(),c2->get_curve()) )
    return true;

  return false;
}

template <class CurveInputIterator,  class SweepLineTraits_2,
         class SweepEvent, class CurveWrap>
inline bool
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
similar_curves(const X_monotone_curve_2 &a, const X_monotone_curve_2 &b)
{
  if ( m_traits->curve_equal(a, b))
    return true;
  return false;
}

template <class CurveInputIterator,  class SweepLineTraits_2,
          class SweepEvent, class CurveWrap>
inline bool
Sweep_line_2_impl<CurveInputIterator,SweepLineTraits_2,SweepEvent,CurveWrap>::
vertical_subcurve_exists(const X_monotone_curve_2 &a)
{
  for (typename std::list<X_monotone_curve_2>::iterator iter =
         m_verticalSubCurves.begin() ;
       iter != m_verticalSubCurves.end() ; ++iter)
  {
    if (similar_curves(*iter, a)) 
      return true;
  }
  return false;
}



////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
//                 point implementation of the methods                    //
////////////////////////////////////////////////////////////////////////////
/////////////////////////////////