sweep_line_2_impl.h

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

// Copyright (c) 1997  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Sweep_line_2/include/CGAL/Sweep_line_2/Sweep_line_2_impl.h,v $
// $Revision: 1.12 $ $Date: 2004/11/03 13:42:20 $
// $Name:  $
//
// Author(s)     : Tali Zvi <[e-mail]>
#ifndef CGAL_SWEEP_LINE_2_IMPL_H
#define CGAL_SWEEP_LINE_2_IMPL_H

#include <CGAL/Sweep_line_2/Sweep_line_functors.h>
#include <CGAL/assertions.h>
#include <map>
#include <set>

#ifndef VERBOSE

#define SL_DEBUG(a)
#define PRINT_INSERT(a)
#define PRINT_ERASE(a)
#define PRINT_NEW_EVENT(p, e) 
#define DBG(a)
#define STORE_RESULT(a)

#else

#define SL_DEBUG(a) {a}
#define PRINT_INSERT(a) { std::cout << "+++ inserting "; \
                          (a)->Print(); \
                          std::cout << "    currentPos = " << m_currentPos \
                                    << "\n"; \
                          }
#define PRINT_ERASE(a)  { std::cout << "--- erasing " ; \
                          (a)->Print(); }
#define PRINT_NEW_EVENT(p, e) \
{ std::cout << "%%% a new event was created at " << (p) << std::endl; \
  (e)->Print(); }
#define DBG(a) { std::cout << a << std::endl; }
#define STORE_RESULT(a) {a}
#endif

#include <list>

CGAL_BEGIN_NAMESPACE

/*!
  Sweep_line_2_impl is a class that implements the sweep line algorithm
  based on the algorithm of Bentley and Ottmann.
  It extends the algorithm to support not only segments but polylines and 
  general curves as well.
  The curves are defined by the traits class that is one of the template 
  arguments.

  The algorithm is also extended to support the following degenerate cases:
  - non x-monotone curves
  - vertical segments
  - multiple (more then two) segments intersecting at one point
  - curves beginning and ending on other curves.
  - overlapping curves

  There are two main functionalities supported by this algorithm:
  1. calculate the non intersecting curves that are a product of 
     intersecting a set of input curves
  2. calculate all the intersection points between the curves specified

  An extension of this algorithm is used to produce a planar map containing
  the input curves efficiently. \sa Pmwx_aggregate_insert.

  General flow:
  After the initialization stage, the events are handled from left to right.

  For each event

    First pass - handles special cases in which curves start or end 
                 at the interior of another curve
    Handle vertical curve (bottom) - special caring if the event 
                 is a bottom end of a vertical curve
    Handle vertical overlapping curves - special caring if there are
                 overlapping vertical curves passing through the event.
    Handle left curves - iterate over the curves that intersect 
                 at the event point and defined to the left of the 
                 event. This is mostly where the output (sub curves 
		 or intersection points) is produced.
    Handle vertical curve (top) - special caring if the event id 
                 the upper end of a vertical curve. In case of vertical 
		 curves, this is where the output is produced.
    Handle right curves - iterate over the curves that intersect 
                 the event point and defined to the right of the 
		 event point. This is where new intersection points 
		 are calculated.
  End

  Convensions through out the code:
  In order to make the code as readable as possible, some convensions were 
  made in regards to variable naming:

    xp - is the intersection point between two curves
    slIter - an iterator to the status line, always points to a curve.
    out - always refer to the output iterator

*/

template <class CurveInputIterator,  class SweepLineTraits_2,
          class SweepEvent, class CurveWrap>
class Sweep_line_2_impl
{
public:
  typedef SweepLineTraits_2 Traits;
  typedef typename Traits::Point_2 Point_2;
  typedef typename Traits::Curve_2 Curve_2;
  typedef typename Traits::X_monotone_curve_2 X_monotone_curve_2;

  typedef SweepEvent Event;
  typedef Point_less_functor<Point_2, Traits> PointLess;
  typedef std::map<const Point_2 *, Event*, PointLess> EventQueue; 
  typedef typename EventQueue::iterator EventQueueIter;
  typedef typename EventQueue::value_type EventQueueValueType;
  typedef std::vector<Event*> EventPtrContainer;
  typedef typename EventPtrContainer::iterator EventPtrContainerIter;

  typedef typename Event::SubCurveIter EventCurveIter;

  typedef CurveWrap Subcurve;
  typedef std::list<Subcurve*> SubCurveList;
  typedef typename SubCurveList::iterator SubCurveListIter;

