sm_overlayer.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 1,638 行 · 第 1/4 页

// 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.
//
// $Source: /CVSROOT/CGAL/Packages/Nef_S2/include/CGAL/Nef_S2/SM_overlayer.h,v $
// $Revision: 1.27.2.1 $ $Date: 2004/12/08 20:10:11 $
// $Name:  $
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_SM_OVERLAYER_H
#define CGAL_SM_OVERLAYER_H

#include <CGAL/basic.h>
#include <CGAL/Union_find.h>
#include <CGAL/Nef_2/Segment_overlay_traits.h>
#include <CGAL/Nef_2/geninfo.h>
#include <CGAL/Nef_S2/Sphere_geometry.h>
#include <CGAL/Nef_S2/SM_decorator.h>
#include <CGAL/Nef_S2/SM_const_decorator.h>
#include <CGAL/Nef_S2/SM_point_locator.h>
#include <CGAL/Nef_S2/SM_io_parser.h>
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 131
#include <CGAL/Nef_2/debug.h>

#ifndef CGAL_USE_LEDA
#define LEDA_MEMORY(t) 
#endif

CGAL_BEGIN_NAMESPACE

template <typename Decorator_, typename I>
struct SMO_from_segs {
  typedef Decorator_ SM_decorator;
  typedef typename SM_decorator::SVertex_handle     Vertex_handle;
  typedef typename SM_decorator::SHalfedge_handle   Halfedge_handle;
  typedef typename SM_decorator::Sphere_point       Point;
  typedef typename SM_decorator::Sphere_segment     Segment;
  typedef CGAL::Unique_hash_map<I,bool>             Iterator_map;
  SM_decorator G;
  const Iterator_map& M;
  SMO_from_segs(SM_decorator Gi, const Iterator_map& Mi) : G(Gi),M(Mi) {}

  Vertex_handle new_vertex(const Point& p)
  { Vertex_handle v = G.new_svertex(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_shalfedge_pair_at_source(v,SM_decorator::BEFORE); 
    return e;
  }

  void supporting_segment(Halfedge_handle e, I it) const
  { if ( M[it] ) G.mark(e) = true; }

  void trivial_segment(Vertex_handle v, I it) const
  { if ( M[it] ) G.mark(v) = true; }

  void starting_segment(Vertex_handle v, I it) const
  { if ( M[it] ) G.mark(v) = true; }

  void passing_segment(Vertex_handle v, I it) const
  { if ( M[it] ) G.mark(v) = true; }

  void ending_segment(Vertex_handle v, I it) const
  { if ( M[it] ) G.mark(v) = true; }

  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 assert_equal_marks(Vertex_handle v1, Vertex_handle v2) const 
  { CGAL_assertion(G.mark(v1)==G.mark(v2)); }

  void discard_info(Vertex_handle v) const 
  { geninfo<Halfedge_handle>::clear(G.info(v)); }

  void assert_equal_marks(Halfedge_handle e1, Halfedge_handle e2) const
  { CGAL_assertion(G.mark(e1)==G.mark(e2)); }

  void discard_info(Halfedge_handle e) const {}

  void clear_temporary_vertex_info() const
  { Vertex_handle v;
    CGAL_forall_svertices(v,G)
      geninfo<Halfedge_handle>::clear(G.info(v));
  }


}; // SMO_from_segs


template <typename SM_overlayer, typename IT, typename INFO>
struct SMO_from_sm {
  typedef typename SM_overlayer::SM_const_decorator      SM_const_decorator;
  typedef typename SM_overlayer::SVertex_handle          Vertex_handle;
  typedef typename SM_overlayer::SHalfedge_handle        Halfedge_handle;
  typedef typename SM_overlayer::Sphere_point            Point;
  typedef typename SM_overlayer::Sphere_segment          Segment;

