sphere_map.h

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

// Copyright (c) 1997-2000  Max-Planck-Institute Saarbruecken (Germany).
// 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/Nef_S2/include/CGAL/Nef_S2/Sphere_map.h $
// $Id: Sphere_map.h 37248 2007-03-19 09:13:00Z afabri $
// 
//
// Author(s)     : Michael Seel       <[e-mail]>
//                 Peter Hachenberger <[e-mail]>

#ifndef CGAL_SPHERE_MAP_H
#define CGAL_SPHERE_MAP_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_2/Object_handle.h>
#include <CGAL/Nef_S2/SM_items.h>
#include <CGAL/Nef_S2/SM_list.h>
#include <CGAL/Nef_S2/SM_iteration.h>
#include <CGAL/Nef_S2/Generic_handle_map.h>
#include <CGAL/Nef_2/iterator_tools.h>
#include <list>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 109
#include <CGAL/Nef_2/debug.h>

#include<boost/optional.hpp>
#include<boost/none.hpp>

CGAL_BEGIN_NAMESPACE

template <typename HE>
class move_edge_around_svertex {
public:
  void forward(HE& e) const  { e = (e->sprev()->twin()); }
  void backward(HE& e) const { e = (e->twin()->snext()); }
};

template <typename HE>
struct move_edge_around_sface {
  void forward(HE& e)  const { e = (e->snext()); }
  void backward(HE& e) const { e = (e->sprev()); }
};

/*{\Manpage {Sphere_map}{Kernel}{Sphere Maps}{M}}*/

template <typename Kernel_, typename Items_, typename Mark_>
class Sphere_map {

/*{\Mdefinition selective sphere map container based on
the HDS design of Kettner.}*/

public:
  /*{\Mtypes 7}*/
  typedef Sphere_map<Kernel_, Items_,Mark_>   Self;
  typedef Kernel_                             Sphere_kernel;
  typedef Items_                              Items;
  typedef Mark_                               Mark;

  friend class SM_const_decorator<Self>;
  friend class SM_decorator<Self>;

  typedef typename Sphere_kernel::Sphere_point     Sphere_point;
  /*{\Mtypemember points on the unit sphere.}*/
  typedef typename Sphere_kernel::Sphere_segment   Sphere_segment;
  /*{\Mtypemember segments on the unit sphere.}*/
  typedef typename Sphere_kernel::Sphere_circle    Sphere_circle;
  /*{\Mtypemember segments on the unit sphere.}*/
  typedef typename Sphere_kernel::Sphere_direction Sphere_direction;
  /*{\Mtypemember directions on the unit sphere.}*/
  //  typedef bool                                     Mark;
  /*{\Mtypemember selective attributes of all objects.}*/
  typedef size_t   Size_type;
  /*{\Mtypemember size type.}*/

  /*{\Mtext For all objects |Vertex|, |Halfedge|, |Halfloop|, |Face|
  there are handle and iterator types |xxx_handle|, |xxx_iterator|.
  There's no type |SLoop_iterator|, as there is
  at most one |SLoop| pair per sphere map.}*/

  typedef typename Items::template SVertex<Self>        SVertex_base;
  typedef SNC_in_place_list_svertex<SVertex_base>       SVertex;
  typedef CGAL::In_place_list<SVertex,false>            SVertex_list;
  typedef CGAL_ALLOCATOR(SVertex)                       SVertex_alloc;
  typedef typename SVertex_list::iterator               SVertex_handle;
  typedef typename SVertex_list::const_iterator         SVertex_const_handle;
  typedef typename SVertex_list::iterator               SVertex_iterator;
  typedef typename SVertex_list::const_iterator         SVertex_const_iterator;

