SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arr_topology_traits/Arr_inc_insertion_zone_visitor.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/Arr_topology_traits/Arr_inc_insertion_zone_visitor.h $
// $Id: Arr_inc_insertion_zone_visitor.h 41108 2007-12-06 15:26:30Z efif $
// 
//
// Author(s)     : Ron Wein          <wein@post.tau.ac.il>
//                 Efi Fogel         <efif@post.tau.ac.il>

#ifndef CGAL_ARR_PLANAR_INC_INSERTION_ZONE_VISITOR_H
#define CGAL_ARR_PLANAR_INC_INSERTION_ZONE_VISITOR_H

#include <CGAL/Arr_accessor.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>

CGAL_BEGIN_NAMESPACE

template <class Arrangement_>
class Arr_inc_insertion_zone_visitor
{
public:

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

  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 typename Arrangement_2::Point_2             Point_2;
  typedef typename Arrangement_2::X_monotone_curve_2  X_monotone_curve_2;

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

protected:

  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2>  Traits_adaptor_2;

private:

  Arrangement_2         *p_arr;         // The arrangement into which we
                                        // insert the curves.
  Traits_adaptor_2      *geom_traits;   // The arrangement geometry-traits.

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

  X_monotone_curve_2     sub_cv1;       // Auxiliary varibale (for splitting).
  X_monotone_curve_2     sub_cv2;       // Auxiliary varibale (for splitting).

public:

  Arr_inc_insertion_zone_visitor () :
    p_arr (NULL),
    geom_traits (NULL),
    invalid_v (),
    invalid_he ()
  {}

  void init (Arrangement_2 *arr)
  {
    p_arr = arr;
    geom_traits = const_cast<Traits_adaptor_2*> 
      (static_cast<const Traits_adaptor_2*> (p_arr->geometry_traits()));
  }

  Result found_subcurve (const X_monotone_curve_2& cv,
                         Face_handle face,
                         Vertex_handle left_v, Halfedge_handle left_he,
                         Vertex_handle right_v, Halfedge_handle right_he);

  Result found_overlap (const X_monotone_curve_2& cv,
                        Halfedge_handle he,
                        Vertex_handle left_v, Vertex_handle right_v);

private:

  void _split_edge (Halfedge_handle he,
                    const Point_2& p,
                    Arr_accessor<Arrangement_2>& arr_access);

};

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

