SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arrangement_zone_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/Arrangement_zone_2.h $
// $Id: Arrangement_zone_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>
//                 (based on old version by Eyal Flato)

#ifndef CGAL_ARRANGEMENT_ZONE_2_H
#define CGAL_ARRANGEMENT_ZONE_2_H

#include <boost/mpl/assert.hpp>
#include <CGAL/Arr_tags.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>

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

CGAL_BEGIN_NAMESPACE

template <class Arrangement_, class ZoneVisitor_>
class Arrangement_zone_2
{
public:

  typedef Arrangement_                                   Arrangement_2;
  typedef typename Arrangement_2::Geometry_traits_2      Geometry_traits_2;
  typedef typename Arrangement_2::Topology_traits        Topology_traits;

protected:
  
  typedef Arr_traits_adaptor_2<Geometry_traits_2>        Traits_adaptor_2;

  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(
      (typename 
       Arr_sane_identified_tagging< Arr_left_side_tag, Arr_bottom_side_tag, 
       Arr_top_side_tag, Arr_right_side_tag >::result)
  );

public:
  
  typedef ZoneVisitor_                                   Visitor;

  typedef typename Arrangement_2::Vertex_handle          Vertex_handle;
  typedef typename Arrangement_2::Halfedge_handle        Halfedge_handle;
  typedef typename Arrangement_2::Face_handle            Face_handle;

  typedef std::pair<Halfedge_handle, bool>               Visitor_result;

  typedef typename Geometry_traits_2::Point_2            Point_2;
  typedef typename Geometry_traits_2::X_monotone_curve_2 X_monotone_curve_2;

protected:

  typedef typename Arr_are_all_sides_oblivious_tag< 
                     Arr_left_side_tag, Arr_bottom_side_tag, 
                     Arr_top_side_tag, Arr_right_side_tag >::result
  Are_all_sides_oblivious_tag;
  
  typedef typename Arrangement_2::Vertex_const_handle    Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle  Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle      Face_const_handle;

  // Types used for caching intersection points:
  typedef std::pair<Point_2, unsigned int>        Intersect_point_2;
  typedef std::list<CGAL::Object>                 Intersect_list;
  typedef std::map<const X_monotone_curve_2*,
                   Intersect_list>                Intersect_map;
  typedef typename Intersect_map::iterator        Intersect_map_iterator;

  typedef std::set<const X_monotone_curve_2*>     Curves_set;
  typedef typename Curves_set::iterator           Curves_set_iterator;

  // Data members:
  Arrangement_2&          arr;          // The associated arrangement.
  const Traits_adaptor_2 * m_geom_traits; // Its associated geometry traits.
  Arr_accessor<Arrangement_2> arr_access; // An accessor for the arrangement.
           
  Visitor                *visitor;      // The zone visitor.

  Intersect_map           inter_map;    // Stores all computed intersections.

  const Vertex_handle     invalid_v;    // An invalid vertex handle.
  const Halfedge_handle   invalid_he;   // An invalid halfedge handle.

  X_monotone_curve_2  cv;               // The current portion of the
                                        // inserted curve.
  CGAL::Object        obj;              // The location of the left endpoint.
  bool                has_left_pt;      // Is the left end of the curve
                                        // bounded.
  bool                left_on_boundary; // Is the left point on the boundary.
  Point_2             left_pt;          // Its current left endpoint.
  bool                has_right_pt;     // Is the right end of the curve
                                        // bounded.
  bool                right_on_boundary;// Is the right point on the boundary.
  Point_2             right_pt;         // Its right endpoint (if bounded).

  Vertex_handle       left_v;           // The arrangement vertex associated
                                        // with the current left_pt (if any).
  Halfedge_handle     left_he;          // If left_v is valid, left_he is the
                                        // predecessor for cv around this
                                        // vertex. Otherwise, if it is valid,
                                        // it is the halfedge that contains
                                        // the left endpoint it its interior.

  Vertex_handle       right_v;          // The arrangement vertex associated
                                        // with the current right_pt (if any).
  Halfedge_handle     right_he;         // If right_v is valid, left_he is the
                                        // predecessor for cv around this
                                        // vertex. Otherwise, if it is valid,
                                        // it is the halfedge that contains
                                        // the right endpoint it its interior.

  Point_2             intersect_p;      // The next intersection point.
  unsigned int        ip_mult;          // Its multiplicity
                                        // (0 in case of an overlap).
  bool                found_intersect;  // Have we found an intersection
                                        // (or an overlap).
  X_monotone_curve_2  overlap_cv;       // The currently discovered overlap.
  bool                found_overlap;    // Have we found an overlap.
  bool                found_iso_vert;   // Check if an isolated vertex induces
                                        // the next intersection.
  Vertex_handle       intersect_v;      // The vertex that intersects cv.
  Halfedge_handle     intersect_he;     // The halfedge that intersects cv
                                        // (or overlaps it).

  X_monotone_curve_2  sub_cv1;          // Auxiliary variable (for curve split).
  X_monotone_curve_2  sub_cv2;          // Auxiliary variable (for curve split).

public:

