regular_triangulation_3.h

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

    {
      return TraitsT::kinetic_kernel_object().weighted_orientation_3_object();
    }

    Base_traits(This_RT3 *t, const TraitsT &tr): TraitsT(tr), wr_(t) {}

    This_RT3* wrapper_handle() {
      return wr_;
    }
    const This_RT3* wrapper_handle() const
    {
      return wr_;
    }

    Active_points_3_table* active_points_3_table_handle() const {
      return TraitsT::active_points_3_table_handle(); // here
    }

    This_RT3 *wr_;
  };

  typedef internal::Delaunay_triangulation_base_3<Base_traits, Delaunay_visitor> KDel;

  typedef typename CGAL::Kinetic::Simulator_kds_listener<typename TraitsT::Simulator::Listener, This>
  Simulator_listener;
  friend  class CGAL::Kinetic::Simulator_kds_listener<typename TraitsT::Simulator::Listener, This>;
  typedef typename CGAL::Kinetic::Active_objects_listener_helper<typename TraitsT::Active_points_3_table::Listener, This>
  Moving_point_table_listener;// here
  friend class CGAL::Kinetic::Active_objects_listener_helper<typename TraitsT::Active_points_3_table::Listener, This>; // here

public:
  

  Regular_triangulation_3(Traits tr, Visitor v= Visitor()): kdel_(Base_traits(this, tr), Delaunay_visitor(this, v)),
							    listener_(NULL) {
    siml_= Simulator_listener(tr.simulator_handle(), this);
    motl_= Moving_point_table_listener(tr.active_points_3_table_handle(), this); // here
  }


  const Visitor &visitor() const
  {
    return kdel_.visitor().v_;
  }

  typedef TriangulationT Triangulation;
  const Triangulation& triangulation() const
  {
    return kdel_.triangulation();
  }

  struct Listener_core
  {
    typedef typename This::Handle Notifier_handle;
    typedef enum {TRIANGULATION}
      Notification_type;
  };
  friend class Listener<Listener_core>;
  typedef Kinetic::Listener<Listener_core> Listener;


  void audit_move(Event_key k, Point_key pk, Cell_handle h, int) const {
    CGAL_assertion(kdel_.vertex_handle(pk) == Vertex_handle());
    CGAL_assertion(redundant_points_.find(pk) != redundant_points_.end());
    CGAL_assertion(redundant_points_.find(pk)->second == k);
    audit_redundant(pk, h);
  }
  
  void audit_push(Event_key k, Point_key pk, Cell_handle h) const {
    CGAL_assertion(kdel_.vertex_handle(pk) == Vertex_handle());
    CGAL_assertion(redundant_points_.find(pk) != redundant_points_.end());
    CGAL_assertion(redundant_points_.find(pk)->second == k);
    audit_redundant(pk, h);
  }
  void audit_pop(Event_key k, Vertex_handle vh) const {
    CGAL_assertion_code(if (vh->info() != k) std::cerr << vh->info() << std::endl << k << std::endl);
    CGAL_assertion(vh->info() == k);
  }


  void audit_redundant(Point_key pk, Cell_handle h) const {
    CGAL_KINETIC_LOG(LOG_LOTS, "Auditing redundant of " << pk << std::endl);
    CGAL_assertion_code(bool found=false);
    for (typename RCMap::const_iterator cur= redundant_cells_.begin();
	 cur != redundant_cells_.end(); ++cur){
      if (cur->first == h && cur->second == pk) {
	CGAL_assertion_code(found=true);
      } else {
	CGAL_assertion(cur->second != pk);
      }
    }
    CGAL_assertion(found);
  }
  void audit() const
  {
    CGAL_KINETIC_LOG(LOG_LOTS, "Verifying regular.\n");
    //if (!has_certificates()) return;
    CGAL_KINETIC_LOG(LOG_LOTS, *this << std::endl);
    //P::instantaneous_kernel().set_time(P::simulator()->audit_time());
    kdel_.audit();
    audit_structure();
    //  RPMap redundant_points_;
    // RCMap redundant_cells_;

   
    Triangulation tri= triangulation();
    for (typename RPMap::const_iterator it= redundant_points_.begin(); it != redundant_points_.end(); ++it) {
      //Vertex_handle vh= tri.insert(it->first);
      //if (vh != Vertex_handle()) 
      CGAL_assertion_code(Vertex_handle rvh= tri.insert(it->first));
      CGAL_assertion(rvh == Vertex_handle() || rvh->point() != it->first);
      //if (has_certificates()) {
      CGAL_assertion_code(Cell_handle ch= get_cell_handle(it->first));
      CGAL_assertion_code( typename Instantaneous_kernel::Current_coordinates cco= triangulation().geom_traits().current_coordinates_object());
      CGAL_assertion_code(Cell_handle lh= triangulation().locate(it->first));
      CGAL_assertion(lh == ch
		     || cco(it->first).point() == cco(lh->vertex(0)->point()).point()
		     || cco(it->first).point() == cco(lh->vertex(1)->point()).point()
		     || cco(it->first).point() == cco(lh->vertex(2)->point()).point()
		     || cco(it->first).point() == cco(lh->vertex(3)->point()).point());
	//}
    }
  
  }

  void write(std::ostream &out) const {
    if (triangulation().dimension() != 3) return;
    kdel_.write(out);
    for (typename Triangulation::Finite_vertices_iterator vit= triangulation().finite_vertices_begin();
	 vit != triangulation().finite_vertices_end(); ++vit) {
      if (kdel_.is_degree_4(vit)) {
	out << vit->point() << ": " << vit->info() << std::endl;
      } else if (!kdel_.is_degree_4(vit) && vit->info() != Event_key()) {
	out << vit->point() << "******: " << vit->info() << std::endl;
      }
    }
    out << "Redundant points: ";
    for (typename RPMap::const_iterator it= redundant_points_.begin(); it != redundant_points_.end();
	 ++it) {
      out << it->first << " ";
    }
    out << std::endl;
    typename Delaunay::Cell_handle last;
    out << "Redundant cells: \n";
    for (typename RCMap::const_iterator it= redundant_cells_.begin(); it != redundant_cells_.end();
	 ++it) {
      if (it->first != last) {
	last= it->first;
	internal::write_cell(last, out);
	out << ": ";
      }
      out << it->second << std::endl;
    }
    out << std::endl;
    
  }



  void push(Point_key k, typename Triangulation::Cell_handle h, Root_stack rs) {
    CGAL_KINETIC_LOG(LOG_LOTS, "Pushing " << k << " into cell ");
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, internal::write_cell(h, LOG_STREAM));
    CGAL_KINETIC_LOG(LOG_LOTS, std::endl);
    
    //redundant_points_.erase(k);

    remove_redundant(h,k);
    
    //typename Triangulation::Vertex_handle vh= kdel_.push_vertex(k, h);
    kdel_.clean_cell(h);
    kdel_.visitor().pre_insert_vertex(k, h);
    // into max dim simplex?
    Vertex_handle vh=kdel_.triangulation().tds().insert_in_cell( h);
    vh->set_point(k);
    kdel_.set_vertex_handle(k, vh);
    handle_vertex(vh, rs);

    std::vector<Cell_handle> ics;
    triangulation().incident_cells(vh, std::back_insert_iterator<std::vector<Cell_handle> >(ics));
    CGAL_postcondition(ics.size() == 4);
    for (unsigned int j=0; j< ics.size(); ++j) {
      Cell_handle cc= ics[j];
      kdel_.handle_new_cell(cc);
    }
    kdel_.visitor().post_insert_vertex(vh);
 
    on_geometry_changed();
  }

  void pop(typename Triangulation::Vertex_handle vh, const Root_stack &rs) {
    CGAL_KINETIC_LOG(LOG_LOTS, "Popping " << vh->point() << std::endl);
   
    Point_key k= vh->point();
    vh->info()= Event_key();
    typename Triangulation::Cell_handle h= kdel_.pop_vertex(vh);
    CGAL_precondition(redundant_points_[k]==Event_key());
    redundant_cells_.insert(typename RCMap::value_type(h,k));
    handle_redundant(k, h, rs);
    /*if (!success) {
      std::cerr << "dropped a vertex when popped.\n";
      redundant_points_[k]=kdel_.simulator()->null_event();
      }*/
    //CGAL_postcondition(success);
    on_geometry_changed();
  }

  void move(Point_key k, typename Triangulation::Cell_handle h, int dir, const Root_stack &rs) {
    kdel_.visitor().pre_move(k,h);
    CGAL_KINETIC_LOG(LOG_LOTS, "Moving " << k << " from ");
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, internal::write_cell(h, LOG_STREAM));
    CGAL_KINETIC_LOG(LOG_LOTS, " to ");
    CGAL_KINETIC_LOG_WRITE(LOG_LOTS, internal::write_cell(h->neighbor(dir), LOG_STREAM ));
    CGAL_KINETIC_LOG(LOG_LOTS, std::endl);
    typename Triangulation::Cell_handle neighbor = h->neighbor(dir);
    
    bool hinf=false;
    for (unsigned int i=0; i<4; ++i) {
      if (neighbor->vertex(i)== triangulation().infinite_vertex()) {
	hinf=true;
	break;
      }
    }
    if (hinf) {
      //insert(k, neighbor);
      push(k, h, rs);
    } else {
      remove_redundant(h, k);
      CGAL_precondition(redundant_points_[k]==Event_key());
      redundant_cells_.insert(typename RCMap::value_type(neighbor, k));
      handle_redundant(k, neighbor);
    }
    kdel_.visitor().post_move(k,neighbor);
  }

  //! remove an object
  /*!
    See if it is redundant. If so, remove it from the list and delete its certificate.
    Otherwise, pass it along.
  */
  void erase(Point_key ) {
    CGAL_assertion(0);
    on_geometry_changed();
  }

  void set(Point_key k) {
    if (!kdel_.has_certificates()) return;
    if (kdel_.vertex_handle(k) != NULL) {
      kdel_.change_vertex(k);
      if (kdel_.is_degree_4(kdel_.vertex_handle(k))) {
	handle_vertex(kdel_.vertex_handle(k));
      }
    } else {
      //kdel_.simulator()->template event<Non_vertex_event>(redundant_points_[k]);
      typename Triangulation::Cell_handle h= get_cell_handle(k);
      kdel_.simulator()->delete_event(redundant_points_[k]);
      redundant_points_.erase(k);
      CGAL_precondition(redundant_points_[k]==Event_key());
      handle_redundant(k, h);
    }
  }

  void insert(Point_key k, Cell_handle h) {
    // almost the same as push
    // if insertion fails, then handle redundant
    CGAL_KINETIC_LOG(LOG_LOTS, "Inserth " << k << std::endl);
    kdel_.set_instantaneous_time();
    typename Instantaneous_kernel::Current_coordinates cco= triangulation().geom_traits().current_coordinates_object();
    typename Triangulation::Vertex_handle vh;
    if (h!= Cell_handle()) {
      for (unsigned int i=0; i<4; ++i) {
	if (h->vertex(i) != Vertex_handle()
	    && h->vertex(i)->point() != Point_key() 
	    && cco(h->vertex(i)->point()).point() == cco(k).point()) {
	  CGAL_KINETIC_LOG(LOG_SOME, "Point " << k << " is on point " 
			   << h->vertex(i)->point() << "\n");
	  vh= h->vertex(i);
	  break;
	}
      }
      if (vh== Vertex_handle()) {
	vh=kdel_.insert(k, h);
      } 
    } else {
      vh= kdel_.insert(k);
    }
   
    
    post_insert(k,vh, h);
  }

  void insert(Point_key k) {
    // almost the same as push
    // if insertion fails, then handle redundant
    CGAL_KINETIC_LOG(LOG_LOTS, "Insert " << k << std::endl);

    kdel_.set_instantaneous_time();
    Cell_handle h= triangulation().locate(k);

    return insert(k, h);
  }

  void post_insert(Point_key k, Vertex_handle vh, Cell_handle h) {
    if (vh != Vertex_handle() && vh->point() != k) {
      if (!has_certificates()) {
	unhandled_keys_.push_back(k);
	return;
      } else {
	typename Instantaneous_kernel::Current_coordinates 
	  cco= triangulation().geom_traits().current_coordinates_object();
	if (cco(vh->point()).weight() < cco(k).weight()) {
	  // swap them
	  Point_key rp = kdel_.replace_vertex(vh, k);
	  degen_handle_redundant(rp,vh);
	  if (kdel_.has_certificates() && kdel_.is_degree_4(vh)) {
	    handle_vertex(vh);
	  }
	} else {
	  vh= Vertex_handle();
	  degen_handle_redundant(k, vh);
	  // need to try various cells, not just one
	}
      }
    } else if (vh == Vertex_handle()) {
      CGAL_precondition(triangulation().geom_traits().time() 
			==kdel_.simulator()->current_time());
     
      if (h== Cell_handle()) {
	h = triangulation().locate(k);
      }
      CGAL_precondition(redundant_points_[k]==Event_key());
      redundant_cells_.insert(typename RCMap::value_type(h, k));
      handle_redundant(k,h);
    } else if (kdel_.has_certificates() && kdel_.is_degree_4(vh)){
      handle_vertex(vh); 
    }

    on_geometry_changed();
  }

  void degen_handle_redundant(Point_key k, Vertex_handle vh) {
    std::vector<Cell_handle> ics;
    triangulation().incident_cells(vh, std::back_inserter(ics));
    kdel_.set_instantaneous_time(true);
    for (unsigned int i=0; i< ics.size(); ++i) {
      if (try_handle_redundant(k, ics[i])) return;
    }
    CGAL_assertion(0);
  }

