pm_const_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_const_decorator.h $
// $Id: PM_const_decorator.h 28567 2006-02-16 14:30:13Z lsaboret $
// 
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_PM_CONST_DECORATOR_H
#define CGAL_PM_CONST_DECORATOR_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <string>
#include <list>
#include <sstream>
#include <CGAL/Nef_2/Object_index.h>
#include <CGAL/Nef_2/iterator_tools.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 7
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

template <typename Iter, typename Move>
inline CGAL::Circulator_tag  
query_circulator_or_iterator(const CircFromIt<Iter,Move>& )
{ return CGAL::Circulator_tag(); }


template <typename HE>
class move_halfedge_around_vertex {
public:
  void forward(HE& e) const  { e = (e->prev()->opposite()); }
  void backward(HE& e) const { e = (e->opposite()->next()); }
};

template <typename HE>
struct move_halfedge_around_face {
  void forward(HE& e)  const { e = (e->next()); }
  void backward(HE& e) const { e = (e->prev()); }
};


/*{\Moptions print_title=yes}*/ 
/*{\Moptions constref=yes}*/ 
/*{\Msubst 
PM_const_decorator#PMConstDecorator
PM_decorator#PMDecorator
}*/ 
/*{\Moptions outfile=PMConstDecorator.man }*/
/*{\Manpage {PMConstDecorator}{}{Topological plane map exploration}{D}}*/

template <typename HDS> class PM_decorator;