  Arrangement_zone_2 (Arrangement_2& _arr, Visitor *_visitor) :
    arr (_arr),
    arr_access (_arr),
    visitor (_visitor),
    invalid_v (),
    invalid_he ()
  {
    m_geom_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());

    CGAL_assertion (visitor != NULL);

    // Initialize the visitor.
    visitor->init (&arr);
  }

  template <class PointLocation>
  void init (const X_monotone_curve_2& _cv, const PointLocation& pl)
  {
    // Set the curve and check whether its left end has boundary conditions.
    cv = _cv;

    const Arr_parameter_space  bx1 =
      m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
    const Arr_parameter_space  by1 =
      m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);

    if (bx1 == ARR_INTERIOR && by1 == ARR_INTERIOR) {
      // The curve has a finite left endpoint with no boundary conditions:
      // locate it in the arrangement.
      has_left_pt = true;
      left_on_boundary = (bx1 != ARR_INTERIOR || by1 != ARR_INTERIOR);
      left_pt = m_geom_traits->construct_min_vertex_2_object() (cv);

      obj = pl.locate (left_pt);
    }
    else {
      // The left end of the curve has boundary conditions: use the topology
      // traits use the arrangement accessor to locate it.
      // Note that if the curve-end is unbounded, left_pt does not exist.
      // Note that if the curve-end is unbounded, left_pt does not exist.
      has_left_pt = m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END);
      left_on_boundary = true;
      if (has_left_pt)
        left_pt = m_geom_traits->construct_min_vertex_2_object() (cv);
      obj = arr_access.locate_curve_end (cv, ARR_MIN_END, bx1, by1);
    }

    // Check the boundary conditions of th right curve end.
    if (m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END)) {
      const Arr_parameter_space  bx2 =
        m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
      const Arr_parameter_space  by2 =
        m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);

      // The right endpoint is valid.
      has_right_pt = true;
      right_pt = m_geom_traits->construct_max_vertex_2_object() (cv);
      right_on_boundary = (bx2 != ARR_INTERIOR) || (by2 != ARR_INTERIOR);
    }
    else {
      // The right end of the curve lies at infinity.
      has_right_pt = false;
      right_on_boundary = true;
    }

    return;
  }

  void init_with_hint (const X_monotone_curve_2& _cv, const Object& _obj);

  void compute_zone ();

private:

  bool _find_prev_around_vertex (Vertex_handle v, Halfedge_handle& he);

  Halfedge_handle
  _direct_intersecting_edge_to_right(const X_monotone_curve_2& cv_ins,
                                     const Point_2& cv_left_pt,
                                     Halfedge_handle query_he);

  Halfedge_handle
  _direct_intersecting_edge_to_left(const X_monotone_curve_2& cv_ins,
                                    Halfedge_handle query_he);

  CGAL::Object _compute_next_intersection (Halfedge_handle he,
                                           bool skip_first_point,
                                           bool& intersect_on_right_boundary);

  void _remove_next_intersection (Halfedge_handle he);

  bool _is_to_left(const Point_2& p, Halfedge_handle he) const
  {
    return (_is_to_left_impl(p, he, Are_all_sides_oblivious_tag()));
  }

  bool _is_to_left_impl(const Point_2& p, Halfedge_handle he,
                        Arr_all_sides_oblivious_tag) const
  {
    return ((he->direction() == ARR_LEFT_TO_RIGHT &&
             m_geom_traits->compare_xy_2_object() 
             (p, he->source()->point()) == SMALLER) ||
            (he->direction() == ARR_RIGHT_TO_LEFT &&
             m_geom_traits->compare_xy_2_object() 
             (p, he->target()->point()) == SMALLER));
  }

  bool _is_to_left_impl(const Point_2& p, Halfedge_handle he,
                        Arr_not_all_sides_oblivious_tag) const;
  
  bool _is_to_right(const Point_2& p, Halfedge_handle he) const
  {
    return (_is_to_right_impl(p, he, Are_all_sides_oblivious_tag()));
  }

  bool _is_to_right_impl(const Point_2& p, Halfedge_handle he,
                         Arr_all_sides_oblivious_tag) const
  {
    return ((he->direction() == ARR_LEFT_TO_RIGHT &&
             m_geom_traits->compare_xy_2_object() 
             (p, he->target()->point()) == LARGER) ||
            (he->direction() == ARR_RIGHT_TO_LEFT &&
             m_geom_traits->compare_xy_2_object() 
             (p, he->source()->point()) == LARGER));
  }

  bool _is_to_right_impl(const Point_2& p, Halfedge_handle he,
                         Arr_not_all_sides_oblivious_tag) const;

  void _leftmost_intersection_with_face_boundary (Face_handle face,
                                                  bool on_boundary);

  bool _zone_in_face (Face_handle face,
                      bool on_boundary);

  bool _zone_in_overlap ();
};

CGAL_END_NAMESPACE

// The function definitions can be found under:
#include <CGAL/Arrangement_2/Arrangement_zone_2_impl.h>

#endif