  SM_overlayer G;
  SM_const_decorator* pGI;
  CGAL::Unique_hash_map<IT,INFO>& M;
  SMO_from_sm(SM_overlayer Gi, 
              SM_const_decorator* pGIi, 
              CGAL::Unique_hash_map<IT,INFO>& Mi) : 
    G(Gi), pGI(pGIi), M(Mi) {}

Vertex_handle new_vertex(const Point& p)
{ Vertex_handle v = G.new_svertex(p);
  G.assoc_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_shalfedge_pair_at_source(v,SM_overlayer::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];
  G.is_forward(e) = true;
  if ( si._from == -1 )  return; // equatorial segment
  G.supp_object(e,si._from) = si._o;
  CGAL_NEF_TRACEN("   supporting segment "<<si._from<<" "<<*it);
}

void trivial_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  CGAL_assertion( si._o != NULL );
  G.supp_object(v,si._from) = si._o; 
  CGAL_NEF_TRACEN("trivial_segment " << si._from << " "<< v->point()); 
}

void starting_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  if ( si._from == -1 ) return;
  G.supp_object(v,si._from) = si._o;
  CGAL_NEF_TRACEN("starting_segment " << si._from << " "<< v->point()); 
}

void ending_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  if ( si._from == -1 ) return;
  G.supp_object(v,si._from) = si._o;
  CGAL_NEF_TRACEN("ending_segment " << si._from << " "<< v->point()); 
}

void passing_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  if ( si._from == -1 ) return;
  G.supp_object(v,si._from) = si._o; 
  CGAL_NEF_TRACEN("passing_segment " << si._from << " "<< v->point()); 
}

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

void assert_equal_marks(Vertex_handle v1, Vertex_handle v2) const 
{ CGAL_NEF_TRACEV(G.mark(v1,0));CGAL_NEF_TRACEV(G.mark(v1,1));
  CGAL_NEF_TRACEV(G.mark(v2,0));CGAL_NEF_TRACEV(G.mark(v2,1));
  CGAL_assertion(G.mark(v1,0)==G.mark(v2,0)&&
		 G.mark(v1,1)==G.mark(v2,1)); }
void discard_info(Vertex_handle v) const 
{ G.discard_info(v); }

void assert_equal_marks(Halfedge_handle e1, Halfedge_handle e2) const
{ CGAL_assertion(G.mark(e1,0)==G.mark(e2,0) && 
		 G.mark(e1,1)==G.mark(e2,1)); }

void discard_info(Halfedge_handle e) const 
{ G.discard_info(e); }

}; // SMO_from_sm

template <typename SM_decorator, typename ITERATOR>
class SMO_decorator { 
public:
  typedef SM_decorator Graph;
  typedef typename SM_decorator::SVertex_handle  SVertex_handle;
  typedef typename SM_decorator::SHalfedge_handle    SHalfedge_handle;
  typedef typename SM_decorator::Sphere_point    Point_2;
  typedef typename SM_decorator::Sphere_segment  Segment_2;
  SM_decorator G;

SMO_decorator(Graph Gi) : G(Gi) {}

SVertex_handle new_vertex(const Point_2& p)
{ return G.snew_vertex(p); }

void link_as_target_and_append(SVertex_handle v, SHalfedge_handle e)
{ G.link_as_target_and_append(v,e); }

SHalfedge_handle new_halfedge_pair_at_source(SVertex_handle v)
{ return G.new_shalfedge_pair_at_source(v,Graph::BEFORE); }

void supporting_segment(SHalfedge_handle e, ITERATOR it) {}
void halfedge_below(SVertex_handle v, SHalfedge_handle e) {}
void trivial_segment(SVertex_handle v, ITERATOR it) {}
void starting_segment(SVertex_handle v, ITERATOR it) {}
void passing_segment(SVertex_handle v, ITERATOR it) {}
void ending_segment(SVertex_handle v, ITERATOR it) {}


}; // SMO_decorator

// ============================================================================
// ============================================================================

/*{\Manpage {SM_overlayer}{SM_decorator}{Overlay in the sphere}{O}}*/