  typedef Status_line_curve_less_functor<Traits, Subcurve> StatusLineCurveLess;
  typedef typename StatusLineCurveLess::Compare_param CompareParams;
  typedef std::set<Subcurve*, StatusLineCurveLess> StatusLine;
  typedef typename StatusLine::iterator StatusLineIter;
  typedef typename Event::VerticalCurveList VerticalCurveList;
  typedef typename Event::VerticalCurveListIter VerticalCurveListIter;
  typedef typename Event::VerticalXPointSet VerticalXPointList;
  typedef typename Event::VerticalXPointSetIter VerticalXPointListIter;

  typedef std::list<Event *> EventList;
  typedef typename EventList::iterator EventListIter;

  typedef std::list<X_monotone_curve_2> CurveList;
  typedef typename CurveList::iterator CurveListIter;

  class  SweepLineGetSubCurves {};
  class  SweepLineGetPoints {};
  class  SweepLineGetInterCurveList {};
  class  SweepLinePlanarmap {};

  Sweep_line_2_impl()  : m_traits(new Traits()), m_traitsOwner(true),
    m_includeEndPoints(true), m_found_intersection(false), is_first_point(true)
  {
  }
  Sweep_line_2_impl(Traits *t) : m_traits(t), m_traitsOwner(false),
    m_includeEndPoints(true), m_found_intersection(false), is_first_point(true)
  {
  }

  virtual ~Sweep_line_2_impl();

  /*!
   *  Given a container of curves, this function returns a list of curves
   *  that are created by intersecting the input curves.
   *  \param curves_begin the input iterator that points to the first curve 
   *                      in the range.
   *  \param curves_end the input past-the-end iterator of the range.
   *  \param subcurves an iterator to the first curve in the range
   *                   of curves created by intersecting the input curves.
   *  \param overlapping indicates whether overlapping curves should be 
   *                   reported once or multiple times. If false, the 
   *                   overlapping curves are reported once only.
   */
  template <class OutpoutIterator>
  void  get_subcurves(CurveInputIterator begin, CurveInputIterator end, 
		      OutpoutIterator subcurves, bool overlapping = false)
  { 
    init(begin, end);
    SL_DEBUG(
      PrintSubCurves();
      PrintEventQueue();
    )
    m_overlapping = overlapping;
    sweep(subcurves, SweepLineGetSubCurves());
  }

  /*!
   *  Given a range of curves, this function returns a list of points 
   *  that are the intersection points of the curves.
   *  The intersections are calculated using the sweep algorithm.
   *  \param curves_begin the input iterator that points to the first curve 
   *                      in the range.
   *  \param curves_end the input past-the-end iterator of the range.
   *  \param subcurves an iterator to the first curve in the range
   *                   of curves created by intersecting the input curves.
   *  \param endpoints if true, the end points of the curves are reported
   *                   as intersection points. Defaults to true.
   *  \param overlapping indicates whether there are overlapping curves
   *                     in the input range. Defaults to false.
   */
  template <class OutpoutIterator>
  void  get_intersection_points(CurveInputIterator begin, 
                                CurveInputIterator end, 
                                OutpoutIterator points,
                                bool includeEndPoints = true)
  { 
    init(begin, end);
    SL_DEBUG(
      PrintSubCurves();
      PrintEventQueue();
    )
    m_includeEndPoints = includeEndPoints;
    m_found_intersection = false;
    sweep(points, SweepLineGetPoints());
  }

 /*!
  *  Given a range of curves, this function returns an iterator 
  *  to the beginning of a range that contains the list of curves 
  *  for each intersection point between any two curves in the 
  *  specified range.
  *  The intersections are calculated using the sweep algorithm.
  *  \param begin the input iterator that points to the first curve 
  *                      in the range.
  *  \param end the input past-the-end iterator of the range.
  *  \param intersecting_curves an iterator to the output
  *  \param endpoints if true, the end points of the curves are reported
  *                   as intersection points. Defaults to true.
  */
  template <class OutputIterator>
  void  get_intersecting_curves(CurveInputIterator begin, 
				CurveInputIterator end, 
				OutputIterator intersecting_curves,
				bool endpoints = true)
  { 
    // TODO - implement...
    SweepLineGetInterCurveList tag;
    (void) tag;
  }

  bool do_curves_intersect(CurveInputIterator begin, 
                            CurveInputIterator end)
  {
    init(begin, end);
    SL_DEBUG(
      PrintSubCurves();
      PrintEventQueue();
    )
    m_includeEndPoints = false;
    std::vector<Point_2> dummy;
    m_stop_at_first_int = true;
    m_found_intersection = false;
    sweep(std::back_inserter(dummy), SweepLineGetPoints(), true);
    return m_found_intersection;
  }


protected:


  void init(CurveInputIterator begin, CurveInputIterator end);
  void init_curve(X_monotone_curve_2 &curve);

  /*! The main loop to calculate intersections among the curves
   *  Looping over the events in the queue, for each event we first
   *  handle the curves that are tothe left of the event point (i.e., 
   *  curves that we are done with), and then we look at the curves 
   *  to the right of the point, which means we attept to find intersections
   *  between them and their neighbours on the sweep line.
   */

