delaunay_triangulation_2.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/Delaunay_triangulation_2.h $
// $Id: Delaunay_triangulation_2.h 36134 2007-02-09 00:39:39Z drussel $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

#ifndef CGAL_KINETIC_KINETIC_DELAUNAY_2_H
#define CGAL_KINETIC_KINETIC_DELAUNAY_2_H
#include <CGAL/Kinetic/basic.h>

#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Kinetic/Delaunay_triangulation_face_base_2.h>
#include <CGAL/Kinetic/Delaunay_triangulation_vertex_base_2.h>
#include <CGAL/Kinetic/Delaunay_triangulation_visitor_base_2.h>
#include <CGAL/Kinetic/Active_objects_batch_listener_helper.h>
#include <CGAL/Kinetic/Simulator_kds_listener.h>
#include <CGAL/Kinetic/internal/tds_2_helpers.h>
#include <CGAL/Triangulation_data_structure_2.h>
#include <CGAL/Kinetic/Ref_counted.h>
#include <iterator>
#include <CGAL/Kinetic/Event_base.h>
#include <CGAL/Kinetic/Delaunay_triangulation_default_traits_2.h>

CGAL_KINETIC_BEGIN_NAMESPACE
//#ifdef NDEBUG
#define CGAL_DELAUNAY_2_DEBUG(x)
/*#else
#define CGAL_DELAUNAY_2_DEBUG(x) x
//#endif*/

template <class KDel>
struct Delaunay_edge_failure_event: public Event_base<KDel*> {
  typedef Event_base<KDel*>  P;
  Delaunay_edge_failure_event(const typename KDel::Certificate_data &c,
			      const typename KDel::Edge &e,
			      KDel *kdel): P(kdel), c_(c), e_(e) {}
  typename KDel::Certificate_data &certificate() const {
    return c_;
  }
  const typename KDel::Edge edge() const {
    return e_;
  }
  KDel* kdel() {
    return P::kds();
  }

  KDel* kdel() const {
    return P::kds();
  }
  void process() {
    kdel()->flip(e_, c_);
  }

  void audit(typename KDel::Event_key k) const {
    kdel()->audit_event(k, e_);
  }

  CGAL::Comparison_result compare_concurrent(typename KDel::Event_key a,
					     typename KDel::Event_key b) const {
    return kdel()->compare_concurrent(a, b);
  }	

  std::ostream& write(std::ostream &out) const
  {
    out << "Flip " << KDel::TDS_helper::origin(edge())->point() << ","
	<< KDel::TDS_helper::destination(edge())->point() 
	<< " to " << KDel::TDS_helper::third_vertex(edge())->point() 
	<< ", " << KDel::TDS_helper::mirror_vertex(edge())->point() ;
    return out;
  }

  typename KDel::Certificate_data c_;
  const typename KDel::Edge e_;
};





//! A 2D kinetic Delaunay triangulation.
/*!  Points are added via the Moving_point_table, so the public
  interface is very limited. See kinetic_Delaunay_2.cc for a useage example.
*/
template <class Simulation_traits_t, 
	  class Visitor= Delaunay_triangulation_visitor_base_2,
	  class Delaunay
	  = CGAL::Delaunay_triangulation_2<typename Simulation_traits_t::Instantaneous_kernel,
					   CGAL::Triangulation_data_structure_2<
	    Delaunay_triangulation_vertex_base_2<typename Simulation_traits_t::Instantaneous_kernel>,
  CGAL::Kinetic::Delaunay_triangulation_face_base_2<Simulation_traits_t > > >,
	  class Delaunay_traits_t= Delaunay_triangulation_default_traits_2<Simulation_traits_t, Delaunay> >
