regular_triangulation_3.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2005  Stanford University (USA).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL 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/Kinetic_data_structures/include/CGAL/Kinetic/Regular_triangulation_3.h $
// $Id: Regular_triangulation_3.h 37995 2007-04-07 19:07:06Z drussel $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#ifndef CGAL_KINETIC_KINETIC_REGULAR_TRIANGULATION_3_H
#define CGAL_KINETIC_KINETIC_REGULAR_TRIANGULATION_3_H
#include <CGAL/basic.h>

#include <CGAL/Regular_triangulation_3.h>
#include <CGAL/Regular_triangulation_euclidean_traits_3.h>
#include <CGAL/Kinetic/internal/Delaunay_triangulation_base_3.h>
#include <CGAL/Kinetic/Regular_triangulation_vertex_base_3.h>
#include <CGAL/Kinetic/Regular_triangulation_cell_base_3.h>
#include <CGAL/Kinetic/Regular_triangulation_visitor_base_3.h>
#include <CGAL/Kinetic/Listener.h>
#include <CGAL/Kinetic/Ref_counted.h>

#include <CGAL/Kinetic/Simulator_kds_listener.h>
#include <CGAL/Kinetic/Active_objects_listener_helper.h>

#if defined(BOOST_MSVC)
#  pragma warning(push)
#  pragma warning(disable:4355) // complaint about using 'this' to
#endif                          // initialize a member


CGAL_KINETIC_BEGIN_INTERNAL_NAMESPACE

template <class KD>
class Regular_3_pop_event: public Delaunay_event_base_3<KD, typename KD::Root_stack>
{
  typedef Delaunay_event_base_3<KD, typename KD::Root_stack>  P;
public:
  Regular_3_pop_event(const typename KD::Root_stack &s,
		      const typename KD::Vertex_handle &vh,
		      KD *kd): P(s, kd), vh_(vh) {
  }

  void process() {
    P::kdel()->pop(vh_, P::root_stack());
  }

  typename KD::Vertex_handle vertex() const
  {
    return vh_;
  }

  std::ostream& write(std::ostream &out) const
  {
    out << "Pop " << vh_->point();
    return out;
  }

  void audit(typename KD::Event_key k) const {
    P::kdel()->audit_pop(k, vh_);
  }
  /*virtual bool is_of_type(int tp) const {
    return (tp &type())!=0 || P::is_of_type(tp);
    }
    static int type() {
    return 2;
    }*/

  virtual ~Regular_3_pop_event(){};

protected:
  const typename KD::Vertex_handle vh_;
};

/*template <class K, class S, class VH>
  std::ostream& operator<<(std::ostream &out, const Regular_3_pop_event<K,S,VH> &e)
  {
  e.write(out);
  return out;
  }*/


template <class KD>
class Regular_3_non_vertex_event: public Delaunay_event_base_3<KD, typename KD::Root_stack>
{
  typedef Delaunay_event_base_3<KD, typename KD::Root_stack>  P;
public:

  Regular_3_non_vertex_event(const typename KD::Root_stack &s,
			     const typename KD::Point_key &k,
			     const typename KD::Cell_handle &c,
			     KD *kd): P(s,kd), k_(k), cell_(c) {
  }

  Regular_3_non_vertex_event(){}

  std::ostream& write(std::ostream &out) const
  {
    out << "Nothing ";
    return out;
  }

  /* virtual bool is_of_type(int tp) const {
     return (tp &type())!=0 || P::is_of_type(tp);
     }
     static int type() {
     return 4;
     }*/

  typename KD::Point_key point() const {return k_;}

  typename KD::Cell_handle cell_handle() const {return cell_;}

  virtual ~Regular_3_non_vertex_event(){};

protected:
  const typename KD::Point_key k_;
  const typename KD::Cell_handle cell_;
};

template <class KD>
class Regular_3_move_event: public Regular_3_non_vertex_event<KD>
{
  typedef Regular_3_non_vertex_event<KD>  P;
public:
  Regular_3_move_event(const typename KD::Root_stack &s,
		       const typename KD::Point_key &k,
		       const typename KD::Cell_handle &c,
		       int dir,
		       KD *kd): P(s,k, c, kd), dir_(dir) {
  }

  void process() {
    P::kdel()->move(P::k_, P::cell_, dir_, P::root_stack());
  }

  std::ostream& write(std::ostream &out) const
  {
    out << "Move " << P::point() << " from ";
    internal::write_cell(P::cell_handle() , out);
    return out;
  }

