pmwx_aggregate_insert_old.h

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

// 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_old.h,v $
// $Revision: 1.4 $ $Date: 2004/09/23 19:37:57 $
// $Name:  $
//
// Author(s)     : Eti Ezra <[e-mail]>

#ifndef CGAL_PMWX_AGGREGATE_INSERT_OLD_H
#define CGAL_PMWX_AGGREGATE_INSERT_OLD_H

#include <vector>
#include <list>

#include <CGAL/In_place_list.h>
#include <CGAL/Handle.h>
#include <CGAL/assertions.h>
#include <CGAL/Sweep_line_2_old/Sweep_curves_base_2.h>
#include <CGAL/Planar_map_2/Point_plus_handle.h>

CGAL_BEGIN_NAMESPACE

struct Sweep_curves_to_planar_map_utils { 
  // X_curve_plus_id:
  // holds a curve and its id number. 
  // The addition of id number to a curve was made due to overlapping 
  // (in which some binary predicates return EQUAL, 
  // while we are interseted in sharp order relation. 
  template <class SweepLineTraits_2> 
  class X_curve_plus_id : public SweepLineTraits_2::X_curve
  {
  public:
    typedef SweepLineTraits_2             Traits;
    typedef typename Traits::X_curve      curve; 
    typedef typename Traits::Point        Point;
    
    X_curve_plus_id() : curve() {};
    X_curve_plus_id(const curve &cv, unsigned int i) : curve(cv) , _id(i) {}
    X_curve_plus_id(const X_curve_plus_id &cv) : curve(cv) , _id(cv.id()) {}
    ~X_curve_plus_id(){}
    
    X_curve_plus_id& operator=(const X_curve_plus_id &cv) {
      curve::operator=(cv);
      _id = cv.id();
      return *this;
    }
    
    bool operator==(const X_curve_plus_id &cv) const {
      Traits traits;
      return (_id == cv.id() && traits.curve_equal(*this, cv));
    }
    
    void  set_id(unsigned int i) { _id = i; }
    unsigned int id() const { return _id; }
    
  protected:
    unsigned int _id;
  };
};

template <class CurveInputIterator, class SweepLineTraits_2, 
          class PM_, class Change_notification_>
