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/Triangulation_2.h $
// $Id: Triangulation_2.h 36128 2007-02-08 16:31:14Z drussel $
// 
//
// Author(s)     : Daniel Russel <[e-mail]>

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

#include <CGAL/Kinetic/Triangulation_face_base_2.h>
#include <CGAL/Kinetic/Triangulation_vertex_base_2.h>
#include <CGAL/Kinetic/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_2.h>
#include <CGAL/Kinetic/Ref_counted.h>
#include <iterator>
#include <CGAL/Kinetic/Event_base.h>
#include <CGAL/Kinetic/Triangulation_default_traits_2.h>

CGAL_KINETIC_BEGIN_NAMESPACE
#ifdef NDEBUG
#define CGAL_TRIANGULATION_2_DEBUG(x)
#else
#define CGAL_TRIANGULATION_2_DEBUG(x) x
#endif

template <class KDel>
struct Triangulation_event: public Event_base<KDel*> {
  typedef Event_base<KDel*>  P;
  Triangulation_event(const typename KDel::Face_handle &e,
		      KDel *kdel): P(kdel), e_(e) {}
  const typename KDel::Face_handle face() const {
    return e_;
  }
  KDel* kdel() {
    return P::kds();
  }

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

  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 << "Face " << e_->vertex(0)->point() << ", "
        << e_->vertex(1)->point() 
        << ", " << e_->vertex(2)->point() ;
    return out;
  }
  const typename KDel::Face_handle e_;
};





//! A 2D kinetic triangulation.
/*!  There is one certificate for each face. For the internal faces
  (inside the convex hull), that certificate is for the face
  collapsing at which point we need to figure out which edge to flip.

  For the faces outside the convex hull, the certificate is for the
  edge that is CCW from the infinite vertex and for whether the other
  vertex on the edge leaves the convex hull.

  The annoying part is how to figure out which edge to flip when an
  internal face collapses.  As far as I can tell this requires
  evaluating which point is in the segment defined by which other two,
  so four 1D orientation predicates.
*/
template <class Simulation_traits_t, 
          class Visitor= Triangulation_visitor_base_2,
          class Tri
          = CGAL::Triangulation_2<typename Simulation_traits_t::Instantaneous_kernel,
                                           CGAL::Triangulation_data_structure_2<
            Triangulation_vertex_base_2<typename Simulation_traits_t::Instantaneous_kernel>,
  CGAL::Kinetic::Triangulation_face_base_2<Simulation_traits_t > > >,
          class Triangulation_traits_t= Triangulation_default_traits_2<Simulation_traits_t, Tri> >
class Triangulation_2:
  public Ref_counted<Triangulation_2<Simulation_traits_t, Visitor, Tri, Triangulation_traits_t> >
{

  typedef CGAL::Triangulation_2<typename Simulation_traits_t::Instantaneous_kernel,
                                         CGAL::Triangulation_data_structure_2<
    Triangulation_vertex_base_2<typename Simulation_traits_t::Instantaneous_kernel>,
    CGAL::Kinetic::Triangulation_face_base_2<Simulation_traits_t > > > Basic_Delaunay;

public:
  typedef Triangulation_traits_t Traits;
  typedef Simulation_traits_t Simulation_traits;
  typedef Triangulation_2<Simulation_traits, Visitor, Tri, 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 Triangulation_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:

  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(true);
  }

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



  //! 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
		//BOOST_PREVENT_MACRO_SUBSTITUTION(s,t) << std::endl;
        update_face(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, Face_handle e) const {
    if (e->event() !=k) {
      std::cerr << "AUDIT FAILURE orphan event " << k << std::endl;
    }
    CGAL_assertion(e->event() ==k);
  }

  void set_has_certificates(bool tf, bool no_failures=false) {
    if (tf == has_certificates_){

    } else {
      if (tf==true && del_.dimension()==2) {
        CGAL_KINETIC_LOG(CGAL::Kinetic::LOG_SOME, "DELAUNAY2: Creating certificates."<< std::endl);
        if (no_failures) {
          for (Face_iterator f = del_.all_faces_begin(); f != del_.all_faces_end(); ++f) {
            f->set_event(traits_.simulator_handle()->null_event());
          }
        }  
        /*for (typename Triangulation::All_vertices_iterator vit = del_.all_vertices_begin(); 
	     vit != del_.all_vertices_end(); ++vit) {
	  int deg=TDS_helper::low_degree(vit, del_.tds());
	  CGAL_assertion(deg >=3);
	  Vertex_handle vh= vit;
	  vh->set_neighbors(deg);
	  CGAL_TRIANGULATION_2_DEBUG(std::cout << "Set degree of " << vit->point() << " to " << deg << std::endl);
          //vit->set_neighbors_is_changed(false);
          }*/
        if (!no_failures) {
          for (Face_iterator eit = del_.all_faces_begin(); eit != del_.all_faces_end(); ++eit) {
            eit->set_event(Event_key());
            update_face(eit);
          }
        }

        watcher_.create_faces(del_.all_faces_begin(), del_.all_faces_end());
      } else if (tf==false) { 
        for (Face_iterator f = del_.all_faces_begin(); f != del_.all_faces_end(); ++f) {
          delete_certificate(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) {
    CGAL_assertion(0);
#if 0    
    // 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_.remove_vertex(vh);
    Face_handle hull_cert;
    if (has_certificates_) {
      // have to clean up hull events which are not adjacent
      Face_circulator fc= vh->incident_faces(), fe=fc;
      if (fc != NULL) {
	do {
	  delete_certificate(fc);
	  ++fc;
	} while (fc != fe);
      }
      hull_cert= hull_face(k);
      if (hull_cert != Face_handle()) {
	delete_certificate(hull_cert);
      }
    }
    // remove from triangulation
    del_.geom_traits().set_time(traits_.rational_current_time());
    del_.remove(vh);
    //new_edges_.clear();
    if (del_.dimension()==2 && has_certificates_) {
      std::vector<Face_handle> faces;