snc_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_3/include/CGAL/Nef_3/SNC_SM_overlayer.h $
// $Id: SNC_SM_overlayer.h 39746 2007-08-07 20:10:09Z hachenb $
// 
//
// Author(s)     : Michael Seel <[e-mail]>
//                 Peter Hachenberger <[e-mail]>

#ifndef CGAL_SNC_SM_OVERLAYER_H
#define CGAL_SNC_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_overlayer.h>
#include <CGAL/Nef_3/SNC_structure.h>
#include <CGAL/Nef_3/SNC_indexed_items.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

/*{\Manpage {SNC_SM_overlayer}{Refs_}{Overlay in the sphere}{O}}*/

template <typename Items, typename SM_decorator_>
class SNC_SM_overlayer : public SM_overlayer<SM_decorator_> {
public:

  typedef SM_decorator_                          SM_decorator;
  typedef typename SM_decorator::Map             Map;
  typedef SM_overlayer<SM_decorator_>            Base;
  typedef SNC_SM_overlayer<Items, SM_decorator_> Self;

  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::SHalfedge_around_sface_circulator 
                         SHalfedge_around_sface_circulator;

  typedef typename Base::Sphere_kernel           Sphere_kernel;

  typedef typename Map::Infi_box Infi_box;

 public:
  SNC_SM_overlayer(Map* M, 
		   const Sphere_kernel& G = Sphere_kernel()) 
    : Base(M,G) {}