template <typename SM_decorator_>
class SM_overlayer : public SM_decorator_ {
public:

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

  The template parameter provides the underlying topological interface
  to sphere maps. The template parameter |SM_decorator| has to be a model
  conforming to our map decorator concept |SM_decorator|.  The concept
  also describes the interface how the topological information stored in
  |M| can be extracted or extended.

  The overlay of a set of sphere segments $S$ is stored in a sphere map
  $M = (V,E,L,F)$. Vertices are either the endpoints of segments (trivial
  segments are allowed) or the result of the internal intersection of
  two segments. Between two vertices there's an edge if there's a
  segment that supports the spherical embedding of $e$ and if there's no
  vertex in the relative interior of the embedding of $e$.

  The faces refer to the maximal connected open point sets of the
  spherical subdivision implied by the embedding of the vertices and
  edges.  SFaces are bounded by possibly several face cycles\footnote{For
  the definition of sphere maps and their concepts see the manual page
  of |SM_decorator|.} including isolated vertices. The overlay process
  in the method |create_from_segments| creates the objects and the
  topology of the result. The method starts from zero- and
  one-dimensional geometric objects in $S$ and produces a spherical
  structure where each point of the sphere can be assigned to an object
  (vertex, edge, loop, or face) of |M|.

  The overlay of two sphere maps $M_i = (V_i, E_i, L_i, F_i)$ has the
  additional aspect that we already start from two spherical
  subdivisions.  We use the index $i=0,1$ defining the reference to
  $M_i$, unindexed variables refer to the resulting sphere map $M$.  The
  $1$-skeleta of the two maps subdivide the edges, loops, and faces of
  the complementary structure into smaller units. This means vertices,
  edges, and loops of $M_i$ can split edges and loops of $M_{1-i}$ and
  face cycles of $M_i$ subdivide faces of $M_{1-i}$. The 1-skeleton $G$
  of $M$ is defined by the overlay of the embedding of the 1-skeleta of
  $M_0$ and $M_1$ (Take a trivial segment for each vertex and a segment
  for each edge, and a circle for a loop, and use the overlay definition
  of a set of segments and loops above). The faces of $M$ refer to the
  maximal connected open point sets of the spherical subdivision implied
  by the embedding of $G$. 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 transparent balls, where one
  contains the other. Then each point of the sphere is covered by an
  object from each of the input structures.  This support relationship
  from the input structures to the output structure defines an
  information flow. Each supporting object $u_i$ of $u$ $(i=0,1)$
  carries an associated information $|mark|(u_i)$. After the subdivision
  operation this information is attributed to the output object $u$ by
  $|mark|(u,i)$.}*/

  typedef SM_decorator_                         SM_decorator;
  typedef typename SM_decorator::Map            Map;
  typedef SM_decorator                          Base;
  typedef SM_overlayer<SM_decorator_>           Self;
  typedef CGAL::SM_const_decorator<Map>         SM_const_decorator;
  typedef SM_point_locator<SM_const_decorator>  SM_point_locator;

  //  typedef typename SM_const_decorator::Constructor_parameter 
  //                                       Constructor_const_parameter;
  typedef typename SM_const_decorator::SVertex_const_handle SVertex_const_handle;
  typedef typename SM_const_decorator::SHalfedge_const_handle SHalfedge_const_handle;
  typedef typename SM_const_decorator::SHalfloop_const_handle SHalfloop_const_handle;
  typedef typename SM_const_decorator::SFace_const_handle SFace_const_handle;
  typedef typename SM_const_decorator::SVertex_const_iterator SVertex_const_iterator;
  typedef typename SM_const_decorator::SHalfedge_const_iterator SHalfedge_const_iterator;
  typedef typename SM_const_decorator::SFace_const_iterator SFace_const_iterator;

  //  typedef typename Base::Constructor_parameter Constructor_parameter;
  typedef typename Base::SVertex_handle SVertex_handle;
  typedef typename Base::SHalfedge_handle SHalfedge_handle;
  typedef typename Base::SHalfloop_handle SHalfloop_handle;
  typedef typename Base::SFace_handle SFace_handle;
  typedef typename Base::SVertex_iterator SVertex_iterator;
  typedef typename Base::SHalfedge_iterator SHalfedge_iterator;
  typedef typename Base::SFace_iterator SFace_iterator;
  typedef typename Base::Object_handle Object_handle;

  typedef typename Base::SHalfedge_around_svertex_circulator 
                         SHalfedge_around_svertex_circulator;
  typedef typename Base::SHalfedge_around_sface_circulator 
                         SHalfedge_around_sface_circulator;
  typedef typename Base::SFace_cycle_iterator 
                         SFace_cycle_iterator;

  typedef std::pair<SHalfedge_handle,SHalfedge_handle> SHalfedge_pair;

  /*{\Mtypes 3}*/

  typedef typename Base::Sphere_kernel           Sphere_kernel;
  /*{\Mtypemember the geometry kernel.}*/
  typedef typename Sphere_kernel::Sphere_point   Sphere_point;
  /*{\Mtypemember the point type of the sphere geometry.}*/
  typedef typename Sphere_kernel::Sphere_segment Sphere_segment;
  /*{\Mtypemember the segment type of the sphere geometry.}*/
  typedef typename Sphere_kernel::Sphere_circle  Sphere_circle;
  /*{\Mtypemember the circle type of the sphere geometry.}*/
  typedef typename Base::Mark Mark;
  /*{\Mtypemember the mark of sphere map objects.}*/

  typedef typename Base::GenPtr GenPtr;

  /*{\Mgeneralization SM_decorator}*/

