sm_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_S2/include/CGAL/Nef_S2/SM_overlayer.h $
// $Id: SM_overlayer.h 39747 2007-08-07 20:10:54Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>
//                 Peter Hachenberger <[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>
#include <CGAL/Nef_3/ID_support_handler.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] ) e->mark() = true; }

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

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

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

  void ending_segment(Vertex_handle v, I it) const
  { if ( M[it] ) v->mark() = 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(v1->mark()==v2->mark()); }

  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(e1->mark()==e2->mark()); }

  void discard_info(Halfedge_handle ) 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;
  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), M(Mi) {}

Vertex_handle new_vertex(const Point& p)
{ CGAL_NEF_TRACEN(" new vertex " << 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)
  { CGAL_NEF_TRACEN(" link as target and append " 
		    << e->source()->point() << "->"
		    << v->point());
		    G.link_as_target_and_append(v,e); }

Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v)
{ CGAL_NEF_TRACEN(" new halfedge pair at source " << v->point());
  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 );
  typename SM_const_decorator::SHalfedge_const_handle se;
  typename SM_const_decorator::SHalfloop_const_handle sl;
  typename SM_const_decorator::SVertex_const_handle sv;
  if(CGAL::assign(se, si._o)) {
    if(se->source()->point() != v->point())
      se = se->twin();
    if(se->source()->point() != v->point())
      G.supp_object(v,si._from) = si._o;
    else
      G.supp_object(v,si._from) = Object_handle(se->source());
  } else if(CGAL::assign(sl, si._o)) {
    G.supp_object(v,si._from) = si._o;
  } else if(CGAL::assign(sv, si._o)) {
    CGAL_assertion(sv->point() == v->point());
    G.supp_object(v,si._from) = si._o;
  } else
    CGAL_assertion_msg(false, "wrong handle");
  
  CGAL_NEF_TRACEN("trivial_segment " << si._from << ":" << v->point()); 
  //  debug();
}

void starting_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  if ( si._from == -1 ) return;
  typename SM_const_decorator::SHalfedge_const_handle se;
  typename SM_const_decorator::SHalfloop_const_handle sl;
  if(CGAL::assign(se, si._o)) {
    if(se->source()->point() != v->point()) {
      se = se->twin();
      if(se->source()->point() != v->point()) {
	G.supp_object(v,si._from) = si._o;
	return;
      }
    }
    G.supp_object(v,si._from) = Object_handle(se->source());
    CGAL_NEF_TRACEN("starting_segment " << si._from << ":"<< 
		    v->point() << " " << se->source()->point()); 
  } else if(CGAL::assign(sl, si._o)) {
    G.supp_object(v,si._from) = si._o;
  } else
    CGAL_assertion_msg(false, "wrong object");
  //  debug();
}

void ending_segment(Vertex_handle v, IT it) const
{ INFO& si = M[it];
  if ( si._from == -1 ) return;
  typename SM_const_decorator::SHalfedge_const_handle se;
  typename SM_const_decorator::SHalfloop_const_handle sl;
  if(CGAL::assign(se, si._o)) {
    if(se->source()->point() != v->point()) {
      se = se->twin();
      if(se->source()->point() != v->point()) {
	G.supp_object(v,si._from) = si._o;
	return;
      }
    }
    G.supp_object(v,si._from) = Object_handle(se->source());
    CGAL_NEF_TRACEN("ending_segment " << si._from << ":"<< 
		    v->point() << ":" << 
		    se->source()->point() << "->" << 
		    se->twin()->source()->point()); 
  } else if(CGAL::assign(sl, si._o)) {
    G.supp_object(v,si._from) = si._o;
  } else
    CGAL_assertion_msg(false, "wrong object");
  //  debug();
}

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()); 
  //  debug();
}

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); }

void debug() const {
  typename SM_overlayer::SVertex_iterator svii;
  CGAL_forall_svertices(svii, G) {
    typename SM_overlayer::SVertex_const_handle vs;
    typename SM_overlayer::SHalfedge_const_handle es;
    if(CGAL::assign(vs, G.supp_object(svii,0)))
      std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
    else if(CGAL::assign(es, G.supp_object(svii,0)))
      std::cerr << svii->point() << " supported by sedge" << std::endl;
    else
      std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
    if(CGAL::assign(vs, G.supp_object(svii,1)))
      std::cerr << svii->point() << " supported by svertex" << vs->point() << std::endl;
    else if(CGAL::assign(es, G.supp_object(svii,1)))
      std::cerr << svii->point() << " supported by sedge" << std::endl;
    else
      std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
  }
}

}; // 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 CGAL::SM_point_locator<SM_const_decorator>  SM_point_locator;

  //  typedef typename SM_const_decorator::Constructor_parameter