sm_triangulator.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_triangulator.h $
// $Id: SM_triangulator.h 38160 2007-04-17 07:29:00Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>

#ifndef CGAL_SM_TRIANGULATOR_H
#define CGAL_SM_TRIANGULATOR_H

#include <CGAL/basic.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_2/Segment_overlay_traits.h>
#include <CGAL/Nef_2/geninfo.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_S2/SM_constrained_triang_traits.h>

#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 137
#include <CGAL/Nef_2/debug.h>

#define CGAL_USING(t) typedef typename Base::t t
#ifndef CGAL_USE_LEDA
#define LEDA_MEMORY(t) 
#endif
CGAL_BEGIN_NAMESPACE

template <typename Decorator_, typename IT, typename INFO>
struct SM_subdivision {
  typedef Decorator_ Triangulator;
  typedef typename Decorator_::SVertex_handle Vertex_handle;
  typedef typename Decorator_::SHalfedge_handle   Halfedge_handle;
  typedef typename Decorator_::Sphere_point   Point;
  typedef typename Decorator_::Sphere_segment Segment;
  Triangulator T;
  CGAL::Unique_hash_map<IT,INFO>& M;
  /* M stores the object that supports the segment that
     is input object of the sweep */

  SM_subdivision(Triangulator Ti, 
                 CGAL::Unique_hash_map<IT,INFO>& Mi) : T(Ti), M(Mi) {}

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

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

Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v)
{ Halfedge_handle e = 
  T.new_shalfedge_pair_at_source(v,Decorator_::BEFORE); 
  T.assoc_info(e);
  return e;
}

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

/* the following operation associates segment support with
   halfedges, we only update if non-NULL; this prevents 
   artificial sphere subdivision segments that have NULL 
   support to overwrite non-NULL support */

void supporting_segment(Halfedge_handle e, IT it) const
{ T.is_forward(e) = true; 
  if ( M[it] != NULL ) T.support(e) = M[it]; }

/* the following operation associate segment support with
   vertices, we only update if non-NULL; this prevents 
   artificial segments that have NULL support to overwrite
   non-NULL support */

void trivial_segment(Vertex_handle v, IT it) const
{ if ( M[it] != NULL ) T.support(v) = M[it]; }

void starting_segment(Vertex_handle v, IT it) const
{ if ( M[it] != NULL ) T.support(v) = M[it]; }

void ending_segment(Vertex_handle v, IT it) const
{ if ( M[it] != NULL ) T.support(v) = M[it]; }

void passing_segment(Vertex_handle v, IT it) const
{ if ( M[it] != NULL ) T.support(v) = M[it]; }


}; // SM_subdivision



/*{\Manpage {SM_triangulator}{Decorator_}{Overlay in the sphere}{O}}*/

template <typename Decorator_>
class SM_triangulator : public Decorator_ {
public:
  /*{\Mdefinition An instance |\Mvar| of data type |\Mname| is a
  decorator object offering sphere map triangulation calculation.}*/

  typedef Decorator_                            Base;
  typedef typename Decorator_::Sphere_map       Sphere_map;
  typedef CGAL::SM_const_decorator<Sphere_map>  SM_const_decorator;
  typedef SM_const_decorator                    Explorer;
  typedef Decorator_                            Decorator;
  typedef SM_triangulator<Decorator_>           Self;
  typedef CGAL::SM_point_locator<SM_const_decorator>  SM_point_locator;

  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::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 std::pair<SHalfedge_handle,SHalfedge_handle> SHalfedge_pair;

  /*{\Mtypes 3}*/

  typedef typename Base::Sphere_kernel Sphere_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 Sphere_kernel::Sphere_triangle Sphere_triangle;
  /*{\Mtypemember the triangle type of the sphere geometry.}*/

  typedef typename Decorator::Mark        Mark;
  /*{\Mtypemember the mark of sphere map objects.}*/

  /*{\Mgeneralization Decorator_}*/

protected:
  const Explorer* E_;
  const Sphere_kernel& K;

public:

  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,Object_handle> Seg_map;

