pm_overlayer.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_overlayer.h $
// $Id: PM_overlayer.h 35730 2007-01-15 17:51:17Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_PM_OVERLAYER_H
#define CGAL_PM_OVERLAYER_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Union_find.h>
#include <CGAL/Nef_2/Segment_overlay_traits.h>
#include <CGAL/Nef_2/geninfo.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 13
#include <CGAL/Nef_2/debug.h>

#ifndef CGAL_USE_LEDA
#define LEDA_MEMORY(t) 
#endif

CGAL_BEGIN_NAMESPACE

template <typename PMD, typename I, typename DA>
struct PMO_from_segs {
  typedef PMD Decorator;
  typedef typename Decorator::Vertex_handle   Vertex_handle;
  typedef typename Decorator::Halfedge_handle Halfedge_handle;
  typedef typename Decorator::Point           Point;
  const Decorator& G;
  DA& D; 
  PMO_from_segs(const Decorator& Gi, DA& Di) : 
    G(Gi),D(Di) {}

  Vertex_handle new_vertex(const Point& p)
  { Vertex_handle v = G.new_vertex(p); 
    geninfo<Halfedge_handle>::create(G.info(v));
    return v;
  }

  void link_as_target_and_append(Vertex_handle v, Halfedge_handle e) 
  { G.link_as_target_and_append(v,e); }

  Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v)
  { Halfedge_handle e = 
    G.new_halfedge_pair_at_source(v,Decorator::BEFORE); 
    return e;
  }

  void supporting_segment(Halfedge_handle e, I it) const
  { D.supporting_segment(e,it); }

  void trivial_segment(Vertex_handle v, I it) const
  { D.trivial_segment(v,it); }

  void starting_segment(Vertex_handle v, I it) const
  { D.starting_segment(v,it); }

  void passing_segment(Vertex_handle v, I it) const
  { D.passing_segment(v,it); }

  void ending_segment(Vertex_handle v, I it) const
  { D.ending_segment(v,it); }

  void halfedge_below(Vertex_handle v, Halfedge_handle e) const
  { geninfo<Halfedge_handle>::access(G.info(v)) = e; }

  Halfedge_handle halfedge_below(Vertex_handle v) const
  { return geninfo<Halfedge_handle>::access(G.info(v)); }

  void clear_temporary_vertex_info() const
  { Vertex_handle v;
    for(v = G.vertices_begin(); v!= G.vertices_end(); ++v)
      geninfo<Halfedge_handle>::clear(G.info(v));
  }


}; // PMO_from_segs


template <typename PMD, typename IT, typename INFO>
struct PMO_from_pm {
  typedef PMD Decorator;
  typedef typename PMD::Const_decorator Const_decorator;
  typedef typename Decorator::Vertex_handle Vertex_handle;
  typedef typename Decorator::Halfedge_handle Halfedge_handle;
  typedef typename Decorator::Vertex_const_handle Vertex_const_handle;
  typedef typename Decorator::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Decorator::Point Point;

  const Decorator& G;
  const Const_decorator* pGI[2];
  CGAL::Unique_hash_map<IT,INFO>& M;
  PMO_from_pm(const Decorator& Gi, 
              const Const_decorator* pG0, 
              const Const_decorator* pG1,
              CGAL::Unique_hash_map<IT,INFO>& Mi) : G(Gi),M(Mi) 
 { pGI[0]=pG0; pGI[1]=pG1; }

 Vertex_handle new_vertex(const Point& p) const
 { Vertex_handle v = G.new_vertex(p);
   G.assoc_info(v);
   return v;
 }

 void link_as_target_and_append(Vertex_handle v, Halfedge_handle e) const
 { G.link_as_target_and_append(v,e); }

 Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v) const
 { Halfedge_handle e = 
   G.new_halfedge_pair_at_source(v,Decorator::BEFORE); 
   G.assoc_info(e);
   return e;
 }

 void halfedge_below(Vertex_handle v, Halfedge_handle e) const
 { G.halfedge_below(v) = e; }

 void supporting_segment(Halfedge_handle e, IT it) const
 { INFO& si = M[it];
   CGAL_assertion( si.e != Halfedge_const_handle() );
   G.supp_halfedge(e,si.i) = si.e;
   G.is_forward(e) = true;
 }


 void trivial_segment(Vertex_handle v, IT it) const
 { INFO& si = M[it];
   CGAL_assertion( si.v != Vertex_const_handle() );
   G.supp_vertex(v,si.i) = si.v; 
 }

 void starting_segment(Vertex_handle v, IT it) const
 { INFO& si = M[it];
   G.supp_vertex(v,si.i) = pGI[si.i]->source(si.e);
 }

 void ending_segment(Vertex_handle v, IT it) const
 { INFO& si = M[it];
   G.supp_vertex(v,si.i) = pGI[si.i]->target(si.e);
 }

 void passing_segment(Vertex_handle v, IT it) const
 { INFO& si = M[it];
   G.supp_halfedge(v,si.i) = si.e; 
 }

 Halfedge_handle halfedge_below(Vertex_handle v) const
 { return G.halfedge_below(v); }


}; // PMO_from_pm

