pmwx_aggregate_insert.h

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

// 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/Arrangement/include/CGAL/Sweep_line_2/Pmwx_aggregate_insert.h,v $
// $Revision: 1.27 $ $Date: 2004/11/03 14:41:10 $
// $Name:  $
//
// Author(s)     : Tali Zvi <[e-mail]>

#ifndef CGAL_PMWX_AGGREGATE_INSERT_H
#define CGAL_PMWX_AGGREGATE_INSERT_H

#include <CGAL/Sweep_line_2/Sweep_line_2_impl.h>
#include <CGAL/Sweep_line_2/Pmwx_sweep_line_event.h>
#include <CGAL/Sweep_line_2/Pmwx_sweep_line_curve.h>
#include <CGAL/assertions.h>
#include <list>

CGAL_BEGIN_NAMESPACE

template <class CurveInputIterator, class SweepLineTraits_2, 
          class PM_, class Change_notification_>
class Pmwx_aggregate_insert :
  public Sweep_line_2_impl<CurveInputIterator, SweepLineTraits_2,
    Pmwx_sweep_line_event<SweepLineTraits_2, 
      Pmwx_sweep_line_curve<SweepLineTraits_2, 
                            typename PM_::Halfedge_handle> > ,
        Pmwx_sweep_line_curve<SweepLineTraits_2, 
                              typename PM_::Halfedge_handle> >
{
public:
  typedef SweepLineTraits_2 Traits;
  typedef typename Traits::X_monotone_curve_2 X_monotone_curve_2;
  typedef typename Traits::Point_2 Point_2;

  typedef PM_ PM;
  typedef typename PM::Halfedge_iterator  Halfedge_iterator; 
  typedef typename PM::Halfedge_handle Halfedge_handle;

  
  //typedef typename PM::Locate_type Locate_type;

  typedef Pmwx_sweep_line_curve<SweepLineTraits_2, 
                                Halfedge_handle> SubCurve;
  typedef Pmwx_sweep_line_event<SweepLineTraits_2, SubCurve> Event;
  typedef typename SubCurve::PmwxInsertInfo PmwxInsertInfo;

  typedef Change_notification_ Change_notification;
  typedef Sweep_line_2_impl<CurveInputIterator, Traits, Event, SubCurve> Base;

  typedef typename Event::VerticalXEventSet VerticalXEventSet;
  typedef typename Event::VerticalXEventSetIter VerticalXEventSetIter;

  typedef Pmwx_sweep_line_curve<SweepLineTraits_2, 
                                typename PM_::Halfedge_handle>  Subcurve;

  // repeated typedefs from the base class to avoid warnings
  typedef typename Base::EventQueueIter EventQueueIter;
  typedef typename Base::EventCurveIter EventCurveIter;
  typedef typename Base::VerticalCurveList VerticalCurveList;
  typedef typename Base::VerticalCurveListIter VerticalCurveListIter;
  typedef typename Base::StatusLineIter StatusLineIter;
  typedef typename Base::SubCurveList SubCurveList;
  typedef typename Base::SubCurveListIter SubCurveListIter;
  typedef typename Base::SweepLinePlanarmap SweepLinePlanarmap;
  typedef typename Base::EventQueueValueType EventQueueValueType;

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Base::m_queue;
  using Base::m_prevPos;
  using Base::m_traits;
  using Base::m_sweepLinePos;
  using Base::m_verticals;
  using Base::m_verticalSubCurves;
  using Base::m_currentPos;
  using Base::m_currentEvent;
  using Base::m_miniq;
  using Base::m_use_hint_for_erase;
  using Base::m_statusLine;
  using Base::m_tmpOut;
  using Base::m_status_line_insert_hint;
  using Base::m_events;
#endif

  Pmwx_aggregate_insert() : 
    Base(), m_change_not(NULL) {}
  
  Pmwx_aggregate_insert(Traits *traits_) : 
    Base(traits_), m_change_not(NULL) {} 
  
  virtual ~Pmwx_aggregate_insert() {}
  
  /*! Initializes the data structures to work with:
    - x-monotonize the input curves
    - for each end point of each curve create an event
    - for each curve in the planarmap do the same
    - initialize the event queue
    -
  */  
  void init(CurveInputIterator begin, CurveInputIterator end, PM &pm)
  {
    Base::init(begin, end);
    
    Halfedge_iterator eit;
    for (eit = pm.halfedges_begin(); eit != pm.halfedges_end(); ++eit, ++eit) 
    {
      init_curve(eit->curve());
    }
    pm.clear();
  }

  void insert_curves(CurveInputIterator begin, 
                     CurveInputIterator end, 
                     PM &planarMap,
                     Change_notification* change_notification)
  {
    m_change_not = change_notification;
    std::vector<X_monotone_curve_2> subcurves;
    init(begin, end, planarMap); 
    

    // initialize the last event in each event 
    for ( EventQueueIter qiter = m_queue->begin();
          qiter != m_queue->end() ; ++qiter ) 
    {
      Event *e = qiter->second;
      for  (EventCurveIter rightCurveIter = e->right_curves_begin() ;
            rightCurveIter != e->right_curves_end() ; 
            ++rightCurveIter )
        (*rightCurveIter)->set_last_event(e);
      VerticalCurveList &vcurves = e->get_vertical_curves();
      VerticalCurveListIter vciter = vcurves.begin();

      while ( vciter != vcurves.end() )
      {
        if ((*vciter)->is_bottom_end(e->get_point()))
          (*vciter)->set_last_event(e);
        ++vciter;

      }
    }
    SL_DEBUG(
      PrintSubCurves();
      PrintEventQueue();
      );

    sweep(planarMap, SweepLinePlanarmap());
  }
  
protected:

  /*! 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 to the 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 attempt to find intersections
    between them and their neighbours on the sweep line.
  */
  template <class _PM_, class Op>
  void sweep(_PM_ &pm, Op tag)
  {
    EventQueueIter eventIter = m_queue->begin();
    m_prevPos = *((*eventIter).first);
   // Point_2 referencePoint;

    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(pm, tag);

      m_queue->erase(eventIter);

      handle_vertical_curve_top(pm, tag);
      handle_right_curves(pm, tag);
      eventIter = m_queue->begin();
    }
  }

  /*! 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.
  */
  void handle_left_curves(PM &pm, SweepLinePlanarmap &tag)
  {
    SL_DEBUG(std::cout << "Handling left curve" << std::endl;);
    SL_DEBUG(m_currentEvent->Print(););
    SL_DEBUG((m_currentEvent->get_insert_info()->Print()););

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

    Halfedge_handle h(NULL);
    m_use_hint_for_erase = false;
    SubCurve *leftCurvePrev = 0;
    bool are_overlap = false; 
    while ( leftCurveIter != m_currentEvent->left_curves_end() )  
    {
      SubCurve *leftCurve = *leftCurveIter; 
      const X_monotone_curve_2 &cv = leftCurve->get_curve();
      const Point_2 &lastPoint = leftCurve->get_last_point();


      
      if(leftCurvePrev && do_curves_overlap(leftCurvePrev,leftCurve) )
          are_overlap = true;
      




      if ( leftCurve->is_source(eventPoint))
      {
        if ( !leftCurve->is_target(lastPoint) )
        {
          X_monotone_curve_2 a,b;
          m_traits->curve_split(cv, a, b, lastPoint);
          if(!are_overlap)
            h = insert_to_pm(a, leftCurve, h, pm);
        }
        else 
        {
          if(!are_overlap)
            h = insert_to_pm(cv, leftCurve, h, pm);
        }
      }
      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);
            if(!are_overlap)
              h = insert_to_pm(b, leftCurve, h, pm);
          }
          else 
          {
            if(!are_overlap)
              h = insert_to_pm(cv, leftCurve, h, pm);
          }
        }
        else  // the event point passes through the interior of 'cv'
        { 
          X_monotone_curve_2 a,b;
          if ( leftCurve->is_source(lastPoint))
          {
            m_traits->curve_split(cv, a, b, eventPoint);
            if(!are_overlap)
              h = insert_to_pm(a, leftCurve, h, pm);
          }  
          else
            if ( leftCurve->is_target(lastPoint))
            {
              m_traits->curve_split(cv, b, a, eventPoint);
              if(!are_overlap)
                h = insert_to_pm(a, leftCurve, h, pm);
            }
            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);
                if(!are_overlap)
                  h = insert_to_pm(a, leftCurve, h, pm);
              }
              else 
              {
                m_traits->curve_split(lastCurve, b, a, eventPoint);
                if(!are_overlap)
                  h = insert_to_pm(a, leftCurve, h, pm);
              }
            }
            leftCurve->set_last_point(eventPoint);
            leftCurve->set_last_curve(b); 
            leftCurve->set_last_event(m_currentEvent);
        }

        // before deleting check new neighbors that will become after deletion
        remove_curve_from_status_line(leftCurve);
        m_use_hint_for_erase = true;
      
        m_currentPos = m_prevPos;
        leftCurvePrev = *leftCurveIter; 
        ++leftCurveIter;
        are_overlap = false;
        
    }  
    
    // when done handling the left curves, we prepare for the right curves
    m_currentEvent->init_right_curves();
  }

  /*!
   * Handles the degenerate case of vertical curves. Most of the cases
   * that occur with vertical curves are handled by this method and 
   * HandleVerticalCurveTop 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