public:
  void set_has_certificates(bool tf) {
    if (tf == has_certificates()) return;
    if (tf==false) {
      for (typename Triangulation::Finite_vertices_iterator vit= triangulation().finite_vertices_begin();
	   vit != triangulation().finite_vertices_end(); ++vit) {
	if (vit->info() != Event_key()) {
	  kdel_.simulator()->delete_event(vit->info());
	  vit->info()=  Event_key();
	}
      }
      for (typename RPMap::iterator it = redundant_points_.begin(); it != redundant_points_.end(); ++it) {
	kdel_.simulator()->delete_event(it->second);
	it->second= Event_key();
      }
      kdel_.set_has_certificates(false);
    }
    else {
      kdel_.set_has_certificates(true);
      if (kdel_.triangulation().dimension()==3) {
	// must be first so the vertex handles are set
	CGAL_KINETIC_LOG(LOG_LOTS, "Setting up certificates.\n");
	for (typename Triangulation::Finite_vertices_iterator vit= triangulation().finite_vertices_begin();
	     vit != triangulation().finite_vertices_end(); ++vit) {
	  /*if (kdel_.is_degree_4( vit)) {
	    handle_vertex(vit);
	    }*/
	  CGAL_assertion(!kdel_.is_degree_4(vit) || vit->info() != Event_key());
	}
	for (typename RCMap::iterator it= redundant_cells_.begin();
	     it != redundant_cells_.end(); ++it) {
	  CGAL_KINETIC_LOG(LOG_LOTS, "On init " << it->second 
			   << " is redundant" << std::endl);
	  typename Triangulation::Cell_handle h= it->first;
	  CGAL_precondition(redundant_points_[it->second]==Event_key());
	  handle_redundant(it->second, it->first);
	}
	CGAL_assertion(unhandled_keys_.empty());
      } else {
	CGAL_KINETIC_LOG(LOG_LOTS, "Triangulation does not have dimension 3.\n");
      }
    }

  }

  bool has_certificates() const
  {
    return kdel_.has_certificates();
  }



protected:

  Cell_handle get_cell_handle(Point_key k) const {
    CGAL_precondition(redundant_points_.find(k) != redundant_points_.end());
    if (redundant_points_.find(k)->second == kdel_.simulator()->null_event()
	|| !has_certificates()) {
      for (typename RCMap::const_iterator it = redundant_cells_.begin();
	   it != redundant_cells_.end(); ++it){
	if (it->second == k) return it->first;
      }
      CGAL_assertion(0);
      return Cell_handle();