1 // Copyright (c) 2006,2007,2009,2010,2011 Tel-Aviv University (Israel). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arr_accessor.h $ 7 // $Id: Arr_accessor.h 3849f5e 2020-06-14T00:41:25+03:00 Efi Fogel 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Ron Wein <wein@post.tau.ac.il> 12 // Efi Fogel <efif@post.tau.ac.il> 13 14 #ifndef CGAL_ARR_ACCESSOR_H 15 #define CGAL_ARR_ACCESSOR_H 16 17 #include <CGAL/license/Arrangement_on_surface_2.h> 18 19 20 /*! \file 21 * Definition of the Arr_accessor<Arrangement> class. 22 */ 23 24 #include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h> 25 #include <CGAL/Arr_point_location_result.h> 26 27 namespace CGAL { 28 29 /*! \class 30 * A class that provides access to some of the internal arrangement operations. 31 * Used mostly by the global insertion functions and by the sweep-line visitors 32 * for utilizing topological and geometrical information available during the 33 * algorithms they perform. 34 * The Arrangement parameter corresponds to an arrangement instantiation 35 * (of the template Arrangement_on_surface_2). 36 */ 37 template <typename Arrangement_> 38 class Arr_accessor { 39 public: 40 typedef Arrangement_ Arrangement_2; 41 typedef Arr_accessor<Arrangement_2> Self; 42 43 typedef typename Arrangement_2::Size Size; 44 typedef typename Arrangement_2::Point_2 Point_2; 45 typedef typename Arrangement_2::X_monotone_curve_2 X_monotone_curve_2; 46 47 typedef typename Arrangement_2::Vertex_handle Vertex_handle; 48 typedef typename Arrangement_2::Vertex_const_handle Vertex_const_handle; 49 typedef typename Arrangement_2::Halfedge_handle Halfedge_handle; 50 typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle; 51 typedef typename Arrangement_2::Face_handle Face_handle; 52 typedef typename Arrangement_2::Face_const_handle Face_const_handle; 53 typedef typename Arrangement_2::Ccb_halfedge_circulator 54 Ccb_halfedge_circulator; 55 56 private: 57 typedef typename Arrangement_2::DVertex DVertex; 58 typedef typename Arrangement_2::DHalfedge DHalfedge; 59 typedef typename Arrangement_2::DFace DFace; 60 typedef typename Arrangement_2::DOuter_ccb DOuter_ccb; 61 typedef typename Arrangement_2::DInner_ccb DInner_ccb; 62 typedef typename Arrangement_2::DIso_vertex DIso_vertex; 63 64 typedef Arr_point_location_result<Arrangement_2> Pl_result; 65 typedef typename Pl_result::Type Pl_result_type; 66 67 private: 68 Arrangement_2* p_arr; // The associated arrangement. 69 70 public: 71 72 /*! Constructor with an associated arrangement. */ Arr_accessor(Arrangement_2 & arr)73 Arr_accessor(Arrangement_2& arr) : p_arr(&arr) {} 74 75 /* Get the arrangement. */ arrangement()76 Arrangement_2& arrangement() { return (*p_arr); } 77 78 /* Get the arrangement (const version). */ arrangement()79 const Arrangement_2& arrangement() const { return (*p_arr); } 80 81 /// \name Accessing the notification functions (for the global functions). 82 //@{ 83 84 /*! Notify that a global operation is about to take place. */ notify_before_global_change()85 void notify_before_global_change() { p_arr->_notify_before_global_change(); } 86 87 /*! Notify that a global operation was completed. */ notify_after_global_change()88 void notify_after_global_change() { p_arr->_notify_after_global_change(); } 89 //@} 90 91 /// \name Local operations and predicates for the arrangement. 92 //@{ 93 94 /*! 95 * Locate the arrangement feature that contains the given curve-end. 96 * \param cv The curve. 97 * \param ind ARR_MIN_END if we refer to cv's minimal end; 98 * ARR_MAX_END if we refer to its maximal end. 99 * \param ps_x The boundary condition in x. 100 * \param ps_y The boundary condition in y. 101 * \pre The relevant end of cv has boundary conditions in x or in y. 102 * \return An object that contains the curve end. 103 * This object may wrap a Face_const_handle (the general case), 104 * or a Halfedge_const_handle (in case of an overlap). 105 */ locate_curve_end(const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y)106 Pl_result_type locate_curve_end(const X_monotone_curve_2& cv, 107 Arr_curve_end ind, 108 Arr_parameter_space ps_x, 109 Arr_parameter_space ps_y) const 110 { 111 CGAL_precondition((ps_x != ARR_INTERIOR) || (ps_y != ARR_INTERIOR)); 112 113 // Use the topology traits to locate the unbounded curve end. 114 auto obj = p_arr->topology_traits()->locate_curve_end(cv, ind, ps_x, ps_y); 115 116 // Return a handle to the DCEL feature. 117 DFace** f_p = boost::get<DFace*>(&obj); 118 if (f_p) return (Pl_result::make_result(p_arr->_const_handle_for(*f_p))); 119 120 DHalfedge** he_p = boost::get<DHalfedge*>(&obj); 121 if (he_p) return (Pl_result::make_result(p_arr->_const_handle_for(*he_p))); 122 123 DVertex** v_p = boost::get<DVertex*>(&obj); 124 if (v_p) return (Pl_result::make_result(p_arr->_const_handle_for(*v_p))); 125 126 // We should never reach here: 127 CGAL_error(); 128 return Pl_result::make_result(Vertex_const_handle()); 129 } 130 131 /*! 132 * Locate the place for the given curve around the given vertex. 133 * \param vh A handle for the arrangement vertex. 134 * \param cv The given x-monotone curve. 135 * \pre v is one of cv's endpoints. 136 * \return A handle for a halfedge whose target is v, where cv should be 137 * inserted between this halfedge and the next halfedge around this 138 * vertex (in a clockwise order). 139 */ locate_around_vertex(Vertex_handle vh,const X_monotone_curve_2 & cv)140 Halfedge_handle locate_around_vertex(Vertex_handle vh, 141 const X_monotone_curve_2& cv) const 142 { 143 typedef 144 Arr_traits_basic_adaptor_2<typename Arrangement_2::Geometry_traits_2> 145 Traits_adaptor_2; 146 147 const Traits_adaptor_2* m_traits = 148 static_cast<const Traits_adaptor_2*> (p_arr->geometry_traits()); 149 150 Arr_curve_end ind = ARR_MIN_END; 151 152 if (m_traits->is_closed_2_object() (cv, ARR_MAX_END) && 153 m_traits->equal_2_object() 154 (vh->point(), m_traits->construct_max_vertex_2_object()(cv))) 155 { 156 ind = ARR_MAX_END; 157 } 158 159 DHalfedge* he = p_arr->_locate_around_vertex(p_arr->_vertex (vh), cv, ind); 160 161 CGAL_assertion(he != nullptr); 162 return (p_arr->_handle_for (he)); 163 } 164 165 /*! 166 * Locate the place for the given curve-end around the given vertex, 167 * which lies on the boundary. 168 * \param vh A handle for the arrangement vertex. 169 * \param cv The curve. 170 * \param ind ARR_MIN_END if we refer to cv's minimal end; 171 * ARR_MAX_END if we refer to its maximal end. 172 * \param ps_x The boundary condition in x. 173 * \param ps_y The boundary condition in y. 174 * \pre The relevant end of cv has boundary conditions in x or in y. 175 * \return A handle for a halfedge whose target is v, where cv should be 176 * inserted between this halfedge and the next halfedge around this 177 * vertex (in a clockwise order). 178 */ 179 Halfedge_handle locate_around_boundary_vertex(Vertex_handle vh,const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y)180 locate_around_boundary_vertex(Vertex_handle vh, 181 const X_monotone_curve_2& cv, 182 Arr_curve_end ind, 183 Arr_parameter_space ps_x, 184 Arr_parameter_space ps_y) const 185 { 186 CGAL_precondition((ps_x != ARR_INTERIOR) || (ps_y != ARR_INTERIOR)); 187 188 // Use the topology traits to locate the unbounded curve end. 189 DHalfedge* he = p_arr->topology_traits()-> 190 locate_around_boundary_vertex(p_arr->_vertex (vh), cv, ind, ps_x, ps_y); 191 192 CGAL_assertion(he != nullptr); 193 return (p_arr->_handle_for (he)); 194 } 195 196 /*! 197 * Compute the distance (in halfedges) between two halfedges. 198 * \param e1 A handle for the source halfedge. 199 * \param e2 A handle for the destination halfedge. 200 * \return In case e1 and e2 belong to the same connected component, the 201 * function returns number of boundary halfedges between the two 202 * halfedges. Otherwise, it returns (-1). 203 */ halfedge_distance(Halfedge_const_handle e1,Halfedge_const_handle e2)204 int halfedge_distance(Halfedge_const_handle e1, 205 Halfedge_const_handle e2) const 206 { 207 // If the two halfedges do not belong to the same component, return (-1). 208 const DHalfedge* he1 = p_arr->_halfedge(e1); 209 const DHalfedge* he2 = p_arr->_halfedge(e2); 210 211 if (he1 == he2) return (0); 212 213 const DInner_ccb* ic1 = (he1->is_on_inner_ccb()) ? he1->inner_ccb() : nullptr; 214 const DOuter_ccb* oc1 = (ic1 == nullptr) ? he1->outer_ccb() : nullptr; 215 const DInner_ccb* ic2 = (he2->is_on_inner_ccb()) ? he2->inner_ccb() : nullptr; 216 const DOuter_ccb* oc2 = (ic2 == nullptr) ? he2->outer_ccb() : nullptr; 217 218 if ((oc1 != oc2) || (ic1 != ic2)) return (-1); 219 220 // Compute the distance between the two halfedges. 221 unsigned int dist = p_arr->_halfedge_distance(he1, he2); 222 return (static_cast<int>(dist)); 223 } 224 225 /*! 226 * Determine whether a given query halfedge lies in the interior of a new 227 * face we are about to create, by connecting it with another halfedge 228 * using a given x-monotone curve. 229 * \param prev1 A handle for the query halfedge. 230 * \param prev2 The other halfedge we are about to connect with prev1. 231 * \param cv The x-monotone curve we use to connect prev1 and prev2. 232 * \pre prev1 and prev2 belong to the same connected component, and by 233 * connecting them using cv we form a new face. 234 * \return (true) if prev1 lies in the interior of the face we are about 235 * to create, (false) otherwise - in which case prev2 must lie 236 * inside this new face. 237 */ defines_outer_ccb_of_new_face(Halfedge_handle prev1,Halfedge_handle prev2,const X_monotone_curve_2 & cv)238 bool defines_outer_ccb_of_new_face(Halfedge_handle prev1, 239 Halfedge_handle prev2, 240 const X_monotone_curve_2& cv) const 241 { 242 return (p_arr->_defines_outer_ccb_of_new_face(p_arr->_halfedge (prev1), 243 p_arr->_halfedge (prev2), 244 cv)); 245 } 246 247 /*! 248 * Check if the given vertex represents one of the ends of a given curve. 249 * \param v The vertex. 250 * \param cv The curve. 251 * \param ind ARR_MIN_END if we refer to cv's minimal end; 252 * ARR_MAX_END if we refer to its maximal end. 253 * \param ps_x The boundary condition of the curve end in x. 254 * \param ps_y The boundary condition of the curve end in y. 255 * \return Whether v represents the left (or right) end of cv. 256 */ are_equal(Vertex_const_handle v,const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y)257 bool are_equal(Vertex_const_handle v, 258 const X_monotone_curve_2& cv, Arr_curve_end ind, 259 Arr_parameter_space ps_x, Arr_parameter_space ps_y) const 260 { 261 return (p_arr->topology_traits()->are_equal(p_arr->_vertex (v), 262 cv, ind, ps_x, ps_y)); 263 } 264 265 /*! 266 * Check whether the given halfedge lies on the outer boundary of its 267 * incident face. 268 * \param he The given halfedge. 269 * \return (true) in case he lies on the outer boundary of its incident face; 270 * (false) if he lies on a hole inside this face. 271 */ is_on_outer_boundary(Halfedge_const_handle he)272 bool is_on_outer_boundary(Halfedge_const_handle he) const 273 { 274 const DHalfedge* p_he = p_arr->_halfedge(he); 275 return (! p_he->is_on_inner_ccb()); 276 } 277 278 /*! 279 * Check whether the given halfedge lies on the inner boundary of its 280 * incident face. 281 * \param he The given halfedge. 282 * \return (true) in case he lies on a hole inside its incident face; 283 * (false) if he lies on the outer boundary of this face. 284 */ is_on_inner_boundary(Halfedge_const_handle he)285 bool is_on_inner_boundary(Halfedge_const_handle he) const 286 { 287 const DHalfedge* p_he = p_arr->_halfedge (he); 288 return (p_he->is_on_inner_ccb()); 289 } 290 291 /*! 292 * Create a new vertex and associate it with the given point. 293 * \param p The point. 294 * \return A handle for the newly created vertex. 295 */ create_vertex(const Point_2 & p)296 Vertex_handle create_vertex(const Point_2& p) 297 { 298 DVertex* v = p_arr->_create_vertex (p); 299 CGAL_assertion(v != nullptr); 300 return (p_arr->_handle_for (v)); 301 } 302 303 /*! 304 * Create a new boundary vertex. 305 * \param cv The curve incident to the boundary. 306 * \param ind The relevant curve-end. 307 * \param ps_x The boundary condition in x. 308 * \param by The boundary condition in y. 309 * \param notify Should we send a notification to the topology traits 310 * on the creation of the vertex (true by default). 311 * \pre Either ps_x or by does not equal ARR_INTERIOR. 312 * \return A handle for the newly created vertex. 313 */ 314 Vertex_handle create_boundary_vertex(const X_monotone_curve_2& cv, 315 Arr_curve_end ind, 316 Arr_parameter_space ps_x, 317 Arr_parameter_space ps_y, 318 bool notify = true) 319 { 320 DVertex* v = p_arr->_create_boundary_vertex (cv, ind, ps_x, ps_y); 321 322 CGAL_assertion(v != nullptr); 323 324 // Notify the topology traits on the creation of the boundary vertex. 325 if (notify) 326 p_arr->topology_traits()->notify_on_boundary_vertex_creation(v, cv, ind, 327 ps_x, ps_y); 328 return (p_arr->_handle_for(v)); 329 } 330 331 /*! 332 * Locate the arrangement features that will be used for inserting the 333 * given curve end, which has a boundary condition, and set a proper vertex 334 * there. 335 * \param f The face that contains the curve end. 336 * \param cv The x-monotone curve. 337 * \param ind The curve end. 338 * \param ps_x The boundary condition at the x-coordinate. 339 * \param ps_y The boundary condition at the y-coordinate. 340 * \return A pair of <Vertex_handle, Halfedge_handle>: 341 * The first element is the vertex that corresponds to the curve end. 342 * The second is its predecessor halfedge (if valid). 343 */ 344 std::pair<Vertex_handle, Halfedge_handle> place_and_set_curve_end(Face_handle f,const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y)345 place_and_set_curve_end(Face_handle f, 346 const X_monotone_curve_2& cv, Arr_curve_end ind, 347 Arr_parameter_space ps_x, Arr_parameter_space ps_y) 348 { 349 DHalfedge* pred; 350 DVertex* v = p_arr->_place_and_set_curve_end(p_arr->_face (f), cv, ind, 351 ps_x, ps_y, &pred); 352 353 if (pred == nullptr) 354 // No predecessor halfedge, return just the vertex: 355 return (std::make_pair(p_arr->_handle_for(v), Halfedge_handle())); 356 357 // Return a pair of the vertex and predecessor halfedge: 358 return (std::make_pair(p_arr->_handle_for(v), p_arr->_handle_for(pred))); 359 } 360 361 /*! 362 * Insert an x-monotone curve into the arrangement, where the end vertices 363 * are given by the target points of two given halfedges. 364 * The two halfedges should be given such that in case a new face is formed, 365 * it will be the incident face of the halfedge directed from the first 366 * vertex to the second vertex. 367 * \param he_to The reference halfedge pointing to the first vertex. 368 * \param cv the given curve. 369 * \param cv_dir the direction of the curve 370 * \param he_away The reference halfedge pointing away from the second vertex. 371 * \param new_face Output - whether a new face has been created. 372 * \param swapped_predecessors Output - whether roles of prev1 and prev2 have 373 * been switched 374 * \param allow_swap_of_predecessors - set to false if no swapping should 375 * take place at all 376 * \return A handle for one of the halfedges corresponding to the inserted 377 * curve directed from prev1's target to prev2's target. 378 * In case a new face has been created, it is given as the incident 379 * face of this halfedge. 380 */ 381 Halfedge_handle insert_at_vertices_ex(Halfedge_handle he_to, 382 const X_monotone_curve_2& cv, 383 Arr_halfedge_direction cv_dir, 384 Halfedge_handle he_away, 385 bool& new_face, 386 bool& swapped_predecessors, 387 bool allow_swap_of_predecessors = true) 388 { 389 DHalfedge* he = p_arr->_insert_at_vertices(p_arr->_halfedge (he_to), 390 cv, cv_dir, 391 p_arr->_halfedge (he_away), 392 new_face, swapped_predecessors, 393 allow_swap_of_predecessors); 394 395 CGAL_assertion(he != nullptr); 396 return (p_arr->_handle_for(he)); 397 } 398 399 /*! 400 * Insert an x-monotone curve into the arrangement, such that one of its 401 * endpoints corresponds to a given arrangement vertex, given the exact 402 * place for the curve in the circular list around this vertex. The other 403 * endpoint corrsponds to a free vertex (a newly created vertex or an 404 * isolated vertex). 405 * \param he_to The reference halfedge. We should represent cv as a pair 406 * of edges, one of them should become he_to's successor. 407 * \param cv The given x-monotone curve. 408 * \param cv_dir The direction of the curve. 409 * \param v The free vertex that corresponds to the other endpoint. 410 * \return A handle to one of the halfedges corresponding to the inserted 411 * curve, whose target is the vertex v. 412 */ insert_from_vertex_ex(Halfedge_handle he_to,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,Vertex_handle v)413 Halfedge_handle insert_from_vertex_ex(Halfedge_handle he_to, 414 const X_monotone_curve_2& cv, 415 Arr_halfedge_direction cv_dir, 416 Vertex_handle v) 417 { 418 DVertex* p_v = p_arr->_vertex(v); 419 if (p_v->is_isolated()) { 420 // Remove the isolated vertex record, which will not be isolated any 421 // more. 422 DIso_vertex* iv = p_v->isolated_vertex(); 423 DFace* f = iv->face(); 424 425 f->erase_isolated_vertex (iv); 426 p_arr->_dcel().delete_isolated_vertex(iv); 427 } 428 429 DHalfedge* he = 430 p_arr->_insert_from_vertex(p_arr->_halfedge(he_to), cv, cv_dir, p_v); 431 432 CGAL_assertion(he != nullptr); 433 return (p_arr->_handle_for (he)); 434 } 435 436 /*! 437 * Insert an x-monotone curve into the arrangement, such that both its 438 * endpoints correspond to free arrangement vertices (newly created vertices 439 * or existing isolated vertices), so a new hole is formed in the face 440 * that contains the two vertices. 441 * \param f The face containing the two end vertices. 442 * \param cv The given x-monotone curve. 443 * \param cv_dir The direction of the curve. 444 * \param v1 The free vertex that corresponds to the left endpoint of cv. 445 * \param v2 The free vertex that corresponds to the right endpoint of cv. 446 * \return A handle to one of the halfedges corresponding to the inserted 447 * curve, directed from v1 to v2. 448 */ insert_in_face_interior_ex(Face_handle f,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,Vertex_handle v1,Vertex_handle v2)449 Halfedge_handle insert_in_face_interior_ex(Face_handle f, 450 const X_monotone_curve_2& cv, 451 Arr_halfedge_direction cv_dir, 452 Vertex_handle v1, 453 Vertex_handle v2) 454 { 455 DVertex* p_v1 = p_arr->_vertex (v1); 456 DVertex* p_v2 = p_arr->_vertex (v2); 457 458 if (p_v1->is_isolated()) { 459 // Remove the isolated vertex record, which will not be isolated any 460 // more. 461 DIso_vertex* iv1 = p_v1->isolated_vertex(); 462 DFace* f1 = iv1->face(); 463 f1->erase_isolated_vertex(iv1); 464 p_arr->_dcel().delete_isolated_vertex(iv1); 465 } 466 467 if (p_v2->is_isolated()) { 468 // Remove the isolated vertex record, which will not be isolated any 469 // more. 470 DIso_vertex* iv2 = p_v2->isolated_vertex(); 471 DFace* f2 = iv2->face(); 472 f2->erase_isolated_vertex(iv2); 473 p_arr->_dcel().delete_isolated_vertex(iv2); 474 } 475 476 DHalfedge* he = p_arr->_insert_in_face_interior(p_arr->_face (f), 477 cv, cv_dir, p_v1, p_v2); 478 479 CGAL_assertion(he != nullptr); 480 return (p_arr->_handle_for (he)); 481 482 } 483 484 /*! 485 * Insert the given vertex as an isolated vertex inside the given face. 486 * \param f The face that should contain the isolated vertex. 487 * \param v The isolated vertex. 488 */ insert_isolated_vertex(Face_handle f,Vertex_handle v)489 void insert_isolated_vertex(Face_handle f, Vertex_handle v) 490 { p_arr->_insert_isolated_vertex(p_arr->_face (f), p_arr->_vertex(v)); } 491 492 /*! 493 * Relocate all holes and isolated vertices to their proper position, 494 * immediately after a face has split due to the insertion of a new halfedge. 495 * In case insert_at_vertices_ex() was invoked and indicated that a new face 496 * has been created, this function should be called with the halfedge 497 * returned by insert_at_vertices_ex(). 498 * \param new_he The new halfedge that caused the split, such that the new 499 * face lies to its left and the old face to its right. 500 */ relocate_in_new_face(Halfedge_handle new_he)501 void relocate_in_new_face(Halfedge_handle new_he) 502 { p_arr->_relocate_in_new_face (p_arr->_halfedge (new_he)); } 503 relocate_isolated_vertices_in_new_face(Halfedge_handle new_he)504 void relocate_isolated_vertices_in_new_face(Halfedge_handle new_he) 505 { 506 p_arr->_relocate_isolated_vertices_in_new_face(p_arr->_halfedge(new_he)); 507 } 508 relocate_holes_in_new_face(Halfedge_handle new_he)509 void relocate_holes_in_new_face(Halfedge_handle new_he) 510 { p_arr->_relocate_holes_in_new_face(p_arr->_halfedge(new_he)); } 511 512 /*! 513 * Move an outer CCB from one face to another. 514 * \param from_face The source face. 515 * \param to_face The destination face. 516 * \param ccb A CCB circulator that corresponds to component to move. 517 */ move_outer_ccb(Face_handle from_face,Face_handle to_face,Ccb_halfedge_circulator ccb)518 void move_outer_ccb(Face_handle from_face, Face_handle to_face, 519 Ccb_halfedge_circulator ccb) 520 { 521 p_arr->_move_outer_ccb(p_arr->_face(from_face), p_arr->_face(to_face), 522 p_arr->_halfedge (ccb)); 523 } 524 525 /*! 526 * Move an inner CCB from one face to another. 527 * \param from_face The source face. 528 * \param to_face The destination face. 529 * \param ccb A CCB circulator that corresponds to component to move. 530 */ move_inner_ccb(Face_handle from_face,Face_handle to_face,Ccb_halfedge_circulator ccb)531 void move_inner_ccb (Face_handle from_face, Face_handle to_face, 532 Ccb_halfedge_circulator ccb) 533 { 534 p_arr->_move_inner_ccb(p_arr->_face(from_face), p_arr->_face(to_face), 535 p_arr->_halfedge(ccb)); 536 } 537 538 /*! 539 * Move an isolated vertex from one face to another. 540 * \param from_face The source face. 541 * \param to_face The destination face. 542 * \param v The isolated vertex to move. 543 */ move_isolated_vertex(Face_handle from_face,Face_handle to_face,Vertex_handle v)544 void move_isolated_vertex(Face_handle from_face, Face_handle to_face, 545 Vertex_handle v) 546 { 547 p_arr->_move_isolated_vertex(p_arr->_face(from_face), 548 p_arr->_face(to_face), p_arr->_vertex(v)); 549 } 550 551 /*! 552 * Remove an isolated vertex from its face. 553 * \param v The isolated vertex to remove. 554 */ remove_isolated_vertex_ex(Vertex_handle v)555 void remove_isolated_vertex_ex (Vertex_handle v) 556 { 557 CGAL_precondition(v->is_isolated()); 558 DVertex* iso_v = p_arr->_vertex(v); 559 p_arr->_remove_isolated_vertex(iso_v); 560 } 561 562 /*! 563 * Modify the point associated with a given vertex. The point may be 564 * geometrically different than the one currently associated with the vertex. 565 * \param v The vertex to modify. 566 * \param p The new point to associate with v. 567 * \return A handle for the modified vertex (same as v). 568 */ modify_vertex_ex(Vertex_handle v,const Point_2 & p)569 Vertex_handle modify_vertex_ex(Vertex_handle v, const Point_2& p) 570 { 571 p_arr->_modify_vertex(p_arr->_vertex(v), p); 572 return v; 573 } 574 575 /*! 576 * Modify the x-monotone curve associated with a given edge. The curve may be 577 * geometrically different than the one currently associated with the edge. 578 * \param e The edge to modify. 579 * \param cv The new x-monotone curve to associate with e. 580 * \return A handle for the modified edge (same as e). 581 */ modify_edge_ex(Halfedge_handle e,const X_monotone_curve_2 & cv)582 Halfedge_handle modify_edge_ex(Halfedge_handle e, 583 const X_monotone_curve_2& cv) 584 { 585 p_arr->_modify_edge(p_arr->_halfedge (e), cv); 586 return e; 587 } 588 589 /*! 590 * Split a given edge into two at a given point, and associate the given 591 * x-monotone curves with the split edges. 592 * \param e The edge to split (one of the pair of twin halfegdes). 593 * \param p The split point. 594 * \param cv1 The curve that should be associated with the first split edge, 595 * whose source equals e's source and its target is p. 596 * \param cv2 The curve that should be associated with the second split edge, 597 * whose source is p and its target equals e's target. 598 * \return A handle for the first split halfedge, whose source equals the 599 * source of e, and whose target is the split point. 600 */ split_edge_ex(Halfedge_handle e,const Point_2 & p,const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2)601 Halfedge_handle split_edge_ex(Halfedge_handle e, const Point_2& p, 602 const X_monotone_curve_2& cv1, 603 const X_monotone_curve_2& cv2) 604 { 605 DHalfedge* he = p_arr->_split_edge (p_arr->_halfedge(e), p, cv1, cv2); 606 607 CGAL_assertion(he != nullptr); 608 return (p_arr->_handle_for(he)); 609 } 610 611 /*! 612 * Split a given edge into two at the given vertex, and associate the given 613 * x-monotone curves with the split edges. 614 * \param e The edge to split (one of the pair of twin halfegdes). 615 * \param v The split vertex. 616 * \param cv1 The curve that should be associated with the first split edge, 617 * whose source equals e's source and its target is v's point. 618 * \param cv2 The curve that should be associated with the second split edge, 619 * whose source is v's point and its target equals e's target. 620 * \return A handle for the first split halfedge, whose source equals the 621 * source of e, and whose target is the split vertex v. 622 */ split_edge_ex(Halfedge_handle e,Vertex_handle v,const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2)623 Halfedge_handle split_edge_ex(Halfedge_handle e, Vertex_handle v, 624 const X_monotone_curve_2& cv1, 625 const X_monotone_curve_2& cv2) 626 { 627 DHalfedge* he = p_arr->_split_edge(p_arr->_halfedge(e), p_arr->_vertex(v), 628 cv1, cv2); 629 630 CGAL_assertion (he != nullptr); 631 return (p_arr->_handle_for(he)); 632 } 633 634 /*! 635 * Split a fictitious edge at the given vertex. 636 * \param e The edge to split (one of the pair of twin halfegdes). 637 * \param v The split vertex. 638 * \return A handle for the first split halfedge, whose source equals the 639 * source of e, and whose target is the split vertex v. 640 */ split_fictitious_edge(Halfedge_handle e,Vertex_handle v)641 Halfedge_handle split_fictitious_edge(Halfedge_handle e, Vertex_handle v) 642 { 643 CGAL_precondition(e->is_fictitious()); 644 DHalfedge* he = 645 p_arr->topology_traits()->split_fictitious_edge(p_arr->_halfedge(e), 646 p_arr->_vertex(v)); 647 return (p_arr->_handle_for(he)); 648 } 649 650 /*! 651 * Remove a pair of twin halfedges from the arrangement. 652 * \param e A handle for one of the halfedges to be removed. 653 * \param remove_source Should the source vertex of e be removed if it 654 * becomes isolated (true by default). 655 * \param remove_target Should the target vertex of e be removed if it 656 * becomes isolated (true by default). 657 * \pre In case the removal causes the creation of a new hole, e should 658 * point at this hole. 659 * \return A handle for the remaining face. 660 */ 661 Face_handle remove_edge_ex(Halfedge_handle e, 662 bool remove_source = true, 663 bool remove_target = true) 664 { 665 DFace* f = 666 p_arr->_remove_edge(p_arr->_halfedge (e), remove_source, remove_target); 667 CGAL_assertion(f != nullptr); 668 return (p_arr->_handle_for(f)); 669 } 670 671 /*! 672 * Check if the two given halfedges lie on the same inner component. 673 * \param e1 A handle for the first halfedge. 674 * \param e2 A handle for the second halfedge. 675 * \return Whether e1 and e2 lie on the same inner component. 676 */ are_on_same_inner_component(Halfedge_handle e1,Halfedge_handle e2)677 bool are_on_same_inner_component(Halfedge_handle e1, Halfedge_handle e2) 678 { 679 DHalfedge* he1 = p_arr->_halfedge(e1); 680 DHalfedge* he2 = p_arr->_halfedge(e2); 681 const DInner_ccb* ic1 = (he1->is_on_inner_ccb()) ? he1->inner_ccb() : nullptr; 682 if (ic1 == nullptr) return (false); 683 const DInner_ccb* ic2 = (he2->is_on_inner_ccb()) ? he2->inner_ccb() : nullptr; 684 return (ic1 == ic2); 685 } 686 687 /*! 688 * Check if the two given halfedges lie on the same outer component. 689 * \param e1 A handle for the first halfedge. 690 * \param e2 A handle for the second halfedge. 691 * \return Whether e1 and e2 lie on the same outer component. 692 */ are_on_same_outer_component(Halfedge_handle e1,Halfedge_handle e2)693 bool are_on_same_outer_component(Halfedge_handle e1, Halfedge_handle e2) 694 { 695 DHalfedge* he1 = p_arr->_halfedge(e1); 696 DHalfedge* he2 = p_arr->_halfedge(e2); 697 const DOuter_ccb* oc1 = (he1->is_on_outer_ccb()) ? he1->outer_ccb() : nullptr; 698 if (oc1 == nullptr) return (false); 699 const DOuter_ccb* oc2 = (he2->is_on_outer_ccb()) ? he2->outer_ccb() : nullptr; 700 return (oc1 == oc2); 701 } 702 //@} 703 704 /// \name Traversal methods for the BOOST graph traits. 705 //@{ 706 707 /*! \class 708 * An iterator for traversing all arrangement vertices, including vertices 709 * at infinity (not including fictitious vertices). 710 */ 711 typedef typename Arrangement_2::_Is_valid_vertex Is_valid_vertex; 712 typedef typename Arrangement_2::_Valid_vertex_iterator Valid_vertex_iterator; 713 714 /*! Get an iterator for the first valid arrangement vertex. */ valid_vertices_begin()715 Valid_vertex_iterator valid_vertices_begin() 716 { 717 return (Valid_vertex_iterator 718 (p_arr->topology_traits()->dcel().vertices_begin(), 719 p_arr->topology_traits()->dcel().vertices_end(), 720 Is_valid_vertex (p_arr->topology_traits()))); 721 } 722 723 /*! Get a past-the-end iterator for the valid arrangement vertices. */ valid_vertices_end()724 Valid_vertex_iterator valid_vertices_end() 725 { 726 return (Valid_vertex_iterator 727 (p_arr->topology_traits()->dcel().vertices_end(), 728 p_arr->topology_traits()->dcel().vertices_end(), 729 Is_valid_vertex (p_arr->topology_traits()))); 730 } 731 732 /*! Get the number of valid arrangement vertices. */ number_of_valid_vertices()733 Size number_of_valid_vertices() const 734 { 735 return (p_arr->topology_traits()->number_of_valid_vertices()); 736 } 737 //@} 738 739 /// \name Functions used by the arrangement reader and writer. 740 //@{ 741 typedef typename Arrangement_2::Dcel Dcel; 742 typedef typename Arrangement_2::DVertex_const_iter Dcel_vertex_iterator; 743 typedef typename Arrangement_2::DEdge_const_iter Dcel_edge_iterator; 744 typedef typename Arrangement_2::DFace_const_iter Dcel_face_iterator; 745 typedef typename Arrangement_2::DOuter_ccb_const_iter 746 Dcel_outer_ccb_iterator; 747 typedef typename Arrangement_2::DInner_ccb_const_iter 748 Dcel_inner_ccb_iterator; 749 typedef typename Arrangement_2::DIso_vertex_const_iter 750 Dcel_iso_vertex_iterator; 751 752 typedef DVertex Dcel_vertex; 753 typedef DHalfedge Dcel_halfedge; 754 typedef DFace Dcel_face; 755 typedef DOuter_ccb Dcel_outer_ccb; 756 typedef DInner_ccb Dcel_inner_ccb; 757 typedef DIso_vertex Dcel_isolated_vertex; 758 759 /*! 760 * Get the arrangement DCEL. 761 */ dcel()762 const Dcel& dcel() const { return (p_arr->_dcel()); } 763 764 /*! 765 * Clear the entire arrangment. 766 */ clear_all()767 void clear_all() 768 { 769 p_arr->clear(); 770 p_arr->_dcel().delete_all(); 771 } 772 773 /*! 774 * Set the boundary of a vertex 775 * \param p A vertex 776 * \param ps_x The boundary condition at x. 777 * \param ps_y The boundary condition at y. 778 * \return A pointer to the created DCEL vertex. 779 */ set_vertex_boundary(const Vertex_handle v,Arr_parameter_space ps_x,Arr_parameter_space ps_y)780 Dcel_vertex* set_vertex_boundary(const Vertex_handle v, 781 Arr_parameter_space ps_x, 782 Arr_parameter_space ps_y) 783 { 784 Dcel_vertex* v_to_set = p_arr->_vertex(v); 785 v_to_set->set_boundary(ps_x, ps_y); 786 return (v_to_set); 787 } 788 789 /*! 790 * Create a new vertex. 791 * \param p A pointer to the point (may be nullptr in case of a vertex at 792 * infinity). 793 * \param ps_x The boundary condition at x. 794 * \param ps_y The boundary condition at y. 795 * \return A pointer to the created DCEL vertex. 796 */ new_vertex(const Point_2 * p,Arr_parameter_space ps_x,Arr_parameter_space ps_y)797 Dcel_vertex* new_vertex(const Point_2* p, 798 Arr_parameter_space ps_x, Arr_parameter_space ps_y) 799 { 800 Dcel_vertex* new_v = p_arr->_dcel().new_vertex(); 801 if (p != nullptr) { 802 typename Dcel::Vertex::Point* p_pt = p_arr->_new_point(*p); 803 new_v->set_point(p_pt); 804 } 805 else 806 { 807 CGAL_precondition (p_arr->is_open(ps_x, ps_y)); 808 new_v->set_point (nullptr); 809 } 810 811 new_v->set_boundary (ps_x, ps_y); 812 return (new_v); 813 } 814 815 /*! 816 * Create a new edge (halfedge pair), associated with the given curve. 817 * \param cv A pointer to the x-monotone curve (may be nullptr in case of 818 * a fictitious edge). 819 * \return A pointer to one of the created DCEL halfedge. 820 */ new_edge(const X_monotone_curve_2 * cv)821 Dcel_halfedge* new_edge(const X_monotone_curve_2* cv) 822 { 823 Dcel_halfedge* new_he = p_arr->_dcel().new_edge(); 824 825 if (cv != nullptr) { 826 typename Dcel::Halfedge::X_monotone_curve* p_cv = p_arr->_new_curve(*cv); 827 new_he->set_curve(p_cv); 828 } 829 else new_he->set_curve(nullptr); 830 return new_he; 831 } 832 833 /*! 834 * Create a new face. 835 * \return A pointer to the created DCEL face. 836 */ new_face()837 Dcel_face* new_face() { return (p_arr->_dcel().new_face()); } 838 839 /*! 840 * Create a new outer CCB. 841 * \return A pointer to the created DCEL outer CCB. 842 */ new_outer_ccb()843 Dcel_outer_ccb* new_outer_ccb() { return (p_arr->_dcel().new_outer_ccb()); } 844 845 /*! 846 * Create a new inner CCB. 847 * \return A pointer to the created DCEL inner CCB. 848 */ new_inner_ccb()849 Dcel_inner_ccb* new_inner_ccb() 850 { return (p_arr->_dcel().new_inner_ccb()); } 851 852 /*! 853 * Create a new isolated vertex. 854 * \return A pointer to the created DCEL isolated vertex. 855 */ new_isolated_vertex()856 Dcel_isolated_vertex* new_isolated_vertex() 857 { return (p_arr->_dcel().new_isolated_vertex()); } 858 859 /*! 860 * Remove a range of vertices 861 */ 862 template <typename VertexRange> delete_vertices(const VertexRange & range)863 void delete_vertices(const VertexRange& range) 864 { 865 for(typename VertexRange::const_iterator it=range.begin(), 866 end=range.end(); 867 it!=end; ++it) 868 { 869 CGAL_assertion(! (*it)->has_null_point()); 870 p_arr->_delete_point( (*it)->point() ); 871 p_arr->_dcel().delete_vertex( *it ); 872 } 873 } 874 875 /*! 876 * Remove a range of edges 877 */ 878 template <typename EdgeRange> delete_edges(const EdgeRange & range)879 void delete_edges(const EdgeRange& range) 880 { 881 for(typename EdgeRange::const_iterator it=range.begin(), 882 end=range.end(); 883 it!=end; ++it) 884 { 885 CGAL_assertion(! (*it)->has_null_curve()); 886 p_arr->_delete_curve( (*it)->curve() ); 887 p_arr->_dcel().delete_edge( *it ); 888 } 889 } 890 891 /*! 892 * Remove a range of faces 893 */ 894 template <typename FaceRange> delete_faces(const FaceRange & range)895 void delete_faces(const FaceRange& range) 896 { 897 for(typename FaceRange::const_iterator it=range.begin(), 898 end=range.end(); 899 it!=end; ++it) 900 { 901 p_arr->_dcel().delete_face( *it ); 902 } 903 } 904 905 /*! 906 * Remove a range of outer ccbs 907 */ 908 template <typename CcbRange> delete_outer_ccbs(const CcbRange & range)909 void delete_outer_ccbs(const CcbRange& range) 910 { 911 for(typename CcbRange::const_iterator it=range.begin(), 912 end=range.end(); 913 it!=end; ++it) 914 { 915 p_arr->_dcel().delete_outer_ccb( *it ); 916 } 917 } 918 919 /*! 920 * Remove a range of inner ccbs 921 */ 922 template <typename CcbRange> delete_inner_ccbs(const CcbRange & range)923 void delete_inner_ccbs(const CcbRange& range) 924 { 925 for(typename CcbRange::const_iterator it=range.begin(), 926 end=range.end(); 927 it!=end; ++it) 928 { 929 p_arr->_dcel().delete_inner_ccb( *it ); 930 } 931 } 932 933 /*! 934 * Update the topology traits after the DCEL has been updated. 935 */ dcel_updated()936 void dcel_updated() { p_arr->topology_traits()->dcel_updated(); } 937 //@} 938 939 }; 940 941 } //namespace CGAL 942 943 #endif 944