sweep_curves_base_2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 1,701 行 · 第 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_old/Sweep_curves_base_2.h,v $
// $Revision: 1.3 $ $Date: 2004/09/27 09:23:51 $
// $Name:  $
//
// Author(s)     : Eti Ezra <[e-mail]>
//                 Ron Wein <[e-mail]>

#ifndef CGAL_SWEEP_CURVES_BASE_2_H
#define CGAL_SWEEP_CURVES_BASE_2_H

#include <vector>
#include <list>
#include <map>
#include <set>

#include <CGAL/In_place_list.h>
#include <CGAL/Handle_for.h>
#include <CGAL/assertions.h>

#ifdef CGAL_SWEEP_LINE_DEBUG
#define CGAL_SL_DEBUG(x) x
#else
#define CGAL_SL_DEBUG(x) 
#endif

//#include <CGAL/IO/leda_window.h>  //used for visualization -

CGAL_BEGIN_NAMESPACE

template <class CurveInputIterator, class SweepLineTraits_2, 
  class Point_plus_, class X_curve_plus_>
class Sweep_curves_base_2 
{
public:
  typedef typename  SweepLineTraits_2::X_curve    X_curve;
protected:
  typedef Sweep_curves_base_2<CurveInputIterator,
    SweepLineTraits_2,Point_plus_,X_curve_plus_>  Self;

  /*!
  Curve_node_rep holds a curve participating in the sweep proccess. 
  It contains a curve and a container of points.
  The points container refers to all the intersedction points 
  (including edge points) calculated so far by the sweep line.
  These points are ordered from left to right on the curve, 
  which means they are sorted in a way we get immidiately all 
  the disjoint subcurves reduce by the curve.
  */

  class Curve_node_rep;
  class Curve_node;
  class Intersection_point_node;

  // SUNPRO requires these friends.
  friend class Curve_node_rep;
  friend class Curve_node;
  friend class Intersection_point_node;
  
  class Curve_node_rep { 
  public:
    typedef SweepLineTraits_2                   Traits;
    typedef Point_plus_                         Point_plus; 
    typedef X_curve_plus_                       X_curve_plus;
    
    typedef typename Traits::Point              Point;
    typedef std::vector<Point_plus>             Points_container;

    Curve_node_rep(const X_curve_plus& cv, const Point& p, 
		   Traits* traits_) : 
      cv_(cv), traits(traits_) {
      points.push_back( Point_plus(p) );
    }

    Curve_node_rep(const X_curve_plus& cv, 
                   const Point_plus& p, Traits* traits_) : 
      cv_(cv), traits(traits_)  {
      points.push_back(p);
    }

    ~Curve_node_rep() {}

    // here we only compare addresses of represenattion.
    bool operator==(const Curve_node_rep& rep) const 
    {
      // first at all comparing pointers to accelarate this operation.
      if (this == &rep)
        return true;
      if (&cv_ == &rep.cv_ && &points == &(rep.points))
        return true;

      return false;
    }

    bool operator!=(const Curve_node_rep& rep) const 
    {
      return !operator==(rep);
    }
    
  protected:
    friend class Curve_node;

    X_curve_plus         cv_;  // hold the left-most intersecting point.
    Points_container     points;
    Traits               *traits;

  private:
    const Point& leftmost(const Point &p1, const Point &p2) const
    {
      Comparison_result res = traits->compare_xy(p1,p2);

      return ((res == SMALLER) ? p1 : p2);
    }
  };
  
  /*!
    A handle to a curve node. This is just a wrapper class with no members.
  */
  // The handle to curve node.
  class Curve_node : public Handle_for<Curve_node_rep> {
    typedef Handle_for<Curve_node_rep>           Handle_for_Curve_node_rep;
  public:
    typedef  Point_plus_                         Point_plus;
    typedef  X_curve_plus_                       X_curve_plus;
    typedef  SweepLineTraits_2                   Traits;
    typedef  typename Traits::X_curve            X_curve; 
    typedef  typename Traits::Point              Point;
    
    typedef typename Curve_node_rep::Points_container   Points_container;
    typedef typename Points_container::iterator         Points_iterator;
    typedef typename Points_container::const_iterator  
	    					Points_const_iterator;
#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
    using Handle_for_Curve_node_rep::ptr;
#endif

    Curve_node(Traits *traits_) : 
      Handle_for_Curve_node_rep(traits_) {
#ifdef CGAL_MAKE_PROFILING
      std::cout<<"alloc handle for DEFAULT Curve_node_rep"<<endl;
#endif
    }
    
    Curve_node(const X_curve_plus& cv, Traits *traits_) : 
      Handle_for_Curve_node_rep(Curve_node_rep(cv, traits_)) {
#ifdef CGAL_MAKE_PROFILING
      std::cout<<"alloc handle for Curve_node_rep(cv)" << cv << endl;
#endif
    }
    
    Curve_node(const X_curve_plus& cv, const Point& p, Traits *traits_) : 
      Handle_for_Curve_node_rep(Curve_node_rep(cv,p, traits_)) {
#ifdef CGAL_MAKE_PROFILING
      std::cout << "alloc handle for Curve_node_rep(cv,p)" << cv << " "
                << p << endl;
#endif
    }

