SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arr_topology_traits/Arr_planar_topology_traits_base_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_topology_traits/Arr_planar_topology_traits_base_2.h $
// $Id: Arr_planar_topology_traits_base_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>

#ifndef CGAL_ARR_PLANAR_TOPOLOGY_TRAITS_BASE_2_H
#define CGAL_ARR_PLANAR_TOPOLOGY_TRAITS_BASE_2_H

#include <CGAL/Arr_enums.h>
#include <CGAL/Arr_default_dcel.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/Sweep_line_2/Arr_construction_event.h>
#include <CGAL/Sweep_line_2/Arr_construction_subcurve.h>
#include <CGAL/Sweep_line_2/Arr_construction_sl_visitor.h>
#include <CGAL/Sweep_line_2/Arr_basic_insertion_traits_2.h>
#include <CGAL/Sweep_line_2/Arr_basic_insertion_sl_visitor.h>
#include <CGAL/Sweep_line_2/Arr_insertion_traits_2.h>
#include <CGAL/Sweep_line_2/Arr_insertion_sl_visitor.h>
#include <CGAL/Sweep_line_2/Arr_overlay_subcurve.h>
#include <CGAL/Sweep_line_2/Arr_overlay_traits_2.h>
#include <CGAL/Sweep_line_2/Arr_overlay_sl_visitor.h>
#include <CGAL/Sweep_line_2/Arr_batched_pl_sl_visitor.h>
#include <CGAL/Sweep_line_2/Arr_vert_decomp_sl_visitor.h>
#include <CGAL/Arr_point_location/Arr_batched_point_location_traits_2.h>

CGAL_BEGIN_NAMESPACE

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


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


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

  typedef Arr_planar_topology_traits_base_2<Geometry_traits_2,
                                            Dcel>         Self;

protected:

  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2>    Traits_adaptor_2;

  // Data members:
  Dcel                m_dcel;       // The DCEL.

  const Traits_adaptor_2 * traits;       // The geometry-traits adaptor.
  bool                own_traits;   // Inidicate whether we should evetually
                                    // free the traits object.

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

public:



  Arr_planar_topology_traits_base_2 () :
    own_traits (true)
  {
    traits = new Traits_adaptor_2;
  }

  Arr_planar_topology_traits_base_2 (const Geometry_traits_2 * geom_traits) :
    own_traits (false)
  {
    traits = static_cast<const Traits_adaptor_2*>(geom_traits);
  }

  void assign (const Self& other);

  virtual ~Arr_planar_topology_traits_base_2 ()
  {
    // Clear the DCEL.
    m_dcel.delete_all();

    if (own_traits)
      delete traits;    
  }



  const Dcel& dcel () const
  {
    return (m_dcel);
  }

  Dcel& dcel ()
  {
    return (m_dcel);
  }

  void notify_on_boundary_vertex_creation (Vertex *,
                                           const X_monotone_curve_2& ,
                                           Arr_curve_end,
                                           Arr_parameter_space /* ps_x */,
                                           Arr_parameter_space /* ps_y */)
  {
    // In the planar-topology traits this function should never be invoked:
    return;
  }

  std::pair<bool, bool>
  face_split_after_edge_insertion(const Halfedge *
                                    CGAL_precondition_code(prev1),
                                  const Halfedge *
                                    CGAL_precondition_code(prev2),
                                  const X_monotone_curve_2 & /* cv */) const
  {
    CGAL_precondition (prev1->is_on_inner_ccb());
    CGAL_precondition (prev2->is_on_inner_ccb());
    CGAL_precondition (prev1->inner_ccb() == prev2->inner_ccb());

    // In case of a planar topology, connecting two vertices on the same
    // inner CCB closes a new face that becomes a hole in the original face:
    return (std::make_pair (true, true));
  }

#if CGAL_NEW_FACE_SPLIT_STRATEGY

  std::pair<bool, bool>
  face_update_upon_edge_insertion(const Halfedge *
                                    CGAL_precondition_code(prev1),
                                  const Halfedge *
                                    CGAL_precondition_code(prev2),
                                  const X_monotone_curve_2 & cv) const
  {
      // In case of a planar topology, connecting two vertices on the same
      // CCB closes a new face that becomes a hole in the original face:
      return (std::make_pair (true, true));
  }
#endif


  bool hole_creation_after_edge_removal (const Halfedge *he) const
  {
    CGAL_precondition (! he->is_on_inner_ccb());
    CGAL_precondition (! he->opposite()->is_on_inner_ccb());

    // Check whether the halfedge and its twin belong to the same outer CCB
    // (and are therefore incident to the same face).
    if (he->outer_ccb() == he->opposite()->outer_ccb())
    {
      // In this case we cut an antenna, therefore we seperate a new hole
      // from the outer CCB of the face.
      return (true);
    }
    else
    {
      // The edge separates two faces. When we remove it, these two faces will
      // be merged, but no new hole will be created.
      return (false);
    }
  }

  bool is_on_new_perimetric_face_boundary (const Halfedge *,
                                           const Halfedge *,
                                           const X_monotone_curve_2&) const
  {
    // We can never have perimetric faces in a planar topology:
    CGAL_error();
    return (false);
  }

  bool boundaries_of_same_face (const Halfedge *,
                                const Halfedge *) const
  {
    // This predicate is only used for case 3.3.2 of the insertion process,
    // therefore it should never be invoked in the planar case.
    CGAL_error();
    return (false);
  }