protected:
  SM_const_decorator PI[2];
  const Sphere_kernel& K;

public:

  // ---------------------------------------------------------------

  struct Seg_info { // to transport information from input to output
    Object_handle _o; int _from;

    Seg_info() : _o(), _from(-1) {}
    Seg_info(SVertex_const_handle v, int i) 
    { _o=Object_handle(v); _from=i; }
    Seg_info(SHalfedge_const_handle e, int i) 
    { _o=Object_handle(e); _from=i; }
    Seg_info(SHalfloop_const_handle l, int i) 
    { _o=Object_handle(l); _from=i; }
    Seg_info(const Seg_info& si) 
    { _o=si._o; _from=si._from; }
    Seg_info& operator=(const Seg_info& si) 
    { _o=si._o; _from=si._from; return *this; }
    LEDA_MEMORY(Seg_info)
  }; // Seg_info

  typedef std::list<Sphere_segment>            Seg_list;
  typedef typename Seg_list::iterator          Seg_iterator;
  typedef std::pair<Seg_iterator,Seg_iterator> Seg_it_pair;
  typedef std::pair<Sphere_segment,Sphere_segment> Seg_pair;
  typedef CGAL::Unique_hash_map<Seg_iterator,Seg_info> Seg_map;

  // ---------------------------------------------------------------

  struct vertex_info {
    Mark m[2];
    Object_handle o_supp[2];
    SHalfedge_handle e_below;
    vertex_info() 
    { o_supp[0]=o_supp[1]=Object_handle(); }
    LEDA_MEMORY(vertex_info)
  }; // vertex_info

  void assoc_info(SVertex_handle v) const
  { geninfo<vertex_info>::create(info(v)); }

  void discard_info(SVertex_handle v) const
  { geninfo<vertex_info>::clear(info(v)); }

  vertex_info& ginfo(SVertex_handle v) const
  { return geninfo<vertex_info>::access(info(v)); }

  Mark& mark(SVertex_handle v, int i) const
  { return ginfo(v).m[i]; }

  Object_handle& supp_object(SVertex_handle v, int i) const
  { return ginfo(v).o_supp[i]; }

  SHalfedge_handle& halfedge_below(SVertex_handle v) const
  { return ginfo(v).e_below; }

  // ---------------------------------------------------------------