snc_decorator.h

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

// Copyright (c) 1997-2002  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 DESISGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Nef_3/include/CGAL/Nef_3/SNC_decorator.h,v $
// $Revision: 1.91.2.1 $ $Date: 2004/12/08 19:30:44 $
// $Name:  $
//
// Author(s)     : Michael Seel    <[e-mail]>
//                 Miguel Granados <[e-mail]>
//                 Susan Hert      <[e-mail]>
//                 Lutz Kettner    <[e-mail]>
#ifndef CGAL_SNC_DECORATOR_H
#define CGAL_SNC_DECORATOR_H

//#define CGAL_NEF3_SM_VISUALIZOR
//#define CGAL_NEF3_DUMP_SPHERE_MAPS
//#define CGAL_NEF3_DUMP_SNC_OPERATORS

#include <CGAL/basic.h>
#include <CGAL/Nef_S2/Normalizing.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_3/SNC_iteration.h>
#include <CGAL/Nef_3/SNC_const_decorator.h>
#include <CGAL/Nef_S2/SM_decorator.h>
#include <CGAL/Nef_S2/SM_point_locator.h>
#include <CGAL/Nef_3/SNC_SM_overlayer.h>
#include <CGAL/Nef_S2/SM_io_parser.h>
#include <CGAL/Nef_3/SNC_constructor.h>
#include <CGAL/Nef_3/SNC_intersection.h>
#include <CGAL/Nef_3/SNC_point_locator.h>
#include <CGAL/Nef_3/SNC_simplify.h>
#include <CGAL/Nef_3/binop_intersection_tests.h>
#include <CGAL/Nef_3/SNC_decorator_traits.h>

#include <CGAL/IO/Verbose_ostream.h>
#ifdef  CGAL_NEF3_SM_VISUALIZOR
#include <CGAL/Nef_3/SNC_SM_visualizor.h>
#endif // CGAL_NEF3_SM_VISUALIZOR
#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 19
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

#if defined (CGAL_NEF3_TIMER_OVERLAY) || defined(CGAL_NEF3_TIMER_INTERSECTION)
CGAL::Timer timer_overlay;
#endif

#ifdef CGAL_NEF3_TIMER_POINT_LOCATION
int number_of_point_location_queries;
int number_of_ray_shooting_queries;
CGAL::Timer timer_point_location;
CGAL::Timer timer_ray_shooting;
#endif 

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
int number_of_edge_facet_overlays=0;
int number_of_clones=0;
int number_of_sphere_sweeps=0;
CGAL::Timer timer_sphere_sweeps;
#endif

#ifdef CGAL_NEF3_TIMER_PLANE_SWEEPS
int number_of_plane_sweeps=0;
CGAL::Timer timer_plane_sweeps;
#endif

#ifdef CGAL_NEF3_DUMP_STATISTICS
int number_of_intersections;
int number_of_intersection_candidates;
#endif

template <typename Map>
class SNC_decorator : public SNC_const_decorator<Map> { 
 public:
  typedef Map SNC_structure;
  typedef typename Map::Sphere_map                     Sphere_map;
  typedef CGAL::SNC_decorator<SNC_structure>           Self;
  typedef CGAL::SNC_const_decorator<SNC_structure>     Base;
  typedef Base                                         SNC_const_decorator;
  typedef CGAL::SNC_constructor<SNC_structure>         SNC_constructor;
  typedef CGAL::SM_decorator<Sphere_map>               SM_decorator;
  typedef CGAL::SM_const_decorator<Sphere_map>         SM_const_decorator;
  typedef CGAL::SNC_SM_overlayer<SM_decorator>         SM_overlayer;
  typedef CGAL::SM_point_locator<SM_decorator>         SM_point_locator;
  typedef CGAL::SNC_intersection<SNC_structure>        SNC_intersection;
  typedef CGAL::SNC_point_locator<SNC_decorator>       SNC_point_locator;
  typedef CGAL::SNC_simplify<SNC_structure>            SNC_simplify;
  SNC_structure* sncp_;

  typedef SNC_decorator_traits<SNC_structure>  Decorator_traits;

  typedef typename SNC_structure::Vertex_handle Vertex_handle;
  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename SNC_structure::Halffacet_handle Halffacet_handle;
  typedef typename SNC_structure::Volume_handle Volume_handle;
  typedef typename SNC_structure::SVertex_handle SVertex_handle;
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;
  typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle;
  typedef typename SNC_structure::SFace_handle SFace_handle;

  typedef typename SNC_structure::Vertex_iterator Vertex_iterator;
  typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator;
  typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator; 
  typedef typename SNC_structure::Volume_iterator Volume_iterator;
  typedef typename SNC_structure::SVertex_iterator SVertex_iterator;  
  typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator;
  typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator;
  typedef typename SNC_structure::SFace_iterator SFace_iterator;  

