1 // Copyright (c) 1997
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel). All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/HalfedgeDS/include/CGAL/halfedgeDS_cut_component.h $
11 // $Id: halfedgeDS_cut_component.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s) : Lutz Kettner <kettner@mpi-sb.mpg.de>
16
17 // Cuts out a piece of a halfedge data structure defined by a predicate.
18
19
20 #ifndef CGAL_HALFEDGEDS_CUT_COMPONENT_H
21 #define CGAL_HALFEDGEDS_CUT_COMPONENT_H 1
22
23 #include <CGAL/disable_warnings.h>
24
25 #include <CGAL/basic.h>
26 #include <CGAL/HalfedgeDS_decorator.h>
27
28 namespace CGAL {
29
30
31 template < class HDS, class Predicate >
32 typename HDS::Halfedge_handle
halfedgeDS_cut_component(HDS & hds,typename HDS::Halfedge_handle h,Predicate pred,typename HDS::Halfedge_handle & cut_piece)33 halfedgeDS_cut_component( HDS& hds,
34 typename HDS::Halfedge_handle h,
35 Predicate pred,
36 typename HDS::Halfedge_handle& cut_piece)
37 // Cuts out a piece of a halfedge data structure for which the predicate
38 // `pred' is true for the vertices.
39 // The edge-vertex graph of the piece has to be a connected component.
40 // The remaining piece gets a new boundary. Returns a border halfedge of
41 // the new boundary on the remaining piece. Assigns a halfedge of the
42 // cut outpiece to `cut_piece'.
43 // The geometry for the vertices
44 // on the boundary and the hole have to be taken care of after this
45 // function call. The cut-out piece can be deleted with the member
46 // function erase_connected_component of the decorator class. It can
47 // technically happen that only an isolated vertex would remain in the
48 // cut out piece, in which case a dummy halfedge pair and vertex will be
49 // created to keep this vertex representable in the halfedge data structure.
50 // Precondition: pred( h->vertex()) && ! pred( h->opposite()->vertex()).
51 {
52 typedef typename HDS::Vertex_handle Vertex_handle;
53 typedef typename HDS::Halfedge_handle Halfedge_handle;
54 typedef typename HDS::Face_handle Face_handle;
55 typedef typename HDS::Vertex Vertex;
56 typedef typename HDS::Halfedge Halfedge;
57 typedef typename HDS::Face Face;
58 CGAL::HalfedgeDS_decorator<HDS> D(hds);
59
60 CGAL_precondition( D.is_valid(false,3));
61 CGAL_precondition( pred( h->vertex()));
62 CGAL_precondition( ! pred( h->opposite()->vertex()));
63
64 Halfedge_handle start = h;
65 Halfedge_handle hnew;
66 Halfedge_handle hlast;
67 while (true) {
68 // search re-entry point
69 Halfedge_handle g = h;
70 while ( pred( g->next()->vertex())) {
71 g = g->next();
72 // create border edges around cap
73 D.set_face( g, Face_handle());
74 }
75 if ( hnew == Halfedge_handle()) {
76 // first edge, special case
77 CGAL_assertion( g->next() != h && g->next()->opposite() != h);
78 Halfedge_handle gnext = g->next()->opposite();
79 D.remove_tip( g);
80 Vertex_handle v = D.vertices_push_back( Vertex());
81 D.close_tip( gnext, v);
82 hnew = hds.edges_push_back( Halfedge(), Halfedge());
83 hlast = hnew->opposite();
84 D.insert_tip( hlast, gnext);
85 D.set_face( hnew, D.get_face( gnext));
86 D.set_face_halfedge( hnew);
87 h = g;
88 D.set_vertex_halfedge( h);
89 } else { // general case and last case
90 Halfedge_handle gnext = g->next()->opposite();
91 if ( gnext == start && gnext == g) {
92 // last edge, special case of isolated vertex.
93 // Create dummy edge and dummy vertex and attach it to g
94 g = hds.edges_push_back( Halfedge(), Halfedge());
95 D.insert_tip( g, gnext);
96 D.close_tip(g->opposite(), D.vertices_push_back(Vertex()));
97 D.set_vertex_halfedge( g);
98 D.set_vertex_halfedge( g->opposite());
99 }
100 D.remove_tip( g);
101 Vertex_handle v = D.vertices_push_back( Vertex());
102 D.close_tip( hnew, v);
103 D.insert_tip( gnext, hnew);
104 hnew = hds.edges_push_back( Halfedge(), Halfedge());
105 D.insert_tip( hnew->opposite(), gnext);
106 D.set_face( hnew, D.get_face( gnext));
107 D.set_face_halfedge( hnew);
108 h = g;
109 D.set_vertex_halfedge( h);
110 if ( gnext == start) {
111 // last edge, special
112 D.insert_tip( hnew, hlast);
113 break;
114 }
115 }
116 } // while(true)
117 Face_handle fnew = D.faces_push_back( Face());
118 D.set_face_in_face_loop( hlast, fnew);
119 D.set_face_halfedge( hlast);
120 cut_piece = h;
121 CGAL_postcondition( D.is_valid(false,3));
122 return hlast;
123 }
124
125 template < class HDS, class Predicate >
126 typename HDS::Halfedge_handle
halfedgeDS_cut_component(HDS & hds,typename HDS::Halfedge_handle h,Predicate pred)127 halfedgeDS_cut_component( HDS& hds,
128 typename HDS::Halfedge_handle h,
129 Predicate pred)
130 // Same function as above, but deletes the cut out piece immediately.
131 {
132 typedef typename HDS::Halfedge_handle Halfedge_handle;
133 CGAL::HalfedgeDS_decorator<HDS> D(hds);
134
135 CGAL_precondition( D.is_valid(false,3));
136 CGAL_precondition( pred( h->vertex()));
137 CGAL_precondition( ! pred( h->opposite()->vertex()));
138 Halfedge_handle cut_piece;
139 Halfedge_handle hnew = halfedgeDS_cut_component( hds, h, pred, cut_piece);
140 D.erase_connected_component( cut_piece);
141 CGAL_postcondition( D.is_valid(false,3));
142 return hnew;
143 }
144
145 } //namespace CGAL
146
147 #include <CGAL/enable_warnings.h>
148
149 #endif // CGAL_HALFEDGEDS_CUT_COMPONENT_H //
150 // EOF //
151