  template <typename Association>
  void simplify(Association&) {
    CGAL_NEF_TRACEN("simplifying"); 
    
    typedef typename CGAL::Union_find<SFace_handle>::handle Union_find_handle;
    CGAL::Unique_hash_map< SFace_handle, Union_find_handle> Pitem(NULL);
    CGAL::Unique_hash_map< SVertex_handle, Union_find_handle> Vitem(NULL);
    CGAL::Union_find< SFace_handle> UF;
    
    SFace_iterator f;
    CGAL_forall_sfaces(f,*this) {
      Pitem[f] = UF.make_set(f);
      clear_face_cycle_entries(f);
    }
    
    if ( this->has_shalfloop() ) {
      SHalfloop_handle l = this->shalfloop();
      SFace_handle f = *(UF.find(Pitem[l->incident_sface()]));
      link_as_loop(l,f);
      f = *(UF.find(Pitem[l->twin()->incident_sface()]));
      link_as_loop(l->twin(),f);
    }
    
    SHalfedge_iterator e, en;
    for(e = this->shalfedges_begin(); e != this->shalfedges_end(); e = en) { 
      en = e; ++en; if ( en==e->twin() ) ++en;
      CGAL_NEF_TRACEN("can simplify ? " << PH(e));
      if(!Infi_box::is_sedge_on_infibox(e)) {
	CGAL_NEF_TRACEN(e->mark() << " " << 
			e->incident_sface()->mark() << " " << 
			e->twin()->incident_sface()->mark());
	if (( e->mark() == e->incident_sface()->mark() && 
	      e->mark() == e->twin()->incident_sface()->mark())){
	  CGAL_NEF_TRACEN("deleting "<<PH(e));
	  if ( !UF.same_set(Pitem[e->incident_sface()],
			    Pitem[e->twin()->incident_sface()]) ) {
	    
	    UF.unify_sets( Pitem[e->incident_sface()],
			   Pitem[e->twin()->incident_sface()] );
	    CGAL_NEF_TRACEN("unioning disjoint faces");
	  }
	  
	  CGAL_NEF_TRACEN("is_closed_at_source " << is_closed_at_source(e) << 
			  " " << is_closed_at_source(e->twin()));
	  
	  if ( is_closed_at_source(e) )
	    Vitem[e->source()] = Pitem[e->incident_sface()];
	  
	  if ( is_closed_at_source(e->twin()))
	    Vitem[e->target()] = Pitem[e->incident_sface()];
	  
	  delete_edge_pair(e);
	}
      }
    }
    
    CGAL::Unique_hash_map<SHalfedge_handle,bool> linked(false);
    for (e = this->shalfedges_begin(); e != this->shalfedges_end(); ++e) {
      if ( linked[e] ) continue;
      SHalfedge_around_sface_circulator hfc(e),hend(hfc);
      SFace_handle f = *(UF.find( Pitem[e->incident_sface()]));
      CGAL_For_all(hfc,hend) {  set_face(hfc,f); linked[hfc]=true; }
      store_sm_boundary_object(e,f);
    }
    
    SVertex_iterator v,vn;
    for(v = this->svertices_begin(); v != this->svertices_end(); v=vn) {
      vn=v; ++vn;
      if ( is_isolated(v) ) {
	if(Vitem[v] != NULL) {
	  set_face(v,*(UF.find(Vitem[v])));
	  CGAL_NEF_TRACEN("incident face of " << PH(v) << " set to " << &*(v->incident_sface()));
	}
	else {
	set_face(v, *(UF.find(Pitem[v->incident_sface()])));
	CGAL_NEF_TRACEN("isolated svertex " << PH(v) << 
			" already has incident face " << &*(v->incident_sface()));
	}
	if ( v->mark() == v->incident_sface()->mark() ) {
	  CGAL_NEF_TRACEN("removing isolated vertex"<<PH(v));
	  delete_vertex_only(v);  
	} 
	else 
	  store_sm_boundary_object(v,v->incident_sface()); // isolated, but should stay
      } else { // v not isolated
	SHalfedge_handle e2 = first_out_edge(v), e1 = e2->sprev();
	if ( has_outdeg_two(v) &&
	     v->mark() == e1->mark() && v->mark() == e2->mark() &&
	     e1->circle() == e2->circle() ) {
	  CGAL_NEF_TRACEN("collinear at "<<PH(v)<<PH(e1)<<PH(e2));
	  if ( e1 == e2 ){ 
	    CGAL_NEF_TRACEN("edge_to_loop"); 
	    convert_edge_to_loop(e1);
	  } else {
	    CGAL_NEF_TRACEN("merge_edge_pairs"); 
	    merge_edge_pairs_at_target(e1); 
	  } 	
	}
      }
    }
    
    SFace_iterator fn;
    for (f = fn = this->sfaces_begin(); f != this->sfaces_end(); f=fn) { 
      ++fn;
      Union_find_handle pit = Pitem[f];
      if ( UF.find(pit) != pit ) {
	CGAL_NEF_TRACEN("delete face " << &*f);
	delete_face_only(f);
      }
    }
    
    CGAL_NEF_TRACEN(" ");
    CGAL_NEF_TRACEN("resulting vertex ");
    
    CGAL_forall_svertices(vn, *this)
      CGAL_NEF_TRACEN("|" << vn->point() << "|" << vn->mark());
    CGAL_NEF_TRACEN(" ");
    
    CGAL_forall_shalfedges(en,*this)
      CGAL_NEF_TRACEN("|" << en->circle() <<
		      "|" << en->mark() << 
		      " " << en->incident_sface()->mark());
    CGAL_NEF_TRACEN("---------------------");
  }

};

template <typename SM_decorator_>
class SNC_SM_overlayer<SNC_indexed_items, SM_decorator_> 
  : public SM_overlayer<SM_decorator_> {

  typedef SM_decorator_                          SM_decorator;
  typedef typename SM_decorator::Map             Map;
  typedef SM_overlayer<SM_decorator_>            Base;
  typedef SNC_SM_overlayer<SNC_indexed_items, 
    SM_decorator_> Self;

  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::SHalfedge_around_sface_circulator 
                         SHalfedge_around_sface_circulator;

  typedef typename Base::Sphere_kernel           Sphere_kernel;

  typedef typename Map::Infi_box Infi_box;

 public:
  SNC_SM_overlayer(Map* M, 
		   const Sphere_kernel& G = Sphere_kernel()) 
    : Base(M,G) {}

  void convert_edge_to_loop(SHalfedge_handle e) {