1 // Copyright (c) 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_spherical_gaussian_map_3/Arr_transform_on_sphere.h $
7 // $Id: Arr_transform_on_sphere.h 03a2d28 2020-06-14T10:47:45+03:00 Efi Fogel
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 // Author(s) : Naama mayer <naamamay@post.tau.ac.il>
11
12
13 // This includes a function for rotating an arrangement on a sphere with
14 // geodesic arcs.
15 // It should be templated with a transformation (affine transformations) and a
16 // transformation traits, defines the way the faces should be rotated.
17
18
19 #ifndef CGAL_ARR_SGM_3_ATOS_H
20 #define CGAL_ARR_SGM_3_ATOS_H
21
22 #include <CGAL/license/Arrangement_on_surface_2.h>
23
24
25 #include <CGAL/Aff_transformation_3.h>
26 #include <CGAL/Arr_spherical_gaussian_map_3/Arr_polyhedral_sgm.h>
27
28 namespace CGAL {
29
30 template < class Arrangement, class Transformation_3, class TransformTraits>
Arr_transform_on_sphere(Arrangement & arr,const Transformation_3 & aff,TransformTraits & tran_tr)31 void Arr_transform_on_sphere(Arrangement & arr,
32 const Transformation_3 & aff,
33 TransformTraits & tran_tr)
34 {
35 typedef typename Arrangement::Geometry_traits_2 Geometry_traits_2;
36 typedef typename Arrangement::Topology_traits Topology_traits;
37
38 typedef typename Geometry_traits_2::Point_2 Point_2;
39 typedef typename Geometry_traits_2::Curve_2 Curve_2;
40 typedef typename Geometry_traits_2::X_monotone_curve_2 X_monotone_curve_2;
41
42 typedef typename Arrangement::Vertex_handle Vertex_handle;
43 typedef typename Arrangement::Halfedge_handle Halfedge_handle;
44 typedef typename Arrangement::Face_handle Face_handle;
45 typedef typename Arrangement::Edge_iterator Edge_iterator;
46 typedef typename Arrangement::Halfedge_around_vertex_circulator
47 Halfedge_around_vertex_circulator;
48
49 typedef boost::variant<Point_2, X_monotone_curve_2> Make_x_monotone_result;
50
51 const Geometry_traits_2 * geom_traits = arr.geometry_traits();
52 Topology_traits * topol_traits = arr.topology_traits();
53
54 Arr_accessor<Arrangement> m_arr_access(arr);
55
56 // Preprocessing loop - merge all the edges that were splited
57 // (meaning have a common endpoint that lies on the boundary and their degree
58 // is 2) on the identification curve.
59 for (auto vi1 = arr.vertices_begin(); vi1 != arr.vertices_end(); ) {
60 Vertex_handle v_temp = vi1;
61 ++vi1;
62
63 Arr_parameter_space bx =
64 geom_traits->parameter_space_in_x_2_object()(v_temp->point());
65 Arr_parameter_space by =
66 geom_traits->parameter_space_in_y_2_object()(v_temp->point());
67
68 // use vertex->parameter_space_in_x() != interior ||
69 // vertex->parameter_space_in_y() != interior)
70 if ((bx != ARR_INTERIOR || by != ARR_INTERIOR) && (v_temp->degree() == 2)) {
71 Curve_2 merged_cv;
72 Halfedge_around_vertex_circulator havc = v_temp->incident_halfedges();
73 Halfedge_around_vertex_circulator havc_next = havc;
74 ++havc_next;
75
76 // Compare the normals
77 bool normal_eq1 = havc->curve().normal() ==
78 havc_next->twin()->curve().normal();
79 // Compare the points
80 bool point_eq1 = havc->target()->point() ==
81 havc_next->twin()->source()->point();
82 // Compare the direction of the edges.
83 bool eq_direction = havc->direction() == havc_next->twin()->direction();
84
85 if (point_eq1 && normal_eq1 && eq_direction) {
86 if (havc->source()->point() == havc->curve().source()) {
87 merged_cv = Curve_2(havc->source()->point(),
88 havc_next->twin()->target()->point(),
89 havc->curve().normal());
90 }
91 else if (havc->source()->point() == havc->curve().target()) {
92 merged_cv = Curve_2(havc_next->twin()->target()->point(),
93 havc->source()->point(),
94 havc->curve().normal());
95 }
96 else
97 CGAL_error_msg
98 ("One of the edge points should be equal to the surce points");
99
100 // Erases the point from the list of boundary vertices (This is a
101 // different data structute than the DCEL, which is handled by the
102 // next call.)
103 topol_traits->erase_redundant_vertex(&(*v_temp));
104
105 // Merge the edges into a single one, and delete the vertex from the
106 // DCEL. (By default, the merge_edge() funtion deletes the vertex.)
107 arr.merge_edge(havc, havc_next->twin() , merged_cv);
108 }
109 }
110 }
111
112 //Rotate all the vertices.
113 for (auto vi1 = arr.vertices_begin(); vi1 != arr.vertices_end(); ++vi1) {
114 m_arr_access.modify_vertex_ex(vi1, aff.transform(vi1->point()));
115 }
116
117 size_t num_of_edges = arr.number_of_edges();
118 Edge_iterator ei1 = arr.edges_begin();
119
120 // Rotate all the halfedges.
121 // The loop is over the initial edges , since new edges are created and
122 // added to the edges list.
123 for (size_t i = 0; i < num_of_edges; ++i) {
124 Curve_2 new_cv;
125
126 Halfedge_handle hei1 = ei1;
127 ++ei1;
128
129 // Take only the halfedge that its source is equal to the source of
130 // the curve.
131 bool eq1 = hei1->source()->point() == aff.transform(hei1->curve().source());
132 if (!eq1) {
133 hei1 = hei1->twin();
134 eq1 = hei1->source()->point() == aff.transform(hei1->curve().source());
135 }
136
137 CGAL_assertion_msg
138 (eq1,
139 "The new curve endpoints should be equal to the transform of the original");
140
141 // Create a new curve instead of the old one.
142 new_cv = Curve_2(hei1->source()->point(), hei1->target()->point(),
143 aff.transform(hei1->curve().normal()));
144
145 // Modify the edge with the new curve.
146 m_arr_access.modify_edge_ex(hei1, new_cv);
147
148 std::list<Make_x_monotone_result> objects;
149 // Try to split the curve into x_monotone pieces.
150 geom_traits->make_x_monotone_2_object()(new_cv , std::back_inserter(objects));
151
152 // If the curve is not x-monotone - split it into 2 x_monotone parts.
153 // Since the curves were x_monotone before , can assume that it will be
154 // splited into 2 parts max.
155 if (objects.size() == 2) {
156 auto it = objects.begin();
157
158 // The curve that its left vertex lies on the identification curve
159 const auto* sub_cv1 = boost::get<X_monotone_curve_2>(&(*it));
160 ++it;
161 //The curve that its rigth vertex lies on the identification curve
162 const auto* sub_cv2 = boost::get<X_monotone_curve_2>(&(*it));
163
164 bool eq1 = (*sub_cv1).source() == hei1->source()->point();
165 bool eq2 = (*sub_cv2).target() == hei1->target()->point();
166
167 if (eq1 && eq2)
168 m_arr_access.split_edge_ex(hei1, (*sub_cv1).target(), *sub_cv1,
169 *sub_cv2);
170 else
171 CGAL_error_msg
172 ("The new curve endpoints should be equal to the original ones");
173 }
174 }
175
176 // Update all the vertices that located on the boundary after the rotation
177 // with boundary conditions
178 for (auto vi = arr.vertices_begin(); vi != arr.vertices_end(); ++vi) {
179 Arr_parameter_space bx =
180 geom_traits->parameter_space_in_x_2_object()(vi->point());
181 Arr_parameter_space by =
182 geom_traits->parameter_space_in_y_2_object()(vi->point());
183
184 if (bx != ARR_INTERIOR || by != ARR_INTERIOR) {
185 // The target of the Halfedge_around_vertex_circulator is the relevant
186 // point.
187 Halfedge_around_vertex_circulator havc = vi->incident_halfedges();
188
189 Arr_curve_end ind =
190 (geom_traits->construct_min_vertex_2_object()(havc->curve()) ==
191 vi->point()) ? ARR_MIN_END : ARR_MAX_END;
192
193 // Check if it was already added.
194 if (topol_traits->discontinuity_vertex(havc->curve(), ind)== nullptr &&
195 topol_traits->south_pole() != &(*havc->target()) &&
196 topol_traits->north_pole() != &(*havc->target()) )
197 {
198 // Update the boundary conditions for the vertex.
199 topol_traits->notify_on_boundary_vertex_creation(&(*havc->target()),
200 havc->curve(), ind,
201 bx, by);
202 m_arr_access.set_vertex_boundary(havc->target(), bx, by);
203
204 }
205 }
206 }
207
208 // Transform the faces with the suitable transformation traits.
209 for (auto f1 = arr.faces_begin(); f1 != arr.faces_end(); ++f1)
210 tran_tr.rotate_face(f1, aff);
211 }
212
213 } //namespace CGAL
214
215 #endif // CGAL_ARR_SGM_3_ATOS_H
216