arrangement_2_functions.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_functions.h $
// $Id: Arrangement_2_functions.h 39243 2007-06-27 09:41:54Z ophirset $
// 
//
// Author(s)     : Ron Wein          <[e-mail]>
//                 Efi Fogel         <[e-mail]>
//                 (based on old version by: Iddo Hanniel,
//                                           Eyal Flato,
//                                           Oren Nechushtan,
//                                           Ester Ezra,
//                                           Shai Hirsch,
//                                           and Eugene Lipovetsky)
//
#ifndef CGAL_ARRANGEMENT_2_FUNCTIONS_H
#define CGAL_ARRANGEMENT_2_FUNCTIONS_H

/*! \file
 * Member-function definitions for the Arrangement_2<Traits,Dcel> class.
 */

#include <CGAL/function_objects.h> 

CGAL_BEGIN_NAMESPACE

//-----------------------------------------------------------------------------
// Default constructor.
//
template<class Traits, class Dcel>
Arrangement_2<Traits,Dcel>::Arrangement_2 ()
{
  // Construct an empty arrangement.
  _construct_empty_arrangement ();

  // Allocate the traits.
  traits = new Traits_adaptor_2;
  own_traits = true;
}

//-----------------------------------------------------------------------------
// Copy constructor.
//
template<class Traits, class Dcel>
Arrangement_2<Traits,Dcel>::Arrangement_2 (const Self& arr) :
  v_bl (NULL),
  v_tl (NULL),
  v_br (NULL),
  v_tr (NULL),
  n_inf_verts (0),
  un_face (NULL),
  traits (NULL),
  own_traits (false)
{
  assign (arr);
}

//-----------------------------------------------------------------------------
// Constructor given a traits object.
//
template<class Traits, class Dcel>
Arrangement_2<Traits,Dcel>::Arrangement_2 (Traits_2 *tr)
{
  // Construct an empty arrangement.
  _construct_empty_arrangement ();

  // Set the traits.
  traits = static_cast<Traits_adaptor_2*>(tr);
  own_traits = false;
}

//-----------------------------------------------------------------------------
// Assignment operator.
//
template<class Traits, class Dcel>
Arrangement_2<Traits,Dcel>&
Arrangement_2<Traits,Dcel>::operator= (const Self& arr)
{
  // Check for self-assignment.
  if (this == &arr)
    return (*this);

  assign (arr);
  return (*this);
}

//-----------------------------------------------------------------------------
// Assign an arrangement.
//
template<class Traits, class Dcel>
void Arrangement_2<Traits,Dcel>::assign (const Self& arr)
{
  // Clear the current contents of the arrangement.
  clear();

  // Notify the observers that an assignment is to take place.
  _notify_before_assign (arr);

  // Duplicate the DCEL.
  un_face = dcel.assign (arr.dcel, arr.un_face);
  n_inf_verts = arr.n_inf_verts;

  // Go over the vertices and create duplicates of the stored points.
  typename Dcel::Vertex_iterator       vit;
  Point_2                             *dup_p;
  DVertex                             *p_v;
  Boundary_type                        inf_x, inf_y;
  const DHalfedge                     *first_he, *next_he;

  for (vit = dcel.vertices_begin(); vit != dcel.vertices_end(); ++vit)
  {
    p_v = &(*vit);
    inf_x = p_v->boundary_in_x();
    inf_y = p_v->boundary_in_y();

    if (inf_x == NO_BOUNDARY && inf_y == NO_BOUNDARY)
    {
      // Normal vertex (not at inifinity): Create the duplicate point and
      // store it in the points container.
      dup_p = _new_point (p_v->point());

      // Associate the vertex with the duplicated point.
      p_v->set_point (dup_p);
    }
    else
    {
      // Check if this is one of the ficitious vertices at infinity. These
      // vertices have degree 2, as opposed to other vertices at infinity
      // which have degree 3.
      first_he = p_v->halfedge();
      next_he = first_he->next()->opposite();
      
      if (next_he->next()->opposite() == first_he)
      {
        if (inf_x == MINUS_INFINITY && inf_y == MINUS_INFINITY)
          v_bl = p_v;
        else if (inf_x == MINUS_INFINITY && inf_y == PLUS_INFINITY)
          v_tl = p_v;
        else if (inf_x == PLUS_INFINITY && inf_y == MINUS_INFINITY)
          v_br = p_v;
        else if (inf_x == PLUS_INFINITY && inf_y == PLUS_INFINITY)
          v_tr = p_v;
        else
          // We should never reach here:
          CGAL_assertion (false);
      }
    }
  }

  // Go over the edge and create duplicates of the stored curves.
  typename Dcel::Edge_iterator         eit;
  X_monotone_curve_2                  *dup_cv;
  DHalfedge                           *p_e;

  for (eit = dcel.edges_begin(); eit != dcel.edges_end(); ++eit)
  {
    p_e = &(*eit);

    if (! p_e->has_null_curve())
    {
      // Create the duplicate curve and store it in the curves container.
      dup_cv = _new_curve (p_e->curve());

      // Associate the halfedge (and its twin) with the duplicated curve. 
      p_e->set_curve (dup_cv);
    }
  }

  // Take care of the traits object.
  if (own_traits && traits != NULL)
    delete traits;

  if (arr.own_traits)
    traits = new Traits_adaptor_2;
  else
    traits = arr.traits;
  own_traits = arr.own_traits;

  // Notify the observers that the assignment has been performed.
  _notify_after_assign ();

  return;
}