  void audit(typename KD::Event_key k) const{
    P::kdel()->audit_move(k, P::point(), P::cell_, dir_);
  }
  /*virtual bool is_of_type(int tp) const {
    return (tp &type())!=0 || P::is_of_type(tp);
    }
    static int type() {
    return 8;
    }*/

  virtual ~Regular_3_move_event(){};

protected:
  int dir_;
};

/*template <class K,  class S, class KK, class C>
  std::ostream& operator<<(std::ostream &out, const Regular_3_move_event<K,S,KK,C> &e)
  {
  e.write(out);
  return out;
  }*/


template <class KD>
class Regular_3_push_event: public Regular_3_non_vertex_event<KD>
{
  typedef Regular_3_non_vertex_event<KD>  P;
public:

  Regular_3_push_event(const typename KD::Root_stack &s,
		       const typename KD::Point_key &k,
		       const typename KD::Cell_handle &c,
		       KD *kd): P(s,k, c, kd) {
  }

  void process() {
    P::kdel()->push(P::k_, P::cell_, P::root_stack());
  }

  std::ostream& write(std::ostream &out) const
  {
    out << "Push " << P::point() << " into ";
    internal::write_cell(P::cell_handle() , out);
    return out;
  }
  
  void audit(typename KD::Event_key k) const {
    P::kdel()->audit_push(k, P::point(), P::cell_);
  }
  /*virtual bool is_of_type(int tp) const {
    return (tp &type())!=0 || P::is_of_type(tp);
    }
    static int type() {
    return 16;
    }*/

  virtual ~Regular_3_push_event(){};
};

/*template <class K, class S, class KK, class C>
  std::ostream& operator<<(std::ostream &out, const Regular_3_push_event<K,S,KK,C> &e)
  {
  e.write(out);
  return out;
  }*/


template <class Traits>
struct Regular_triangulation_3_types
{
  typedef typename Traits::Active_points_3_table MPT; // here
  typedef typename Traits::Kinetic_kernel KK;
  // typedef CGAL::Triangulation_cell_base_3<typename Traits::Instantaneous_kernel> CFB;

  /*typedef CGAL::Triangulation_cell_base_with_info_3<Delaunay_cache_3<MPT, KK>,
    typename Traits::Instantaneous_kernel, CFB> CFBI;*/

  //typedef Triangulation_labeled_edge_cell_base_3<CFBI, typename Traits::Simulator::Event_key> TFB;
  //typedef Triangulation_labeled_facet_cell_base_3<TFB, typename Traits::Simulator::Event_key> FB;
  /*typedef CGAL::Triangulation_vertex_base_3<typename Traits::Instantaneous_kernel> CVB;
    typedef CGAL::Triangulation_vertex_base_with_info_3<typename Traits::Simulator::Event_key,
    typename Traits::Instantaneous_kernel,
    CVB> LVB;*/
  typedef CGAL::Kinetic::Regular_triangulation_cell_base_3<Traits> FB;
  typedef CGAL::Kinetic::Regular_triangulation_vertex_base_3<Traits> LVB;

  typedef CGAL::Triangulation_data_structure_3<LVB, FB> TDS;

  typedef CGAL::Regular_triangulation_3<typename Traits::Instantaneous_kernel, TDS> Default_triangulation;

 

  //friend class CGAL::Delaunay_triangulation_3<typename P::Instantaneous_kernel, TDS>;

};

CGAL_KINETIC_END_INTERNAL_NAMESPACE

CGAL_KINETIC_BEGIN_NAMESPACE

/*!
  redundant_cells_ maps each cell with redundant points to the ids of the points in that cell

  redundant_points_ maps each redundant point to a certificate
*/
template <class TraitsT,
	  class VisitorT= Regular_triangulation_visitor_base_3,
	  class TriangulationT= typename internal::Regular_triangulation_3_types<TraitsT>::Default_triangulation>