  typedef typename SNC_structure::SHalfedge_around_facet_circulator SHalfedge_around_facet_circulator;
  typedef typename SNC_structure::SFace_cycle_iterator SFace_cycle_iterator;
  typedef typename SNC_structure::Halffacet_cycle_iterator Halffacet_cycle_iterator;
  typedef typename SNC_structure::Shell_entry_iterator Shell_entry_iterator;
 
  typedef typename SNC_structure::Vertex Vertex;
  typedef typename SNC_structure::Halfedge Halfedge;
  typedef typename SNC_structure::Halffacet Halffacet;
  typedef typename SNC_structure::Volume Volume;
  typedef typename SNC_structure::SVertex SVertex;
  typedef typename SNC_structure::SHalfedge SHalfedge;
  typedef typename SNC_structure::SHalfloop SHalfloop;
  typedef typename SNC_structure::SFace SFace;

  typedef typename SNC_structure::Object_handle Object_handle;
  typedef typename SNC_structure::Object_iterator Object_iterator;

  typedef typename Base::Vertex_const_handle Vertex_const_handle;
  typedef typename Base::Halfedge_const_handle Halfedge_const_handle;
  typedef typename Base::Halffacet_const_handle Halffacet_const_handle;
  typedef typename Base::Volume_const_handle Volume_const_handle;
  typedef typename Base::SVertex_const_handle SVertex_const_handle;
  typedef typename Base::SHalfedge_const_handle SHalfedge_const_handle;
  typedef typename Base::SHalfloop_const_handle SHalfloop_const_handle;
  typedef typename Base::SFace_const_handle SFace_const_handle;

  typedef typename Base::Vertex_const_iterator Vertex_const_iterator;
  typedef typename Base::Halfedge_const_iterator Halfedge_const_iterator;
  typedef typename Base::Halffacet_const_iterator Halffacet_const_iterator;
  typedef typename Base::Volume_const_iterator Volume_const_iterator;
  typedef typename Base::SVertex_const_iterator SVertex_const_iterator;
  typedef typename Base::SHalfedge_const_iterator SHalfedge_const_iterator;
  typedef typename Base::SHalfloop_const_iterator SHalfloop_const_iterator;
  typedef typename Base::SFace_const_iterator SFace_const_iterator;

  typedef typename Base::SHalfedge_around_facet_const_circulator SHalfedge_around_facet_const_circulator;
  typedef typename Base::SFace_cycle_const_iterator SFace_cycle_const_iterator;
  typedef typename Base::Halffacet_cycle_const_iterator Halffacet_cycle_const_iterator;
  typedef typename Base::Shell_entry_const_iterator Shell_entry_const_iterator;

  typedef typename Base::Kernel Kernel;
  typedef typename Base::FT FT;
  typedef typename Base::RT RT;

  typedef typename Base::Point_3 Point_3;
  typedef typename Base::Segment_3 Segment_3;
  typedef typename Base::Ray_3 Ray_3;
  typedef typename Base::Line_3 Line_3;
  typedef typename Base::Plane_3 Plane_3;
  typedef typename Base::Vector_3 Vector_3;

  typedef typename Base::Sphere_kernel Sphere_kernel;
  typedef typename Base::Sphere_point Sphere_point;
  typedef typename Base::Sphere_segment Sphere_segment;
  typedef typename Base::Sphere_circle Sphere_circle;
  typedef typename Base::Sphere_direction Sphere_direction;

  typedef typename Base::Size_type Size_type;
  typedef typename Base::Mark Mark;
  typedef typename Base::Infi_box Infi_box;
  typedef typename Base::Aff_transformation_3 Aff_transformation_3;

  typedef typename SM_decorator::SHalfedge_around_svertex_circulator 
                                 SHalfedge_around_svertex_circulator;
  typedef typename SM_decorator::SHalfedge_around_sface_circulator 
                                 SHalfedge_around_sface_circulator;

  struct points_lt {
    bool operator()(Point_3& p1, Point_3& p2) const {
      return CGAL::lexicographically_xyz_smaller(p1,p2);
    }
  };

  enum {NO_SNC, WITH_SNC};

 public:
  typedef void* GenPtr;


#define using(f) using Base::f
  //  using(mark);
  //  using(vertex);
  //  using(twin);
  //  using(source);
  //  using(target);
  //  using(sface);

  // using(vertex);
  // using(twin);
  // using(source);
  // using(target);
  //  using(previous);
  //  using(next);
  //  using(facet);
  // using(sface);
  //  using(ssource);
  //  using(starget);

  // using(mark);
  // using(twin);
  //  using(facet);
  // using(vertex);
  // using(sface);