template <typename HDS>
class PM_const_decorator 
{ typedef PM_const_decorator<HDS> Self;
/*{\Mdefinition An instance |\Mvar| of the data type |\Mname| is a 
decorator for interfacing the topological structure of a plane map |P| 
(read-only).

A plane map |P| consists of a triple $(V, E, F)$ of vertices, edges, and
faces. We collectively call them objects. An edge |e| is a pair of
vertices |(v,w)| with incidence operations |v = source(e)|, |w =
target(e)|. The list of all edges with source |v| is called the
adjacency list |A(v)|.

Edges are paired into twins. For each edge |e = (v,w)| there's an edge
|twin(e) = (w,v)| and |twin(twin(e)) == e|\footnote{The existence of 
the edge pairs makes |P| a bidirected graph, the |twin| links make
|P| a map.}.

An edge |e = (v,w)| knows two adjacent edges |en = next(e)| and |ep
= previous(e)| where |source(en) = w|, |previous(en) = e| and
|target(ep) = v| and |next(ep) = e|. By this symmetric |previous-next|
relationship all edges are partitioned into face cycles.  Two edges
$e$ and $e'$ are in the same face cycle if $e = |next|^*(e')$.  All
edges |e| in the same face cycle have the same incident face $f =
|face|(e)$. The cyclic order on the adjacency list of a vertex |v =
source(e)| is given by |cyclic_adj_succ(e) = twin(previous(e))| and
|cyclic_adj_pred(e) = next(twin(e))|.

A vertex |v| is embedded via coordinates |point(v)|. By the
embedding of its source and target an edge corresponds to a
segment. |P| has the property that the embedding is always
\emph{order-preserving}.  This means a ray fixed in |point(v)| of a
vertex |v| and swept around counterclockwise meets the embeddings of
|target(e)| ($e \in A(v)$) in the cyclic order defined by the list
order of |A|.

The embedded face cycles partition the plane into maximal connected
subsets of points. Each such set corresponds to a face. A face is
bounded by its incident face cycles. For all the edges in the
non-trivial face cycles it holds that the face is left of the edges.
There can also be trivial face cycles in form of isolated vertices in
the interior of a face. Each such vertex |v| knows its surrounding
face |f = face(v)|.

We call the embedded map |(V,E)| also the $1$-skeleton of |P|.

Plane maps are attributed. To each object $u \in V \cup E \cup F$
we attribute a value |mark(u)| of type |Mark|. |Mark| fits the
concepts assignable, default-constructible, and equal-comparable.}*/

protected: 
HDS* phds; 
friend class PM_decorator<HDS>;

public:
/*{\Mtypes 6}*/
typedef HDS Plane_map;
/*{\Mtypemember The underlying plane map type}*/

typedef typename HDS::Traits Traits;

typedef typename Traits::Point  Point;
/*{\Mtypemember The point type of vertices.}*/
typedef typename Traits::Mark   Mark;
/*{\Mtypemember All objects (vertices, edges, faces) are attributed by a 
|Mark| object.}*/
typedef size_t Size_type;
/*{\Mtypemember The size type.}*/
typedef void*  GenPtr;


typedef typename HDS::Vertex                  Vertex; 
typedef typename HDS::Vertex_base             Vertex_base;
typedef typename HDS::Vertex_handle           Vertex_handle;
typedef typename HDS::Vertex_const_handle     Vertex_const_handle;
typedef typename HDS::Vertex_const_iterator   Vertex_const_iterator;
typedef typename HDS::Halfedge                Halfedge ; 
typedef typename HDS::Halfedge_base           Halfedge_base ;
typedef typename HDS::Halfedge_handle         Halfedge_handle; 
typedef typename HDS::Halfedge_const_handle   Halfedge_const_handle;
typedef typename HDS::Halfedge_const_iterator Halfedge_const_iterator;
typedef typename HDS::Face                    Face;
typedef typename HDS::Face_base               Face_base;
typedef typename HDS::Face_handle             Face_handle;
typedef typename HDS::Face_const_handle       Face_const_handle;
typedef typename HDS::Face_const_iterator     Face_const_iterator;


/*{\Mtext Local types are handles, iterators and circulators of the
following kind: |Vertex_const_handle|,
|Vertex_const_iterator|, |Halfedge_const_handle|,
|Halfedge_const_iterator|, |Face_const_handle|, |Face_\-const_\-ite\-rator|.
Additionally the following circulators are defined.}*/

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

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

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

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

typedef PntItFromVertIt<Vertex_const_iterator,Point> 
  Point_const_iterator;

/*{\Mcreation 3}*/

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

PM_const_decorator(const Plane_map& P) 
/*{\Mcreate constructs a plane map decorator exploring |P|.}*/
 : phds(const_cast<HDS*>(&P)) {}

/*{\Moperations 4 4}*/

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

Vertex_const_handle target(Halfedge_const_handle e) const
/*{\Mop returns the target of |e|.}*/
{ return e->vertex(); }

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

bool is_isolated(Vertex_const_handle v) const
/*{\Mop returns |true| iff $A(v) = \emptyset$.}*/
{ return v->is_isolated(); }

Halfedge_const_handle first_out_edge(Vertex_const_handle v) const
/*{\Mop returns one 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_const_handle last_out_edge(Vertex_const_handle v) const
/*{\Mop returns 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_const_handle cyclic_adj_succ(
                        Halfedge_const_handle e) const
/*{\Mop returns the edge after |e| in the cyclic ordered adjacency list of
  |source(e)|.}*/
{ return e->prev()->opposite(); }

Halfedge_const_handle cyclic_adj_pred(
                        Halfedge_const_handle e) const
/*{\Mop returns the edge before |e| in the cyclic ordered adjacency list of
  |source(e)|.}*/
{ return e->opposite()->next(); }


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

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

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

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

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


/*{\Mtext \headerline{Iteration} \setopdims{7.5cm}{0cm}}*/
  
Vertex_const_iterator   vertices_begin() const
{ return phds->vertices_begin(); }
Halfedge_const_iterator halfedges_begin() const
{ return phds->halfedges_begin(); }
Face_const_iterator     faces_begin() const
{ return phds->faces_begin(); }
Vertex_const_iterator   vertices_end() const
{ return phds->vertices_end(); }
Halfedge_const_iterator halfedges_end() const
{ return phds->halfedges_end(); }
Face_const_iterator     faces_end() const
{ return phds->faces_end(); }
Point_const_iterator points_begin() const
{ return Point_const_iterator(vertices_begin()); }
Point_const_iterator points_end() const
{ return Point_const_iterator(vertices_end()); }

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

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

Hole_const_iterator  holes_begin(Face_const_handle f) const
/*{\Mop returns an iterator for all holes in the interior of |f|.