class Pmwx_aggregate_insert_old  : 
  public Sweep_curves_base_2<
            CurveInputIterator, 
            SweepLineTraits_2, 
            Point_plus_handle<SweepLineTraits_2, typename PM_::Vertex_handle>, 
            Sweep_curves_to_planar_map_utils::
                                         X_curve_plus_id<SweepLineTraits_2> >
{
public:
  typedef CurveInputIterator                     Curve_iterator;
  typedef PM_                                    PM;
  typedef Change_notification_                   Change_notification;
  
  typedef typename PM::Vertex_handle              Vertex_handle;
  typedef typename PM::Halfedge_handle            Halfedge_handle;
  typedef typename PM::Vertex_const_handle        Vertex_const_handle;
  typedef typename PM::Halfedge_const_handle      Halfedge_const_handle;
  typedef typename  PM::Vertex_iterator           Vertex_iterator; 
  typedef typename  PM::Vertex_const_iterator     Vertex_const_iterator; 
  typedef typename  PM::Halfedge_iterator         Halfedge_iterator; 
  typedef typename  PM::Halfedge_const_iterator   Halfedge_const_iterator; 
 
  typedef SweepLineTraits_2                      Traits;
  typedef typename  Traits::X_curve               X_curve;
  typedef typename  Traits::Point                 Point;

  typedef Point_plus_handle<Traits, Vertex_handle>  Point_plus;
  typedef Sweep_curves_to_planar_map_utils::X_curve_plus_id<SweepLineTraits_2>
                                                 X_curve_plus;

  typedef Sweep_curves_base_2<Curve_iterator, Traits, 
    Point_plus, X_curve_plus>                        Base;
  
  typedef typename Base::Curve_node                  Curve_node;
  typedef typename Base::Intersection_point_node     Intersection_point_node;
  typedef typename Base::Points_iterator             Points_iterator;  
  typedef typename Base::Points_const_iterator       Points_const_iterator;
  typedef typename Base::Curve_node_iterator         Curve_node_iterator;
  typedef typename Base::Curve_node_const_iterator   Curve_node_const_iterator;
  typedef typename Base::X_curve_list                X_curve_list;
  typedef typename Base::X_curve_list_iterator       X_curve_list_iterator;
  typedef typename Base::Vertices_points_plus        Vertices_points_plus;
  typedef typename Base::Event_queue                 Event_queue;
  typedef typename Base::Status_line                 Status_line;
  
  typedef typename Vertices_points_plus::value_type  
                                            Vertices_points_plus_value_type; 
  typedef typename Event_queue::value_type           Event_queue_value_type;
  typedef typename Status_line::value_type           Status_line_value_type;
  
  typedef typename Vertices_points_plus::iterator 
                                              Vertices_points_plus_iterator;
  typedef typename Event_queue::iterator            Event_queue_iterator;  
  typedef typename Status_line::iterator            Status_line_iterator; 
  typedef typename std::list<Curve_node>::iterator  list_Curve_node_iterator;

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Base::traits;
  using Base::is_right;
#endif

  Pmwx_aggregate_insert_old() : 
    Base() {}
  
  Pmwx_aggregate_insert_old(Traits *traits_) : 
    Base(traits_) {} 
  
  ~Pmwx_aggregate_insert_old() {}
  
  void insert_curves(Curve_iterator curves_begin, 
                     Curve_iterator curves_end, 
                     PM &result,
                     Change_notification* change_notification)
  {
    Curve_iterator cv_iter;
    X_curve_list_iterator xcv_iter;
    
    typename Base::Less_xy  event_queue_pred(traits);
    Event_queue event_queue(event_queue_pred);
    typename Base::Less_yx  status_pred(traits);
    Status_line status(status_pred);

    // building a container of all curves in the input planar
    // map and the curves specified (which we break into x_monotone first)    
    X_curve_list x_monotone_curves;
    for (Halfedge_iterator h_iter = result.halfedges_begin(); 
         h_iter != result.halfedges_end(); ++h_iter, ++h_iter) {
      x_monotone_curves.push_back(h_iter->curve());
    }
    result.clear();

    // splitting all curves to x-monotone curves.
    for (cv_iter = curves_begin; cv_iter != curves_end; ++cv_iter){
      X_curve_list x_monotone_subcurves;
      traits->curve_make_x_monotone(*cv_iter,
                                    std::back_inserter(x_monotone_subcurves));

      for(X_curve_list_iterator iter = x_monotone_subcurves.begin(); 
          iter != x_monotone_subcurves.end(); ++iter) {
        x_monotone_curves.push_back(*iter);  
      }
    }

    // creating a container of all (unique) vertices
    typename Base::Less_xy  pred(traits);
    Vertices_points_plus  input_vertices(pred);
    for (xcv_iter = x_monotone_curves.begin(); 
         xcv_iter != x_monotone_curves.end(); ++xcv_iter){
      if (input_vertices.find(traits->curve_source(*xcv_iter)) == 
          input_vertices.end())  
        input_vertices.insert( Vertices_points_plus_value_type
                               (traits->curve_source(*xcv_iter), 
                                Point_plus(traits->curve_source(*xcv_iter))) );
      if (input_vertices.find(traits->curve_target(*xcv_iter)) == 
          input_vertices.end())  
        input_vertices.insert( Vertices_points_plus_value_type
                               (traits->curve_target(*xcv_iter), 
                                Point_plus(traits->curve_target(*xcv_iter))) );
    }
    
    
    // initializing the event queue with all edge points
    unsigned int id = 0;
    for ( xcv_iter = x_monotone_curves.begin(); 
          xcv_iter != x_monotone_curves.end(); ++xcv_iter, ++id) {
      X_curve cv(*xcv_iter);
      if (is_right(traits->curve_source(*xcv_iter), 
                   traits->curve_target(*xcv_iter)) )
        cv = traits->curve_opposite(*xcv_iter);
   
      Vertices_points_plus_iterator curr_point_plus = 
        input_vertices.find( traits->curve_source(cv) );

      // defining one cv_node for both source and target event points.  
      Curve_node cv_node = Curve_node(X_curve_plus(cv, id), 
                                      curr_point_plus->second, traits); 

      // creating the "event" for the queue
      Intersection_point_node  source_point_node = 
        Intersection_point_node(cv_node, curr_point_plus->second, traits );
      
      // if the "event" does not exist, we add it. Otherwise, we merge it
      // with the existing one.
      Event_queue_iterator  edge_point = 
        event_queue.find( traits->curve_source(cv) );

      if (edge_point == event_queue.end() || 
          edge_point->second.get_point() != source_point_node.get_point())