  typedef typename Items::template SHalfedge<Self>      SHalfedge_base;
  typedef SNC_in_place_list_shalfedge<SHalfedge_base>   SHalfedge;
  typedef CGAL::In_place_list<SHalfedge,false>          SHalfedge_list;
  typedef CGAL_ALLOCATOR(SHalfedge)                     SHalfedge_alloc;
  typedef typename SHalfedge_list::iterator             SHalfedge_handle;
  typedef typename SHalfedge_list::const_iterator       SHalfedge_const_handle;
  typedef typename SHalfedge_list::iterator             SHalfedge_iterator;
  typedef typename SHalfedge_list::const_iterator       SHalfedge_const_iterator;

  typedef typename Items::template SFace<Self>          SFace_base;
  typedef SNC_in_place_list_sface<SFace_base>           SFace;
  typedef CGAL::In_place_list<SFace,false>              SFace_list;
  typedef CGAL_ALLOCATOR(SFace)                         SFace_alloc;
  typedef typename SFace_list::iterator                 SFace_handle;
  typedef typename SFace_list::const_iterator           SFace_const_handle;
  typedef typename SFace_list::iterator                 SFace_iterator;
  typedef typename SFace_list::const_iterator           SFace_const_iterator;

  typedef typename Items::template SHalfloop<Self>      SHalfloop;
  typedef SHalfloop*                                    SHalfloop_handle;
  typedef const SHalfloop*                              SHalfloop_const_handle;
  typedef SHalfloop*                                    SHalfloop_iterator;
  typedef const SHalfloop*                              SHalfloop_const_iterator;

  typedef CGAL::Object_handle Object_handle;
  /*{\Mtypemember a generic handle to an object of |\Mvar|. 
  The kind of the object can be determined and the object assigned 
  by the function:\\ 
  |bool assign(xxx_handle& h, Object_handle o)|\\ 
  where the function returns |true| iff the assignment of |o| to 
  |h| was valid.}*/

  typedef std::list<Object_handle>                     Object_list;
  typedef typename Object_list::iterator               Object_iterator;
  typedef typename Object_list::const_iterator         Object_const_iterator;
  typedef boost::optional<Object_iterator>             Optional_object_iterator ;
  typedef Generic_handle_map<Optional_object_iterator> Handle_to_iterator_map;

  typedef Sphere_map*       Constructor_parameter;
  typedef const Sphere_map* Constructor_const_parameter;

  class SFace_cycle_iterator : public Object_iterator 
  /*{\Mtypemember a generic iterator to an object in the boundary
  of a facet. Convertible to |Object_handle|.}*/
  { typedef Object_iterator Ibase;
  public:
    SFace_cycle_iterator() : Ibase() {}
    SFace_cycle_iterator(const Ibase& b) : Ibase(b) {}
    SFace_cycle_iterator(const SFace_cycle_iterator& i) : Ibase(i) {}  
    bool is_svertex() const 
    { SVertex_handle v; return CGAL::assign(v,Ibase::operator*()); }
    bool is_shalfedge() const
    { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
    bool is_shalfloop() const
    { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
    operator SVertex_handle() const 
    { SVertex_handle v; CGAL::assign(v,Ibase::operator*()); return v; }
    operator SHalfedge_handle() const 
    { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); return e; }
    operator SHalfloop_handle() const 
    { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); return l; }

    operator Object_handle() const { return Ibase::operator*(); }
    Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { CGAL_assertion_msg(0,"not impl."); return Object_handle(); }
  };

  class SFace_cycle_const_iterator : public Object_const_iterator 
  /*{\Mtypemember a generic iterator to an object in the boundary
  of a facet. Convertible to |Object_handle|.}*/
  { typedef Object_const_iterator Ibase;
  public:
    SFace_cycle_const_iterator() : Ibase() {}
    SFace_cycle_const_iterator(const Ibase& b) : Ibase(b) {}
    SFace_cycle_const_iterator(const SFace_cycle_const_iterator& i) 
      : Ibase(i) {}  
    bool is_svertex() const 
    { SVertex_handle v; return CGAL::assign(v,Ibase::operator*()); }
    bool is_shalfedge() const
    { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
    bool is_shalfloop() const
    { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
    operator SVertex_const_handle() const 
    { SVertex_handle v; CGAL::assign(v,Ibase::operator*()); 
      return SVertex_const_handle(v); }
    operator SHalfedge_const_handle() const 
    { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); 
      return SHalfedge_const_handle(e); }
    operator SHalfloop_const_handle() const 
    { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); 
      return SHalfloop_const_handle(l); }

    operator Object_handle() const { return Ibase::operator*(); }
    const Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { CGAL_assertion_msg(0,"not impl."); return Object_handle(); }
  };

