// 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; either version 3 of the License, // or (at your option) any later version. // // 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$ // $Id$ // // // Author(s) : Daniel Russel #ifndef CGAL_KINETIC_KINETIC_REGULAR_TRIANGULATION_3_H #define CGAL_KINETIC_KINETIC_REGULAR_TRIANGULATION_3_H #include #include #include #include #include #include #include #include #include #include #include #include #if defined(BOOST_MSVC) # pragma warning(push) # pragma warning(disable:4355) // complaint about using 'this' to #endif // initialize a member namespace CGAL { namespace Kinetic { namespace internal { template class Regular_3_pop_event: public Delaunay_event_base_3 { typedef Delaunay_event_base_3 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 std::ostream& operator<<(std::ostream &out, const Regular_3_pop_event &e) { e.write(out); return out; }*/ template class Regular_3_non_vertex_event: public Delaunay_event_base_3 { typedef Delaunay_event_base_3 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 Regular_3_move_event: public Regular_3_non_vertex_event { typedef Regular_3_non_vertex_event 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 std::ostream& operator<<(std::ostream &out, const Regular_3_move_event &e) { e.write(out); return out; }*/ template class Regular_3_push_event: public Regular_3_non_vertex_event { typedef Regular_3_non_vertex_event 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 std::ostream& operator<<(std::ostream &out, const Regular_3_push_event &e) { e.write(out); return out; }*/ template 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 CFB; /*typedef CGAL::Triangulation_cell_base_with_info_3, typename Traits::Instantaneous_kernel, CFB> CFBI;*/ //typedef Triangulation_labeled_edge_cell_base_3 TFB; //typedef Triangulation_labeled_facet_cell_base_3 FB; /*typedef CGAL::Triangulation_vertex_base_3 CVB; typedef CGAL::Triangulation_vertex_base_with_info_3 LVB;*/ typedef CGAL::Kinetic::Regular_triangulation_cell_base_3 FB; typedef CGAL::Kinetic::Regular_triangulation_vertex_base_3 LVB; typedef CGAL::Triangulation_data_structure_3 TDS; typedef CGAL::Regular_triangulation_3 Default_triangulation; //friend class CGAL::Delaunay_triangulation_3; }; } } } //namespace CGAL::Kinetic::internal namespace CGAL { namespace Kinetic { /*! 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 ::Default_triangulation> class Regular_triangulation_3: public Ref_counted > { private: typedef Regular_triangulation_3 This; typedef typename TraitsT::Instantaneous_kernel Instantaneous_kernel; public: typedef Regular_triangulation_3 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 Types; struct Delaunay_visitor { template void pre_insert_vertex(Point_key v, Cell_handle h) { v_.pre_insert_vertex(v, h); } template void post_insert_vertex(Vertex_handle v) { v_.post_insert_vertex(v); } template void pre_remove_vertex(Vertex_handle v) { v_.pre_remove_vertex(v); } template void post_remove_vertex(Point_key v) { v_.post_remove_vertex(v); } template void change_vertex(Vertex_handle v) { v_.change_vertex(v); } template void create_cell(Cell_handle h) { krt_->create_cell(h); v_.create_cell(h); } template void destroy_cell(Cell_handle h) { krt_->destroy_cell(h); v_.destroy_cell(h); } template void pre_edge_flip(const Edge &e) { v_.pre_edge_flip(e); } template void post_facet_flip(const Edge& e) { v_.post_facet_flip(e); } template void pre_facet_flip(const Facet &f) { v_.pre_facet_flip(f); } template void post_edge_flip(const Facet& f) { v_.post_edge_flip(f); } template void pre_move(Key k, Cell h){ v_.pre_move(k,h); } template 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 struct 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; typedef internal::Delaunay_3_edge_flip_event Edge_flip; friend class internal::Delaunay_3_edge_flip_event; typedef internal::Delaunay_3_facet_flip_event Facet_flip; friend class internal::Delaunay_3_facet_flip_event; typedef internal::Regular_3_pop_event Pop_event; friend class internal::Regular_3_pop_event; typedef internal::Regular_3_non_vertex_event Non_vertex_event; friend class internal::Regular_3_non_vertex_event; typedef internal::Regular_3_move_event Move_event; friend class internal::Regular_3_move_event ; typedef internal::Regular_3_push_event Push_event; friend class internal::Regular_3_push_event ; protected: typedef std::multimap RCMap; typedef std::map 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 { 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 KDel; CGAL_KINETIC_DECLARE_LISTENERS(typename TraitsT::Simulator, typename Traits::Active_points_3_table) public: Regular_triangulation_3(Traits tr, Visitor v= Visitor()): kdel_(Base_traits(this, tr), Delaunay_visitor(this, v)) { CGAL_KINETIC_INITIALIZE_LISTENERS(tr.simulator_handle(), tr.active_points_3_table_handle()); } const Visitor &visitor() const { return kdel_.visitor().v_; } typedef TriangulationT Triangulation; const Triangulation& triangulation() const { return kdel_.triangulation(); } CGAL_KINETIC_LISTENER1(TRIANGULATION) public: void audit_move(Event_key k, Point_key pk, Cell_handle h, int) const { CGAL_USE(k); 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_USE(k); 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_USE(k); CGAL_USE(vh); 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_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_LOG(Log::LOTS, "Verifying regular.\n"); //if (!has_certificates()) return; CGAL_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_LOG(Log::LOTS, "Pushing " << k << " into cell "); CGAL_LOG_WRITE(Log::LOTS, internal::write_cell(h, LOG_STREAM)); CGAL_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 ics; triangulation().incident_cells(vh, std::back_insert_iterator >(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_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_LOG(Log::LOTS, "Moving " << k << " from "); CGAL_LOG_WRITE(Log::LOTS, internal::write_cell(h, LOG_STREAM)); CGAL_LOG(Log::LOTS, " to "); CGAL_LOG_WRITE(Log::LOTS, internal::write_cell(h->neighbor(dir), LOG_STREAM )); CGAL_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_error(); 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(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_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_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_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 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_error(); } 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_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_LOG(Log::LOTS, "On init " << it->second << " is redundant" << std::endl); CGAL_precondition(redundant_points_[it->second]==Event_key()); handle_redundant(it->second, it->first); } CGAL_assertion(unhandled_keys_.empty()); } else { CGAL_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_error(); return Cell_handle(); } else { return kdel_.simulator()->template event(redundant_points_.find(k)->second).cell_handle(); } } void audit_structure() const { if (!has_certificates()) { for (typename RPMap::const_iterator it= redundant_points_.begin(); it != redundant_points_.end(); ++it) { CGAL_assertion(it->second==Event_key()); } for (typename RCMap::const_iterator it= redundant_cells_.begin(); it != redundant_cells_.end(); ++it) { Cell_handle h= it->first; Point_key k=it->second; Cell_handle lh= triangulation().locate(k); if (lh != h) { typename Instantaneous_kernel::Current_coordinates cco= triangulation().geom_traits().current_coordinates_object(); bool found=false; for (unsigned int i=0; i<4; ++i) { if (lh->vertex(i)->point() != Point_key() && cco(lh->vertex(i)->point()).point() == cco(k).point()) { found=true; } } CGAL_assertion(found); CGAL_USE(found); } } } else { for (typename Triangulation::Finite_vertices_iterator vit= triangulation().finite_vertices_begin(); vit != triangulation().finite_vertices_end(); ++vit) { if (triangulation().degree(vit) == 4) { CGAL_assertion_code(Point_key k= vit->point()); // it could be infinite // !! for VC CGAL_assertion(vit->info() != Event_key() || !k.is_valid()); } else { CGAL_assertion(vit->info() == Event_key()); } CGAL_assertion(redundant_points_.find(vit->point())== redundant_points_.end()); } CGAL_assertion(triangulation().infinite_vertex()->info() == Event_key()); for (typename RPMap::const_iterator it= redundant_points_.begin(); it != redundant_points_.end(); ++it) { CGAL_assertion(kdel_.vertex_handle(it->first) == Vertex_handle()); Cell_handle ch= get_cell_handle(it->first); typename RCMap::const_iterator beg= redundant_cells_.lower_bound(ch); typename RCMap::const_iterator end= redundant_cells_.upper_bound(ch); bool found=false; for (; beg != end; ++beg) { if (beg->second == it->first) { found=true; break; } } CGAL_assertion(found); CGAL_USE(found); } for (typename RCMap::const_iterator it= redundant_cells_.begin(); it != redundant_cells_.end(); ++it) { Point_key pk= it->second; Cell_handle ch= it->first; CGAL_assertion(redundant_points_.find(pk) != redundant_points_.end()); Event_key k= redundant_points_.find(pk)->second; CGAL_assertion_code(Cell_handle ech= get_cell_handle(pk)); CGAL_assertion(ch== ech); } } } protected: //! also much check for vertex_events void flip(const typename Triangulation::Edge &edge) { kdel_.flip(edge); on_geometry_changed(); } void flip(const typename KDel::Facet &flip_facet) { kdel_.flip(flip_facet); on_geometry_changed(); } CGAL::Sign orientation(Point_key k, Cell_handle h) const { kdel_.set_instantaneous_time(); int hinf=-1; for (int i=0; i< 4; ++i) { if (h->vertex(i)->point() == Point_key()) { hinf=i; } } CGAL::Sign ret=CGAL::POSITIVE; for (int i=0; i< 4; ++i) { if (hinf == -1 || hinf == i) { typename Triangulation::Facet f(h, i); typename Traits::Instantaneous_kernel::Orientation_3 o3= triangulation().geom_traits().orientation_3_object(); CGAL::Sign sn= o3((internal::vertex_of_facet(f,0)->point()), (internal::vertex_of_facet(f,1)->point()), (internal::vertex_of_facet(f,2)->point()), (k)); if (sn ==CGAL::ZERO) { CGAL_LOG(Log::SOME, "Point " << k << " lies on face ") ; CGAL_LOG_WRITE(Log::SOME, internal::write_facet( f, LOG_STREAM)); CGAL_LOG(Log::SOME, "\nPoint trajectory is " << point(k) << std::endl) ; CGAL_LOG(Log::SOME, "Triangle 0 " << point(internal::vertex_of_facet(f,0)->point()) << std::endl) ; CGAL_LOG(Log::SOME, "Triangle 1 " << point(internal::vertex_of_facet(f,1)->point()) << std::endl) ; CGAL_LOG(Log::SOME, "Triangle 2 " << point(internal::vertex_of_facet(f,2)->point()) << std::endl) ; ret=CGAL::ZERO; } else if (sn==CGAL::NEGATIVE) { ret=CGAL::NEGATIVE; return ret; } } } return ret; } void handle_redundant(Point_key k, Cell_handle h, Root_stack s) { CGAL_LOG(Log::LOTS, "Handle redundant " << k << " ") ; CGAL_LOG_WRITE(Log::LOTS, internal::write_cell( h, LOG_STREAM)); CGAL_LOG(Log::LOTS, std::endl); CGAL_precondition(orientation(k,h) != CGAL::NEGATIVE); CGAL_precondition(redundant_points_[k]==Event_key()); CGAL_assertion_code(bool found=false); for( typename RCMap::iterator it = redundant_cells_.begin(); it != redundant_cells_.end(); ++it) { CGAL_assertion_code(if(it->second==k) found=true); CGAL_assertion(h== it->first || it->second != k); } CGAL_assertion(found); redundant_points_[k]= Event_key(); if (!kdel_.has_certificates()) return; Time pst; /*if (!ps.empty()) pst = ps.top(); else pst= std::numeric_limits