#if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE || CGAL_NEW_FACE_SPLIT_STRATEGY

  CGAL::Sign _sign_of_subpath(const Halfedge* he1, const Halfedge* he2) 
    const {
    return CGAL::ZERO;
  }
    
  CGAL::Sign _sign_of_subpath(const Halfedge* he1, 
                              const bool target,
                              const X_monotone_curve_2& cv2,
                              const CGAL::Arr_curve_end& end2) const {
    return CGAL::ZERO;
  }
#endif

  bool is_in_face (const Face *f, const Point_2& p, const Vertex *v) const;



  virtual const Face* initial_face () const = 0;



  virtual Comparison_result compare_x (const Point_2& p,
                                       const Vertex* v) const = 0;

  virtual Comparison_result compare_xy (const Point_2& p,
                                        const Vertex* v) const = 0;

  virtual Comparison_result compare_y_at_x (const Point_2& p,
                                            const Halfedge* he) const = 0;
};

//-----------------------------------------------------------------------------
// Memeber-function definitions:
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// Assign the contents of another topology-traits class.
//
template <class GeomTraits, class Dcel_>
void Arr_planar_topology_traits_base_2<GeomTraits, Dcel_>::assign
    (const Self& other)
{
  // Clear the current DCEL and duplicate the other DCEL.
  m_dcel.delete_all();
  m_dcel.assign (other.m_dcel);
  
  // Take care of the traits object.
  if (own_traits && traits != NULL)
    delete traits;
  
  if (other.own_traits)
    traits = new Traits_adaptor_2;
  else
    traits = other.traits;
  own_traits = other.own_traits;

  return;
}

//-----------------------------------------------------------------------------
// Determine whether the given vertex lies in the interior of the given face.
//
template <class GeomTraits, class Dcel_>
bool Arr_planar_topology_traits_base_2<GeomTraits, Dcel_>::
is_in_face(const Face *f, const Point_2& p, const Vertex *v) const
{
  CGAL_precondition (v == NULL || ! v->has_null_point());
  CGAL_precondition (v == NULL || 
                     traits->equal_2_object()(p, v->point()));

  // In case the face is unbounded and has no outer ccbs, this is the single
  // unbounded face of an arrangement of bounded curves. This face obviously
  // contains any point in its interior.
  if (f->is_unbounded() && f->number_of_outer_ccbs() == 0)
    return (true);

  // Keep a counter of the number of x-monotone curves that intersect an upward
  // vertical emanating from p (except for some degenerate cases that are
  // explained below).
  unsigned int       n_ray_intersections = 0;

  // Get a halfedge along the outer CCB of the given face, go over all curves
  // of the boundary component, and count those which are above p.
  // We begin by comparing p to the source vertex of the first halfedge.
  // Note that if p coincides with this vertex, p is obviously not in the
  // interior of the component.
  const Halfedge    *first = *(f->outer_ccbs_begin());
  const Halfedge    *curr = first;
  Comparison_result  res_source;
  Comparison_result  res_target;
  Comparison_result  res_y_at_x;

  if (curr->opposite()->vertex() == v)
    return (false);

  res_source = compare_xy (p, curr->opposite()->vertex());

  do
  {
    // Compare p to the target vertex of the current halfedge.
    // If the vertex v associated with p (if v is given and is not NULL)
    // on the boundary of the component, p is obviously not in the interior
    // the component.
    if (curr->vertex() == v)
      return (false);

    res_target = compare_xy (p, curr->vertex());

    // In case the current halfedge belongs to an "antenna", namely its
    // incident face is the same as its twin's, we can simply skip it
    // (in order not to count it twice).
    if (! curr->opposite()->is_on_inner_ccb() &&
        curr->outer_ccb()->face() == curr->opposite()->outer_ccb()->face())
    {
      curr = curr->next();
      res_source = res_target;
      continue;
    }

    // Check that if we shoot a "tilted" vertical ray from p upward
    // (by "tilted" we mean the angle it forms with the x-axis is
    //  PI/2 + epsilon, where epsilon is arbitrarily small), then we hit
    // the x-monotone curve associated with curr once.
    if (res_source != res_target)
    {
      res_y_at_x = compare_y_at_x (p, curr);

      if (res_y_at_x == SMALLER)
      {
        n_ray_intersections++;
      }        
      else if (res_y_at_x == EQUAL)
      {
        // In this case p lies on the current edge, so it is obviously not
        // contained in the interior of the component.
        return (false);
      }
    }

    // Proceed to the next halfedge along the component boundary.
    // Note that the source vertex of this halfedge is the current target.
    curr = curr->next();
    res_source = res_target;

  } while (curr != first);

  // The query point lies inside the connected components if and only if the
  // ray we shoot from it intersects the boundary an odd number of time.
  return ((n_ray_intersections % 2) != 0);
}

CGAL_END_NAMESPACE

#endif