class Delaunay_triangulation_2:
  public Ref_counted<Delaunay_triangulation_2<Simulation_traits_t, Visitor, Delaunay, Delaunay_traits_t> >
{

  typedef CGAL::Delaunay_triangulation_2<typename Simulation_traits_t::Instantaneous_kernel,
					 CGAL::Triangulation_data_structure_2<
    Delaunay_triangulation_vertex_base_2<typename Simulation_traits_t::Instantaneous_kernel>,
    CGAL::Kinetic::Delaunay_triangulation_face_base_2<Simulation_traits_t > > > Basic_Delaunay;

public:
  typedef Delaunay_traits_t Traits;
  typedef Simulation_traits_t Simulation_traits;
  typedef Delaunay_triangulation_2<Simulation_traits, Visitor, Delaunay, Traits> This;

  typedef typename Simulation_traits::Kinetic_kernel Kinetic_kernel;
  typedef typename Simulation_traits::Simulator Simulator;
  typedef typename Simulation_traits::Active_points_2_table Moving_point_table;

  typedef typename Moving_point_table::Key Point_key;
  typedef typename Simulator::Event_key Event_key;
  //typedef typename Simulator::Root_stack Root_stack;

  typedef typename Traits::Triangulation Triangulation;

  typedef typename Triangulation::Edge_circulator Edge_circulator;
  typedef typename Triangulation::Face_circulator Face_circulator;
  typedef typename Triangulation::Finite_edges_iterator Finite_edges_iterator;
  //typedef typename Triangulation::Edge_iterator Edge_iterator;

  typedef typename Triangulation::Geom_traits::Point_2 Del_point;

  typedef typename Triangulation::Vertex_handle Vertex_handle;
  typedef typename Triangulation::Face_handle Face_handle;
  typedef typename Triangulation::Edge Edge;
  typedef typename Triangulation::All_faces_iterator Face_iterator;
  typedef typename Triangulation::All_edges_iterator Edge_iterator;
  typedef typename Traits::Certificate_data Certificate_data;
  typedef typename Traits::Time Time;
  typedef internal::Triangulation_data_structure_helper_2<typename Triangulation::Triangulation_data_structure> TDS_helper;

  typedef Delaunay_edge_failure_event<This> Event;
  
  //friend class Delaunay_edge_failure_event<This>;
  //friend class Delaunay_hull_edge_failure_event<This>;

  typedef typename CGAL::Kinetic::Simulator_kds_listener<typename Simulator::Listener, This> Simulator_listener;
  friend  class CGAL::Kinetic::Simulator_kds_listener<typename Simulator::Listener, This>;
  typedef typename CGAL::Kinetic::Active_objects_batch_listener_helper<typename Moving_point_table::Listener, This> Moving_point_table_listener;
  friend class CGAL::Kinetic::Active_objects_batch_listener_helper<typename Moving_point_table::Listener, This>;

  /*struct Compare_edges{
    bool operator()(const Edge &a, const Edge &b) const {
      Point_key a0, a1, b0, b1;
      a0= a.first->vertex((a.second+1)%3)->point();
      a1= a.first->vertex((a.second+2)%3)->point();
      b0= b.first->vertex((b.second+1)%3)->point();
      b1= b.first->vertex((b.second+2)%3)->point();
      if (a0 > a1) std::swap(a0, a1);
      if (b0 > b1) std::swap(b0, b1);
      if (a0 < b0) return true;
      else if (a0 > b0) return false;
      else return a1 < b1;
    }
    };*/

  void init_data(bool insert) {
    siml_ = Simulator_listener(traits_.simulator_handle(), this);
    motl_= Moving_point_table_listener(traits_.active_points_2_table_handle(), this, insert);
    has_certificates_=false; 
    clear_stats();
   
    batching_=false;
  }

public:

  Delaunay_triangulation_2(Traits st,
			   Triangulation del,
			   Visitor w= Visitor()): 
    traits_(st),
    watcher_(w),
    del_(del) {
    vhs_.resize(del_.number_of_vertices());
    for (typename Triangulation::Vertex_iterator vit = del_.vertices_begin(); vit != del_.vertices_end(); ++vit) {
      CGAL_assertion(vit->point().to_index() < del_.number_of_vertices());
      vhs_[vit->point().to_index()]=vit;
    }
    init_data(false);
  
    set_has_certificates(false, 0);
  }

  Delaunay_triangulation_2(Simulation_traits st,
			   Visitor w= Visitor()): 
    traits_(st),
    watcher_(w),
    del_(traits_.instantaneous_kernel_object()) {
    init_data(true);
    set_has_certificates(true, 0);
  }



  //! Just write the objects in order;
  void write(std::ostream &out) const
  {
    out << del_;
  }

  void clear_stats() {
    num_events_=0;
    // num_single_certificates_=0;
  }

  void write_stats(std::ostream &out) const {
    out << "Num events is " << num_events_ << std::endl;
  }

  const Triangulation &triangulation(const typename Simulator::NT &t) const
  {
    //update_instantaneous_kernel_time();
    del_.geom_traits().set_time(t);
    return del_;
  }

  const Triangulation &triangulation() const
  {
    return del_;
  }


  // for Qt_triangulation
  /*Event_key null_event() const {
    return traits_.simulator_handle()->null_event();
    }*/

  /*const Simulation_traits& simulation_traits_object() const {
    return traits_;
    }*/

  typedef typename Triangulation::Triangulation_data_structure Triangulation_data_structure;
  const Triangulation_data_structure &triangulation_data_structure() const
  {
    return del_.tds();
  }

  bool is_batch_editing() const {
    return batching_;
  }

  void set_is_batch_editing(bool tf) {
    if (tf) {
      batching_=true;
    } else if (batching_) {

      //unsigned int num_certs= num_certificates_;
      // this is important that it be before update
      batching_=false;

      //std::sort(batched_certs_.begin(), batched_certs_.end(), Compare_edges());
     
      /*batched_certs_.erase(std::unique(batched_certs_.begin(), 
				       batched_certs_.end()), 
				       batched_certs_.end());*/
     
      
      for (unsigned int i=0; i< batched_certs_.size(); ++i){
	//Point_key s=TDS_helper::origin(batched_certs_[i])->point();
	//Point_key t=TDS_helper::destination(batched_certs_[i])->point();
	
	//std::cout << std::min(s,t) << "--" << std::max(s,t) << std::endl;
	update_edge(batched_certs_[i]);
      }
      
      batched_certs_.clear();
      /*CGAL_KINETIC_LOG(CGAL::Kinetic::LOG_SOME, 
       *traits_.simulator_handle() << std::endl;);*/
      //int dnum= num_certificates_-num_certs;
      //std::cout << "Edit had " << dnum << " certificate computations" << std::endl;

      //audit();
    }
  }
  
  /*const std::set<Edge>& recent_edges() const {
    return new_edges_;
    }*/

  //! Verify that the current state of the
  void audit()const;

  void audit_event(Event_key k, Edge e) const {
    if (get_undirected_edge_label(e) !=k) {
      std::cerr << "AUDIT FAILURE orphan event " << k << std::endl;
    }
    CGAL_assertion(get_undirected_edge_label(e) ==k);
  }

  void set_neighbors_initialized(bool tf) const {
    if (tf) {
      for (typename Triangulation::All_vertices_iterator vit = del_.all_vertices_begin(); 
	   vit != del_.all_vertices_end(); ++vit) {
	vit->set_neighbors(0);
      }
      for (Face_iterator f = del_.all_faces_begin(); f != del_.all_faces_end(); ++f) {
	f->vertex(0)->set_neighbors(f->vertex(0)->neighbors()+1);
	f->vertex(1)->set_neighbors(f->vertex(1)->neighbors()+1);
	f->vertex(2)->set_neighbors(f->vertex(2)->neighbors()+1);
      }
    }
  }

  enum New_certificate_state {HAD_NO_FAILURES=1, HAS_NO_FAILURES = 2, NO_STRUCTURE_CHANGES = 4};

  void set_has_certificates(bool tf, int state=0) {
    if (tf == has_certificates_){

    } else {
      if (tf==true && del_.dimension()==2) {
	CGAL_KINETIC_LOG(CGAL::Kinetic::LOG_SOME, "DELAUNAY2: Creating certificates."<< std::endl);
	if (!(state & NO_STRUCTURE_CHANGES)) {
	  set_neighbors_initialized(true);
	}
	if (state & HAS_NO_FAILURES && !(state & HAD_NO_FAILURES)) {
	  for (Face_iterator f = del_.all_faces_begin(); f != del_.all_faces_end(); ++f) {
	    
	    set_directed_edge_label(Edge(f,0), traits_.simulator_handle()->null_event());
	    set_directed_edge_label(Edge(f,1), traits_.simulator_handle()->null_event());
	    set_directed_edge_label(Edge(f,2), traits_.simulator_handle()->null_event());
	    if (f->vertex(0)->neighbors() == 3) {
	      set_directed_edge_label(Edge(f,1), Event_key()); 
	      set_directed_edge_label(Edge(f,2), Event_key()); 
	    }
	    if (f->vertex(1)->neighbors() == 3) {
	      set_directed_edge_label(Edge(f,0), Event_key()); 
	      set_directed_edge_label(Edge(f,2), Event_key()); 
	    }
	    if (f->vertex(2)->neighbors() == 3) {
	      set_directed_edge_label(Edge(f,1), Event_key()); 
	      set_directed_edge_label(Edge(f,0), Event_key()); 
	    }
	    watcher_.create_face(f);
	  }
	} else if (state & HAD_NO_FAILURES  && state & HAS_NO_FAILURES)  {
	  // nothing to do, yeah!!!
	} else {
	  for (Edge_iterator eit = del_.all_edges_begin(); eit != del_.all_edges_end(); ++eit) {
	    set_undirected_edge_label(*eit, Event_key());
	    update_edge(*eit);
	  }
	}
      } else if (tf==false) { 
	if (!(state & HAD_NO_FAILURES)) {
	  for (Face_iterator f = del_.all_faces_begin(); f != del_.all_faces_end(); ++f) {
	    for(unsigned int i=0; i< 3; ++i) {
	      Edge e(f,i);
	      delete_certificate(e);
	    }
	    watcher_.destroy_face(f);
	  }
	}
      } 
      CGAL_KINETIC_LOG(CGAL::Kinetic::LOG_SOME, 
		       *traits_.simulator_handle() << std::endl;);
      has_certificates_=tf;
    }
  }
  bool has_certificates() {
    return has_certificates_;
  }

  void erase(Point_key k) {
    // erase all incident certificates
    Vertex_handle vh= vertex_handle(k);
    if (vh == Vertex_handle()) {
      CGAL_KINETIC_LOG(CGAL::Kinetic::LOG_SOME, "Point " << k << " is not in triangulation on removal."<< std::endl);
      return;
    }
    watcher_.pre_remove_vertex(vh);
    if (has_certificates_) {
      Face_circulator fc= vh->incident_faces(), fe=fc;
      if (fc != NULL) {
	do {
	  for (unsigned int j=0; j<3; ++j) {
	    Edge e(fc, j);
	    Event_key k= get_undirected_edge_label(e);
	    delete_certificate(e);
	  }