class Regular_triangulation_3:
  public Ref_counted<Regular_triangulation_3<TraitsT, VisitorT, TriangulationT> >
{
private:
  typedef Regular_triangulation_3<TraitsT, VisitorT, TriangulationT> This;
  typedef typename TraitsT::Instantaneous_kernel Instantaneous_kernel;
public:
  typedef Regular_triangulation_3<TraitsT, VisitorT, TriangulationT> This_RT3;
  typedef TraitsT Traits;
  typedef typename Traits::Active_points_3_table::Key Point_key; //here
  typedef typename Traits::Kinetic_kernel::Certificate Root_stack;
protected:
  typedef typename Traits::Active_points_3_table MPT; // here
  typedef typename Traits::Simulator Simulator;
  typedef typename Traits::Simulator::Event_key Event_key;
  typedef typename Traits::Simulator::Time Time;

  
  typedef TriangulationT Delaunay;

  typedef internal::Regular_triangulation_3_types<TraitsT> Types;

  struct Delaunay_visitor {
    template <class Point_key, class Cell_handle>
    void pre_insert_vertex(Point_key v, Cell_handle h) {
      v_.pre_insert_vertex(v, h);
    }

    template <class Vertex_handle>
    void post_insert_vertex(Vertex_handle v) {
      v_.post_insert_vertex(v);
    }

    template <class Vertex_handle>
    void pre_remove_vertex(Vertex_handle v) {
      v_.pre_remove_vertex(v);
    }


    template <class Point_key>
    void post_remove_vertex(Point_key v) {
      v_.post_remove_vertex(v);
    }

    template <class Vertex_handle>
    void change_vertex(Vertex_handle v) {
      v_.change_vertex(v);
    }

    template <class Cell_handle> 
    void create_cell(Cell_handle h) {
      krt_->create_cell(h);
      v_.create_cell(h);
    }

    template <class Cell_handle>
    void destroy_cell(Cell_handle h) {
      krt_->destroy_cell(h);
      v_.destroy_cell(h);
    }

    template <class Edge>
    void pre_edge_flip(const Edge &e) {
      v_.pre_edge_flip(e);
    }
    template <class Edge>
    void post_facet_flip(const Edge& e) {
      v_.post_facet_flip(e);
    }

    template <class Facet>
    void pre_facet_flip(const Facet &f) {
      v_.pre_facet_flip(f);
    }

    template <class Facet>
    void post_edge_flip(const Facet& f) {
      v_.post_edge_flip(f);
    }

    template <class Key, class Cell>
    void pre_move(Key k, Cell h){
      v_.pre_move(k,h);
    }

    template <class Key, class Cell>
    void post_move(Key k, Cell h){
      v_.post_move(k,h);
    }

    Delaunay_visitor(This* krt, VisitorT v): krt_(krt), v_(v){}

    This* krt_;
    VisitorT v_;
  };

  friend class Delaunay_visitor;

  typedef typename Delaunay::Facet Facet;
  typedef typename Delaunay::Edge Edge;

public:
  typedef typename Delaunay::Cell_handle Cell_handle;
  typedef typename Delaunay::Vertex_handle Vertex_handle;
  typedef VisitorT Visitor;


  friend class internal::Delaunay_event_base_3<This, Root_stack>;
  typedef internal::Delaunay_3_edge_flip_event<This, Root_stack> Edge_flip;
  friend class internal::Delaunay_3_edge_flip_event<This, Root_stack>;
  typedef internal::Delaunay_3_facet_flip_event<This, Root_stack> Facet_flip;
  friend class internal::Delaunay_3_facet_flip_event<This, Root_stack>;

  typedef internal::Regular_3_pop_event<This> Pop_event;
  friend class internal::Regular_3_pop_event<This>;

  typedef internal::Regular_3_non_vertex_event<This> Non_vertex_event;
  friend class internal::Regular_3_non_vertex_event<This>;

  typedef internal::Regular_3_move_event<This> Move_event;
  friend class internal::Regular_3_move_event<This> ;

  typedef internal::Regular_3_push_event<This> Push_event;
  friend class internal::Regular_3_push_event<This> ;

protected:
  typedef std::multimap<typename Delaunay::Cell_handle,
			Point_key> RCMap;
  typedef std::map<Point_key, Event_key> RPMap;

  struct Base_traits;
  friend struct Base_traits;

  struct Base_traits: public TraitsT
  {
    
    typedef TriangulationT Triangulation;
    typedef typename This_RT3::Edge_flip Edge_flip;
    typedef typename This_RT3::Facet_flip Facet_flip;
    typedef typename TraitsT::Kinetic_kernel::Power_test_3 Side_of_oriented_sphere_3;
    typedef typename TraitsT::Kinetic_kernel::Weighted_orientation_3 Orientation_3;
    typedef typename TraitsT::Active_points_3_table Active_points_3_table; // here

    Side_of_oriented_sphere_3 side_of_oriented_sphere_3_object() const
    {
      //std::cout << "Getting power test" << std::endl;
      return TraitsT::kinetic_kernel_object().power_test_3_object();
    }

    Orientation_3 orientation_3_object() const