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

Go to the documentation of this file.

// Copyright (c) 2006  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/Arr_bounded_planar_topology_traits_2.h $
// $Id: Arr_bounded_planar_topology_traits_2.h 50366 2009-07-05 12:56:48Z efif $
// 
//
// Author(s) : Ron Wein        <wein@post.tau.ac.il>
//             Efi Fogel       <efif@post.tau.ac.il>
//             Eric Berberich  <ericb@post.tau.ac.il>

#ifndef CGAL_ARR_BOUNDED_PLANAR_TOPOLOGY_TRAITS_2_H
#define CGAL_ARR_BOUNDED_PLANAR_TOPOLOGY_TRAITS_2_H

#include <CGAL/Arr_tags.h>
#include <CGAL/Arr_topology_traits/Arr_planar_topology_traits_base_2.h>
#include <CGAL/Arr_topology_traits/Arr_bounded_planar_construction_helper.h>
#include <CGAL/Arr_topology_traits/Arr_bounded_planar_insertion_helper.h>
#include <CGAL/Arr_topology_traits/Arr_bounded_planar_overlay_helper.h>
#include <CGAL/Arr_topology_traits/Arr_bounded_planar_batched_pl_helper.h>
#include <CGAL/Arr_topology_traits/Arr_bounded_planar_vert_decomp_helper.h>
#include <CGAL/Arr_topology_traits/Arr_inc_insertion_zone_visitor.h>

CGAL_BEGIN_NAMESPACE

// Forward declaration:
template <class GeomTraits_, class TopTraits_> 
class Arrangement_on_surface_2;

template <class GeomTraits_,
          class Dcel_ = Arr_default_dcel<GeomTraits_> >
