1 // Copyright (c) 2013 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/Minkowski_sum_2/include/CGAL/Polygon_vertical_decomposition_2.h $ 7 // $Id: Polygon_vertical_decomposition_2.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Efi Fogel <efifogel@gmail.com> 11 12 #ifndef CGAL_POLYGON_VERTICAL_DECOMPOSITION_2_H 13 #define CGAL_POLYGON_VERTICAL_DECOMPOSITION_2_H 14 15 #include <CGAL/license/Minkowski_sum_2.h> 16 17 18 #include <CGAL/Polygon_2.h> 19 #include <CGAL/Polygon_with_holes_2.h> 20 #include <CGAL/General_polygon_set_2.h> 21 #include <CGAL/Arr_vertical_decomposition_2.h> 22 #include <CGAL/Arr_segment_traits_2.h> 23 #include <CGAL/Gps_segment_traits_2.h> 24 25 #include <vector> 26 #include <list> 27 28 namespace CGAL { 29 30 31 /*! 32 * \class 33 * Vertical decomposition strategy. 34 */ 35 template <typename Kernel_, 36 typename Container_ = std::vector<typename Kernel_::Point_2> > 37 class Polygon_vertical_decomposition_2 { 38 public: 39 typedef Kernel_ Kernel; 40 typedef Container_ Container; 41 42 typedef CGAL::Polygon_2<Kernel, Container> Polygon_2; 43 typedef CGAL::Polygon_with_holes_2<Kernel, Container> Polygon_with_holes_2; 44 45 typedef CGAL::Arr_segment_traits_2<Kernel> Arr_segment_traits; 46 typedef CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits> 47 Traits_2; 48 typedef CGAL::General_polygon_set_2<Traits_2> General_polygon_set_2; 49 typedef typename General_polygon_set_2::Arrangement_2 Arrangement_2; 50 51 typedef typename Arrangement_2::Halfedge_const_iterator 52 Halfedge_const_iterator; 53 typedef typename Arrangement_2::Face_const_iterator Face_const_iterator; 54 55 typedef typename Arrangement_2::Vertex_const_handle Vertex_const_handle; 56 typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle; 57 typedef typename Arrangement_2::Face_const_handle Face_const_handle; 58 59 typedef typename Arrangement_2::Vertex_handle Vertex_handle; 60 typedef typename Arrangement_2::Halfedge_handle Halfedge_handle; 61 typedef typename Arrangement_2::Face_handle Face_handle; 62 63 typedef std::pair<Vertex_const_handle, std::pair<CGAL::Object, CGAL::Object> > 64 Vert_decomp_entry; 65 typedef std::list<Vert_decomp_entry> Vert_decomp_list; 66 67 typedef typename Kernel::Point_2 Point_2; 68 69 typedef typename Arrangement_2::Outer_ccb_const_iterator 70 Outer_ccb_const_iterator; 71 72 private: 73 typedef typename Arrangement_2::X_monotone_curve_2 Segment_2; 74 typedef typename Kernel::Line_2 Line_2; 75 76 typedef typename Polygon_2::Vertex_circulator Vertex_circulator; 77 78 // An arrangement observer, used to receive notifications of face splits and 79 // face mergers. 80 class My_observer : public CGAL::Arr_observer<Arrangement_2> { 81 public: My_observer(Arrangement_2 & arr)82 My_observer(Arrangement_2& arr) : Arr_observer<Arrangement_2>(arr) {} 83 after_split_face(Face_handle f,Face_handle new_f,bool)84 virtual void after_split_face(Face_handle f, Face_handle new_f, 85 bool /* is_hole */) 86 { if (f->contained()) new_f->set_contained(true); } 87 }; 88 89 // Kernel functors: 90 typedef typename Kernel::Compare_x_2 Compare_x_2; 91 typedef typename Kernel::Intersect_2 Intersect_2; 92 typedef typename Kernel::Equal_2 Equal_2; 93 94 // Data members: 95 const Traits_2* m_traits; 96 bool m_own_traits; // inidicates whether the kernel should be freed up. 97 98 Compare_x_2 f_cmp_x; 99 Intersect_2 f_intersect; 100 Equal_2 f_equal; 101 102 public: 103 /*! Default constructor. */ Polygon_vertical_decomposition_2()104 Polygon_vertical_decomposition_2() : 105 m_traits(nullptr), 106 m_own_traits(false) 107 { init(); } 108 109 /*! Constructor */ Polygon_vertical_decomposition_2(const Traits_2 & traits)110 Polygon_vertical_decomposition_2(const Traits_2& traits) : 111 m_traits(&traits), 112 m_own_traits(false) 113 { init(); } 114 115 /*! Initialize */ init()116 void init() 117 { 118 // Allocate the traits if not provided. 119 if (m_traits == nullptr) { 120 m_traits = new Traits_2; 121 m_own_traits = true; 122 } 123 124 // Obtain kernel functors. 125 const Kernel* kernel = m_traits; 126 f_cmp_x = kernel->compare_x_2_object(); 127 f_intersect = kernel->intersect_2_object(); 128 f_equal = kernel->equal_2_object(); 129 } 130 131 // Destructor ~Polygon_vertical_decomposition_2()132 ~Polygon_vertical_decomposition_2() 133 { 134 if (m_own_traits) { 135 if (m_traits) { 136 delete m_traits; 137 m_traits = nullptr; 138 } 139 m_own_traits = false; 140 } 141 } 142 143 /*! Obtain the traits 144 * \return the traits 145 */ traits()146 const Traits_2& traits() const { return *m_traits; } 147 148 /*! Decompose a polygon into convex sub-polygons. 149 * \param pgn The input polygon. 150 * \param oi An output iterator of convex polygons. 151 * \return A past-the-end iterator for the sub-polygons. 152 */ 153 template <typename OutputIterator_> operator()154 OutputIterator_ operator()(const Polygon_2& pgn, OutputIterator_ oi) const 155 { return decomp(pgn, oi); } 156 157 /*! Decompose a polygon with holes into convex sub-polygons. 158 * \param pgn The input polygon. 159 * \param oi An output iterator of convex polygons. 160 * \return A past-the-end iterator for the sub-polygons. 161 */ 162 template <typename OutputIterator_> 163 OutputIterator_ operator()164 operator()(const Polygon_with_holes_2& pgn, OutputIterator_ oi) const 165 { return decomp(pgn, oi); } 166 167 private: 168 /*! 169 * Decompose a polygon-with-holes into convex sub-polygons. 170 * \param pgn The input polygon. 171 * \param oi An output iterator of convex polygons. 172 * \return A past-the-end iterator for the sub-polygons. 173 */ 174 template <typename Polygon_, typename OutputIterator_> decomp(const Polygon_ & pgn,OutputIterator_ oi)175 OutputIterator_ decomp(const Polygon_& pgn, OutputIterator_ oi) const 176 { 177 const Traits_2& traits = *m_traits; 178 General_polygon_set_2 gps(traits); 179 gps.insert(pgn); 180 Arrangement_2& arr = gps.arrangement(); 181 My_observer obs(arr); 182 vertical_decomposition(arr); 183 Face_const_iterator fi; 184 for (fi = arr.faces_begin(); fi != arr.faces_end(); ++fi) { 185 if (! fi->contained()) continue; 186 CGAL_assertion(fi->number_of_outer_ccbs() == 1); 187 Outer_ccb_const_iterator oci = fi->outer_ccbs_begin(); 188 Halfedge_const_iterator first = *oci; 189 Halfedge_const_iterator curr = first; 190 Polygon_2 pgn; 191 do { 192 pgn.push_back(curr->target()->point()); 193 curr = curr->next(); 194 } while (curr != first); 195 *oi++ = pgn; 196 } 197 return oi; 198 } 199 200 // Add a vertical segment from the given vertex to some other arrangement 201 // feature. 202 Halfedge_const_handle add_vertical_segment(Arrangement_2 & arr,Vertex_handle v,CGAL::Object obj)203 add_vertical_segment(Arrangement_2& arr, Vertex_handle v, CGAL::Object obj) 204 const 205 { 206 Segment_2 seg; 207 Vertex_const_handle vh; 208 Halfedge_const_handle hh; 209 Face_const_handle fh; 210 Vertex_handle v2; 211 212 if (CGAL::assign(vh, obj)) { 213 // The given feature is a vertex. 214 seg = Segment_2(v->point(), vh->point()); 215 v2 = arr.non_const_handle(vh); 216 } 217 else if (CGAL::assign(hh, obj)) { 218 // The given feature is a halfedge. We ignore fictitious halfedges. 219 if (hh->is_fictitious()) 220 return Halfedge_const_handle(); 221 222 // Check whether v lies in the interior of the x-range of the edge (in 223 // which case this edge should be split). 224 if (f_cmp_x(v->point(), hh->target()->point()) == CGAL::EQUAL) { 225 // In case the target of the edge already has the same x-coordinate as 226 // the vertex v, just connect these two vertices. 227 seg = Segment_2(v->point(), hh->target()->point()); 228 v2 = arr.non_const_handle(hh->target()); 229 } 230 else { 231 // Compute the vertical projection of v onto the segment associated 232 // with the halfedge. Split the edge and connect v with the split point. 233 Line_2 supp_line(hh->source()->point(), hh->target()->point()); 234 Line_2 vert_line(v->point(), 235 Point_2(v->point().x(), v->point().y() + 1)); 236 Point_2 point; 237 CGAL::assign(point, f_intersect(supp_line, vert_line)); 238 seg = Segment_2(v->point(), point); 239 arr.split_edge(arr.non_const_handle(hh), 240 Segment_2(hh->source()->point(), point), 241 Segment_2(point, hh->target()->point())); 242 v2 = arr.non_const_handle(hh->target()); 243 } 244 } 245 // Ignore faces and empty objects. 246 else return Halfedge_const_handle(); 247 248 // Add the vertical segment to the arrangement using its two end vertices. 249 return arr.insert_at_vertices(seg, v, v2); 250 } 251 252 // Construct the vertical decomposition of the given arrangement. vertical_decomposition(Arrangement_2 & arr)253 void vertical_decomposition(Arrangement_2& arr) const 254 { 255 // For each vertex in the arrangment, locate the feature that lies 256 // directly below it and the feature that lies directly above it. 257 Vert_decomp_list vd_list; 258 CGAL::decompose(arr, std::back_inserter(vd_list)); 259 260 // Go over the vertices (given in ascending lexicographical xy-order), 261 // and add segements to the feautres below and above it. 262 typename Vert_decomp_list::iterator it, prev = vd_list.end(); 263 for (it = vd_list.begin(); it != vd_list.end(); ++it) { 264 // If the feature above the previous vertex is not the current vertex, 265 // add a vertical segment to the feature below the vertex. 266 Vertex_const_handle v; 267 if ((prev == vd_list.end()) || 268 !CGAL::assign(v, prev->second.second) || 269 !f_equal(v->point(), it->first->point())) 270 add_vertical_segment(arr, arr.non_const_handle(it->first), 271 it->second.first); 272 // Add a vertical segment to the feature above the vertex. 273 add_vertical_segment(arr, arr.non_const_handle(it->first), 274 it->second.second); 275 prev = it; 276 } 277 } 278 }; 279 280 } //namespace CGAL 281 282 #endif 283