/*{\Moptions print_title=yes }*/ 
/*{\Msubst 
PM_decorator_#PMD
Geometry_#GEO
}*/
/*{\Manpage {PM_overlayer}{PMD,GEO}{Plane Map Overlay}{O}}*/
template <typename PM_decorator_, typename Geometry_>
class PM_overlayer : public PM_decorator_ {
  typedef PM_decorator_ Base;
  typedef PM_overlayer<PM_decorator_,Geometry_>  Self;
  const Geometry_& K; // geometry reference

/*{\Mdefinition An instance |\Mvar| of data type |\Mname| is a
decorator object offering plane map overlay calculation. Overlay is
either calculated from two plane maps or from a set of segments.  The
result is stored in a plane map |P| that carries the geometry and the
topology of the overlay.

The two template parameters allow to adapt the overlay calculation
to different scenarios.  The template parameter |PM_decorator_| has to
be a model conforming to our plane map decorator concept
|PMDecorator|.  The concept describes the interface how the
topological information stored in |P| can be extracted.  The geometry
|Geometry_| has to be a model conforming to the concept 
|OverlayerGeometry_2|.

The overlay of a set of segments $S$ is stored in a plane map $P =
(V,E,F)$. Vertices are either the endpoints of segments (trivial
segments are allowed) or the result of a non-degenerate internal
intersection of two segments. Between two vertices there is an edge if
there is a segment that supports the straight line embedding of $e$ and
if there is no vertex in the relative interior of the embedding of $e$.

The faces refer to the maximal connected open point sets of the
planar subdivision implied by the embedding of the vertices and edges.
Faces are bounded by possibly several face cycles\footnote{For the
definition of plane maps and their concepts see the manual page of
|PMConstDecorator|.} including isolated vertices. The overlay process
in the method |create| creates the objects, the topology of the result
and allows to link the plane map objects to input segments by means of
a data accessor. The method starts from zero- and one-dimensional
geometric objects in $S$ and produces a plane map |P| where each point
of the plane can be assigned to an object (vertex, edge, or face) of
|P|.

The overlay of two plane maps $P_i = (V_i, E_i, F_i)$ has the
additional aspect that we already start from two planar subdivisions.
We use the index $i=0,1$ defining the reference to $P_i$, unindexed
variables refer to the resulting plane map $P$.  The $1$-skeleta of
the two maps subdivide the edges and faces of the complementary
structure into smaller units. This means vertices and edges of $P_i$
can split edges of $P_{1-i}$ and face cycles of $P_i$ subdivide faces
of $P_{1-i}$. The 1-skeleton $P'$ of $P$ is defined by the overlay of
the embedding of the 1-skeleta of $P_0$ and $P_1$ (Take a trivial
segment for each vertex and a segment for each edge and use the
overlay definition of a set of segments above). The faces of $P$ refer
to the maximal connected open point sets of the planar subdivision
implied by the embedding of $P'$. Each object from the output tuple
$(V,E,F)$ has a \emph{supporting} object $u_i$ in each of the two
input structures.  Imagine the two maps to be transparencies, which we
stack. Then each point of the plane is covered by an object from each
of the input structures.  This support relation from the input
structures to the output structure defines an information flow. Each
supporting object $u_i$ of $u$ $(i=0,1)$ carries an attribute
$|mark|(u_i)$. After the subdivision operation this attribute
is associated to the output object $u$ by $|mark|(u,i)$.}*/

/*{\Mgeneralization PM_decorator_}*/

public:
/*{\Mtypes 8}*/
  typedef PM_decorator_                 Decorator;
  /*{\Mtypemember the plane map decorator |PM_decorator_|.}*/
  typedef typename Decorator::Plane_map Plane_map;
  /*{\Mtypemember the plane map type decorated by |PM_decorator_|.}*/
  typedef Geometry_                     Geometry;
  /*{\Mtypemember the geometry kernel |Geometry_|.}*/
  typedef typename Geometry::Point_2    Point;
  /*{\Mtypemember the point type of the geometric kernel, 
     \precond |Point| equals |Plane_map::Point|.}*/
  typedef typename Geometry::Segment_2  Segment;
  /*{\Mtypemember the segment type of the geometric kernel.}*/
  typedef typename Decorator::Mark      Mark;
  /*{\Mtypemember the attribute type of plane map objects.}*/


  typedef typename Decorator::Base Const_decorator;
  typedef typename Decorator::Halfedge_handle Halfedge_handle;
  typedef typename Decorator::Vertex_handle Vertex_handle;
  typedef typename Decorator::Face_handle Face_handle;
  typedef typename Decorator::Vertex_iterator Vertex_iterator;
  typedef typename Decorator::Halfedge_iterator Halfedge_iterator;
  typedef typename Decorator::Face_iterator Face_iterator;
  typedef typename Decorator::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Decorator::Vertex_const_handle Vertex_const_handle;
  typedef typename Decorator::Face_const_handle Face_const_handle;
  typedef typename Decorator::Halfedge_const_iterator Halfedge_const_iterator;
  typedef typename Decorator::Vertex_const_iterator Vertex_const_iterator;
  typedef typename Decorator::Face_const_iterator Face_const_iterator;
  typedef typename Decorator::Halfedge_around_vertex_circulator 
    Halfedge_around_vertex_circulator;
  typedef typename Decorator::Halfedge_around_face_circulator 
    Halfedge_around_face_circulator;
  typedef typename Decorator::Hole_iterator Hole_iterator;
  typedef typename Decorator::Isolated_vertex_iterator Isolated_vertex_iterator;

#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
  using Base::clear;
  using Base::vertices_begin;
  using Base::vertices_end;
  using Base::halfedges_begin;
  using Base::halfedges_end;
  using Base::faces_begin;
  using Base::faces_end;
  using Base::number_of_vertices;
  using Base::number_of_halfedges;
  using Base::number_of_faces;
  using Base::new_vertex;
  using Base::new_face;
#endif