class Arr_bounded_planar_topology_traits_2 :
  public Arr_planar_topology_traits_base_2<GeomTraits_, Dcel_>
{
private:

  typedef Arr_planar_topology_traits_base_2<GeomTraits_, Dcel_> Base;

public:


  typedef GeomTraits_                                     Geometry_traits_2;
  typedef typename Base::Point_2                          Point_2;
  typedef typename Base::X_monotone_curve_2               X_monotone_curve_2;


  typedef Dcel_                                           Dcel;
  typedef typename Base::Size                             Size;
  typedef typename Base::Vertex                           Vertex;
  typedef typename Base::Halfedge                         Halfedge;
  typedef typename Base::Face                             Face;
  typedef typename Base::Outer_ccb                        Outer_ccb;
  typedef typename Base::Inner_ccb                        Inner_ccb;
  typedef typename Base::Isolated_vertex                  Isolated_vertex;

  // TODO remove adaptor as top-traits might be instantiated by Aos_2 itself
  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2>   Traits_adaptor_2;
  
  typedef Arr_bounded_planar_topology_traits_2<Geometry_traits_2, Dcel>
                                                          Self;
  

  // are inherited from the geometry traits
  typedef typename Traits_adaptor_2::Arr_left_side_tag   Arr_left_side_tag;
  typedef typename Traits_adaptor_2::Arr_bottom_side_tag Arr_bottom_side_tag;
  typedef typename Traits_adaptor_2::Arr_top_side_tag    Arr_top_side_tag;
  typedef typename Traits_adaptor_2::Arr_right_side_tag  Arr_right_side_tag;
  
  BOOST_MPL_ASSERT
  ((boost::is_same< Arr_left_side_tag, Arr_oblivious_side_tag >));
  BOOST_MPL_ASSERT
  ((boost::is_same< Arr_bottom_side_tag, Arr_oblivious_side_tag >));
  BOOST_MPL_ASSERT
  ((boost::is_same< Arr_top_side_tag, Arr_oblivious_side_tag >));
  BOOST_MPL_ASSERT
  ((boost::is_same< Arr_right_side_tag, Arr_oblivious_side_tag >));

  template<typename T, typename D>
  struct rebind
  {
    typedef Arr_bounded_planar_topology_traits_2<T,D> other;
  };

protected:

  // Data members:
  Face               *unb_face;     // The unbounded face.  

  // Copy constructor and assignment operator - not supported.
  Arr_bounded_planar_topology_traits_2 (const Self& );
  Self& operator= (const Self& );

public:



  Arr_bounded_planar_topology_traits_2 () :
    Base(),
    unb_face (NULL)
  {}

  Arr_bounded_planar_topology_traits_2 (const Geometry_traits_2 *tr) :
    Base (tr),
    unb_face (NULL)
  {}

  void assign (const Self& other);



  bool is_empty_dcel () const
  {
    // An empty bounded arrangement has no edges or vertices.
    return (this->m_dcel.size_of_vertices() == 0 &&
            this->m_dcel.size_of_halfedges() == 0);
  }

  inline bool is_concrete_vertex (const Vertex *) const
  {
    return (true);
  }

  Size number_of_concrete_vertices () const
  {
    // All vertices are concrete.
    return (this->m_dcel.size_of_vertices());
  }

  inline bool is_valid_vertex (const Vertex *) const
  {
    return (true);
  }

  Size number_of_valid_vertices () const
  {
    // All vertices are valid.
    return (this->m_dcel.size_of_vertices());
  }

  inline bool is_valid_halfedge (const Halfedge *) const
  {
    return (true);
  }

  Size number_of_valid_halfedges () const
  {
    // All halfedges are valid.
    return (this->m_dcel.size_of_halfedges());
  }

  inline bool is_valid_face (const Face *) const
  {
    return (true);
  }

  Size number_of_valid_faces () const
  {
    // All faces are valid.
    return (this->m_dcel.size_of_faces());
  }

private:


  typedef Arrangement_on_surface_2<Geometry_traits_2, Self>    Arr;

  // Type definition for the constuction sweep-line visitor.
  typedef Arr_construction_subcurve<Geometry_traits_2>         CSubcurve; 
  typedef Arr_construction_event<Geometry_traits_2,
                                 CSubcurve,
                                 Arr>                          CEvent;
  typedef Arr_bounded_planar_construction_helper<Geometry_traits_2,
                                                 Arr,
                                                 CEvent,
                                                 CSubcurve>    CHelper;

  // Type definition for the basic insertion sweep-line visitor.
  typedef Arr_basic_insertion_traits_2<Geometry_traits_2, Arr> BInsTraits;
  typedef Arr_construction_subcurve<BInsTraits>                BISubcurve; 
  typedef Arr_construction_event<BInsTraits,
                                 BISubcurve,
                                 Arr>                          BIEvent;
  typedef Arr_bounded_planar_insertion_helper<BInsTraits,
                                              Arr,
                                              BIEvent,
                                              BISubcurve>      BIHelper;

  // Type definition for the insertion sweep-line visitor.
  typedef Arr_insertion_traits_2<Geometry_traits_2, Arr>       InsTraits;
  typedef Arr_construction_subcurve<InsTraits>                 ISubcurve; 
  typedef Arr_construction_event<InsTraits,
                                 ISubcurve,
                                 Arr>                          IEvent;
  typedef Arr_bounded_planar_insertion_helper<InsTraits,
                                              Arr,
                                              IEvent,
                                              ISubcurve>       IHelper;

  // Type definition for the batched point-location sweep-line visitor.
  typedef Arr_batched_point_location_traits_2<Arr>             BplTraits;
  typedef Arr_bounded_planar_batched_pl_helper<BplTraits, Arr> BplHelper;

  // Type definition for the vertical decomposition sweep-line visitor.
  typedef Arr_batched_point_location_traits_2<Arr>             VdTraits;
  typedef Arr_bounded_planar_vert_decomp_helper<VdTraits, Arr> VdHelper;

  // Type definition for the overlay sweep-line visitor.
  template <class ExGeomTraits_, class ArrangementA_, class ArrangementB_>
  struct _Overlay_helper : public Arr_bounded_planar_overlay_helper
      <ExGeomTraits_, ArrangementA_, ArrangementB_, Arr,
       Arr_construction_event<ExGeomTraits_,
                              Arr_overlay_subcurve<ExGeomTraits_>,
                              Arr>,
       Arr_overlay_subcurve<ExGeomTraits_> >
  {
    typedef Arr_bounded_planar_overlay_helper
              <ExGeomTraits_, ArrangementA_, ArrangementB_, Arr,
               Arr_construction_event<ExGeomTraits_,
                                      Arr_overlay_subcurve<ExGeomTraits_>,
                                      Arr>,
               Arr_overlay_subcurve<ExGeomTraits_> >     Base;

    typedef typename Base::Traits_2                      Traits_2;
    typedef typename Base::Arrangement_red_2             Arrangement_red_2;
    typedef typename Base::Arrangement_blue_2            Arrangement_blue_2;
    typedef typename Base::Arrangement_2                 Arrangement_2;
    typedef typename Base::Event                         Event;
    typedef typename Base::Subcurve                      Subcurve;
    typedef typename Base::Construction_helper           Construction_helper;

    _Overlay_helper (const ArrangementA_ *arrA,
                     const ArrangementB_ *arrB) :
      Base (arrA, arrB)
    {}
  };

public:



  typedef Arr_construction_sl_visitor<CHelper>
                             Sweep_line_construction_visitor;

  typedef Arr_insertion_sl_visitor<IHelper>
                             Sweep_line_insertion_visitor;

  typedef Sweep_line_construction_visitor
                             Sweep_line_non_intersecting_construction_visitor;
  
  typedef Arr_basic_insertion_sl_visitor<BIHelper>
                             Sweep_line_non_intersecting_insertion_visitor;

  template <class OutputIterator_>
  struct Sweep_line_bacthed_point_location_visitor :
    public Arr_batched_pl_sl_visitor<BplHelper, OutputIterator_>
  {
    typedef OutputIterator_                                   Output_iterator;
    typedef Arr_batched_pl_sl_visitor<BplHelper,
                                      Output_iterator>        Base;

    typedef typename Base::Traits_2                           Traits_2;
    typedef typename Base::Event                              Event;
    typedef typename Base::Subcurve                           Subcurve;

    Sweep_line_bacthed_point_location_visitor (const Arr *arr,
                                               Output_iterator *oi) :
      Base (arr, oi)
    {}
  };

  template <class OutputIterator_>
  struct Sweep_line_vertical_decomposition_visitor :
    public Arr_vert_decomp_sl_visitor<VdHelper, OutputIterator_>
  {
    typedef OutputIterator_                                   Output_iterator;
    typedef Arr_vert_decomp_sl_visitor<VdHelper,
                                       Output_iterator>       Base;

    typedef typename Base::Traits_2                           Traits_2;
    typedef typename Base::Event                              Event;
    typedef typename Base::Subcurve                           Subcurve;

    Sweep_line_vertical_decomposition_visitor (const Arr *arr,
                                               Output_iterator *oi) :
      Base (arr, oi)
    {}
  };

  template <class ArrangementA_, class ArrangementB_, class OverlayTraits_>
  struct Sweep_line_overlay_visitor :
    public Arr_overlay_sl_visitor <
      _Overlay_helper<
        Arr_overlay_traits_2< Arr_traits_basic_adaptor_2<Geometry_traits_2>,
                              ArrangementA_,
                              ArrangementB_>,
        ArrangementA_, 
        ArrangementB_>,
      OverlayTraits_>
  {
    typedef ArrangementA_                            ArrangementA_2;
    typedef ArrangementB_                            ArrangementB_2;
    typedef Arr                                      Arrangement_result_2;
    typedef OverlayTraits_                           Overlay_traits;

    typedef Arr_overlay_traits_2< 
              Arr_traits_basic_adaptor_2<Geometry_traits_2>,
              ArrangementA_2,
              ArrangementB_2>                        Geom_ovl_traits_2;

    typedef _Overlay_helper<Geom_ovl_traits_2, ArrangementA_2, ArrangementB_2>
                                                     Ovl_helper;

    typedef Arr_overlay_sl_visitor<Ovl_helper, Overlay_traits>
                                                     Base;

    typedef typename Base::Traits_2                  Traits_2;
    typedef typename Base::Event                     Event;
    typedef typename Base::Subcurve                  Subcurve;

    Sweep_line_overlay_visitor (const ArrangementA_2 *arrA,
                                const ArrangementB_2 *arrB,
                                Arrangement_result_2 *arr_res,
                                Overlay_traits *overlay_tr) :
      Base (arrA, arrB, arr_res, overlay_tr)
    {}
  };

  typedef Arr_inc_insertion_zone_visitor<Arr>
                                              Zone_insertion_visitor;

  typedef Arr_walk_along_line_point_location<Arr>
                                              Default_point_location_strategy;




  void init_dcel ();

  void dcel_updated ();

  bool are_equal (const Vertex *v,
                  const X_monotone_curve_2& cv, Arr_curve_end ind,
                  Arr_parameter_space ps_x, Arr_parameter_space ps_y) const
  {
    CGAL_assertion (ps_x == ARR_INTERIOR && ps_y == ARR_INTERIOR);

    if (ind == ARR_MIN_END)
    {
      // Compare v with the left endpoint of cv.
      return (this->traits->equal_2_object()
              (this->traits->construct_min_vertex_2_object() (cv),
               v->point()));
    }
    else
    {
      // Compare v with the right endpoint of cv.
      return (this->traits->equal_2_object()
              (this->traits->construct_max_vertex_2_object() (cv),
               v->point()));
    }
  }

  CGAL::Object place_boundary_vertex (Face *,
                                      const X_monotone_curve_2&,
                                      Arr_curve_end,
                                      Arr_parameter_space /* ps_x */,
                                      Arr_parameter_space /* ps_y */)
  {
    // This function should never be called:
    CGAL_error();
    return Object();
  }

  Halfedge*
  locate_around_boundary_vertex (Vertex *,
                                 const X_monotone_curve_2&,
                                 Arr_curve_end,
                                 Arr_parameter_space /* ps_x */,
                                 Arr_parameter_space /* ps_y */) const
  {
    CGAL_error();
    return (NULL);
  }

  CGAL::Object locate_curve_end (const X_monotone_curve_2&,
                                 Arr_curve_end,
                                 Arr_parameter_space /* ps_x */,
                                 Arr_parameter_space /* ps_y */)
  {
    // This function should never be called:
    CGAL_error();
    return Object();
  }

  Halfedge* split_fictitious_edge (Halfedge *, Vertex *)
  {
    // This function should never be called:
    CGAL_error();
    return (NULL);
  }

  bool is_unbounded (const Face *f) const
  {
    // There is only one unbounded face in the arrangement:
    return (f == unb_face);
  }

  bool is_redundant (const Vertex *) const
  {
    // There are no redundant vertices.
    return (false);
  }

  Halfedge* erase_redundant_vertex (Vertex *)
  {
    // This function should never be called:
    CGAL_error();
    return (NULL);
  }


  const Face* reference_face() const
  {
    return unbounded_face();
  }
 

  Face* reference_face()
  {
    return unbounded_face();
  }




  const Face* initial_face () const
  {
    return (unb_face);
  }

  const Face* unbounded_face () const
  {
    return (unb_face);
  }

  Face* unbounded_face ()
  {
    return (unb_face);
  }



  virtual Comparison_result compare_x (const Point_2& p,
                                       const Vertex* v) const
  {
    return (this->traits->compare_x_2_object() (p, v->point()));
  }

  virtual Comparison_result compare_xy (const Point_2& p,
                                        const Vertex* v) const
  {
    return (this->traits->compare_xy_2_object() (p, v->point()));
  }

  virtual Comparison_result compare_y_at_x (const Point_2& p,
                                            const Halfedge* he) const
  {
    return (this->traits->compare_y_at_x_2_object() (p, he->curve()));
  }
};

CGAL_END_NAMESPACE

#include <CGAL/Arr_topology_traits/Arr_bounded_planar_topology_traits_2_impl.h>

#endif