delaunay_triangulation_base_3.h

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

	  clean_cell(cells[i]);
	}
      }
      
   
      //! \todo replace by insert_in_hole

      CGAL_KINETIC_LOG(LOG_LOTS, "Inserting " << k << " at time " 
		       << triangulation_.geom_traits().time() << "\n");
      vh=triangulation_.insert_in_hole(k, cells.begin(), cells.end(), 
						     bfacets.front().first, bfacets.front().second);
    } else {
      vh= triangulation_.insert(k,h);
    }
    set_vertex_handle(k,vh);
    if (triangulation_.dimension() == 3 && vh != Vertex_handle()) {
      change_vertex(k);
    }
    
    CGAL_expensive_postcondition(audit_structure());
    v_.post_insert_vertex(vh);
    return vh;
  }

  bool has_certificates() const
  {
    return has_certificates_;
  }

  void set_instantaneous_time(bool after=false) const {
    if (!triangulation_.geom_traits().has_time() || triangulation_.geom_traits().time() != simulator()->current_time()) {
      typename Simulator::NT nt= simulator()->next_time_representable_as_nt();
      
      if (simulator()->current_time() == nt) {
	if (after) {
	  triangulation_.geom_traits().set_time_to_after(nt);
	} else {
	  triangulation_.geom_traits().set_time(nt);
	}
      } else {
	CGAL_KINETIC_LOG(LOG_SOME, "Warning, insertion of points at non-rational times is slow.\n");
	if (after) {
	  triangulation_.geom_traits().set_time_to_after(simulator()->current_time());
	} else {
	  triangulation_.geom_traits().set_time(simulator()->current_time());
	}
      }
    }
  }

  void set_has_certificates(bool b) {
    if (!has_certificates_ && b) {
      if (triangulation().dimension() == 3) {
	for (All_edges_iterator eit = triangulation_.all_edges_begin();
	     eit != triangulation_.all_edges_end(); ++eit) {
	  CGAL_assertion(!has_event(*eit));
	}
	for (All_facets_iterator eit = triangulation_.all_facets_begin();
	     eit != triangulation_.all_facets_end(); ++eit) {
	  CGAL_assertion(!has_event(*eit));
	}
	create_all_certificates();
	has_certificates_=true;
      }
    } else if (has_certificates_ && !b) {
      destroy_all_certificates();
      has_certificates_=false;
    }
  }

 void create_all_certificates() {
    CGAL_precondition(!has_certificates_);
 
    for (All_edges_iterator eit = triangulation_.all_edges_begin();
	 eit != triangulation_.all_edges_end(); ++eit) {
      if (is_degree_3(*eit) && !has_degree_4_vertex(*eit)) {
	make_certificate(*eit);
      }
    }
    for (All_facets_iterator eit = triangulation_.all_facets_begin();
	 eit != triangulation_.all_facets_end(); ++eit) {
      if (!has_degree_3_edge(*eit)) {
	make_certificate(*eit);
      }
    }
    for (All_cells_iterator cit= triangulation_.all_cells_begin(); 
	 cit != triangulation_.all_cells_end(); ++cit) {
      v_.create_cell(cit);
    }
  }


  void destroy_all_certificates() {
    //vhs_.clear();
    CGAL_precondition(has_certificates_);
    for (All_edges_iterator eit = triangulation_.all_edges_begin();
	 eit != triangulation_.all_edges_end(); ++eit) {
      Event_key k= triangulation_.label(*eit);
      if ( k != Event_key() ) {
	simulator()->delete_event(k);
	triangulation_.set_label(*eit,Event_key());
      }
    }
    for (All_facets_iterator eit = triangulation_.all_facets_begin();
	 eit != triangulation_.all_facets_end(); ++eit) {
      Event_key k= triangulation_.label(*eit);
      if (k != Event_key() ) {
	simulator()->delete_event(k);
	triangulation_.set_label(*eit,Event_key());
      }
      //}
    }
    for (All_cells_iterator cit= triangulation_.all_cells_begin(); 
	 cit != triangulation_.all_cells_end(); ++cit) {
      v_.destroy_cell(cit);
    }
  }
 


  Facet flip(const Edge &edge) {
    v_.pre_edge_flip(edge);
    
    CGAL_KINETIC_LOG(LOG_LOTS,"\n\nFlipping edge ");
    CGAL_KINETIC_LOG(LOG_LOTS,edge.first->vertex(edge.second)->point() << "--" 
		     << edge.first->vertex(edge.third)->point() << std::endl);
    CGAL_assertion(triangulation_.tds().is_edge(edge.first, edge.second, edge.third) || print());
    if (has_degree_4_vertex(edge)) {
      CGAL_KINETIC_LOG(LOG_LOTS,"dropping edge since endpoint is degree 4\n ");
      triangulation_.set_label(edge, simulator()->null_event());
      return Facet();
    }
    CGAL_assertion(!has_degree_4_vertex(edge));

    Vertex_handle poles[2];
    poles[0]= edge.first->vertex(edge.second);
    poles[1]= edge.first->vertex(edge.third);
    int polesi[2];
    polesi[0] = edge.first->index(poles[0]);
    polesi[1]= edge.first->index(poles[1]);

    typename Simulator::Event_key failed_key = triangulation_.label(edge);
    CGAL_precondition(failed_key.is_valid());
    Certificate ore= extract_root_stack(failed_key);
   
    Facet neighboring_facet= triangulation_.opposite(Facet(edge.first, polesi[0]));

    triangulation_.set_label(edge, typename Simulator::Event_key());

    // handle the cross edges to make sure that they are no longer edge flips
    {
      Cell_circulator cc= triangulation_.incident_cells(edge), ce= cc;
      do {
	Cell_handle h=cc;
	clean_cell(h);
      } while (++cc != ce);
    }

    triangulation_.tds().flip_flippable(edge);
    CGAL_expensive_assertion(labeling_is_valid());
    /*if (verbose){
      write_labeled_state();
      }*/

    CGAL_assertion(triangulation_.tds().is_facet(neighboring_facet.first, neighboring_facet.second));
    Facet internal_facet= triangulation_.opposite(neighboring_facet);

    Cell_handle cells[2];
    cells[1]= internal_facet.first;
    polesi[1]= cells[1]->index(poles[1]);
    cells[0]= cells[1]->neighbor(polesi[1]);
    polesi[0]= cells[0]->index(poles[0]);

    Facet middle_facet(cells[0], polesi[0]);
    triangulation_.clear_cell_labels(middle_facet.first);
    triangulation_.clear_cell_labels(triangulation_.opposite(middle_facet).first);

    if (ore.will_fail()) {
      typename Simulator::Time t= ore.failure_time();
      ore.pop_failure_time();
      typename Simulator::Event_key k= simulator()->new_event(t, 
							      Facet_flip_event(ore, middle_facet, tr_.wrapper_handle()));
      
      triangulation_.set_label(middle_facet, k);
    } else {
      triangulation_.set_label(middle_facet, simulator()->null_event());
    }

    for (int c=0; c<2; ++c) {
      handle_new_cell(cells[c]);
    }

    CGAL_postcondition(audit_structure());
    v_.post_edge_flip(middle_facet);
    return middle_facet;
  }











  Edge flip(const Facet &flip_facet) {
    v_.pre_facet_flip(flip_facet);
    Vertex_handle poles[2];
    Facet other_flip_facet= triangulation_.opposite(flip_facet);
    poles[0]= flip_facet.first->vertex(flip_facet.second);
    poles[1]= other_flip_facet.first->vertex(other_flip_facet.second);
    
    CGAL_KINETIC_LOG(LOG_LOTS,"\n\nFlipping facet ");
    CGAL_KINETIC_LOG(LOG_LOTS,flip_facet.first->vertex((flip_facet.second+1)%4)->point() << "--"
		     << flip_facet.first->vertex((flip_facet.second+2)%4)->point() << "--"
		     << flip_facet.first->vertex((flip_facet.second+3)%4)->point() << std::endl);
    //triangulation_.write_labeled_facet(flip_facet, log_lots() );
    CGAL_KINETIC_LOG(LOG_LOTS," with poles " << poles[0]->point() << ", " << poles[1]->point());
    CGAL_KINETIC_LOG(LOG_LOTS,std::endl);
    
    CGAL_assertion(triangulation_.tds().is_facet(flip_facet.first, flip_facet.second) || print());

    Event_key failed_key= triangulation_.label(flip_facet);
    Certificate ore= extract_root_stack(failed_key);
    if (ore.will_fail()) {
      CGAL_KINETIC_LOG(LOG_LOTS, "Next root of certificate is " << ore.failure_time() << std::endl);
    } else {
      CGAL_KINETIC_LOG(LOG_LOTS, "Certificate will never fail" << std::endl);
    }
    triangulation_.set_label(flip_facet, Event_key());

    //typename P::Event_key index= triangulation_.label(flip_facet);

    Facet inside_facet(flip_facet.first, (flip_facet.second+1)%4);
    Facet neighbor_facet= triangulation_.opposite(inside_facet);
    Cell_handle cells[2]= {flip_facet.first, other_flip_facet.first};
    CGAL_assertion(neighbor_facet.first != cells[0] && neighbor_facet.first != cells[1]);

    // go around and change the handler for each edge if it is degree 3. Don't have to look off cell
    for (int c=0; c<2; ++c) {
      clean_cell(cells[c]);
    }
   
   
    triangulation_.tds().flip_flippable(flip_facet);

    CGAL_assertion(triangulation_.tds().is_facet(neighbor_facet.first, neighbor_facet.second));

    Facet a_facet= triangulation_.opposite(neighbor_facet);
    Cell_handle a_cell= a_facet.first;

    Edge central_edge(a_cell, a_cell->index(poles[0]), a_cell->index(poles[1]));

    Cell_circulator cc= triangulation_.incident_cells(central_edge), ce=cc;
    do {
      triangulation_.clear_cell_labels(cc);
    } while (++cc != ce);


    if (ore.will_fail()) {
      typename Simulator::Time t= ore.failure_time();
      ore.pop_failure_time();
      typename Simulator::Event_key k= simulator()->new_event(t, Edge_flip_event(ore, central_edge, tr_.wrapper_handle()));
      triangulation_.set_label(central_edge, k);
    } else {
      triangulation_.set_label(central_edge, simulator()->null_event());
    }
    
    CGAL_expensive_assertion(labeling_is_valid());

    {
      Cell_circulator cc= triangulation_.incident_cells(central_edge), ce=cc;
      do {
	handle_new_cell(cc);
      } while (++cc != ce);
    }

    CGAL_postcondition(audit_structure());
    v_.post_facet_flip(central_edge);
    return central_edge;
  }











  void audit() const
  {
    CGAL_KINETIC_LOG(LOG_SOME, "Verifying at time " << simulator()->audit_time() << ".\n");
    set_instantaneous_time();
    //CGAL_precondition(triangulation_.geom_traits().time()== simulator()->audit_time());
    //triangulation_.geom_traits().set_time(simulator().rational_current_time());
    audit_structure();
    triangulation_.is_valid(true);
  }









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

  Triangulation& triangulation() {
    return triangulation_;
  }

  const Moving_object_table* moving_object_table() const
  {
    return tr_.active_points_3_table_handle();
  }

  Simulator* simulator() {
    return tr_.simulator_handle();
  }

  const Simulator* simulator() const
  {
    return tr_.simulator_handle();
  }

  const Point& point(Point_key k) const
  {
    return moving_object_table()->at(k);
  }

  Vertex_handle vertex_handle(Point_key k) const
  {
    if (k.is_valid() && k.to_index() < vhs_.size()) {
      return vhs_[k.to_index()];
    }
    else {
      return NULL;
    }
  }

  void set_vertex_handle(Point_key k, Vertex_handle vh) {
    CGAL_precondition(k != Point_key());
    unsigned int bin= k.to_index();
    while (vhs_.size() <= bin) {
      vhs_.push_back(NULL);
    }
    /*if (vhs_.size() <=bin){
      vhs_.resize(bin+1);
      }*/
    vhs_[k.to_index()]=vh;
  }

  typename TraitsT::Side_of_oriented_sphere_3 power_test_object() const
  {
    return soc_;
  };
  typename TraitsT::Orientation_3 orientation_object() const
  {
    return o3_;
  }
  Certificate extract_root_stack(Event_key k) const
  {
    //typename Simulator::Event_handle<Event_base> eh(simulator()->event(k, Event_base()));
    //typename Simulator::Root_stack s= eh.pointer()->root_stack();
    return simulator()->template event<Event_base>(k/*, Event_base()*/).root_stack();
  }
  /*
    typename Simulator::Time extract_time(Event_key k) const {
    return simulator()->event<Facet_flip_event::Base>(k)->time();
    }*/



  void make_certificate( const Edge &e,
			 const typename Simulator::Time& st) {
    CGAL_KINETIC_LOG(LOG_LOTS, "making certificate for edge ");
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, triangulation_.write_edge(e, LOG_STREAM));
    CGAL_KINETIC_LOG(LOG_LOTS, std::endl);
    CGAL_precondition(is_degree_3(e));
    CGAL_precondition_code(Facet_circulator fc= triangulation_.incident_facets(e));
    CGAL_precondition_code(Facet_circulator fe= fc);
    CGAL_precondition_code(do {
      );
			   CGAL_precondition(!has_event(*fc));
			   CGAL_precondition_code(++fc);
			   CGAL_precondition_code(
						  }while(fc != fe));

    CGAL_precondition(is_degree_3(e));
    CGAL_precondition(!has_degree_4_vertex(e));
    CGAL_precondition(!has_event(e));
    
    Certificate s= root_stack(e, st);
   
    if (s.will_fail()) {
      CGAL_KINETIC_LOG(LOG_LOTS,"Failure time is " << s.failure_time() << std::endl);
      typename Simulator::Time t= s.failure_time();
      s.pop_failure_time();
      if (s.will_fail()) {
	CGAL_KINETIC_LOG(LOG_LOTS, "Next root of this cert is " << s.failure_time() << std::endl);
      }
      typename Simulator::Event_key k=  simulator()->new_event(t, Edge_flip_event(s, e, tr_.wrapper_handle()));
      triangulation_.set_label(e, k);
    } else {
      CGAL_KINETIC_LOG(LOG_LOTS,"Certificate will not fail "<< std::endl);
      triangulation_.set_label(e, simulator()->null_event());
    }
  }
  void make_certificate( const Edge &e) {
    make_certificate(e, simulation_traits_object().simulator_handle()->current_time());
  }





  void make_certificate( const Facet &e,
			 const typename Simulator::Time &st) {
    CGAL_precondition(!has_event(e));
    CGAL_KINETIC_LOG(LOG_LOTS, "making certificate for facet ");
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, triangulation_.write_facet(e, LOG_STREAM ));
    //triangulation_.write_facet(e, log_lots());
    CGAL_KINETIC_LOG(LOG_LOTS,  std::endl);

    CGAL_precondition(!has_degree_3_edge(e));
    for (int i=0; i<3; ++i) {
      CGAL_precondition(triangulation_.label(triangulation_.edge(e, i)) == Event_key());
    }
    Certificate s= root_stack(e, st);
    if (s.will_fail()) {
      typename Simulator::Time t= s.failure_time();
      CGAL_KINETIC_LOG(LOG_LOTS, "Failure time is " << t << std::endl);
      s.pop_failure_time();
      if (s.will_fail()) {
	CGAL_KINETIC_LOG(LOG_LOTS, "Next root of this cert is " << s.failure_time() << std::endl);
      }
      typename Simulator::Event_key k= simulator()->new_event(t, Facet_flip_event(s, e, tr_.wrapper_handle()));
      triangulation_.set_label(e, k);
    } else {
      CGAL_KINETIC_LOG(LOG_LOTS, "Certificate will not fail" << std::endl);
      triangulation_.set_label(e, simulator()->null_event());
    }
  }

   void make_certificate( const Facet &e) {
     make_certificate(e,
		      simulation_traits_object().simulator_handle()->current_time());
   }

 

  template <class Oit>
  void point_keys(const Facet &f, Oit out) const
  {
    int hinf=-1;