  // vertex_info stores the origin of vertices
  struct vertex_info {
    Object_handle         o_;
    SHalfedge_handle       e_;
    vertex_info() : o_(),e_() {}
    LEDA_MEMORY(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)); }

  Object_handle& support(SVertex_handle v) const
  { return ginfo(v).o_; }

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

  // edge_info stores the origin of edges
  struct edge_info {
    Mark m_left_; Object_handle o_; bool forw_;

    edge_info() { m_left_=Mark(); o_=Object_handle(); forw_=false; }
    LEDA_MEMORY(edge_info)
  };

  void assoc_info(SHalfedge_handle e)  const
  { geninfo<edge_info>::create(info(e)); 
    geninfo<edge_info>::create(info(e->twin())); }

  void discard_info(SHalfedge_handle e)  const
  { geninfo<edge_info>::clear(info(e)); 
    geninfo<edge_info>::clear(info(e->twin())); }

  edge_info& ginfo(SHalfedge_handle e)  const
  { return geninfo<edge_info>::access(info(e)); }

  Object_handle& support(SHalfedge_handle e) const
  // uedge information we store in the smaller one 
  { if (&*e < &*(e->twin())) return ginfo(e).o_; 
    else                   return ginfo(e->twin()).o_; }

  Mark& incident_mark(SHalfedge_handle e)  const
  // biedge information we store in the edge
  { return ginfo(e).m_left_; }

  const edge_info& ginfo(SHalfedge_const_handle e)  const
  { return geninfo<edge_info>::const_access(info(e)); }
  const Mark& incident_mark(SHalfedge_const_handle e)  const
  { return ginfo(e).m_left_; }

  bool& is_forward(SHalfedge_handle e) const
  // biedge information we store in the edge
  { return ginfo(e).forw_; }

  void assert_equal_marks(SVertex_handle v1, SVertex_handle v2) const 
  { CGAL_assertion(v1->mark()==v2->mark()); }

  void assert_equal_marks(SHalfedge_handle e1, SHalfedge_handle e2) const
  { CGAL_assertion(e1->mark()==e2->mark()); }

  Sphere_segment segment(const Explorer* , 
                         SHalfedge_const_handle e) const
  { return Sphere_segment(
	    e->source()->point(),e->twin()->source()->point(),e->circle()); }

  Sphere_segment trivial_segment(const Explorer* , 
                                 SVertex_const_handle v) const
  { Sphere_point p = v->point(); 
    return Sphere_segment(p,p); }

  Seg_pair two_segments(const Explorer* , 
                        SHalfedge_const_handle e) const
  // we know that source(e)==target(e)
  { return e->circle().split_at(e->source()->point()); }

  Seg_pair two_segments(const Explorer* , 
                        SHalfloop_const_handle l) const
  { return l->circle().split_at_xy_plane(); }

  /*{\Mcreation 6}*/
  SM_triangulator(Sphere_map* M, const Explorer* E,
		  const Sphere_kernel& G = Sphere_kernel()) : Base(M), E_(E), K(G) {}
  /*{\Mcreate |\Mvar| is a triangulator object for the map |M|,
     stores the triangulation in |MT|.}*/

  /*{\Moperations 1.1 1}*/

  void triangulate();
  /*{\Mop produces a triangulated sphere map.}*/

  void triangulate_per_hemisphere(SVertex_iterator start, SVertex_iterator end);

  template <typename Iterator, typename T>
  void partition_to_halfsphere(Iterator start, Iterator end,
    Seg_list& L, CGAL::Unique_hash_map<Iterator,T>& M, int pos) const;

  void merge_halfsphere_maps(SVertex_handle v1, SVertex_handle v2);
  void merge_nodes(SHalfedge_handle e1, SHalfedge_handle e2);
  void complete_support(SVertex_iterator v_start, SVertex_iterator v_end, 
			Mark mohs) const;

  void correct_triangle_at(SVertex_handle v)
  { CGAL_NEF_TRACEN("correct_triangle_at "<<PH(v));
    if ( !has_outdeg_two(v) ) return;
    SHalfedge_handle e = first_out_edge(v);
    CGAL_assertion(e->snext()->snext()->snext()==e);
    flip_diagonal(e->snext());
  }

  void dump(std::ostream& os = std::cerr) const
  { SM_io_parser<Explorer>::dump(E_,os);
    SM_io_parser<Base>::dump(*this,os); }

  Sphere_triangle incident_triangle(SHalfedge_handle e) const
  { SHalfedge_handle en(e->snext()), enn(en->snext());
    CGAL_assertion(enn->snext()==e);
    return Sphere_triangle(e->source()->point(),
			   en->source()->point(),
			   enn->source()->point(),
			   e->circle(),
			   en->circle(),
			   enn->circle());
  }

  Sphere_triangle incident_triangle(SHalfedge_const_handle e) const
  { SHalfedge_const_handle en(e->snext()), enn(en->snext());
    CGAL_assertion(enn->snext()==e);
    return Sphere_triangle(e->source()->point(),
			   en->source()->point(),
			   enn->source()->point(),
			   e->circle(),
			   en->circle(),
			   enn->circle());
  }

  void discard_info()
  {
    SVertex_iterator v;
    SHalfedge_iterator e;
    CGAL_forall_svertices(v,*this) discard_info(v);
    CGAL_forall_shalfedges(e,*this) discard_info(e);
  }


}; // SM_triangulator<Decorator_>


template <typename Decorator_>
void SM_triangulator<Decorator_>::triangulate()
{ CGAL_NEF_TRACEN("triangulate");
  // first create sphere segments from isoverts, edges, loops
  Seg_list L;
  Seg_map From;
  SVertex_const_iterator v;
  CGAL_forall_svertices(v,*E_) {
    if ( !E_->is_isolated(v) ) continue;
    L.push_back(trivial_segment(E_,v));