    Curve_node(const X_curve_plus& cv, const Point_plus& p, 
	       Traits *traits_) : 
      Handle_for_Curve_node_rep(Curve_node_rep(cv,p,traits_)) {
#ifdef CGAL_MAKE_PROFILING
      std::cout<<"allocating handle for Curve_node_rep(cv,p_plus)" 
               << cv <<" "<< p.point() << endl;
#endif
    }
    
    Curve_node(const Curve_node& cv_node) : 
      Handle_for_Curve_node_rep(cv_node) {
#ifdef CGAL_MAKE_PROFILING
      std::cout<<"allocating handle for cv_node" << endl;
#endif
    }

    ~Curve_node() {}

    bool operator==(const Curve_node& cv_node) const 
    {
      return *ptr() == *(cv_node.ptr());
    }

    bool operator!=(const Curve_node& cv_node) const 
    {
      return !operator==(cv_node);
    }

    void  push_event_point(const Point_plus &event_point) {
      ptr()->points.push_back(event_point);
    }
    
    void  erase_rightmost_point() { 
      Points_iterator  iter = ptr()->points.end();
      iter--;
      ptr()->points.erase(iter); 
    } 

    const X_curve_plus& get_curve() const { 
      return  ptr()->cv_; 
    }
    
    Point_plus& get_rightmost_point() { 
      CGAL_assertion ( ptr()->points.size() > 0);
      return *(ptr()->points.rbegin());
    }
    
    const Point_plus& get_rightmost_point() const { 
      CGAL_assertion ( ptr()->points.size() > 0);
      return *(ptr()->points.rbegin());
    }

    Points_iterator  points_begin() { 
      return  ptr()->points.begin(); 
    }
    
    Points_iterator  points_end() { 
      return  ptr()->points.end(); 
    }
    
    Points_const_iterator  points_begin() const { 
      return  ptr()->points.begin(); 
    }
    
    Points_const_iterator  points_end() const { 
      return  ptr()->points.end(); 
    }
    
    Self& operator=(const Self &cv_node)
    {
      Handle_for_Curve_node_rep::operator=(cv_node);
      
      return *this;
    }
    
  };

  /*!
    A class describing an intersection point.
    It contains the point itself and a list of
    all curves going through that point, ordered by
    compare_at_x and compare_at_x_right of the traits.
  */
  class Intersection_point_node {
    typedef Curve_node                                  Curve_node_;
  public:
    typedef  SweepLineTraits_2                          Traits;
    typedef  Point_plus_                                Point_plus;
    typedef  X_curve_plus_                              X_curve_plus;
    typedef  typename Traits::X_monotone_curve_2        X_monotone_curve_2; 
    typedef  typename Traits::Point_2                   Point_2;
    typedef  Intersection_point_node                    Self;
    typedef  std::vector<Curve_node_>                   Curve_node_container;
    typedef  typename Curve_node_container::iterator    Curve_node_iterator;
    typedef  typename Curve_node_container::const_iterator  
                                                Curve_node_const_iterator;
    typedef typename Traits::Has_left_category          Has_left_category;

      // Obsolete
    typedef Point_2                                     Point;
    typedef X_monotone_curve_2                                   X_curve;

    Intersection_point_node(Traits *traits_) : traits(traits_) {}
    
    Intersection_point_node(const Curve_node_& cv, 
                            Traits *traits_) : 
      intersect_p(cv.get_rightmost_point()), traits(traits_) {
      curves.push_back(cv);  
    }
    
    Intersection_point_node(const Curve_node_& cv, 
                            const Point_plus& ref_point, 
                            Traits *traits_) : 
      intersect_p(ref_point), traits(traits_) {
      curves.push_back(cv);  
    }
    
    Intersection_point_node(const Curve_node_& cv1, 
                            const Curve_node_& cv2, 
                            const Point_plus& ref_point, 
                            Traits *traits_) : 
      intersect_p(ref_point), traits(traits_) {
      
      Comparison_result result = _curves_compare_y_at_x_right(cv1.get_curve(), 
							   cv2.get_curve(), 
							   ref_point.point());

      if (result == SMALLER){
        curves.push_back(cv1);
        curves.push_back(cv2);
      }
      else if (result == LARGER){
        curves.push_back(cv2);
        curves.push_back(cv1);
      }
      else { //equal: if one of the curve is to left of ref_point - 
        // this curve will be pushed first.
        if (traits->point_equal(
              rightmost(traits->curve_source(cv1.get_curve()), 
                        traits->curve_target(cv1.get_curve())),
              ref_point.point())) {
          curves.push_back(cv1);
          curves.push_back(cv2);
        }
        else { //include the case : 
          // if (rightmost(traits.curve_source(cv2.get_curve()), 
          // traits.curve_target(cv2.get_curve())) == ref_point)
          curves.push_back(cv2);
          curves.push_back(cv1);
        } 
      }
    } 
    
    /*!
      Merges the curves of the "this" point and the input node.
      The point in the input point node has to be the same as
      the point in this instance.
  
      This function orders all the curves enemating from 
      intersect_p in counter clock wise order, particularly, the order 
      when comparing the curves to the right of the intersection point 
      is monotonicaly increasing.
    */
    void merge(const Self& point_node)
    {
      CGAL_assertion (intersect_p == point_node.get_point());
      
      CGAL_assertion (curves.size() > 0 && 
                      point_node.curves_begin() != point_node.curves_end());
      
      Curve_node_container    merged_left_curves, merged_right_curves;