  /*{\Mtext Local types are handles, iterators and circulators of the
    following kind: |SVertex_handle|, |SVertex_iterator|, |SHalfedge_handle|,
    |SHalfedge_iterator|, |SHalfloop_handle|, |SHalfloop_iterator|,
    |SFace_handle|, |SFace_iterator|.  Additionally the following
    circulators are defined.}*/

  typedef CircFromIt<
    SHalfedge_const_iterator, 
    move_edge_around_svertex<SHalfedge_const_iterator> > 
    SHalfedge_around_svertex_const_circulator;
  /*{\Mtypemember circulating the adjacency list of an vertex |v|.}*/
  
  typedef CircFromIt<
    SHalfedge_const_iterator, 
    move_edge_around_sface<SHalfedge_const_iterator> > 
    SHalfedge_around_sface_const_circulator;
  /*{\Mtypemember circulating the face cycle of an face |f|.}*/

  typedef CircFromIt<
    SHalfedge_iterator, 
    move_edge_around_svertex<SHalfedge_iterator> > 
    SHalfedge_around_svertex_circulator;
  /*{\Mtypemember circulating the adjacency list of an vertex |v|.}*/
  
  typedef CircFromIt<
    SHalfedge_iterator, 
    move_edge_around_sface<SHalfedge_iterator> > 
    SHalfedge_around_sface_circulator;
  /*{\Mtypemember circulating the face cycle of an face |f|.}*/
  
  /*{\Mcreation 3}*/
  /*{\Mtext |\Mname| is default and copy constructible. Note that copy
  construction means cloning an isomorphic structure and is thus an
  expensive operation.}*/

  Sphere_map(bool = false) : boundary_item_(boost::none), 
    svertices_(), sedges_(), sfaces_(), shalfloop_() {}

  ~Sphere_map() { clear(); }

  Sphere_map(const Self& D) : boundary_item_(boost::none),
    svertices_(D.svertices_), 
    sedges_(D.sedges_), 
    sfaces_(D.sfaces_), 
    shalfloop_(0)
  { if ( D.shalfloop_ != 0 ) new_shalfloop_pair(*(D.shalfloop_));
    pointer_update(D); 
  }

  Self& operator=(const Self& D) 
  { if ( this == &D ) return *this; 
    clear();
    svertices_ = D.svertices_; 
    sfaces_ = D.sfaces_;
    sedges_ = D.sedges_;
    if ( D.shalfloop_ != 0 ) new_shalfloop_pair(*D.shalfloop_);
    pointer_update(D);
    return *this;
  }

  void clear()
  { 
    boundary_item_.clear(boost::none);
    svertices_.destroy(); 
    sfaces_.destroy();
    while ( shalfedges_begin() != shalfedges_end() )
      delete_shalfedge_pair( shalfedges_begin() );
    if ( shalfloop_ != 0 ) { delete_shalfloop_pair(); shalfloop_=0; }
  }

  template <typename H>
  bool is_sm_boundary_object(H h) const
  { return boundary_item_[h]!=boost::none; }

  template <typename H>
  Object_iterator& sm_boundary_item(H h)
  { return *boundary_item_[h]; }

  template <typename H>
  void store_sm_boundary_item(H h, Object_iterator o)
  { boundary_item_[h] = o; }

  template <typename H>
  void undef_sm_boundary_item(H h)
  { CGAL_assertion(boundary_item_[h]!=boost::none);
    boundary_item_[h] = boost::none; }

  void reset_sm_iterator_hash(Object_iterator it)
  { SVertex_handle sv;
    SHalfedge_handle se;
    SHalfloop_handle sl;