pm_decorator.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_2/include/CGAL/Nef_2/PM_decorator.h $
// $Id: PM_decorator.h 28567 2006-02-16 14:30:13Z lsaboret $
// 
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_PM_DECORATOR_H
#define CGAL_PM_DECORATOR_H
#include <CGAL/Nef_2/PM_const_decorator.h>
#include <CGAL/Nef_2/geninfo.h>
#include <CGAL/Unique_hash_map.h>
#include <vector>

CGAL_BEGIN_NAMESPACE

/*{\Moptions outfile=PMDecorator.man }*/
/*{\Msubst 
PM_decorator#PMDecorator
PM_const_decorator#PMConstDecorator
}*/
/*{\Manpage {PMDecorator}{}{Plane map manipulation}{D}}*/

template <typename HDS>
class PM_decorator : public PM_const_decorator<HDS>
{ 
/*{\Mdefinition An instance |\Mvar| of the data type |\Mname| is a 
decorator to examine and modify a plane map. |\Mvar| inherits from 
|PM_const_decorator| but provides additional manipulation operations.}*/

/*{\Mgeneralization PM_const_decorator}*/

public:
/*{\Mtypes 3}*/
  typedef PM_decorator<HDS>        Self;
  typedef PM_const_decorator<HDS>  Base;
  typedef HDS                       Plane_map;
  typedef typename HDS::Vertex_base Vertex_base; 
  typedef typename HDS::Halfedge_base Halfedge_base; 
  typedef typename HDS::Face_base Face_base;
  typedef typename HDS::Vertex Vertex; 
  typedef typename HDS::Halfedge Halfedge; 
  typedef typename HDS::Face Face; 
  typedef typename HDS::Vertex_handle Vertex_handle;    
  typedef typename HDS::Vertex_iterator Vertex_iterator;
  typedef typename HDS::Halfedge_handle Halfedge_handle;  
  typedef typename HDS::Halfedge_iterator Halfedge_iterator;
  typedef typename HDS::Face_handle Face_handle;      
  typedef typename HDS::Face_iterator Face_iterator;
  typedef typename HDS::Vertex_const_handle Vertex_const_handle;
  typedef typename HDS::Halfedge_const_handle Halfedge_const_handle; 
  typedef typename HDS::Face_const_handle Face_const_handle; 
  typedef typename HDS::Vertex_const_iterator Vertex_const_iterator; 
  typedef typename HDS::Halfedge_const_iterator Halfedge_const_iterator; 
  typedef typename HDS::Face_const_iterator Face_const_iterator; 
  typedef typename Base::Hole_const_iterator Hole_const_iterator ; 
  typedef typename Base::Isolated_vertex_const_iterator Isolated_vertex_const_iterator; 
  typedef typename Base::Point_const_iterator Point_const_iterator;
  typedef typename Base::Mark Mark; 
typedef typename Base::Point Point; 
typedef typename Base::GenPtr GenPtr;

/*{\Mtext Local types are handles, iterators and circulators of the following
kind: |Vertex_handle|, |Vertex_iterator|, |Halfedge_handle|,
|Halfedge_iterator|, |Face_handle|, |Face_iterator|.  Additionally the
following circulators are defined. The |circulators| can be constructed from
the corresponding halfedge handles or iterators.}*/

typedef CircFromIt<
        Halfedge_iterator, 
        move_halfedge_around_vertex<Halfedge_iterator> > 
        Halfedge_around_vertex_circulator;
/*{\Mtypemember circulating the outgoing halfedges in $A(v)$.}*/

typedef CircFromIt<
        Halfedge_iterator, 
        move_halfedge_around_face<Halfedge_iterator> > 
        Halfedge_around_face_circulator;
/*{\Mtypemember circulating the halfedges in the face cycle of a 
face |f|.}*/

typedef typename Face::Hole_iterator Hole_iterator;
/*{\Mtypemember iterating all holes of a face |f|. The type is 
convertible to |Halfedge_handle|.}*/

typedef typename Face::Isolated_vertex_iterator Isolated_vertex_iterator;
/*{\Mtypemember iterating all isolated vertices of a face |f|. 
The type generalizes |Vertex_handle|.}*/


/* note: originally I had the mhavs, mhafs hardwired to Halfedge
   in this class scope. egcs 290.60 reacted with an internal compiler
   error; this recursive instatiation scheme works however! 
   what a shitty world */

enum { BEFORE = -1, AFTER = 1 };
/*{\Menum insertion order labels.}*/




#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Base::phds;
#endif

/*{\Mcreation 3}*/

PM_decorator() : Base() {}
PM_decorator(const PM_decorator& D) : 
  Base((PM_const_decorator<HDS>)D) {}
PM_decorator& operator=(const PM_decorator& D)
{ Base::phds = ((PM_const_decorator<HDS>)D).phds; return *this; }

PM_decorator(Plane_map& p) : Base(p) {}
/*{\Mcreate constructs a decorator working on |P|.}*/

#define BASE(t) { return Base::t; }
Hole_const_iterator  holes_begin(Face_const_handle f) const
BASE(holes_begin(f))
Hole_const_iterator  holes_end(Face_const_handle f) const
BASE(holes_end(f))
Isolated_vertex_const_iterator  
isolated_vertices_begin(Face_const_handle f) const
BASE(isolated_vertices_begin(f))
Isolated_vertex_const_iterator  
isolated_vertices_end(Face_const_handle f) const
BASE(isolated_vertices_end(f))
Vertex_const_handle source(Halfedge_const_handle e) const
BASE(source(e))
Vertex_const_handle target(Halfedge_const_handle e) const
BASE(target(e))
Halfedge_const_handle twin(Halfedge_const_handle e) const 
BASE(twin(e))
bool is_isolated(Vertex_const_handle v) const
BASE(is_isolated(v))
Halfedge_const_handle first_out_edge(Vertex_const_handle v) const
BASE(first_out_edge(v))
Halfedge_const_handle last_out_edge(Vertex_const_handle v) const
BASE(last_out_edge(v))
Halfedge_const_handle cyclic_adj_succ(
  Halfedge_const_handle e) const
BASE(cyclic_adj_succ(e))
Halfedge_const_handle cyclic_adj_pred(
  Halfedge_const_handle e) const
BASE(cyclic_adj_pred(e))
Halfedge_const_handle next(Halfedge_const_handle e) const
BASE(next(e))
Halfedge_const_handle previous(Halfedge_const_handle e) const
BASE(previous(e))
Face_const_handle face(Halfedge_const_handle e) const
BASE(face(e))
Face_const_handle face(Vertex_const_handle v) const
BASE(face(v))
const Mark& mark(Vertex_const_handle v) const  
BASE(mark(v))
const Mark& mark(Halfedge_const_handle e) const 
BASE(mark(e))
const Mark& mark(Face_const_handle f) const
BASE(mark(f))
const Point& point(Vertex_const_handle v) const
BASE(point(v))
const GenPtr& info(Vertex_const_handle v) const
BASE(info(v))
const GenPtr& info(Halfedge_const_handle e) const
BASE(info(e))
const GenPtr& info(Face_const_handle f) const
BASE(info(f))
#undef BASE

/*{\Moperations 3 3}*/

Plane_map& plane_map() const
/*{\Mop returns the plane map decorated.}*/
{ return *Base::phds; }

void clear() const
/*{\Mop reinitializes |P| to the empty map.}*/
{ this->phds->clear(); }

Vertex_handle source(Halfedge_handle e) const
/*{\Mop returns the source of |e|.}*/
{ return e->opposite()->vertex(); }

Vertex_handle target(Halfedge_handle e) const
/*{\Mop returns the target of |e|.}*/
{ return e->vertex(); }
 
Halfedge_handle twin(Halfedge_handle e) const
/*{\Mop returns the twin of |e|.}*/
{ return e->opposite(); }

bool is_isolated(Vertex_handle v) const
/*{\Mop returns |true| iff |v| is linked to the interior of a face.
This is equivalent to the condition that $A(v) = \emptyset$.}*/
{ return v->is_isolated(); }

bool is_closed_at_source(Halfedge_handle e) const
/*{\Mop returns |true| when |prev(e) == twin(e)|.}*/
{ return e->prev() == e->opposite(); }

Halfedge_handle first_out_edge(Vertex_handle v) const
/*{\Mop returns a halfedge with source |v|. It's the starting point for
  the circular iteration over the halfedges with source |v|.
  \precond |!is_isolated(v)|.}*/
{ return v->halfedge()->opposite(); }

Halfedge_handle last_out_edge(Vertex_handle v) const
/*{\Mop returns a the halfedge with source |v| that is the last
  in the circular iteration before encountering |first_out_edge(v)| 
  again. \precond |!is_isolated(v)|.}*/
{ return v->halfedge()->next(); }

Halfedge_handle cas(Halfedge_handle e) const 
{ return e->prev()->opposite(); } 

Halfedge_handle cap(Halfedge_handle e) const
{ return e->opposite()->next(); }

Halfedge_handle cyclic_adj_succ(Halfedge_handle e) const
{ return cas(e); }
/*{\Mop returns the edge after |e| in the cyclic ordered adjacency list of
  |source(e)|.}*/

Halfedge_handle cyclic_adj_pred(Halfedge_handle e) const
{ return cap(e); }
/*{\Mop returns the edge before |e| in the cyclic ordered adjacency list of
  |source(e)|.}*/

Halfedge_handle adj_succ_at_source(Halfedge_handle e) const
{ if (e==last_out_edge(source(e))) return Halfedge_handle(); 
  return cas(e); }
// the edge of source(e) is the first in the adj list
 
Halfedge_handle adj_pred_at_source(Halfedge_handle e) const
{ if (e==first_out_edge(source(e))) return Halfedge_handle();
  return cap(e); }
// the edge of source(e) is the first in the adj list

Halfedge_handle next(Halfedge_handle e) const
/*{\Mop returns the next edge in the face cycle containing |e|.}*/
{ return e->next(); }

Halfedge_handle previous(Halfedge_handle e) const
/*{\Mop returns the previous edge in the face cycle containing |e|.}*/
{ return e->prev(); }

Face_handle face(Halfedge_handle e) const
/*{\Mop returns the face incident to |e|.}*/
{ return e->face(); }

Face_handle face(Vertex_handle v) const
/*{\Mop returns the face incident to |v|.
   \precond |is_isolated(v)|.}*/
{ return v->face(); }

Halfedge_handle halfedge(Face_handle f) const
/*{\Mop returns a halfedge in the bounding face cycle of |f| 
(|Halfedge_handle()| if there is no bounding face cycle).}*/
{ return f->halfedge(); }

Vertex_iterator   vertices_begin() const
{ return this->phds->vertices_begin(); }
Halfedge_iterator halfedges_begin() const
{ return this->phds->halfedges_begin(); }
Face_iterator     faces_begin() const
{ return this->phds->faces_begin(); }
Vertex_iterator   vertices_end() const
{ return this->phds->vertices_end(); }
Halfedge_iterator halfedges_end() const
{ return this->phds->halfedges_end(); }
Face_iterator     faces_end() const
{ return this->phds->faces_end(); }

/*{\Mtext \headerline{Iteration} \setopdims{6.5cm}{0cm}}*/

Halfedge_around_vertex_circulator 
  out_edges(Vertex_handle v) const
/*{\Mop returns a circulator for the cyclic adjacency list of |v|.}*/
{ return Halfedge_around_vertex_circulator(first_out_edge(v)); }

Halfedge_around_face_circulator 
  face_cycle(Face_handle f) const
/*{\Mop returns a circulator for the outer face cycle of |f|.}*/
{ return Halfedge_around_face_circulator(f->halfedge()); }

Hole_iterator  holes_begin(Face_handle f) const
/*{\Mop returns an iterator for all holes in the interior of |f|.
   A |Hole_iterator| can be assigned to a 
   |Halfedge_around_face_circulator|.}*/
{ return f->fc_begin(); }

Hole_iterator  holes_end(Face_handle f) const
/*{\Mop returns the past-the-end iterator of |f|.}*/
{ return f->fc_end(); }

Isolated_vertex_iterator isolated_vertices_begin(Face_handle f) const
/*{\Mop returns an iterator for all isolated vertices in the interior 
of |f|.}*/
{ return f->iv_begin(); }

Isolated_vertex_iterator isolated_vertices_end(Face_handle f) const
/*{\Mop returns the past the end iterator of |f|.}*/
{ return f->iv_end(); }

/*{\Mtext \headerline{Update Operations} \restoreopdims}*/

Vertex_handle new_vertex(const Vertex_base& vb = Vertex_base()) const
/*{\Mop creates a new vertex.}*/
{ Vertex_handle v = this->phds->vertices_push_back(vb);
  v->set_halfedge(Halfedge_handle());
  return v;