//-----------------------------------------------------------------------------
// Handle the a subcurve located in the interior of a given face.
//
template <class Arrangement>
typename Arr_inc_insertion_zone_visitor<Arrangement>::Result
Arr_inc_insertion_zone_visitor<Arrangement>::
found_subcurve (const X_monotone_curve_2& cv, Face_handle face,
                Vertex_handle left_v, Halfedge_handle left_he,
                Vertex_handle right_v, Halfedge_handle right_he)
{
  // Create an arrangement accessor.
  Arr_accessor<Arrangement_2>    arr_access (*p_arr);
  
  // Get the boundary conditions of the curve ends.
  const Arr_parameter_space bx_l =
    geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
  const Arr_parameter_space by_l =
    geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);

  const Arr_parameter_space bx_r =
    geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
  const Arr_parameter_space by_r =
    geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);

  // Check if the left and the right endpoints of cv should be associated
  // with arrangement vertices.
  const bool vertex_for_left =
    (left_v != invalid_v) || (left_he != invalid_he);
  const bool vertex_for_right =
    (right_v != invalid_v) || (right_he != invalid_he);

  // Find the previous halfedges for the left and right endpoints (if any).
  Halfedge_handle  prev_he_left;
  Halfedge_handle  prev_he_right;

  if (vertex_for_left)
  {
    // If we are given the previous halfedge, use it. Otherwise, we are given
    // the vertex and we should locate cv around it.
    if (left_he != invalid_he)
      prev_he_left = left_he;
    else if (! left_v->is_isolated())
      prev_he_left = arr_access.locate_around_vertex (left_v, cv);

    // In case the vertex does not exist, split left_he at cv's left endpoint
    // and create the vertex.
    if (left_v == invalid_v)
    {
      _split_edge (left_he,
                   geom_traits->construct_min_vertex_2_object() (cv),
                   arr_access);

      // Check if we have just split the halfedge that right_he refers to,
      // and if this halfedge is directed from left to right.
      // If so, right_he's target is now the new vertex, and we have to
      // proceed to the next halfedge (which is going to be split).
      if (right_he == left_he && left_he->direction() == ARR_LEFT_TO_RIGHT)
        right_he = right_he->next();
    }
  }
  else
  {
    // Check if the left end of cv is bounded of not.
    if ((bx_l == ARR_LEFT_BOUNDARY) || (by_l != ARR_INTERIOR)) {
      // Use the arrangement accessor and obtain a vertex associated with
      // the unbounded left end (possibly with a predecessor halfedge).
      std::pair<Vertex_handle, Halfedge_handle>  pos =
        arr_access.place_and_set_curve_end (face, cv, ARR_MIN_END, bx_l, by_l);

      if (pos.second != invalid_he)
        // Use the predecessor halfedge, if possible:
        prev_he_left = pos.second;
      else
        // Use just the isolated vertex:
        left_v = pos.first;
    }
  }

  if (vertex_for_right)
  {
    // If we are given the previous halfedge, use it. Otherwise, we are given
    // the vertex and we should locate cv around it.
    if (right_he != invalid_he)
      prev_he_right = right_he;
    else if (! right_v->is_isolated())
      prev_he_right = arr_access.locate_around_vertex (right_v, cv);
    
    // In case the vertex does not exist, split right_he at cv's right
    // endpoint and create the vertex.
    if (right_v == invalid_v)
    {
      _split_edge (right_he,
                   geom_traits->construct_max_vertex_2_object() (cv),
                   arr_access);
      
      // Check if we have just split the halfedge that left_he refers to.
      // If so, prev_he_right's target is now the new vertex, and we have to
      // proceed to the next halfedge (whose target is right_v).
      if (right_he == prev_he_left)
      {
        prev_he_left = prev_he_left->next();
      }
    }
  }
  else
  {
    // Check if the right end of cv is bounded of not.    
    if ((bx_r == ARR_RIGHT_BOUNDARY) || (by_r != ARR_INTERIOR)) {
      // Use the arrangement accessor and obtain a vertex associated with
      // the unbounded right end (possibly with a predecessor halfedge).
      std::pair<Vertex_handle, Halfedge_handle>  pos =
        arr_access.place_and_set_curve_end (face, cv, ARR_MAX_END, bx_r, by_r);

      if (pos.second != invalid_he)
        // Use the predecessor halfedge, if possible:
        prev_he_right = pos.second;
      else
        // Use just the isolated vertex:
        right_v = pos.first;
    }
  }

  // Insert the curve into the arrangement.
  Halfedge_handle   inserted_he;

  if (prev_he_left == invalid_he)
  {
    // The left endpoint is associated with an isolated vertex, or is not
    // associated with any vertex. In the latter case, we create such a vertex
    // now.
    if (left_v == invalid_v)
    {
      if (bx_l == ARR_INTERIOR && by_l == ARR_INTERIOR)
      {
        left_v = arr_access.create_vertex 
          (geom_traits->construct_min_vertex_2_object() (cv));
      }
      else
      {
        left_v =
          arr_access.create_boundary_vertex (cv, ARR_MIN_END, bx_l, by_l);
      }
    }

    if (prev_he_right == invalid_he)
    {
      // The right endpoint is associated with an isolated vertex, or is not
      // associated with any vertex. In the latter case, we create such a
      // vertex now.
      if (right_v == invalid_v)
      {
        if (bx_r == ARR_INTERIOR && by_r == ARR_INTERIOR)
        {
          right_v = arr_access.create_vertex 
            (geom_traits->construct_max_vertex_2_object() (cv));
        }
        else
        {
          right_v = arr_access.create_boundary_vertex (cv, ARR_MAX_END,
                                                       bx_r, by_r);
        }
      }
     
      // We should insert the curve in the interior of the face.
      inserted_he = arr_access.insert_in_face_interior_ex (cv, face,
                                                           left_v, right_v,
                                                           SMALLER);
    }
    else
    {
      // The right endpoint is associated with an arrangement vertex, and
      // we have the predecessor halfedge for the insertion.
      inserted_he = arr_access.insert_from_vertex_ex (cv, prev_he_right,
                                                      left_v, LARGER);

      // The returned halfedge is directed to the newly created vertex
      // (the left one), so we take its twin.
      inserted_he = inserted_he->twin();
    }
  }
  else
  {
    // We have a vertex associated with the left end of the curve, along
    // with a predecessor halfedge.
    if (prev_he_right == invalid_he)
    {
      // The right endpoint is associated with an isolated vertex, or is not
      // associated with any vertex. In the latter case, we create such a
      // vertex now.
      if (right_v == invalid_v)
      {
        if (bx_r == ARR_INTERIOR && by_r == ARR_INTERIOR)
        {
          right_v = arr_access.create_vertex 
              (geom_traits->construct_max_vertex_2_object() (cv));
        }
        else
        {
          right_v =
            arr_access.create_boundary_vertex (cv, ARR_MAX_END, bx_r, by_r);
        }
      }
     
      // Use the left predecessor for the insertion.
      inserted_he = arr_access.insert_from_vertex_ex (cv, prev_he_left,
                                                      right_v, SMALLER);
    }
    else
    {
      // The right endpoint is associated with an arrangement vertex, and
      // we have the predecessor halfedge for the insertion.
      CGAL_assertion (prev_he_right != invalid_he);

      // Perform the insertion using the predecessor halfedges.
      inserted_he = p_arr->insert_at_vertices (cv,
                                               prev_he_left,
                                               prev_he_right);
    }
  }

  // Return the inserted halfedge, and indicate we should not halt the
  // zone-computation process.
  Result    res = Result (inserted_he, false);
  
  return (res);
}

