|
BWAPI
|
00001 // Copyright (c) 2003,2004,2005,2006 INRIA Sophia-Antipolis (France) and 00002 // Notre Dame University (U.S.A.). All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under 00005 // the terms of the Q Public License version 1.0. 00006 // See the file LICENSE.QPL distributed with CGAL. 00007 // 00008 // Licensees holding a valid commercial license may use this file in 00009 // accordance with the commercial license agreement provided with the software. 00010 // 00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00013 // 00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Segment_Delaunay_graph_2/include/CGAL/Segment_Delaunay_graph_2.h $ 00015 // $Id: Segment_Delaunay_graph_2.h 48908 2009-04-26 14:03:12Z spion $ 00016 // 00017 // 00018 // Author(s) : Menelaos Karavelas <mkaravel@cse.nd.edu> 00019 00020 00021 00022 #ifndef CGAL_SEGMENT_DELAUNAY_GRAPH_2_H 00023 #define CGAL_SEGMENT_DELAUNAY_GRAPH_2_H 00024 00025 #include <iostream> 00026 #include <vector> 00027 #include <list> 00028 #include <set> 00029 #include <map> 00030 #include <algorithm> 00031 #include <boost/tuple/tuple.hpp> 00032 00033 #include <CGAL/Segment_Delaunay_graph_2/basic.h> 00034 00035 #include <CGAL/Triangulation_2.h> 00036 #include <CGAL/Segment_Delaunay_graph_storage_traits_2.h> 00037 #include <CGAL/Segment_Delaunay_graph_vertex_base_2.h> 00038 #include <CGAL/Triangulation_data_structure_2.h> 00039 #include <CGAL/Triangulation_face_base_2.h> 00040 00041 #include <CGAL/in_place_edge_list.h> 00042 #include <CGAL/Segment_Delaunay_graph_2/edge_list.h> 00043 #include <CGAL/Segment_Delaunay_graph_2/Traits_wrapper_2.h> 00044 #include <CGAL/Segment_Delaunay_graph_2/Constructions_C2.h> 00045 00046 #include <CGAL/Iterator_project.h> 00047 #include <CGAL/utility.h> 00048 00049 00050 /* 00051 Conventions: 00052 ------------ 00053 1. we treat segments as open; the endpoints are separate objects 00054 2. a segment of length zero is treated as a point 00055 3. a point is deleted only if it has no segment adjacent to it 00056 4. when a segment is deleted it's endpoints are not deleted 00057 5. the user can force the deletion of endpoints; this is only done 00058 if condition 3 is met. 00059 6. when objects are written to a stream we distinguish between 00060 points and segments; points start by a 'p' and segments by an 's'. 00061 */ 00062 00063 00064 CGAL_BEGIN_NAMESPACE 00065 00066 CGAL_SEGMENT_DELAUNAY_GRAPH_2_BEGIN_NAMESPACE 00067 00068 namespace Internal { 00069 00070 template<typename Edge, typename LTag> struct Which_list; 00071 00072 // use the in-place edge list 00073 template<typename E> 00074 struct Which_list<E,Tag_true> 00075 { 00076 typedef E Edge; 00077 typedef In_place_edge_list<Edge> List; 00078 }; 00079 00080 // do not use the in-place edge list 00081 template<typename E> 00082 struct Which_list<E,Tag_false> 00083 { 00084 typedef E Edge; 00085 // change the following to Tag_false in order to use 00086 // CGAL's Unique_hash_map 00087 typedef Tag_true Use_stl_map_tag; 00088 typedef Edge_list<Edge,Use_stl_map_tag> List; 00089 }; 00090 00091 00092 template < class Node > 00093 struct Project_site_2 { 00094 typedef Node argument_type; 00095 typedef typename Node::Site_2 Site; 00096 typedef Site result_type; 00097 Site& operator()(const Node& x) const { 00098 static Site s; 00099 s = x.site(); 00100 return s; 00101 } 00102 // const Site& operator()(const Node& x) const { return x.site(); } 00103 }; 00104 00105 template < class Node, class Site_t > 00106 struct Project_input_to_site_2 { 00107 typedef Node argument_type; 00108 typedef Site_t Site; 00109 typedef Site result_type; 00110 Site& operator()(const Node& x) const { 00111 static Site s; 00112 if ( boost::tuples::get<2>(x) /*x.third*/ ) { // it is a point 00113 // s = Site::construct_site_2(*x.first); 00114 s = Site::construct_site_2( *boost::tuples::get<0>(x) ); 00115 } else { 00116 // s = Site::construct_site_2(*x.first, *x.second); 00117 s = Site::construct_site_2 00118 (*boost::tuples::get<0>(x), *boost::tuples::get<1>(x)); 00119 } 00120 return s; 00121 } 00122 }; 00123 00124 template<typename T, typename U> 00125 struct Check_type_equality_for_info 00126 { 00127 Check_type_equality_for_info() 00128 { 00129 ERROR__INFO_TYPES_OF_insert_AND_Storage_traits_with_info_2_MUST_MATCH 00130 (T(), U()); 00131 } 00132 }; 00133 00134 template<typename T> 00135 struct Check_type_equality_for_info<T,T> 00136 { 00137 }; 00138 00139 } // namespace Internal 00140 00141 CGAL_SEGMENT_DELAUNAY_GRAPH_2_END_NAMESPACE 00142 00143 00144 template<class Gt, class ST, class STag, class D_S, class LTag > 00145 class Segment_Delaunay_graph_hierarchy_2; 00146 00147 00148 00149 template<class Gt, 00150 class ST = Segment_Delaunay_graph_storage_traits_2<Gt>, 00151 class D_S = Triangulation_data_structure_2 < 00152 Segment_Delaunay_graph_vertex_base_2<ST>, 00153 Triangulation_face_base_2<Gt> >, 00154 class LTag = Tag_false > 00155 class Segment_Delaunay_graph_2 00156 : private Triangulation_2< 00157 Segment_Delaunay_graph_traits_wrapper_2<Gt>, D_S > 00158 { 00159 friend class Segment_Delaunay_graph_hierarchy_2<Gt,ST,Tag_true,D_S,LTag>; 00160 friend class Segment_Delaunay_graph_hierarchy_2<Gt,ST,Tag_false,D_S,LTag>; 00161 protected: 00162 // LOCAL TYPES 00163 //------------ 00164 typedef Segment_Delaunay_graph_2<Gt,ST,D_S,LTag> Self; 00165 00166 typedef Segment_Delaunay_graph_traits_wrapper_2<Gt> Modified_traits; 00167 typedef Triangulation_2<Modified_traits,D_S> DG; 00168 typedef DG Delaunay_graph; 00169 00170 typedef LTag List_tag; 00171 00172 public: 00173 // PUBLIC TYPES 00174 //------------- 00175 typedef D_S Data_structure; 00176 typedef D_S Triangulation_data_structure; 00177 typedef Gt Geom_traits; 00178 typedef ST Storage_traits; 00179 typedef typename Gt::Site_2 Site_2; 00180 typedef typename Gt::Point_2 Point_2; 00181 00182 typedef typename D_S::Edge Edge; 00183 typedef typename D_S::Vertex_handle Vertex_handle; 00184 typedef typename D_S::Face_handle Face_handle; 00185 typedef typename D_S::Vertex Vertex; 00186 typedef typename D_S::Face Face; 00187 00188 typedef typename D_S::size_type size_type; 00189 00190 typedef typename D_S::Vertex_circulator Vertex_circulator; 00191 typedef typename D_S::Edge_circulator Edge_circulator; 00192 typedef typename D_S::Face_circulator Face_circulator; 00193 00194 typedef typename D_S::Face_iterator All_faces_iterator; 00195 typedef typename D_S::Vertex_iterator All_vertices_iterator; 00196 typedef typename D_S::Edge_iterator All_edges_iterator; 00197 00198 typedef typename DG::Finite_faces_iterator Finite_faces_iterator; 00199 typedef typename DG::Finite_vertices_iterator Finite_vertices_iterator; 00200 typedef typename DG::Finite_edges_iterator Finite_edges_iterator; 00201 00202 typedef typename Storage_traits::Point_container Point_container; 00203 typedef typename Storage_traits::Point_handle Point_handle; 00204 typedef typename Storage_traits::const_Point_handle const_Point_handle; 00205 00206 protected: 00207 typedef typename Geom_traits::Arrangement_type_2 AT2; 00208 typedef typename AT2::Arrangement_type Arrangement_type; 00209 00210 // these containers should have point handles and should replace the 00211 // point container... 00212 typedef boost::tuples::tuple<Point_handle,Point_handle,bool> Site_rep_2; 00213 00214 struct Site_rep_less_than { 00215 // less than for site reps 00216 bool operator()(const Site_rep_2& x, const Site_rep_2& y) const { 00217 Point_handle x1 = boost::tuples::get<0>(x); 00218 Point_handle y1 = boost::tuples::get<0>(y); 00219 00220 if ( &(*x1) < &(*y1) ) { return true; } 00221 if ( &(*y1) < &(*x1) ) { return false; } 00222 00223 Point_handle x2 = boost::tuples::get<1>(x); 00224 Point_handle y2 = boost::tuples::get<1>(y); 00225 00226 return &(*x2) < &(*y2); 00227 } 00228 }; 00229 00230 typedef std::set<Site_rep_2,Site_rep_less_than> Input_sites_container; 00231 typedef typename Input_sites_container::const_iterator 00232 All_inputs_iterator; 00233 00234 typedef 00235 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Internal:: 00236 Project_input_to_site_2<Site_rep_2, Site_2> 00237 Proj_input_to_site; 00238 00239 typedef CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Internal::Project_site_2<Vertex> 00240 Proj_site; 00241 00242 struct Point_handle_less_than { 00243 // less than 00244 bool operator()(const const_Point_handle& x, 00245 const const_Point_handle& y) const { 00246 return &(*x) < &(*y); 00247 } 00248 }; 00249 00250 typedef std::pair<Point_handle,Point_handle> Point_handle_pair; 00251 00252 typedef std::map<Point_handle,Point_handle,Point_handle_less_than> 00253 Handle_map; 00254 00255 public: 00256 typedef Iterator_project<All_inputs_iterator, Proj_input_to_site> 00257 Input_sites_iterator; 00258 00259 typedef Iterator_project<Finite_vertices_iterator, 00260 Proj_site> Output_sites_iterator; 00261 protected: 00262 // LOCAL VARIABLE(S) 00263 //------------------ 00264 // the container of points 00265 Point_container pc_; 00266 Input_sites_container isc_; 00267 Storage_traits st_; 00268 00269 protected: 00270 // MORE LOCAL TYPES 00271 //----------------- 00272 typedef typename Gt::Intersections_tag Intersections_tag; 00273 00274 typedef std::map<Face_handle,bool> Face_map; 00275 typedef std::vector<Edge> Edge_vector; 00276 00277 typedef std::list<Vertex_handle> Vertex_list; 00278 typedef typename Vertex_list::iterator Vertex_list_iterator; 00279 00280 typedef Triple<Vertex_handle,Vertex_handle,Vertex_handle> 00281 Vertex_triple; 00282 00283 typedef Vertex_handle Vh_triple[3]; 00284 typedef std::map<Face_handle,Sign> Sign_map; 00285 00286 typedef std::pair<Face_handle,Face_handle> Face_pair; 00287 00288 typedef typename Storage_traits::Storage_site_2 Storage_site_2; 00289 00290 // the edge list 00291 typedef typename 00292 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Internal::Which_list<Edge,List_tag>::List 00293 List; 00294 00295 public: 00296 // CREATION 00297 //--------- 00298 Segment_Delaunay_graph_2(const Geom_traits& gt = Geom_traits(), 00299 const Storage_traits& st = Storage_traits()) 00300 : DG(gt), st_(st) {} 00301 00302 template< class Input_iterator > 00303 Segment_Delaunay_graph_2(Input_iterator first, Input_iterator beyond, 00304 const Geom_traits& gt = Geom_traits(), 00305 const Storage_traits& st = Storage_traits()) 00306 : DG(gt), st_(st) 00307 { 00308 insert(first, beyond); 00309 } 00310 00311 Segment_Delaunay_graph_2(const Self& other); 00312 Self& operator=(const Self& other); 00313 00314 public: 00315 // ACCESS METHODS 00316 // -------------- 00317 const Geom_traits& geom_traits() const { return DG::geom_traits(); } 00318 00319 const Storage_traits& storage_traits() const { return st_; } 00320 00321 const Data_structure& data_structure() const { return this->_tds; } 00322 const Triangulation_data_structure& tds() const { return this->_tds; } 00323 const Point_container& point_container() const { return pc_; } 00324 00325 inline size_type number_of_input_sites() const { 00326 return isc_.size(); 00327 } 00328 00329 inline size_type number_of_output_sites() const { 00330 return number_of_vertices(); 00331 } 00332 00333 inline size_type number_of_vertices() const { 00334 return DG::number_of_vertices(); 00335 } 00336 00337 inline size_type number_of_faces() const { 00338 return DG::number_of_faces(); 00339 } 00340 00341 inline Vertex_handle infinite_vertex() const { 00342 return DG::infinite_vertex(); 00343 } 00344 00345 inline Face_handle infinite_face() const { 00346 return DG::infinite_face(); 00347 } 00348 00349 inline Vertex_handle finite_vertex() const { 00350 return DG::finite_vertex(); 00351 } 00352 00353 inline int dimension() const { 00354 return DG::dimension(); 00355 } 00356 00357 using Delaunay_graph::cw; 00358 using Delaunay_graph::ccw; 00359 00360 public: 00361 // TRAVERSAL OF THE DUAL GRAPH 00362 //---------------------------- 00363 inline Finite_faces_iterator finite_faces_begin() const { 00364 return DG::finite_faces_begin(); 00365 } 00366 00367 inline Finite_faces_iterator finite_faces_end() const { 00368 return DG::finite_faces_end(); 00369 } 00370 00371 inline Finite_vertices_iterator finite_vertices_begin() const { 00372 return DG::finite_vertices_begin(); 00373 } 00374 00375 inline Finite_vertices_iterator finite_vertices_end() const { 00376 return DG::finite_vertices_end(); 00377 } 00378 00379 inline Finite_edges_iterator finite_edges_begin() const { 00380 return DG::finite_edges_begin(); 00381 } 00382 00383 inline Finite_edges_iterator finite_edges_end() const { 00384 return DG::finite_edges_end(); 00385 } 00386 00387 inline All_faces_iterator all_faces_begin() const { 00388 return DG::all_faces_begin(); 00389 } 00390 00391 inline All_faces_iterator all_faces_end() const { 00392 return DG::all_faces_end(); 00393 } 00394 00395 inline All_vertices_iterator all_vertices_begin() const { 00396 return DG::all_vertices_begin(); 00397 } 00398 00399 inline All_vertices_iterator all_vertices_end() const { 00400 return DG::all_vertices_end(); 00401 } 00402 00403 inline All_edges_iterator all_edges_begin() const { 00404 return DG::all_edges_begin(); 00405 } 00406 00407 inline All_edges_iterator all_edges_end() const { 00408 return DG::all_edges_end(); 00409 } 00410 00411 inline Input_sites_iterator input_sites_begin() const { 00412 return Input_sites_iterator(isc_.begin()); 00413 } 00414 00415 inline Input_sites_iterator input_sites_end() const { 00416 return Input_sites_iterator(isc_.end()); 00417 } 00418 00419 inline Output_sites_iterator output_sites_begin() const { 00420 return Output_sites_iterator(finite_vertices_begin()); 00421 } 00422 00423 inline Output_sites_iterator output_sites_end() const { 00424 return Output_sites_iterator(finite_vertices_end()); 00425 } 00426 00427 public: 00428 // CIRCULATORS 00429 //------------ 00430 inline Face_circulator 00431 incident_faces(Vertex_handle v, 00432 Face_handle f = Face_handle()) const { 00433 return DG::incident_faces(v, f); 00434 } 00435 00436 inline Vertex_circulator 00437 incident_vertices(Vertex_handle v, 00438 Face_handle f = Face_handle()) const { 00439 return DG::incident_vertices(v, f); 00440 } 00441 00442 inline Edge_circulator 00443 incident_edges(Vertex_handle v, 00444 Face_handle f = Face_handle()) const { 00445 return DG::incident_edges(v, f); 00446 } 00447 00448 public: 00449 // PREDICATES 00450 //----------- 00451 inline bool is_infinite(const Vertex_handle& v) const { 00452 return DG::is_infinite(v); 00453 } 00454 00455 inline bool is_infinite(const Face_handle& f) const { 00456 return DG::is_infinite(f); 00457 } 00458 00459 inline bool is_infinite(const Face_handle& f, int i) const { 00460 return DG::is_infinite(f, i); 00461 } 00462 00463 inline bool is_infinite(const Edge& e) const { 00464 return is_infinite(e.first, e.second); 00465 } 00466 00467 inline bool is_infinite(const Edge_circulator& ec) const { 00468 return DG::is_infinite(ec); 00469 } 00470 00471 public: 00472 // INSERTION METHODS 00473 //------------------ 00474 template<class Input_iterator> 00475 inline size_type insert(Input_iterator first, Input_iterator beyond) { 00476 return insert(first, beyond, Tag_false()); 00477 } 00478 00479 template<class Input_iterator> 00480 size_type insert(Input_iterator first, Input_iterator beyond, Tag_true) 00481 { 00482 std::vector<Site_2> site_vec; 00483 for (Input_iterator it = first; it != beyond; ++it) { 00484 site_vec.push_back(Site_2(*it)); 00485 } 00486 std::random_shuffle(site_vec.begin(), site_vec.end()); 00487 return insert(site_vec.begin(), site_vec.end(), Tag_false()); 00488 } 00489 00490 template<class Input_iterator> 00491 size_type insert(Input_iterator first, Input_iterator beyond, Tag_false) 00492 { 00493 // do it the obvious way: insert them as they come; 00494 // one might think though that it might be better to first insert 00495 // all end points and then all segments, or a variation of that. 00496 size_type n_before = number_of_vertices(); 00497 for (Input_iterator it = first; it != beyond; ++it) { 00498 insert(*it); 00499 } 00500 size_type n_after = number_of_vertices(); 00501 return n_after - n_before; 00502 } 00503 00504 // insert a point 00505 inline Vertex_handle insert(const Point_2& p) { 00506 // update input site container 00507 Point_handle ph = register_input_site(p); 00508 Storage_site_2 ss = st_.construct_storage_site_2_object()(ph); 00509 return insert_point(ss, p, Vertex_handle()); 00510 } 00511 00512 inline Vertex_handle insert(const Point_2& p, Vertex_handle vnear) { 00513 // update input site container 00514 Point_handle ph = register_input_site(p); 00515 Storage_site_2 ss = st_.construct_storage_site_2_object()(ph); 00516 return insert_point(ss, p, vnear); 00517 } 00518 00519 protected: 00520 // insert a point without registering it in the input sites 00521 // container: useful for the hierarchy 00522 inline Vertex_handle insert_no_register(const Storage_site_2& ss, 00523 const Point_2& p, 00524 Vertex_handle vnear) { 00525 return insert_point(ss, p, vnear); 00526 } 00527 00528 public: 00529 // insert a segment 00530 inline Vertex_handle insert(const Point_2& p0, const Point_2& p1) { 00531 // update input site container 00532 Point_handle_pair php = register_input_site(p0, p1); 00533 Storage_site_2 ss = 00534 st_.construct_storage_site_2_object()(php.first, php.second); 00535 Vertex_handle v = insert_segment(ss, Site_2::construct_site_2(p0, p1), 00536 Vertex_handle()); 00537 if ( v == Vertex_handle() ) { 00538 unregister_input_site(php.first, php.second); 00539 } 00540 return v; 00541 } 00542 00543 // inserting a segment whose endpoints have already been inserted 00544 // update input site container 00545 inline Vertex_handle insert(const Vertex_handle& v0, 00546 const Vertex_handle& v1) { 00547 CGAL_precondition( v0->storage_site().is_point() && 00548 v1->storage_site().is_point() ); 00549 00550 Point_handle h0 = v0->storage_site().point(); 00551 Point_handle h1 = v1->storage_site().point(); 00552 Storage_site_2 ss = st_.construct_storage_site_2_object()(h0, h1); 00553 00554 // update input site container 00555 Point_handle_pair php = register_input_site(h0, h1); 00556 00557 if ( number_of_vertices() == 2 ) { 00558 return insert_third(ss, v0, v1); 00559 } 00560 00561 Vertex_handle v = insert_segment_interior(ss.site(), ss, v0); 00562 if ( v == Vertex_handle() ) { 00563 unregister_input_site(php.first, php.second); 00564 } 00565 return v; 00566 } 00567 00568 inline Vertex_handle insert(const Point_2& p0, const Point_2& p1, 00569 Vertex_handle vnear) { 00570 // update input site container 00571 Point_handle_pair php = register_input_site(p0, p1); 00572 Storage_site_2 ss = 00573 st_.construct_storage_site_2_object()(php.first, php.second); 00574 Vertex_handle v = 00575 insert_segment(ss, Site_2::construct_site_2(p0, p1), vnear); 00576 if ( v == Vertex_handle() ) { 00577 unregister_input_site(php.first, php.second); 00578 } 00579 return v; 00580 } 00581 00582 inline Vertex_handle insert(const Site_2& t) { 00583 return insert(t, Vertex_handle()); 00584 } 00585 00586 Vertex_handle insert(const Site_2& t, Vertex_handle vnear) 00587 { 00588 // the intended use is to unify the calls to insert(...); 00589 // thus the site must be an exact one; 00590 CGAL_precondition( t.is_input() ); 00591 00592 // update input site container 00593 00594 if ( t.is_segment() ) { 00595 Point_handle_pair php = 00596 register_input_site( t.source_of_supporting_site(), 00597 t.target_of_supporting_site() ); 00598 Storage_site_2 ss = 00599 st_.construct_storage_site_2_object()(php.first, php.second); 00600 Vertex_handle v = insert_segment(ss, t, vnear); 00601 if ( v == Vertex_handle() ) { 00602 unregister_input_site( php.first, php.second ); 00603 } 00604 return v; 00605 } else if ( t.is_point() ) { 00606 Point_handle ph = register_input_site( t.point() ); 00607 Storage_site_2 ss = st_.construct_storage_site_2_object()(ph); 00608 return insert_point(ss, t.point(), vnear); 00609 } else { 00610 CGAL_precondition ( t.is_defined() ); 00611 return Vertex_handle(); // to avoid compiler error 00612 } 00613 } 00614 00615 protected: 00616 template<class SSite> 00617 inline void convert_info1(SSite& ss_trg, const SSite& ss_src, 00618 bool is_src, int, 00619 typename SSite::Has_info_tag const* = 0) const 00620 { 00621 // std::cerr << "converting info..." << std::flush; 00622 typename Storage_traits::Convert_info convert = st_.convert_info_object(); 00623 00624 ss_trg.set_info( convert(ss_src.info(), is_src) ); 00625 // std::cerr << " done!" << std::endl; 00626 } 00627 00628 template<class SSite> 00629 inline void convert_info1(SSite& /* ss_trg */, 00630 const SSite& /* ss_src */, bool, char) const 00631 { 00632 } 00633 00634 void convert_info(Storage_site_2& ss_trg, 00635 const Storage_site_2& ss_src, bool is_src) const { 00636 CGAL_precondition( ss_src.is_segment() && ss_trg.is_point() ); 00637 CGAL_precondition( ss_src.is_input() && ss_trg.is_input() ); 00638 CGAL_assertion( (is_src && same_points(ss_src.source_site(), ss_trg)) || 00639 (!is_src && same_points(ss_src.target_site(), ss_trg)) 00640 ); 00641 convert_info1(ss_trg, ss_src, is_src, 0); 00642 } 00643 00644 template<class SSite> 00645 inline void merge_info1(Vertex_handle v, const SSite& ss, int, 00646 typename SSite::Has_info_tag const* = 0) 00647 { 00648 // std::cerr << "merging info..." << std::flush; 00649 Storage_site_2 ss_v = v->storage_site(); 00650 00651 typename Storage_traits::Merge_info merge = st_.merge_info_object(); 00652 00653 ss_v.set_info( merge(ss_v.info(), ss.info()) ); 00654 v->set_site(ss_v); 00655 // std::cerr << " done!" << std::endl; 00656 } 00657 00658 template<class SSite> 00659 inline void merge_info1(Vertex_handle, const SSite&, char) const 00660 { 00661 } 00662 00663 // merges the info of the storage site of the vertex handle with the 00664 // info of the given site; the vertex_handle contains the storage 00665 // site with the new info 00666 inline void merge_info(Vertex_handle v, const Storage_site_2& ss) { 00667 CGAL_precondition( (v->storage_site().is_segment() && 00668 ss.is_segment() && 00669 same_segments(v->site(), ss.site())) || 00670 (v->storage_site().is_point() && 00671 ss.is_point() && 00672 same_points(v->site(), ss.site())) || 00673 (v->storage_site().is_point() && ss.is_segment()) 00674 ); 00675 merge_info1(v, ss, 0); 00676 } 00677 00678 public: 00679 template<typename Info_t> 00680 inline Vertex_handle insert(const Site_2& t, 00681 const Info_t& info) { 00682 return insert(t, info, Vertex_handle()); 00683 } 00684 00685 template<typename Info_t> 00686 Vertex_handle insert(const Site_2& t, 00687 const Info_t& info, 00688 Vertex_handle vnear) 00689 { 00690 typedef typename Storage_traits::Info Info; 00691 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Internal:: 00692 Check_type_equality_for_info<Info_t, Info>(); 00693 // the intended use is to unify the calls to insert(...); 00694 // thus the site must be an exact one; 00695 CGAL_precondition( t.is_input() ); 00696 00697 // update input site container 00698 00699 if ( t.is_segment() ) { 00700 Point_handle_pair php = 00701 register_input_site( t.source_of_supporting_site(), 00702 t.target_of_supporting_site() ); 00703 Storage_site_2 ss = 00704 st_.construct_storage_site_2_object()(php.first, php.second); 00705 ss.set_info(info); 00706 Vertex_handle v = insert_segment(ss, t, vnear); 00707 if ( v == Vertex_handle() ) { 00708 unregister_input_site( php.first, php.second ); 00709 } 00710 return v; 00711 } else if ( t.is_point() ) { 00712 Point_handle ph = register_input_site( t.point() ); 00713 Storage_site_2 ss = st_.construct_storage_site_2_object()(ph); 00714 ss.set_info(info); 00715 return insert_point(ss, t.point(), vnear); 00716 } else { 00717 CGAL_precondition ( t.is_defined() ); 00718 return Vertex_handle(); // to avoid compiler error 00719 } 00720 } 00721 00722 // REMOVAL METHODS 00723 //---------------- 00724 protected: 00725 bool is_star(const Vertex_handle& v) const; 00726 bool is_linear_chain(const Vertex_handle& v0, const Vertex_handle& v1, 00727 const Vertex_handle& v2) const; 00728 bool is_flippable(const Face_handle& f, int i) const; 00729 00730 void minimize_degree(const Vertex_handle& v); 00731 00732 // this method does not really do the job as intended, i.e., for removal 00733 void equalize_degrees(const Vertex_handle& v, Self& small_d, 00734 std::map<Vertex_handle,Vertex_handle>& vmap, 00735 List& l) const; 00736 00737 void expand_conflict_region_remove(const Face_handle& f, 00738 const Site_2& t, 00739 const Storage_site_2& ss, 00740 List& l, Face_map& fm, 00741 Sign_map& sign_map); 00742 00743 void find_conflict_region_remove(const Vertex_handle& v, 00744 const Vertex_handle& vnearest, 00745 List& l, Face_map& fm, Sign_map& vm); 00746 00747 template<class OutputItFaces> 00748 OutputItFaces get_faces(const List& l, OutputItFaces fit) const 00749 { 00750 // map that determines if a face has been visited 00751 std::map<Face_handle,bool> fmap; 00752 00753 // compute the initial face 00754 Edge e_front = l.front(); 00755 Face_handle fstart = e_front.first->neighbor(e_front.second); 00756 00757 // do the recursion 00758 return get_faces(l, fstart, fmap, fit); 00759 } 00760 00761 template<class OutputItFaces> 00762 OutputItFaces get_faces(const List& l, Face_handle f, 00763 std::map<Face_handle,bool>& fmap, 00764 OutputItFaces fit) const 00765 { 00766 // if the face has been visited return 00767 if ( fmap.find(f) != fmap.end() ) { return fit; } 00768 00769 // mark the face as visited 00770 fmap[f] = true; 00771 00772 // output the face 00773 *fit++ = f; 00774 00775 // recursively go to neighbors 00776 for (int i = 0; i < 3; i++) { 00777 Face_handle n = f->neighbor(i); 00778 Edge ee(n, n->index( this->_tds.mirror_vertex(f,i) )); 00779 if ( !l.is_in_list(ee) ) { 00780 fit = get_faces(l, n, fmap, fit); 00781 } 00782 } 00783 return fit; 00784 } 00785 00786 size_type count_faces(const List& l) const; 00787 00788 void fill_hole(const Self& small_d, const Vertex_handle& v, const List& l, 00789 std::map<Vertex_handle,Vertex_handle>& vmap); 00790 00791 bool remove_first(const Vertex_handle& v); 00792 bool remove_second(const Vertex_handle& v); 00793 bool remove_third(const Vertex_handle& v); 00794 00795 void compute_small_diagram(const Vertex_handle& v, Self& small_d) const; 00796 void compute_vertex_map(const Vertex_handle& v, const Self& small_d, 00797 std::map<Vertex_handle,Vertex_handle>& vmap) const; 00798 void remove_degree_d_vertex(const Vertex_handle& v); 00799 00800 bool remove_base(const Vertex_handle& v); 00801 00802 public: 00803 bool remove(const Vertex_handle& v); 00804 00805 protected: 00806 inline void unregister_input_site(const Point_handle& h) 00807 { 00808 Site_rep_2 rep(h, h, true); 00809 typename Input_sites_container::iterator it = isc_.find(rep); 00810 CGAL_assertion( it != isc_.end() ); 00811 00812 pc_.erase(h); 00813 isc_.erase(it); 00814 } 00815 00816 inline void unregister_input_site(const Point_handle& h1, 00817 const Point_handle& h2) 00818 { 00819 Site_rep_2 rep(h1, h2, false); 00820 typename Input_sites_container::iterator it = isc_.find(rep); 00821 00822 Site_rep_2 sym_rep(h2, h1, false); 00823 typename Input_sites_container::iterator sym_it = isc_.find(sym_rep); 00824 00825 CGAL_assertion( it != isc_.end() || sym_it != isc_.end() ); 00826 00827 if ( it != isc_.end() ) { isc_.erase(it); } 00828 if ( sym_it != isc_.end() ) { isc_.erase(sym_it); } 00829 00830 Site_rep_2 r1(h1, h1, true); 00831 if ( isc_.find(r1) == isc_.end() ) { isc_.insert(r1); } 00832 00833 Site_rep_2 r2(h2, h2, true); 00834 if ( isc_.find(r2) == isc_.end() ) { isc_.insert(r2); } 00835 } 00836 00837 inline Point_handle register_input_site(const Point_2& p) 00838 { 00839 std::pair<Point_handle,bool> it = pc_.insert(p); 00840 Site_rep_2 rep(it.first, it.first, true); 00841 isc_.insert( rep ); 00842 return it.first; 00843 } 00844 00845 inline 00846 Point_handle_pair register_input_site(const Point_2& p0, const Point_2& p1) 00847 { 00848 std::pair<Point_handle,bool> it1 = pc_.insert(p0); 00849 std::pair<Point_handle,bool> it2 = pc_.insert(p1); 00850 Site_rep_2 rep(it1.first, it2.first, false); 00851 isc_.insert( rep ); 00852 return Point_handle_pair(it1.first, it2.first); 00853 } 00854 00855 inline 00856 Point_handle_pair register_input_site(const Point_handle& h0, 00857 const Point_handle& h1) 00858 { 00859 CGAL_precondition( h0 != h1 ); 00860 Site_rep_2 rep(h0, h1, false); 00861 isc_.insert( rep ); 00862 return Point_handle_pair(h0, h1); 00863 } 00864 00865 Vertex_handle insert_first(const Storage_site_2& ss, const Point_2& p); 00866 Vertex_handle insert_second(const Storage_site_2& ss, const Point_2& p); 00867 Vertex_handle insert_third(const Storage_site_2& ss, const Point_2& p); 00868 Vertex_handle insert_third(const Site_2& t, const Storage_site_2& ss); 00869 Vertex_handle insert_third(const Storage_site_2& ss, Vertex_handle v0, 00870 Vertex_handle v1); 00871 00872 Vertex_handle insert_point(const Storage_site_2& ss, const Point_2& p, 00873 Vertex_handle vnear); 00874 Vertex_handle insert_point(const Storage_site_2& ss, 00875 const Site_2& t, Vertex_handle vnear); 00876 Vertex_handle insert_point2(const Storage_site_2& ss, 00877 const Site_2& t, Vertex_handle vnear); 00878 00879 Triple<Vertex_handle,Vertex_handle,Vertex_handle> 00880 insert_point_on_segment(const Storage_site_2& ss, const Site_2& t, 00881 Vertex_handle v, const Tag_true&); 00882 00883 Triple<Vertex_handle,Vertex_handle,Vertex_handle> 00884 insert_exact_point_on_segment(const Storage_site_2& ss, const Site_2& t, 00885 Vertex_handle v); 00886 00887 Vertex_handle insert_segment(const Storage_site_2& ss, const Site_2& t, 00888 Vertex_handle vnear); 00889 00890 Vertex_handle insert_segment_interior(const Site_2& t, 00891 const Storage_site_2& ss, 00892 Vertex_handle vnear); 00893 00894 template<class ITag> 00895 inline 00896 Vertex_handle insert_intersecting_segment(const Storage_site_2& ss, 00897 const Site_2& t, 00898 Vertex_handle v, 00899 ITag tag) { 00900 return insert_intersecting_segment_with_tag(ss, t, v, tag); 00901 } 00902 00903 Vertex_handle 00904 insert_intersecting_segment_with_tag(const Storage_site_2& ss, 00905 const Site_2& t, 00906 Vertex_handle v, Tag_false); 00907 00908 Vertex_handle 00909 insert_intersecting_segment_with_tag(const Storage_site_2& ss, 00910 const Site_2& t, 00911 Vertex_handle v, Tag_true); 00912 00913 00914 00915 public: 00916 // NEAREST NEIGHBOR LOCATION 00917 //-------------------------- 00918 inline Vertex_handle nearest_neighbor(const Point_2& p) const { 00919 return nearest_neighbor(Site_2::construct_site_2(p), Vertex_handle()); 00920 } 00921 00922 inline Vertex_handle nearest_neighbor(const Point_2& p, 00923 Vertex_handle vnear) const { 00924 return nearest_neighbor(Site_2::construct_site_2(p), vnear); 00925 } 00926 00927 protected: 00928 Vertex_handle nearest_neighbor(const Site_2& p, 00929 Vertex_handle vnear) const; 00930 00931 00932 protected: 00933 // I/O METHODS 00934 //------------ 00935 typedef std::map<const_Point_handle,size_type,Point_handle_less_than> 00936 Point_handle_mapper; 00937 00938 typedef std::vector<Point_handle> Point_handle_vector; 00939 00940 void file_output(std::ostream&, const Storage_site_2&, 00941 Point_handle_mapper&) const; 00942 00943 void file_output(std::ostream&, Point_handle_mapper&, 00944 bool print_point_container) const; 00945 00946 void file_input(std::istream&, Storage_site_2&, 00947 const Point_handle_vector&, const Tag_true&) const; 00948 void file_input(std::istream&, Storage_site_2&, 00949 const Point_handle_vector&, const Tag_false&) const; 00950 void file_input(std::istream&, bool read_handle_vector, 00951 Point_handle_vector&); 00952 00953 public: 00954 void file_input(std::istream& is) { 00955 Point_handle_vector P; 00956 file_input(is, true, P); 00957 } 00958 00959 void file_output(std::ostream& os) const { 00960 Point_handle_mapper P; 00961 size_type inum = 0; 00962 for (const_Point_handle ph = pc_.begin(); ph != pc_.end(); ++ph) { 00963 P[ph] = inum++; 00964 } 00965 file_output(os, P, true); 00966 } 00967 00968 template< class Stream > 00969 Stream& draw_dual(Stream& str) const 00970 { 00971 Finite_edges_iterator eit = finite_edges_begin(); 00972 for (; eit != finite_edges_end(); ++eit) { 00973 draw_dual_edge(*eit, str); 00974 } 00975 return str; 00976 } 00977 00978 template < class Stream > 00979 Stream& draw_skeleton(Stream& str) const 00980 { 00981 Finite_edges_iterator eit = finite_edges_begin(); 00982 for (; eit != finite_edges_end(); ++eit) { 00983 Site_2 p = eit->first->vertex( cw(eit->second) )->site(); 00984 Site_2 q = eit->first->vertex( ccw(eit->second) )->site(); 00985 00986 bool is_endpoint_of_seg = 00987 ( p.is_segment() && q.is_point() && 00988 is_endpoint_of_segment(q, p) ) || 00989 ( p.is_point() && q.is_segment() && 00990 is_endpoint_of_segment(p, q) ); 00991 00992 if ( !is_endpoint_of_seg ) { 00993 draw_dual_edge(*eit, str); 00994 } 00995 } 00996 return str; 00997 } 00998 00999 // MK: this has to be rewritten. all the checking must be done in 01000 // the geometric traits class. 01001 template< class Stream > 01002 Stream& draw_dual_edge(Edge e, Stream& str) const 01003 { 01004 CGAL_precondition( !is_infinite(e) ); 01005 01006 typename Geom_traits::Line_2 l; 01007 typename Geom_traits::Segment_2 s; 01008 typename Geom_traits::Ray_2 r; 01009 CGAL::Parabola_segment_2<Gt> ps; 01010 01011 Object o = primal(e); 01012 01013 if (CGAL::assign(l, o)) str << l; 01014 if (CGAL::assign(s, o)) str << s; 01015 if (CGAL::assign(r, o)) str << r; 01016 if (CGAL::assign(ps, o)) ps.draw(str); 01017 01018 return str; 01019 } 01020 01021 template< class Stream > 01022 inline 01023 Stream& draw_dual_edge(Edge_circulator ec, Stream& str) const { 01024 return draw_dual_edge(*ec, str); 01025 } 01026 01027 template< class Stream > 01028 inline 01029 Stream& draw_dual_edge(Finite_edges_iterator eit, Stream& str) const { 01030 return draw_dual_edge(*eit, str); 01031 } 01032 01033 public: 01034 // VALIDITY CHECK 01035 //--------------- 01036 bool is_valid(bool verbose = false, int level = 1) const; 01037 01038 public: 01039 // MISCELLANEOUS 01040 //-------------- 01041 void clear() { 01042 DG::clear(); 01043 pc_.clear(); 01044 isc_.clear(); 01045 } 01046 01047 void swap(Segment_Delaunay_graph_2& sdg) { 01048 DG::swap(sdg); 01049 pc_.swap(sdg.pc_); 01050 isc_.swap(sdg.isc_); 01051 } 01052 01054 // THE METHODS BELOW ARE LOCAL 01056 01057 protected: 01058 // THE COPY METHOD 01059 //------------------------------------------------------------------ 01060 // used in the copy constructor and assignment operator 01061 01062 Storage_site_2 01063 copy_storage_site(const Storage_site_2& ss_other, 01064 Handle_map& hm, const Tag_false&); 01065 01066 Storage_site_2 01067 copy_storage_site(const Storage_site_2& ss_other, 01068 Handle_map& hm, const Tag_true&); 01069 01070 void copy(Segment_Delaunay_graph_2& other); 01071 void copy(Segment_Delaunay_graph_2& other, Handle_map& hm); 01072 01073 protected: 01074 // HELPER METHODS FOR COMBINATORIAL OPERATIONS ON THE DATA STRUCTURE 01075 //------------------------------------------------------------------ 01076 01077 // getting the degree of a vertex 01078 inline 01079 typename Data_structure::size_type degree(const Vertex_handle& v) const { 01080 return this->_tds.degree(v); 01081 } 01082 01083 // getting the symmetric edge 01084 inline Edge sym_edge(const Edge e) const { 01085 return sym_edge(e.first, e.second); 01086 } 01087 01088 inline Edge sym_edge(const Face_handle& f, int i) const { 01089 Face_handle f_sym = f->neighbor(i); 01090 return Edge( f_sym, f_sym->index( this->_tds.mirror_vertex(f, i) ) ); 01091 } 01092 01093 Edge flip(Face_handle& f, int i) { 01094 CGAL_precondition ( f != Face_handle() ); 01095 CGAL_precondition (i == 0 || i == 1 || i == 2); 01096 CGAL_precondition( this->dimension()==2 ); 01097 01098 CGAL_precondition( f->vertex(i) != this->_tds.mirror_vertex(f, i) ); 01099 01100 this->_tds.flip(f, i); 01101 01102 return Edge(f, ccw(i)); 01103 } 01104 01105 inline Edge flip(Edge e) { 01106 return flip(e.first, e.second); 01107 } 01108 01109 inline bool is_degree_2(const Vertex_handle& v) const { 01110 Face_circulator fc = incident_faces(v); 01111 Face_circulator fc1 = fc; 01112 ++(++fc1); 01113 return ( fc == fc1 ); 01114 } 01115 01116 inline Vertex_handle insert_degree_2(Edge e) { 01117 return this->_tds.insert_degree_2(e.first,e.second); 01118 } 01119 01120 inline Vertex_handle insert_degree_2(Edge e, const Storage_site_2& ss) { 01121 Vertex_handle v = insert_degree_2(e); 01122 v->set_site(ss); 01123 return v; 01124 } 01125 01126 inline void remove_degree_2(Vertex_handle v) { 01127 CGAL_precondition( is_degree_2(v) ); 01128 this->_tds.remove_degree_2(v); 01129 } 01130 01131 inline void remove_degree_3(Vertex_handle v) { 01132 CGAL_precondition( degree(v) == 3 ); 01133 this->_tds.remove_degree_3(v, Face_handle()); 01134 } 01135 01136 inline Vertex_handle create_vertex(const Storage_site_2& ss) { 01137 Vertex_handle v = this->_tds.create_vertex(); 01138 v->set_site(ss); 01139 return v; 01140 } 01141 01142 inline Vertex_handle create_vertex_dim_up(const Storage_site_2& ss) { 01143 Vertex_handle v = this->_tds.insert_dim_up(infinite_vertex()); 01144 v->set_site(ss); 01145 return v; 01146 } 01147 01148 protected: 01149 // HELPER METHODS FOR CREATING STORAGE SITES 01150 //------------------------------------------ 01151 inline 01152 Storage_site_2 split_storage_site(const Storage_site_2& ss0, 01153 const Storage_site_2& ss1, 01154 bool first) 01155 { 01156 // Split the first storage site which is a segment using the 01157 // second storage site which is an exact point 01158 // i denotes whether the first or second half is to be created 01159 CGAL_precondition( ss0.is_segment() && ss1.is_point() ); 01160 01161 return st_.construct_storage_site_2_object()(ss0, ss1, first); 01162 } 01163 01164 public: 01165 // METHODS FOR ACCESSING THE PRIMAL GRAPH 01166 //--------------------------------------- 01167 // used primarily for visualization 01168 inline Point_2 primal(const Face_handle& f) const { 01169 return circumcenter(f); 01170 } 01171 01172 Object primal(const Edge e) const; 01173 01174 inline Object primal(const Edge_circulator& ec) const { 01175 return primal(*ec); 01176 } 01177 01178 inline Object primal(const Finite_edges_iterator& ei) const { 01179 return primal(*ei); 01180 } 01181 01182 protected: 01183 void print_error_message() const; 01184 01185 void print_error_message(const Tag_false&) const 01186 { 01187 static int i = 0; 01188 01189 if ( i == 0 ) { 01190 i++; 01191 std::cerr << "SDG::Insert aborted: intersecting segments found" 01192 << std::endl; 01193 } 01194 } 01195 01196 void print_error_message(const Tag_true&) const {} 01197 01198 //protected: 01199 public: 01200 // wrappers for constructions 01201 inline Point_2 circumcenter(const Face_handle& f) const { 01202 CGAL_precondition( this->dimension()==2 || !is_infinite(f) ); 01203 return circumcenter(f->vertex(0)->site(), 01204 f->vertex(1)->site(), 01205 f->vertex(2)->site()); 01206 } 01207 01208 inline Point_2 circumcenter(const Site_2& t0, const Site_2& t1, 01209 const Site_2& t2) const { 01210 return 01211 geom_traits().construct_svd_vertex_2_object()(t0, t1, t2); 01212 } 01213 01214 protected: 01215 // HELPER METHODS FOR INSERTION 01216 //----------------------------- 01217 void initialize_conflict_region(const Face_handle& f, List& l); 01218 01219 std::pair<Face_handle,Face_handle> 01220 find_faces_to_split(const Vertex_handle& v, const Site_2& t) const; 01221 01222 void expand_conflict_region(const Face_handle& f, const Site_2& t, 01223 const Storage_site_2& ss, 01224 List& l, Face_map& fm, 01225 std::map<Face_handle,Sign>& sign_map, 01226 Triple<bool, Vertex_handle, 01227 Arrangement_type>& vcross); 01228 01229 Vertex_handle add_bogus_vertex(Edge e, List& l); 01230 Vertex_list add_bogus_vertices(List& l); 01231 void remove_bogus_vertices(Vertex_list& vl); 01232 01233 void retriangulate_conflict_region(Vertex_handle v, List& l, 01234 Face_map& fm); 01235 01236 01237 protected: 01238 // TYPES AND ACCESS METHODS FOR VISUALIZATION 01239 //------------------------------------------- 01240 01241 // types 01242 typedef 01243 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Construct_sdg_circle_2<Gt,Integral_domain_without_division_tag> 01244 Construct_sdg_circle_2; 01245 01246 typedef 01247 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Construct_sdg_bisector_2<Gt,Integral_domain_without_division_tag> 01248 Construct_sdg_bisector_2; 01249 01250 typedef 01251 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS::Construct_sdg_bisector_ray_2<Gt,Integral_domain_without_division_tag> 01252 Construct_sdg_bisector_ray_2; 01253 01254 typedef 01255 CGAL_SEGMENT_DELAUNAY_GRAPH_2_NS:: 01256 Construct_sdg_bisector_segment_2<Gt,Integral_domain_without_division_tag> 01257 Construct_sdg_bisector_segment_2; 01258 01259 // access 01260 inline Construct_sdg_circle_2 01261 construct_sdg_circle_2_object() const{ 01262 return Construct_sdg_circle_2(); 01263 } 01264 01265 inline Construct_sdg_bisector_2 01266 construct_sdg_bisector_2_object() const { 01267 return Construct_sdg_bisector_2(); 01268 } 01269 01270 inline Construct_sdg_bisector_ray_2 01271 construct_sdg_bisector_ray_2_object() const { 01272 return Construct_sdg_bisector_ray_2(); 01273 } 01274 01275 inline Construct_sdg_bisector_segment_2 01276 construct_sdg_bisector_segment_2_object() const { 01277 return Construct_sdg_bisector_segment_2(); 01278 } 01279 01280 protected: 01281 // WRAPPERS FOR GEOMETRIC PREDICATES 01282 //---------------------------------- 01283 inline 01284 bool same_points(const Storage_site_2& p, const Storage_site_2& q) const { 01285 return geom_traits().equal_2_object()(p.site(), q.site()); 01286 } 01287 01288 inline 01289 bool same_segments(const Storage_site_2& t, Vertex_handle v) const { 01290 if ( is_infinite(v) ) { return false; } 01291 if ( t.is_point() || v->storage_site().is_point() ) { return false; } 01292 return same_segments(t.site(), v->site()); 01293 } 01294 01295 inline 01296 bool is_endpoint_of_segment(const Storage_site_2& p, 01297 const Storage_site_2& s) const 01298 { 01299 CGAL_precondition( p.is_point() && s.is_segment() ); 01300 return ( same_points(p, s.source_site()) || 01301 same_points(p, s.target_site()) ); 01302 } 01303 01304 inline 01305 bool is_degenerate_segment(const Storage_site_2& s) const { 01306 CGAL_precondition( s.is_segment() ); 01307 return same_points(s.source_site(), s.target_site()); 01308 } 01309 01310 // returns: 01311 // ON_POSITIVE_SIDE if q is closer to t1 01312 // ON_NEGATIVE_SIDE if q is closer to t2 01313 // ON_ORIENTED_BOUNDARY if q is on the bisector of t1 and t2 01314 inline 01315 Oriented_side side_of_bisector(const Storage_site_2 &t1, 01316 const Storage_site_2 &t2, 01317 const Storage_site_2 &q) const { 01318 return 01319 geom_traits().oriented_side_of_bisector_2_object()(t1.site(), 01320 t2.site(), 01321 q.site()); 01322 } 01323 01324 inline 01325 Sign incircle(const Storage_site_2 &t1, const Storage_site_2 &t2, 01326 const Storage_site_2 &t3, const Storage_site_2 &q) const { 01327 return geom_traits().vertex_conflict_2_object()(t1.site(), 01328 t2.site(), 01329 t3.site(), 01330 q.site()); 01331 } 01332 01333 inline 01334 Sign incircle(const Storage_site_2 &t1, const Storage_site_2 &t2, 01335 const Storage_site_2 &q) const { 01336 return geom_traits().vertex_conflict_2_object()(t1.site(), 01337 t2.site(), 01338 q.site()); 01339 } 01340 01341 inline 01342 Sign incircle(const Face_handle& f, const Storage_site_2& q) const { 01343 return incircle(f, q.site()); 01344 } 01345 01346 inline 01347 bool finite_edge_interior(const Storage_site_2& t1, 01348 const Storage_site_2& t2, 01349 const Storage_site_2& t3, 01350 const Storage_site_2& t4, 01351 const Storage_site_2& q, Sign sgn) const { 01352 return 01353 geom_traits().finite_edge_interior_conflict_2_object() 01354 (t1.site(), t2.site(), t3.site(), t4.site(), q.site(), sgn); 01355 } 01356 01357 inline 01358 bool finite_edge_interior(const Face_handle& f, int i, 01359 const Storage_site_2& q, Sign sgn) const { 01360 CGAL_precondition( !is_infinite(f) && 01361 !is_infinite(f->neighbor(i)) ); 01362 return finite_edge_interior( f->vertex( ccw(i) )->site(), 01363 f->vertex( cw(i) )->site(), 01364 f->vertex( i )->site(), 01365 this->_tds.mirror_vertex(f, i)->site(), 01366 q.site(), sgn); 01367 } 01368 01369 inline 01370 bool finite_edge_interior(const Storage_site_2& t1, 01371 const Storage_site_2& t2, 01372 const Storage_site_2& t3, 01373 const Storage_site_2& q, 01374 Sign sgn) const { 01375 return geom_traits().finite_edge_interior_conflict_2_object()(t1.site(), 01376 t2.site(), 01377 t3.site(), 01378 q.site(), 01379 sgn); 01380 } 01381 01382 inline 01383 bool finite_edge_interior(const Storage_site_2& t1, 01384 const Storage_site_2& t2, 01385 const Storage_site_2& q, 01386 Sign sgn) const { 01387 return 01388 geom_traits().finite_edge_interior_conflict_2_object()(t1.site(), 01389 t2.site(), 01390 q.site(), 01391 sgn); 01392 } 01393 01394 bool finite_edge_interior(const Face_handle& f, int i, 01395 const Storage_site_2& p, Sign sgn, 01396 int j) const { 01397 return finite_edge_interior(f, i, p.site(), sgn, j); 01398 } 01399 01400 inline 01401 bool infinite_edge_interior(const Storage_site_2& t2, 01402 const Storage_site_2& t3, 01403 const Storage_site_2& t4, 01404 const Storage_site_2& q, Sign sgn) const { 01405 return 01406 geom_traits().infinite_edge_interior_conflict_2_object() 01407 (t2.site(), t3.site(), t4.site(), q.site(), sgn); 01408 } 01409 01410 inline 01411 bool infinite_edge_interior(const Face_handle& f, int i, 01412 const Storage_site_2& q, Sign sgn) const 01413 { 01414 return infinite_edge_interior(f, i, q, sgn); 01415 } 01416 01417 inline 01418 bool edge_interior(const Face_handle& f, int i, 01419 const Storage_site_2& t, Sign sgn) const { 01420 return edge_interior(f, i, t.site(), sgn); 01421 } 01422 01423 inline 01424 bool edge_interior(const Edge& e, 01425 const Storage_site_2& t, Sign sgn) const { 01426 return edge_interior(e.first, e.second, t, sgn); 01427 } 01428 01429 inline Arrangement_type 01430 arrangement_type(const Storage_site_2& t, const Vertex_handle& v) const { 01431 if ( is_infinite(v) ) { return AT2::DISJOINT; } 01432 return arrangement_type(t, v->storage_site()); 01433 } 01434 01435 inline 01436 Arrangement_type arrangement_type(const Storage_site_2& p, 01437 const Storage_site_2& q) const { 01438 return arrangement_type(p.site(), q.site()); 01439 } 01440 01441 inline 01442 bool are_parallel(const Storage_site_2& p, const Storage_site_2& q) const { 01443 return geom_traits().are_parallel_2_object()(p.site(), q.site()); 01444 } 01445 01446 inline Oriented_side 01447 oriented_side(const Storage_site_2& q, const Storage_site_2& supp, 01448 const Storage_site_2& p) const 01449 { 01450 CGAL_precondition( q.is_point() && supp.is_segment() && p.is_point() ); 01451 return 01452 geom_traits().oriented_side_2_object()(q.site(), supp.site(), p.site()); 01453 } 01454 01455 inline Oriented_side 01456 oriented_side(const Storage_site_2& s1, const Storage_site_2& s2, 01457 const Storage_site_2& s3, const Storage_site_2& supp, 01458 const Storage_site_2& p) const { 01459 CGAL_precondition( supp.is_segment() && p.is_point() ); 01460 return geom_traits().oriented_side_2_object()(s1.site(), 01461 s2.site(), 01462 s3.site(), 01463 supp.site(), p.site()); 01464 } 01465 01466 01467 //------- 01468 01469 inline 01470 bool same_points(const Site_2& p, const Site_2& q) const { 01471 return geom_traits().equal_2_object()(p, q); 01472 } 01473 01474 inline 01475 bool same_segments(const Site_2& t, Vertex_handle v) const { 01476 if ( is_infinite(v) ) { return false; } 01477 if ( t.is_point() || v->site().is_point() ) { return false; } 01478 return same_segments(t, v->site()); 01479 } 01480 01481 inline 01482 bool same_segments(const Site_2& p, const Site_2& q) const { 01483 CGAL_precondition( p.is_segment() && q.is_segment() ); 01484 01485 return 01486 (same_points(p.source_site(), q.source_site()) && 01487 same_points(p.target_site(), q.target_site())) || 01488 (same_points(p.source_site(), q.target_site()) && 01489 same_points(p.target_site(), q.source_site())); 01490 } 01491 01492 inline 01493 bool is_endpoint_of_segment(const Site_2& p, const Site_2& s) const 01494 { 01495 CGAL_precondition( p.is_point() && s.is_segment() ); 01496 return ( same_points(p, s.source_site()) || 01497 same_points(p, s.target_site()) ); 01498 } 01499 01500 inline 01501 bool is_degenerate_segment(const Site_2& s) const { 01502 CGAL_precondition( s.is_segment() ); 01503 return same_points(s.source_site(), s.target_site()); 01504 } 01505 01506 // returns: 01507 // ON_POSITIVE_SIDE if q is closer to t1 01508 // ON_NEGATIVE_SIDE if q is closer to t2 01509 // ON_ORIENTED_BOUNDARY if q is on the bisector of t1 and t2 01510 inline 01511 Oriented_side side_of_bisector(const Site_2 &t1, const Site_2 &t2, 01512 const Site_2 &q) const { 01513 return geom_traits().oriented_side_of_bisector_2_object()(t1, t2, q); 01514 } 01515 01516 inline 01517 Sign incircle(const Site_2 &t1, const Site_2 &t2, 01518 const Site_2 &t3, const Site_2 &q) const { 01519 return geom_traits().vertex_conflict_2_object()(t1, t2, t3, q); 01520 } 01521 01522 inline 01523 Sign incircle(const Site_2 &t1, const Site_2 &t2, 01524 const Site_2 &q) const { 01525 return geom_traits().vertex_conflict_2_object()(t1, t2, q); 01526 } 01527 01528 inline 01529 Sign incircle(const Face_handle& f, const Site_2& q) const; 01530 01531 inline 01532 Sign incircle(const Vertex_handle& v0, const Vertex_handle& v1, 01533 const Vertex_handle& v) const { 01534 CGAL_precondition( !is_infinite(v0) && !is_infinite(v1) 01535 && !is_infinite(v) ); 01536 01537 return incircle( v0->site(), v1->site(), v->site()); 01538 } 01539 01540 Sign incircle(const Vertex_handle& v0, const Vertex_handle& v1, 01541 const Vertex_handle& v2, const Vertex_handle& v) const; 01542 01543 inline 01544 bool finite_edge_interior(const Site_2& t1, const Site_2& t2, 01545 const Site_2& t3, const Site_2& t4, 01546 const Site_2& q, Sign sgn) const { 01547 return 01548 geom_traits().finite_edge_interior_conflict_2_object() 01549 (t1,t2,t3,t4,q,sgn); 01550 } 01551 01552 inline 01553 bool finite_edge_interior(const Face_handle& f, int i, 01554 const Site_2& q, Sign sgn) const { 01555 CGAL_precondition( !is_infinite(f) && 01556 !is_infinite(f->neighbor(i)) ); 01557 return finite_edge_interior( f->vertex( ccw(i) )->site(), 01558 f->vertex( cw(i) )->site(), 01559 f->vertex( i )->site(), 01560 this->_tds.mirror_vertex(f, i)->site(), 01561 q, sgn); 01562 } 01563 01564 inline 01565 bool finite_edge_interior(const Vertex_handle& v1, const Vertex_handle& v2, 01566 const Vertex_handle& v3, const Vertex_handle& v4, 01567 const Vertex_handle& v, Sign sgn) const { 01568 CGAL_precondition( !is_infinite(v1) && !is_infinite(v2) && 01569 !is_infinite(v3) && !is_infinite(v4) && 01570 !is_infinite(v) ); 01571 return finite_edge_interior( v1->site(), v2->site(), 01572 v3->site(), v4->site(), 01573 v->site(), sgn); 01574 } 01575 01576 inline 01577 bool finite_edge_interior(const Site_2& t1, const Site_2& t2, 01578 const Site_2& t3, const Site_2& q, 01579 Sign sgn) const { 01580 return 01581 geom_traits().finite_edge_interior_conflict_2_object()(t1,t2,t3,q,sgn); 01582 } 01583 01584 inline 01585 bool finite_edge_interior(const Site_2& t1, const Site_2& t2, 01586 const Site_2& q, Sign sgn) const { 01587 return 01588 geom_traits().finite_edge_interior_conflict_2_object()(t1,t2,q,sgn); 01589 } 01590 01591 bool finite_edge_interior(const Face_handle& f, int i, 01592 const Site_2& p, Sign sgn, int) const; 01593 01594 bool finite_edge_interior(const Vertex_handle& v1, const Vertex_handle& v2, 01595 const Vertex_handle& v3, const Vertex_handle& v4, 01596 const Vertex_handle& v, Sign, int) const; 01597 01598 inline 01599 bool infinite_edge_interior(const Site_2& t2, const Site_2& t3, 01600 const Site_2& t4, const Site_2& q, 01601 Sign sgn) const { 01602 return 01603 geom_traits().infinite_edge_interior_conflict_2_object() 01604 (t2,t3,t4,q,sgn); 01605 } 01606 01607 01608 bool infinite_edge_interior(const Face_handle& f, int i, 01609 const Site_2& q, Sign sgn) const; 01610 01611 bool infinite_edge_interior(const Vertex_handle& v1, 01612 const Vertex_handle& v2, 01613 const Vertex_handle& v3, 01614 const Vertex_handle& v4, 01615 const Vertex_handle& v, 01616 Sign sgn) const; 01617 01618 bool edge_interior(const Face_handle& f, int i, 01619 const Site_2& t, Sign sgn) const; 01620 01621 bool edge_interior(const Edge& e, 01622 const Site_2& t, Sign sgn) const { 01623 return edge_interior(e.first, e.second, t, sgn); 01624 } 01625 01626 bool edge_interior(const Vertex_handle& v1, 01627 const Vertex_handle& v2, 01628 const Vertex_handle& v3, 01629 const Vertex_handle& v4, 01630 const Vertex_handle& v, 01631 Sign sgn) const; 01632 01633 inline Arrangement_type 01634 arrangement_type(const Site_2& t, const Vertex_handle& v) const { 01635 if ( is_infinite(v) ) { return AT2::DISJOINT; } 01636 return arrangement_type(t, v->site()); 01637 } 01638 01639 Arrangement_type arrangement_type(const Site_2& p, const Site_2& q) const; 01640 01641 inline 01642 bool are_parallel(const Site_2& p, const Site_2& q) const { 01643 return geom_traits().are_parallel_2_object()(p, q); 01644 } 01645 01646 inline Oriented_side 01647 oriented_side(const Site_2& q, const Site_2& supp, const Site_2& p) const 01648 { 01649 CGAL_precondition( q.is_point() && supp.is_segment() && p.is_point() ); 01650 return geom_traits().oriented_side_2_object()(q, supp, p); 01651 } 01652 01653 inline Oriented_side 01654 oriented_side(const Site_2& s1, const Site_2& s2, const Site_2& s3, 01655 const Site_2& supp, const Site_2& p) const { 01656 CGAL_precondition( supp.is_segment() && p.is_point() ); 01657 return geom_traits().oriented_side_2_object()(s1, s2, s3, supp, p); 01658 } 01659 01660 bool is_degenerate_edge(const Site_2& p1, 01661 const Site_2& p2, 01662 const Site_2& p3, 01663 const Site_2& p4) const { 01664 return geom_traits().is_degenerate_edge_2_object() 01665 (p1, p2, p3, p4); 01666 } 01667 01668 bool is_degenerate_edge(const Vertex_handle& v1, 01669 const Vertex_handle& v2, 01670 const Vertex_handle& v3, 01671 const Vertex_handle& v4) const { 01672 CGAL_precondition( !is_infinite(v1) && !is_infinite(v2) && 01673 !is_infinite(v3) && !is_infinite(v4) ); 01674 01675 return is_degenerate_edge(v1->site(), v2->site(), 01676 v3->site(), v4->site()); 01677 } 01678 01679 bool is_degenerate_edge(const Face_handle& f, int i) const { 01680 Vertex_handle v1 = f->vertex( ccw(i) ); 01681 Vertex_handle v2 = f->vertex( cw(i) ); 01682 Vertex_handle v3 = f->vertex( i ); 01683 Vertex_handle v4 = this->_tds.mirror_vertex(f, i); 01684 01685 return is_degenerate_edge(v1, v2, v3, v4); 01686 } 01687 01688 bool is_degenerate_edge(const Edge& e) const { 01689 return is_degenerate_edge(e.first, e.second); 01690 } 01691 01692 Vertex_handle first_endpoint_of_segment(const Vertex_handle& v) const; 01693 Vertex_handle second_endpoint_of_segment(const Vertex_handle& v) const; 01694 01695 }; // Segment_Delaunay_graph_2 01696 01697 01698 template<class Gt, class D_S, class LTag> 01699 std::istream& operator>>(std::istream& is, 01700 Segment_Delaunay_graph_2<Gt,D_S,LTag>& sdg) 01701 { 01702 sdg.file_input(is); 01703 return is; 01704 } 01705 01706 template<class Gt, class D_S, class LTag> 01707 std::ostream& operator<<(std::ostream& os, 01708 const Segment_Delaunay_graph_2<Gt,D_S,LTag>& sdg) 01709 { 01710 sdg.file_output(os); 01711 return os; 01712 } 01713 01714 CGAL_END_NAMESPACE 01715 01716 01717 #include <CGAL/Segment_Delaunay_graph_2/Segment_Delaunay_graph_2_impl.h> 01718 01719 01720 #endif // CGAL_SEGMENT_DELAUNAY_GRAPH_2_H
1.7.6.1