  // using(vertex);
  //  using(volume);

  //  using(twin);
  // using(volume);

  //  using(point);
  //  using(point);
  // using(calc_point);

  //  using(segment);
  //  using(plane);
  //  using(vector);
  //  using(orthogonal_vector);
  // using(mark);
#undef using

  SNC_decorator() : Base(), sncp_() {}
  SNC_decorator(SNC_structure& W) 
    : Base(W), sncp_(&W) {}
  SNC_decorator(const Self& S) {
    sncp_ = S.sncp_;
  }

  SNC_structure* sncp() const { 
    CGAL_assertion( sncp_ != NULL);
    return sncp_; 
  }

  void set_snc(SNC_structure& W) {
    sncp_ = &W;
  }

  static Vertex_handle vertex( Halfedge_handle e)
  { return e->center_vertex(); }
  static Halfedge_handle twin( Halfedge_handle e)
  { return e->twin(); }
  static Vertex_handle source( Halfedge_handle e)
  { return e->center_vertex(); }
  static Vertex_handle target( Halfedge_handle e)
  { return e->twin()->source(); }
  static SFace_handle sface( Halfedge_handle e)
  { return e->incident_sface(); }
  /* SVertex queries*/

  static Vertex_handle vertex(SHalfedge_handle e)
  { return vertex(e->source()); }
  static SHalfedge_handle twin(SHalfedge_handle e)
  { return e->twin(); }
  static Vertex_handle source(SHalfedge_handle e)
  { return e->source()->center_vertex(); }
  static Vertex_handle source(SHalfedge e)
  { return e.source()->center_vertex(); }
  static Vertex_handle target(SHalfedge_handle e)
  { return e->twin()->source()->twin()->center_vertex(); }
  static SHalfedge_handle previous(SHalfedge_handle e)
  { return e->prev(); }
  static SHalfedge_handle next(SHalfedge_handle e)
  { return e->next(); }
  static Halffacet_handle facet(SHalfedge_handle e)
  { return e->facet(); }
  static SFace_handle sface(SHalfedge_handle e)
  { return e->incident_sface(); }
  static Halfedge_handle ssource(SHalfedge_handle e)
  { return e->source(); }
  static Halfedge_handle starget(SHalfedge_handle e)
  { return e->twin()->source(); }
  /* SHalfedge queries */

  static const Mark& mark(SHalfedge_handle e)
  /*{\Mop returns the mark associated to |e| as
  a sphere object. This is temporary information!!!}*/
  { return e->mark(); }

  static const Sphere_circle& circle(SHalfedge_handle e)
  { return e->circle(); }
  static const Sphere_circle& circle(SHalfloop_handle l)
  { return l->circle(); }

  std::string debug(SHalfedge_handle e) const
  { std::stringstream os; set_pretty_mode(os);
    os << "sedge-use " << point(source(e)) << point(target(e))<<'\0';
    return os.str();
  }

  static SHalfloop_handle twin( SHalfloop_handle l)
  { return l->twin(); }
  static Halffacet_handle facet( SHalfloop_handle l)
  { return l->facet(); }
  static Vertex_handle vertex( SHalfloop_handle l)
  { return l->incident_sface()->center_vertex(); }
  static SFace_handle sface( SHalfloop_handle l)
  { return l->incident_sface(); }
  /* SHalfloop queries */

  static Vertex_handle vertex(SFace_handle f)
  { return f->center_vertex(); }
  static Volume_handle volume(SFace_handle f)
  { return f->volume(); }
  /* SHalffacet queries */

  static Halffacet_handle twin(Halffacet_handle f)
  { return f->twin(); }
  static Volume_handle volume(Halffacet_handle f)
    { return f->incident_volume(); }
  /* Halffacet queries */

  SFace_handle adjacent_sface(Halffacet_handle f) const {
    Halffacet_cycle_iterator fc(f->facet_cycles_begin());
    CGAL_assertion( fc != f->facet_cycles_end());
    if ( fc.is_shalfedge() ) {
      SHalfedge_handle se(fc);
      CGAL_assertion( facet(se) == f);
      CGAL_assertion( sface(se) != SFace_handle());
      CGAL_assertion( volume(sface(twin(se))) == volume(f));
      return sface(twin(se));
    } 
    else 
      CGAL_assertion_msg( 0, "Facet outer cycle entry point"
			     "is not an SHalfedge? ");
    return SFace_handle(); // never reached
  }

  static Point_3& point(Vertex_handle v)
  { return v->point(); }

  static Vector_3 to_vector(Halfedge_handle e) {  // rename to to_vector
    return Vector_3(e->vector()-CGAL::ORIGIN);
  }

  static Segment_3 segment(Halfedge_handle e)
  { return Segment_3(point(source(e)),