//-----------------------------------------------------------------------------
// Handle the a subcurve located in the interior of a given face.
//
template <class Arrangement>
typename Arr_inc_insertion_zone_visitor<Arrangement>::Result
Arr_inc_insertion_zone_visitor<Arrangement>::
found_overlap (const X_monotone_curve_2& cv,
               Halfedge_handle he,
               Vertex_handle left_v, Vertex_handle right_v)
{
  // Get the boundary conditions of the curve ends.
  const Arr_parameter_space bx_l =
    geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
  const Arr_parameter_space by_l =
    geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);

  const Arr_parameter_space bx_r =
    geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
  const Arr_parameter_space by_r =
    geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);

  // Modify (perhaps split) the overlapping arrangement edge.
  Halfedge_handle   updated_he;

  if (left_v == invalid_v &&
      ! ((bx_l == ARR_LEFT_BOUNDARY) || (by_l != ARR_INTERIOR)))
  {
    // Split the curve associated with he at the left endpoint of cv.
    geom_traits->split_2_object()
      (he->curve(),
       geom_traits->construct_min_vertex_2_object() (cv), sub_cv1, sub_cv2);

    if (right_v == invalid_v &&
        ! ((bx_r == ARR_RIGHT_BOUNDARY) || (by_r != ARR_INTERIOR)))
    {
      // The overlapping curve is contained strictly in the interior of he:
      // Split he as an intermediate step.
      updated_he = p_arr->split_edge (he, sub_cv1, sub_cv2);
      updated_he = updated_he->next();

      // Split the left subcurve at the right endpoint of cv.
      geom_traits->split_2_object()
        (updated_he->curve(),
         geom_traits->construct_max_vertex_2_object() (cv), sub_cv1, sub_cv2);

      // Split updated_he once again, so that the left portion corresponds
      // to the overlapping curve and the right portion corresponds to
      // sub_cv2.
      updated_he = p_arr->split_edge (updated_he, cv, sub_cv2);
    }
    else
    {
      // Split he, such that the left portion corresponds to sub_cv1 and the
      // right portion corresponds to the overlapping curve.
      updated_he = p_arr->split_edge (he, sub_cv1, cv);
      updated_he = updated_he->next();
    }
  }
  else
  {
    if (right_v == invalid_v &&
        ! ((bx_r == ARR_RIGHT_BOUNDARY) || (by_r != ARR_INTERIOR)))
    {
      // Split the curve associated with he at the right endpoint of cv.
      geom_traits->split_2_object()
        (he->curve(),
         geom_traits->construct_max_vertex_2_object() (cv), sub_cv1, sub_cv2);

      // Split he, such that the left portion corresponds to the overlapping
      // curve and the right portion corresponds to sub_cv2.
      updated_he = p_arr->split_edge (he, cv, sub_cv2);
    }
    else
    {
      // The entire edge is overlapped: Modify the curve associated with cv
      // to be the overlapping curve.
      updated_he = p_arr->modify_edge (he, cv);
    }
  }

  // Return the updated halfedge, and indicate we should not halt the
  // zone-computation process.
  Result    res = Result (updated_he, false);

  return (res);
}

//-----------------------------------------------------------------------------
// Split an arrangement edge.
//
template <class Arrangement>
void Arr_inc_insertion_zone_visitor<Arrangement>::
_split_edge (Halfedge_handle he, const Point_2& p,
             Arr_accessor<Arrangement_2>& arr_access)
{
  // Split the curve at the split point.
  geom_traits->split_2_object() (he->curve(), p, sub_cv1, sub_cv2);

  // sub_cv1 is always to the left of the split point p and sub_cv2 lies to
  // its right. Thus, if the split edge is directed from left to right then
  // left end of sub_cv1 equals he's source, and if the edge is directed from
  // right to left, we have to reverse the subcurve order.
  if (he->direction() == ARR_LEFT_TO_RIGHT)
  {
    arr_access.split_edge_ex (he, p, sub_cv1, sub_cv2);
  }
  else
  {
    arr_access.split_edge_ex (he, p, sub_cv2, sub_cv1);
  }

  return;
}

CGAL_END_NAMESPACE

#endif