SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Sweep_line_2.h

Go to the documentation of this file.

// Copyright (c) 2005  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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/Sweep_line_2.h $
// $Id: Sweep_line_2.h 50366 2009-07-05 12:56:48Z efif $
// 
//
// Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 (based on old version by Tali Zvi)

#ifndef CGAL_SWEEP_LINE_2_H
#define CGAL_SWEEP_LINE_2_H

#include <list>
#include <CGAL/Object.h>
#include <CGAL/Basic_sweep_line_2.h>
#include <CGAL/Sweep_line_2/Sweep_line_curve_pair.h>
#include <CGAL/Arrangement_2/Open_hash.h>

CGAL_BEGIN_NAMESPACE

template < class Traits_,
           class Visitor_,
           class Subcurve_ = Sweep_line_subcurve<Traits_>,
           class Event_ = Sweep_line_event<Traits_, Subcurve_>,
           typename Allocator_ = CGAL_ALLOCATOR(int) >
class Sweep_line_2 : public Basic_sweep_line_2<Traits_,
                                               Visitor_,
                                               Subcurve_,
                                               Event_,
                                               Allocator_>
{
public:

  typedef Traits_                                        Traits_2;
  typedef Visitor_                                       Visitor;
  typedef Event_                                         Event;
  typedef Subcurve_                                      Subcurve;
  typedef Allocator_                                     Allocator;

  typedef Basic_sweep_line_2<Traits_2,
                             Visitor,
                             Subcurve,
                             Event,
                             Allocator>                  Base;

  typedef typename Base::Traits_adaptor_2                Traits_adaptor_2;
  typedef typename Traits_adaptor_2::Point_2             Point_2;
  typedef typename Traits_adaptor_2::X_monotone_curve_2  X_monotone_curve_2;
 
  typedef typename Base::Event_queue_iterator         Event_queue_iterator;
  typedef typename Event::Subcurve_iterator           Event_subcurve_iterator;

  typedef typename Base::Base_event                   Base_event;
  typedef typename Base_event::Attribute              Attribute;

  typedef typename Base::Base_subcurve                Base_subcurve;
  
  typedef std::list<Subcurve*>                        Subcurve_container;
  typedef typename Subcurve_container::iterator       Subcurve_iterator; 

  typedef typename Base::Status_line_iterator         Status_line_iterator;
  
  typedef CGAL::Curve_pair<Subcurve>                       Curve_pair;
  typedef CGAL::Curve_pair_hasher<Subcurve>                Curve_pair_hasher;
  typedef CGAL::Equal_curve_pair<Subcurve>                 Equal_curve_pair;
  typedef Open_hash<Curve_pair,
                    Curve_pair_hasher,
                    Equal_curve_pair>                 Curve_pair_set;

  typedef random_access_input_iterator<std::vector<Object> >
                                                      vector_inserter;

protected:

  // Data members:
  Subcurve_container  m_overlap_subCurves;
                                     // Contains all of the new sub-curves
                                     // creaed by an overlap.

  Curve_pair_set m_curves_pair_set;  // A lookup table of pairs of Subcurves
                                     // that have been intersected.

  std::vector<Object> m_x_objects;   // Auxiliary vector for storing the
                                     // intersection objects.

  X_monotone_curve_2  sub_cv1;       // Auxiliary varibales
  X_monotone_curve_2  sub_cv2;       // (for splitting curves).

public:

  Sweep_line_2 (Visitor * visitor) :
    Base(visitor),
    m_curves_pair_set(0)
  {}


  Sweep_line_2 (const Traits_2 * traits, Visitor * visitor) :
    Base(traits, visitor),
    m_curves_pair_set(0)
  {}

  virtual ~Sweep_line_2()
  {}

protected:

  virtual void _init_structures ();

  virtual void _complete_sweep ();

  virtual void _handle_left_curves ();

  virtual void _handle_right_curves ();

  virtual bool _add_curve_to_right (Event * event, Subcurve * curve,
                                    bool overlap_exist = false);

  void _fix_overlap_subcurves();

  void _handle_overlap (Event * event, Subcurve * curve,
                        Event_subcurve_iterator iter, bool overlap_exist);
  
  void _intersect (Subcurve * c1, Subcurve * c2);

  void _remove_curve_from_status_line (Subcurve * leftCurve,
                                       bool remove_for_good);

  void _create_intersection_point (const Point_2 & xp,
                                   unsigned int mult,
                                   Subcurve *& c1,
                                   Subcurve *& c2,
                                   bool is_overlap = false);

  void _fix_finished_overlap_subcurve (Subcurve * sc);

};

CGAL_END_NAMESPACE

// The member-function definitions can be found in:
#include <CGAL/Sweep_line_2/Sweep_line_2_impl.h>

#endif