1 /* 2 Copyright 2008 Intel Corporation 3 4 Use, modification and distribution are subject to the Boost Software License, 5 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt). 7 */ 8 #ifndef BOOST_POLYGON_POLYGON_45_SET_CONCEPT_HPP 9 #define BOOST_POLYGON_POLYGON_45_SET_CONCEPT_HPP 10 #include "polygon_45_set_data.hpp" 11 #include "polygon_45_set_traits.hpp" 12 #include "detail/polygon_45_touch.hpp" 13 namespace boost { namespace polygon{ 14 15 template <typename T, typename T2> 16 struct is_either_polygon_45_set_type { 17 typedef typename gtl_or<typename is_polygon_45_set_type<T>::type, typename is_polygon_45_set_type<T2>::type >::type type; 18 }; 19 20 template <typename T> 21 struct is_polygon_45_or_90_set_type { 22 typedef typename gtl_or<typename is_polygon_45_set_type<T>::type, typename is_polygon_90_set_type<T>::type >::type type; 23 }; 24 25 template <typename polygon_set_type> 26 typename enable_if< typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type>::type>::type, 27 typename polygon_45_set_traits<polygon_set_type>::iterator_type>::type begin_45_set_data(const polygon_set_type & polygon_set)28 begin_45_set_data(const polygon_set_type& polygon_set) { 29 return polygon_45_set_traits<polygon_set_type>::begin(polygon_set); 30 } 31 32 template <typename polygon_set_type> 33 typename enable_if< typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type>::type>::type, 34 typename polygon_45_set_traits<polygon_set_type>::iterator_type>::type end_45_set_data(const polygon_set_type & polygon_set)35 end_45_set_data(const polygon_set_type& polygon_set) { 36 return polygon_45_set_traits<polygon_set_type>::end(polygon_set); 37 } 38 39 template <typename polygon_set_type> 40 typename enable_if< typename gtl_if<typename is_polygon_45_set_type<polygon_set_type>::type>::type, 41 bool>::type clean(const polygon_set_type & polygon_set)42 clean(const polygon_set_type& polygon_set) { 43 return polygon_45_set_traits<polygon_set_type>::clean(polygon_set); 44 } 45 46 //assign 47 template <typename polygon_set_type_1, typename polygon_set_type_2> 48 typename enable_if< typename gtl_and< typename gtl_if<typename is_mutable_polygon_45_set_type<polygon_set_type_1>::type>::type, 49 typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type_2>::type>::type>::type, 50 polygon_set_type_1>::type & assign(polygon_set_type_1 & lvalue,const polygon_set_type_2 & rvalue)51 assign(polygon_set_type_1& lvalue, const polygon_set_type_2& rvalue) { 52 polygon_45_set_mutable_traits<polygon_set_type_1>::set(lvalue, begin_45_set_data(rvalue), end_45_set_data(rvalue)); 53 return lvalue; 54 } 55 56 //get trapezoids 57 template <typename output_container_type, typename polygon_set_type> 58 typename enable_if< typename gtl_if<typename is_polygon_45_set_type<polygon_set_type>::type>::type, 59 void>::type get_trapezoids(output_container_type & output,const polygon_set_type & polygon_set)60 get_trapezoids(output_container_type& output, const polygon_set_type& polygon_set) { 61 clean(polygon_set); 62 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type>::coordinate_type> ps; 63 assign(ps, polygon_set); 64 ps.get_trapezoids(output); 65 } 66 67 //get trapezoids 68 template <typename output_container_type, typename polygon_set_type> 69 typename enable_if< typename gtl_if<typename is_polygon_45_set_type<polygon_set_type>::type>::type, 70 void>::type get_trapezoids(output_container_type & output,const polygon_set_type & polygon_set,orientation_2d slicing_orientation)71 get_trapezoids(output_container_type& output, const polygon_set_type& polygon_set, orientation_2d slicing_orientation) { 72 clean(polygon_set); 73 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type>::coordinate_type> ps; 74 assign(ps, polygon_set); 75 ps.get_trapezoids(output, slicing_orientation); 76 } 77 78 //equivalence 79 template <typename polygon_set_type_1, typename polygon_set_type_2> 80 typename enable_if< typename gtl_and_3<typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type_1>::type>::type, 81 typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type_2>::type>::type, 82 typename gtl_if<typename is_either_polygon_45_set_type<polygon_set_type_1, 83 polygon_set_type_2>::type>::type>::type, 84 bool>::type equivalence(const polygon_set_type_1 & lvalue,const polygon_set_type_2 & rvalue)85 equivalence(const polygon_set_type_1& lvalue, 86 const polygon_set_type_2& rvalue) { 87 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type_1>::coordinate_type> ps1; 88 assign(ps1, lvalue); 89 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type_2>::coordinate_type> ps2; 90 assign(ps2, rvalue); 91 return ps1 == ps2; 92 } 93 94 //clear 95 template <typename polygon_set_type> 96 typename enable_if< typename gtl_if<typename is_mutable_polygon_45_set_type<polygon_set_type>::type>::type, 97 void>::type clear(polygon_set_type & polygon_set)98 clear(polygon_set_type& polygon_set) { 99 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type>::coordinate_type> ps; 100 assign(polygon_set, ps); 101 } 102 103 //empty 104 template <typename polygon_set_type> 105 typename enable_if< typename gtl_if<typename is_mutable_polygon_45_set_type<polygon_set_type>::type>::type, 106 bool>::type empty(const polygon_set_type & polygon_set)107 empty(const polygon_set_type& polygon_set) { 108 if(clean(polygon_set)) return begin_45_set_data(polygon_set) == end_45_set_data(polygon_set); 109 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type>::coordinate_type> ps; 110 assign(ps, polygon_set); 111 ps.clean(); 112 return ps.empty(); 113 } 114 115 //extents 116 template <typename polygon_set_type, typename rectangle_type> 117 typename enable_if< 118 typename gtl_and< typename gtl_if<typename is_mutable_polygon_45_set_type<polygon_set_type>::type>::type, 119 typename is_mutable_rectangle_concept<typename geometry_concept<rectangle_type>::type>::type>::type, 120 bool>::type extents(rectangle_type & extents_rectangle,const polygon_set_type & polygon_set)121 extents(rectangle_type& extents_rectangle, 122 const polygon_set_type& polygon_set) { 123 clean(polygon_set); 124 polygon_45_set_data<typename polygon_45_set_traits<polygon_set_type>::coordinate_type> ps; 125 assign(ps, polygon_set); 126 return ps.extents(extents_rectangle); 127 } 128 129 //area 130 template <typename polygon_set_type> 131 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 132 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::area_type>::type area(const polygon_set_type & polygon_set)133 area(const polygon_set_type& polygon_set) { 134 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 135 typedef polygon_45_with_holes_data<Unit> p_type; 136 typedef typename coordinate_traits<Unit>::area_type area_type; 137 std::vector<p_type> polys; 138 assign(polys, polygon_set); 139 area_type retval = (area_type)0; 140 for(std::size_t i = 0; i < polys.size(); ++i) { 141 retval += area(polys[i]); 142 } 143 return retval; 144 } 145 146 //interact 147 template <typename polygon_set_type_1, typename polygon_set_type_2> 148 typename enable_if < 149 typename gtl_and< typename gtl_if<typename is_mutable_polygon_45_set_type<polygon_set_type_1>::type>::type, 150 typename gtl_if<typename is_polygon_45_or_90_set_type<polygon_set_type_2>::type>::type >::type, 151 polygon_set_type_1>::type& interact(polygon_set_type_1 & polygon_set_1,const polygon_set_type_2 & polygon_set_2)152 interact(polygon_set_type_1& polygon_set_1, const polygon_set_type_2& polygon_set_2) { 153 typedef typename polygon_45_set_traits<polygon_set_type_1>::coordinate_type Unit; 154 std::vector<polygon_45_data<Unit> > polys; 155 assign(polys, polygon_set_1); 156 std::vector<std::set<int> > graph(polys.size()+1, std::set<int>()); 157 connectivity_extraction_45<Unit> ce; 158 ce.insert(polygon_set_2); 159 for(std::size_t i = 0; i < polys.size(); ++i){ 160 ce.insert(polys[i]); 161 } 162 ce.extract(graph); 163 clear(polygon_set_1); 164 polygon_45_set_data<Unit> ps; 165 for(std::set<int>::iterator itr = graph[0].begin(); itr != graph[0].end(); ++itr){ 166 ps.insert(polys[(*itr)-1]); 167 } 168 assign(polygon_set_1, ps); 169 return polygon_set_1; 170 } 171 172 // //self_intersect 173 // template <typename polygon_set_type> 174 // typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type>::type, 175 // polygon_set_type>::type & 176 // self_intersect(polygon_set_type& polygon_set) { 177 // typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 178 // //TODO 179 // } 180 181 template <typename polygon_set_type, typename coord_type> 182 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 183 polygon_set_type>::type & resize(polygon_set_type & polygon_set,coord_type resizing,RoundingOption rounding=CLOSEST,CornerOption corner=INTERSECTION)184 resize(polygon_set_type& polygon_set, coord_type resizing, 185 RoundingOption rounding = CLOSEST, CornerOption corner = INTERSECTION) { 186 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 187 clean(polygon_set); 188 polygon_45_set_data<Unit> ps; 189 assign(ps, polygon_set); 190 ps.resize(resizing, rounding, corner); 191 assign(polygon_set, ps); 192 return polygon_set; 193 } 194 195 template <typename polygon_set_type> 196 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 197 polygon_set_type>::type & bloat(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type bloating)198 bloat(polygon_set_type& polygon_set, 199 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type bloating) { 200 return resize(polygon_set, static_cast<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>(bloating)); 201 } 202 203 template <typename polygon_set_type> 204 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 205 polygon_set_type>::type & shrink(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type shrinking)206 shrink(polygon_set_type& polygon_set, 207 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type shrinking) { 208 return resize(polygon_set, -(typename polygon_45_set_traits<polygon_set_type>::coordinate_type)shrinking); 209 } 210 211 template <typename polygon_set_type> 212 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 213 polygon_set_type>::type & grow_and(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type bloating)214 grow_and(polygon_set_type& polygon_set, 215 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type bloating) { 216 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 217 std::vector<polygon_45_data<Unit> > polys; 218 assign(polys, polygon_set); 219 clear(polygon_set); 220 polygon_45_set_data<Unit> ps; 221 for(std::size_t i = 0; i < polys.size(); ++i) { 222 polygon_45_set_data<Unit> tmpPs; 223 tmpPs.insert(polys[i]); 224 bloat(tmpPs, bloating); 225 tmpPs.clean(); //apply implicit OR on tmp polygon set 226 ps.insert(tmpPs); 227 } 228 ps.self_intersect(); 229 assign(polygon_set, ps); 230 return polygon_set; 231 } 232 233 template <typename polygon_set_type> 234 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 235 polygon_set_type>::type & scale_up(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type factor)236 scale_up(polygon_set_type& polygon_set, 237 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type factor) { 238 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 239 clean(polygon_set); 240 polygon_45_set_data<Unit> ps; 241 assign(ps, polygon_set); 242 ps.scale_up(factor); 243 assign(polygon_set, ps); 244 return polygon_set; 245 } 246 247 template <typename polygon_set_type> 248 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 249 polygon_set_type>::type & scale_down(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type factor)250 scale_down(polygon_set_type& polygon_set, 251 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type factor) { 252 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 253 clean(polygon_set); 254 polygon_45_set_data<Unit> ps; 255 assign(ps, polygon_set); 256 ps.scale_down(factor); 257 assign(polygon_set, ps); 258 return polygon_set; 259 } 260 261 template <typename polygon_set_type> 262 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 263 polygon_set_type>::type & scale(polygon_set_type & polygon_set,double factor)264 scale(polygon_set_type& polygon_set, double factor) { 265 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 266 clean(polygon_set); 267 polygon_45_set_data<Unit> ps; 268 assign(ps, polygon_set); 269 ps.scale(factor); 270 assign(polygon_set, ps); 271 return polygon_set; 272 } 273 274 //self_intersect 275 template <typename polygon_set_type> 276 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 277 polygon_set_type>::type & self_intersect(polygon_set_type & polygon_set)278 self_intersect(polygon_set_type& polygon_set) { 279 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 280 polygon_45_set_data<Unit> ps; 281 assign(ps, polygon_set); 282 ps.self_intersect(); 283 assign(polygon_set, ps); 284 return polygon_set; 285 } 286 287 //self_xor 288 template <typename polygon_set_type> 289 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 290 polygon_set_type>::type & self_xor(polygon_set_type & polygon_set)291 self_xor(polygon_set_type& polygon_set) { 292 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 293 polygon_45_set_data<Unit> ps; 294 assign(ps, polygon_set); 295 ps.self_xor(); 296 assign(polygon_set, ps); 297 return polygon_set; 298 } 299 300 //transform 301 template <typename polygon_set_type, typename transformation_type> 302 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 303 polygon_set_type>::type & transform(polygon_set_type & polygon_set,const transformation_type & transformation)304 transform(polygon_set_type& polygon_set, 305 const transformation_type& transformation) { 306 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 307 clean(polygon_set); 308 polygon_45_set_data<Unit> ps; 309 assign(ps, polygon_set); 310 ps.transform(transformation); 311 assign(polygon_set, ps); 312 return polygon_set; 313 } 314 315 //keep 316 template <typename polygon_set_type> 317 typename enable_if< typename is_mutable_polygon_45_set_type<polygon_set_type>::type, 318 polygon_set_type>::type & keep(polygon_set_type & polygon_set,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::area_type min_area,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::area_type max_area,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type min_width,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type max_width,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type min_height,typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type max_height)319 keep(polygon_set_type& polygon_set, 320 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::area_type min_area, 321 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::area_type max_area, 322 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type min_width, 323 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type max_width, 324 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type min_height, 325 typename coordinate_traits<typename polygon_45_set_traits<polygon_set_type>::coordinate_type>::unsigned_area_type max_height) { 326 typedef typename polygon_45_set_traits<polygon_set_type>::coordinate_type Unit; 327 typedef typename coordinate_traits<Unit>::unsigned_area_type uat; 328 std::list<polygon_45_data<Unit> > polys; 329 assign(polys, polygon_set); 330 typename std::list<polygon_45_data<Unit> >::iterator itr_nxt; 331 for(typename std::list<polygon_45_data<Unit> >::iterator itr = polys.begin(); itr != polys.end(); itr = itr_nxt){ 332 itr_nxt = itr; 333 ++itr_nxt; 334 rectangle_data<Unit> bbox; 335 extents(bbox, *itr); 336 uat pwidth = delta(bbox, HORIZONTAL); 337 if(pwidth > min_width && pwidth <= max_width){ 338 uat pheight = delta(bbox, VERTICAL); 339 if(pheight > min_height && pheight <= max_height){ 340 typename coordinate_traits<Unit>::area_type parea = area(*itr); 341 if(parea <= max_area && parea >= min_area) { 342 continue; 343 } 344 } 345 } 346 polys.erase(itr); 347 } 348 assign(polygon_set, polys); 349 return polygon_set; 350 } 351 352 template <typename T> 353 struct view_of<polygon_90_set_concept, T> { 354 typedef typename get_coordinate_type<T, typename geometry_concept<T>::type >::type coordinate_type; 355 T* tp; 356 std::vector<polygon_90_with_holes_data<coordinate_type> > polys; view_ofboost::polygon::view_of357 view_of(T& obj) : tp(&obj), polys() { 358 std::vector<polygon_with_holes_data<coordinate_type> > gpolys; 359 assign(gpolys, obj); 360 for(typename std::vector<polygon_with_holes_data<coordinate_type> >::iterator itr = gpolys.begin(); 361 itr != gpolys.end(); ++itr) { 362 polys.push_back(polygon_90_with_holes_data<coordinate_type>()); 363 assign(polys.back(), view_as<polygon_90_with_holes_concept>(*itr)); 364 } 365 } view_ofboost::polygon::view_of366 view_of(const T& obj) : tp(), polys() { 367 std::vector<polygon_with_holes_data<coordinate_type> > gpolys; 368 assign(gpolys, obj); 369 for(typename std::vector<polygon_with_holes_data<coordinate_type> >::iterator itr = gpolys.begin(); 370 itr != gpolys.end(); ++itr) { 371 polys.push_back(polygon_90_with_holes_data<coordinate_type>()); 372 assign(polys.back(), view_as<polygon_90_with_holes_concept>(*itr)); 373 } 374 } 375 376 typedef typename std::vector<polygon_90_with_holes_data<coordinate_type> >::const_iterator iterator_type; 377 typedef view_of operator_arg_type; 378 beginboost::polygon::view_of379 inline iterator_type begin() const { 380 return polys.begin(); 381 } 382 endboost::polygon::view_of383 inline iterator_type end() const { 384 return polys.end(); 385 } 386 orientboost::polygon::view_of387 inline orientation_2d orient() const { return HORIZONTAL; } 388 cleanboost::polygon::view_of389 inline bool clean() const { return false; } 390 sortedboost::polygon::view_of391 inline bool sorted() const { return false; } 392 getboost::polygon::view_of393 inline T& get() { return *tp; } 394 395 }; 396 397 template <typename T> 398 struct polygon_90_set_traits<view_of<polygon_90_set_concept, T> > { 399 typedef typename view_of<polygon_90_set_concept, T>::coordinate_type coordinate_type; 400 typedef typename view_of<polygon_90_set_concept, T>::iterator_type iterator_type; 401 typedef view_of<polygon_90_set_concept, T> operator_arg_type; 402 beginboost::polygon::polygon_90_set_traits403 static inline iterator_type begin(const view_of<polygon_90_set_concept, T>& polygon_set) { 404 return polygon_set.begin(); 405 } 406 endboost::polygon::polygon_90_set_traits407 static inline iterator_type end(const view_of<polygon_90_set_concept, T>& polygon_set) { 408 return polygon_set.end(); 409 } 410 orientboost::polygon::polygon_90_set_traits411 static inline orientation_2d orient(const view_of<polygon_90_set_concept, T>& polygon_set) { 412 return polygon_set.orient(); } 413 cleanboost::polygon::polygon_90_set_traits414 static inline bool clean(const view_of<polygon_90_set_concept, T>& polygon_set) { 415 return polygon_set.clean(); } 416 sortedboost::polygon::polygon_90_set_traits417 static inline bool sorted(const view_of<polygon_90_set_concept, T>& polygon_set) { 418 return polygon_set.sorted(); } 419 420 }; 421 422 template <typename T> 423 struct geometry_concept<view_of<polygon_90_set_concept, T> > { 424 typedef polygon_90_set_concept type; 425 }; 426 427 template <typename T> 428 struct get_coordinate_type<view_of<polygon_90_set_concept, T>, polygon_90_set_concept> { 429 typedef typename view_of<polygon_90_set_concept, T>::coordinate_type type; 430 }; 431 template <typename T> 432 struct get_iterator_type_2<view_of<polygon_90_set_concept, T>, polygon_90_set_concept> { 433 typedef typename view_of<polygon_90_set_concept, T>::iterator_type type; beginboost::polygon::get_iterator_type_2434 static type begin(const view_of<polygon_90_set_concept, T>& t) { return t.begin(); } endboost::polygon::get_iterator_type_2435 static type end(const view_of<polygon_90_set_concept, T>& t) { return t.end(); } 436 }; 437 438 } 439 } 440 #include "detail/polygon_45_set_view.hpp" 441 #endif 442