arrangement_2_insert.h

很多二维 三维几何计算算法 C++ 类库

// 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.3-branch/Arrangement_2/include/CGAL/Arrangement_2/Arrangement_2_insert.h $
// $Id: Arrangement_2_insert.h 35514 2006-12-11 15:34:13Z wein $
// 
//
// Author(s)     : Ron Wein          <[e-mail]>
//                 Baruch Zukerman   <[e-mail]>
//                 Efi Fogel         <[e-mail]>
//
#ifndef CGAL_ARRANGEMENT_2_INSERT_H
#define CGAL_ARRANGEMENT_2_INSERT_H

/*! \file
 * Global insertion functions for the Arrangement_2 class.
 */

#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_accessor.h>
#include <CGAL/Arrangement_zone_2.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/Arrangement_2/Arr_inc_insertion_zone_visitor.h>
#include <CGAL/Sweep_line_2/Arr_construction.h>
#include <CGAL/Sweep_line_2/Arr_addition.h>
#include <CGAL/Sweep_line_2/Arr_non_x_construction.h>
#include <CGAL/Sweep_line_2/Arr_non_x_addition.h>
#include <CGAL/Sweep_line_2/Sweep_line_2_visitors.h>
#include <CGAL/Sweep_line_2.h>
#include <CGAL/Arr_naive_point_location.h>
#include <set>
#include <list>
#include <map>

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Insert a curve into the arrangement (incremental insertion).
// The inserted x-monotone curve may intersect the existing arrangement.
//
template <class Traits, class Dcel, class PointLocation>
void insert_curve (Arrangement_2<Traits,Dcel>& arr, 
                   const typename Traits::Curve_2& c,
                   const PointLocation& pl)
{
  // Obtain an arrangement accessor.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  // Define a zone-computation object an a visitor that performs the
  // incremental insertion.
  typedef Arr_inc_insertion_zone_visitor<Arrangement_2>  Zone_visitor;

  Zone_visitor                                     visitor;
  Arrangement_zone_2<Arrangement_2, Zone_visitor>  arr_zone (arr, &visitor);

  // Break the input curve into x-monotone subcurves and isolated points.
  typedef Arr_traits_adaptor_2<Traits>                   Traits_adaptor_2;

  Traits_adaptor_2   *traits =
                        static_cast<Traits_adaptor_2*> (arr.get_traits());

  std::list<CGAL::Object>                     x_objects;
  std::list<CGAL::Object>::const_iterator     obj_iter;
  const typename Traits::X_monotone_curve_2  *x_curve;
  const typename Traits::Point_2             *iso_p;

  traits->make_x_monotone_2_object() (c,
                                      std::back_inserter (x_objects));

  // Insert each x-monotone curve into the arrangement.
  for (obj_iter = x_objects.begin(); obj_iter != x_objects.end(); ++obj_iter)
  {
    // Act according to the type of the current object.
    x_curve = object_cast<typename Traits::X_monotone_curve_2> (&(*obj_iter));
    if (x_curve != NULL)
    {
      // Inserting an x-monotone curve:
      // Initialize the zone-computation object with the given curve.
      arr_zone.init (*x_curve, pl);

      // Notify the arrangement observers that a global operation is about to 
      // take place.
      arr_access.notify_before_global_change();

      // Insert the current x-monotone curve into the arrangement.
      arr_zone.compute_zone();

      // Notify the arrangement observers that the global operation has been
      // completed.
      arr_access.notify_after_global_change();
    }
    else
    {
      iso_p = object_cast<typename Traits::Point_2> (&(*obj_iter));
      CGAL_assertion (iso_p != NULL);

      // Inserting a point into the arrangement:
      insert_point (arr, *iso_p, pl);
    }
  }

  return;
}

//-----------------------------------------------------------------------------
// Insert a curve into the arrangement (incremental insertion).
// The inserted x-monotone curve may intersect the existing arrangement.
// Overloaded version with no point location object - the walk point-location
// strategy is used as default.
//
template <class Traits, class Dcel>
void insert_curve (Arrangement_2<Traits,Dcel>& arr,
                   const typename Traits::Curve_2& c)
{
  typedef Arrangement_2<Traits, Dcel>                          Arrangement_2;
  typedef Arr_walk_along_line_point_location<Arrangement_2>    Walk_pl;
  
  // create walk point location object
  Walk_pl    walk_pl(arr);

  //insert the curve using the walk point location
  insert_curve (arr, c, walk_pl);
  return;
}