  template <class OutpoutIterator, class Op>
  void sweep(OutpoutIterator out, Op tag, bool stop_at_first_int=false)
  {
    EventQueueIter eventIter = m_queue->begin();
    m_prevPos = *eventIter->first;
    m_sweepLinePos = *(eventIter->first);

    while ( eventIter != m_queue->end() )
    {
      const Point_2 *p = (eventIter->first);
      if ( m_traits->compare_x(m_sweepLinePos, *p) == SMALLER ) {
        m_prevPos = m_sweepLinePos;
	m_verticals.clear();
	m_verticalSubCurves.clear();
      }
      m_sweepLinePos = *p;
      m_currentPos = *p;

      p = (eventIter->first);
      m_currentEvent = eventIter->second;
      SL_DEBUG(std::cout << "------------- " << *p << " --------------"
	       << std::endl;
	       PrintStatusLine();
	       m_currentEvent->Print();
      )
      
      if ( m_traits->compare_x(*(eventIter->first), m_sweepLinePos) != EQUAL) {
	SL_DEBUG(std::cout << "====================== clearing miniq " 
		 << eventIter->first  << " "
		 << m_prevPos << "\n";)
	m_miniq.clear();
      }
      m_miniq.push_back(m_currentEvent);
      

      handle_vertical_curve_bottom(tag);
      handle_vertical_overlap_curves();
      handle_left_curves(out, tag);
      
      m_queue->erase(eventIter);
      
      handle_vertical_curve_top(out, tag);
      handle_right_curves(out, tag);
      eventIter = m_queue->begin();
    }

    if ( stop_at_first_int && m_found_intersection )
      return;
  }

  void handle_vertical_curve_bottom(SweepLineGetSubCurves &tag);
  void handle_vertical_curve_bottom(SweepLineGetPoints &tag);
  void handle_vertical_overlap_curves();



  /*! 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>
  void handle_left_curves(OutpoutIterator out, 
			SweepLineGetSubCurves &tag)
  {
    SL_DEBUG(std::cout << "Handling left curve" << std::endl;)
    SL_DEBUG(m_currentEvent->Print();)

    EventCurveIter leftCurveIter = m_currentEvent->left_curves_begin();
    m_currentPos = m_prevPos;
    const Point_2 &eventPoint = m_currentEvent->get_point();

    m_use_hint_for_erase = false;
    while ( leftCurveIter != m_currentEvent->left_curves_end() )  
    // ** fix here
    {
      Subcurve *leftCurve = *leftCurveIter; 
      const X_monotone_curve_2 &cv = leftCurve->get_curve();
      const Point_2 &lastPoint = leftCurve->get_last_point();

      if ( leftCurve->is_source(eventPoint))
      {      
        if ( !leftCurve->is_target(lastPoint) )
        {
          X_monotone_curve_2 a,b;
          m_traits->curve_split(cv, a, b, lastPoint);
          add_curve_to_output(a, leftCurve, out);
        } else {
          add_curve_to_output(cv, leftCurve, out);
        }
      } else if ( leftCurve->is_target(eventPoint))
      {
        if ( !leftCurve->is_source(lastPoint))
        {
          X_monotone_curve_2 a,b;
          m_traits->curve_split(cv, a, b, lastPoint);
          add_curve_to_output(b, leftCurve, out);
        } else {
          add_curve_to_output(cv, leftCurve, out);
        }

      } else { 
        X_monotone_curve_2 a,b;
        if ( leftCurve->is_source(lastPoint)) {
          m_traits->curve_split(cv, a, b, eventPoint);
          add_curve_to_output(a, leftCurve, out);
        } else if ( leftCurve->is_target(lastPoint)) {
          m_traits->curve_split(cv, b, a, eventPoint);
          add_curve_to_output(a, leftCurve, out);
        } else {
          const X_monotone_curve_2 &lastCurve = leftCurve->get_last_curve();
          if ( leftCurve->is_source_left_to_target() ) {
            m_traits->curve_split(lastCurve, a, b, eventPoint);
            add_curve_to_output(a, leftCurve, out);
          } else {
	    m_traits->curve_split(lastCurve, b, a, eventPoint);
	    add_curve_to_output(a, leftCurve, out);
          }
        }
        leftCurve->set_last_point(eventPoint);
        leftCurve->set_last_curve(b); 
      
      }
      
      // remove curve from the status line (also checks intersection 
      // between the neighbouring curves)
      remove_curve_from_status_line(leftCurve);
      m_use_hint_for_erase = true;

      m_currentPos = m_prevPos;
      ++leftCurveIter;
    }
    SL_DEBUG(std::cout << "Handling left curve END" << std::endl;)
      
  }

  /*!
   *  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