//-----------------------------------------------------------------------------
// Destructor.
//
template<class Traits, class Dcel>
Arrangement_2<Traits,Dcel>::~Arrangement_2 ()
{  
  // Free all stored points.
  typename Dcel::Vertex_iterator       vit;

  for (vit = dcel.vertices_begin(); vit != dcel.vertices_end(); ++vit)
  {
    if (! vit->has_null_point())
      _delete_point (vit->point());
  }

  // Free all stores curves.
  typename Dcel::Edge_iterator         eit;

  for (eit = dcel.edges_begin(); eit != dcel.edges_end(); ++eit)
  {
    if (! eit->has_null_curve())
      _delete_curve (eit->curve());
  }

  // Clear the DCEL.
  dcel.delete_all();

  // Free the traits object, if necessary.
  if (own_traits)
    delete traits;

  // Detach all observers still attached to the arrangement.
  Observers_iterator  iter = observers.begin();
  Observers_iterator  next;
  Observers_iterator  end = observers.end();

  while (iter != end)
  {
    next = iter;
    ++next;
    (*iter)->detach();
    iter = next;
  }
}

//-----------------------------------------------------------------------------
// Clear the arrangement.
template<class Traits, class Dcel>
void Arrangement_2<Traits,Dcel>::clear ()
{
  // Notify the observers that we are about to clear the arragement.
  _notify_before_clear ();

  // Free all stored points.
  typename Dcel::Vertex_iterator       vit;

  for (vit = dcel.vertices_begin(); vit != dcel.vertices_end(); ++vit)
  {
    if (! vit->has_null_point())
      _delete_point (vit->point());
  }

  // Free all stores curves.
  typename Dcel::Edge_iterator         eit;

  for (eit = dcel.edges_begin(); eit != dcel.edges_end(); ++eit)
  {
    if (! eit->has_null_curve())
      _delete_curve (eit->curve());
  }

  // Clear the DCEL and construct an empty arrangement.
  dcel.delete_all();
  _construct_empty_arrangement ();

  // Notify the observers that we have just cleared the arragement.
  _notify_after_clear (unbounded_face());

  return;
}

//-----------------------------------------------------------------------------
// Insert a point as an isolated vertex in the interior of a given face.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Vertex_handle
Arrangement_2<Traits,Dcel>::insert_in_face_interior (const Point_2& p,
                                                     Face_handle f)
{
  DFace          *p_f = _face (f);

  // Create a new vertex associated with the given point.
  DVertex         *v =_create_vertex (p);
  Vertex_handle   vh (v);

  // Insert v as an isolated vertex inside the given face.
  _insert_isolated_vertex (p_f, v);

  // Return a handle to the new isolated vertex.
  return (vh);
}

//-----------------------------------------------------------------------------
// Insert an x-monotone curve into the arrangement as a new hole (inner
// component) inside the given face.
//
template<class Traits, class Dcel>
typename Arrangement_2<Traits,Dcel>::Halfedge_handle
Arrangement_2<Traits,Dcel>::insert_in_face_interior
    (const X_monotone_curve_2& cv, 
     Face_handle f)
{
  DFace            *p_f = _face (f);

  // Check if cv's left end lies at infinity, and create a vertex v1 that
  // corresponds to this end.
  const Boundary_type  inf_x1 = traits->boundary_in_x_2_object()(cv, MIN_END);
  const Boundary_type  inf_y1 = traits->boundary_in_y_2_object()(cv, MIN_END);
  DVertex             *v1 = NULL;
  DHalfedge           *fict_prev1 = NULL;

  if (inf_x1 == NO_BOUNDARY && inf_y1 == NO_BOUNDARY)
  {
    // The curve has a valid left endpoint: Create a new vertex associated
    // with the curve's left endpoint.
    v1 = _create_vertex (traits->construct_min_vertex_2_object()(cv));
  }
  else
  {
    // Locate a halfedge of f's outer CCB such that contains cv's left end
    // in its range.
    CGAL_precondition (f->is_unbounded());

    fict_prev1 = _locate_along_ccb (p_f, cv, MIN_END,
                                    inf_x1, inf_y1);

    CGAL_assertion (fict_prev1 != NULL);

    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's left end.
    fict_prev1 = _split_fictitious_edge (fict_prev1,
                                         inf_x1, inf_y1);
  }

  // Check if cv's right end lies at infinity, and create a vertex v2 that
  // corresponds to this end.
  const Boundary_type  inf_x2 = traits->boundary_in_x_2_object()(cv, MAX_END);
  const Boundary_type  inf_y2 = traits->boundary_in_y_2_object()(cv, MAX_END);
  DVertex             *v2 = NULL;
  DHalfedge           *fict_prev2 = NULL;

  if (inf_x2 == NO_BOUNDARY && inf_y2 == NO_BOUNDARY)
  {
    // The curve has a valid right endpoint: Create a new vertex associated
    // with the curve's right endpoint.
    v2 = _create_vertex (traits->construct_max_vertex_2_object()(cv));
  }
  else
  {    
    // Locate a halfedge of f's outer CCB such that contains cv's right end
    // in its range.
    CGAL_precondition (f->is_unbounded());
    
    fict_prev2 = _locate_along_ccb (p_f, cv, MAX_END,
                                    inf_x2, inf_y2);

    CGAL_assertion (fict_prev2 != NULL);

    // Split the fictitious edge and create a vertex at infinity that
    // represents cv's right end.
    fict_prev2 = _split_fictitious_edge (fict_prev2,
                                         inf_x2, inf_y2);
  }

  // Create the edge connecting the two vertices (note we know v1 is 
  // lexicographically smaller than v2).
  DHalfedge       *new_he;

  if (fict_prev1 == NULL && fict_prev2 == NULL)
  {