//-----------------------------------------------------------------------------
// Insert a range of curves into the arrangement (aggregated insertion). 
// The inserted curves may intersect one another and may also intersect the 
// existing arrangement.
//
template <class Traits, class Dcel, class InputIterator>
void insert_curves (Arrangement_2<Traits,Dcel>& arr,
                    InputIterator begin, InputIterator end)
{
  // Notify the arrangement observers that a global operation is about to 
  // take place.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  arr_access.notify_before_global_change();

  if(arr.is_empty())
  {
    // Perform the aggregated insertion.
    Arr_construction<Arrangement_2>              arr_construct (arr);
    arr_construct.insert_curves (begin, end);
  }
  else
  {
    Arr_addition<Arrangement_2>                  arr_adder(arr);
    arr_adder.insert_curves (begin, end);
  }

  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  return;
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement (incremental insertion).
// The inserted x-monotone curve may intersect the existing arrangement.
//
template <class Traits, class Dcel, class PointLocation>
void insert_x_monotone_curve (Arrangement_2<Traits,Dcel>& arr,
                              const typename Traits::X_monotone_curve_2& c,
                              const PointLocation& pl)
{
  // Obtain an arrangement accessor.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  // Define a zone-computation object an a visitor that performs the
  // incremental insertion.
  typedef Arr_inc_insertion_zone_visitor<Arrangement_2>  Zone_visitor;
  Zone_visitor                                     visitor;
  Arrangement_zone_2<Arrangement_2, Zone_visitor>  arr_zone (arr, &visitor);

  // Initialize the zone-computation object with the given curve.
  arr_zone.init (c, pl);

  // Notify the arrangement observers that a global operation is about to 
  // take place.
  arr_access.notify_before_global_change();

  // Insert the x-monotone curve into the arrangement.
  arr_zone.compute_zone();

  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  return;
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement (incremental insertion)
// when the location of the left endpoint of the curve is known and is
// given as an isertion hint.
// The inserted x-monotone curve may intersect the existing arrangement.
//
template <class Traits, class Dcel>
void insert_x_monotone_curve (Arrangement_2<Traits,Dcel>& arr,
                              const typename Traits::X_monotone_curve_2& c,
                              const Object& obj)
{
  // Obtain an arrangement accessor.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  // Define a zone-computation object an a visitor that performs the
  // incremental insertion.
  typedef Arr_inc_insertion_zone_visitor<Arrangement_2>  Zone_visitor;
  Zone_visitor                                     visitor;
  Arrangement_zone_2<Arrangement_2, Zone_visitor>  arr_zone (arr, &visitor);

  // Initialize the zone-computation object with the given curve.
  arr_zone.init_with_hint (c, obj);

  // Notify the arrangement observers that a global operation is about to 
  // take place.
  arr_access.notify_before_global_change();

  // Insert the x-monotone curve into the arrangement.
  arr_zone.compute_zone();

  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  return;
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement (incremental insertion).
// The inserted x-monotone curve may intersect the existing arrangement.
// Overloaded version with no point location object - the walk point-location
// strategy is used as default.
//
template <class Traits, class Dcel>
void insert_x_monotone_curve (Arrangement_2<Traits,Dcel>& arr,
                              const typename Traits::X_monotone_curve_2& c)
{
  typedef Arrangement_2<Traits, Dcel>                          Arrangement_2;
  typedef Arr_walk_along_line_point_location<Arrangement_2>    Walk_pl;
  
  // create walk point location object
  Walk_pl    walk_pl(arr);

  insert_x_monotone_curve (arr, c, walk_pl);
  return;
}

//-----------------------------------------------------------------------------
// Insert a range of x-monotone curves into the arrangement (aggregated
// insertion). The inserted x-monotone curves may intersect one another and
// may also intersect the existing arrangement.
//
template <class Traits, class Dcel, class InputIterator>
void insert_x_monotone_curves (Arrangement_2<Traits,Dcel>& arr,
                               InputIterator begin, InputIterator end)
{
  // Notify the arrangement observers that a global operation is about to 
  // take place.
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;

  Arr_accessor<Arrangement_2>                      arr_access (arr);

  arr_access.notify_before_global_change();

  // Perform the aggregated insertion.
  if(arr.is_empty())
  {
    // Perform the aggregated insertion.
    Arr_construction<Arrangement_2>              arr_construct (arr);
    arr_construct.insert_x_curves (begin, end);
  }
  else
  {
    Arr_addition<Arrangement_2>                  arr_adder(arr);
    arr_adder.insert_x_curves (begin, end);
  }
 
  // Notify the arrangement observers that the global operation has been
  // completed.
  arr_access.notify_after_global_change();

  return;
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement, such that the curve
// interior does not intersect with any existing edge or vertex in the
// arragement (incremental insertion).
//
template <class Traits, class Dcel, class PointLocation>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
insert_non_intersecting_curve (Arrangement_2<Traits,Dcel>& arr,
                               const typename Traits::X_monotone_curve_2& c,
                               const PointLocation& pl)
{
  typedef Arrangement_2<Traits,Dcel>                     Arrangement_2;
  typedef Arr_traits_basic_adaptor_2<typename Arrangement_2::Traits_2>
                                                         Traits_adaptor_2;
  typedef typename Arrangement_2::Vertex_const_handle    Vertex_const_handle;
  typedef typename Arrangement_2::Halfedge_const_handle  Halfedge_const_handle;

  Arr_accessor<Arrangement_2>       arr_access (arr);
  const Traits_adaptor_2           *traits =
    static_cast<const Traits_adaptor_2*> (arr.get_traits());

  // Check whether the left end of c lies at infinity, or whether it is a
  // normal endpoint, and locate it in the arrangement accordingly.
  const Boundary_type  inf_x1 = traits->boundary_in_x_2_object() (c, MIN_END);
  const Boundary_type  inf_y1 = traits->boundary_in_y_2_object() (c, MIN_END);
  CGAL::Object         obj1;
  const Halfedge_const_handle *fict_hh1 = NULL;
  const Vertex_const_handle   *vh1 = NULL;

  if (inf_x1 == NO_BOUNDARY && inf_y1 == NO_BOUNDARY)
  {
    // We have a normal left endpoint.
    obj1 = pl.locate (arr.get_traits()->construct_min_vertex_2_object() (c));

    // The endpoint must not lie on an existing edge, but may coincide with
    // and existing vertex vh1.
    CGAL_precondition_msg
      (object_cast<Halfedge_const_handle> (&obj1) == NULL,
       "The curve must not intersect an existing edge.");

    vh1 = object_cast<Vertex_const_handle> (&obj1);
  }
  else
  {
    // We have an unbounded left end.