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_TRAITS_HPP 9 #define BOOST_POLYGON_POLYGON_TRAITS_HPP 10 namespace boost { namespace polygon{ 11 12 template <typename T, typename enable = gtl_yes> 13 struct polygon_90_traits { 14 typedef typename T::coordinate_type coordinate_type; 15 typedef typename T::compact_iterator_type compact_iterator_type; 16 17 // Get the begin iterator begin_compactboost::polygon::polygon_90_traits18 static inline compact_iterator_type begin_compact(const T& t) { 19 return t.begin_compact(); 20 } 21 22 // Get the end iterator end_compactboost::polygon::polygon_90_traits23 static inline compact_iterator_type end_compact(const T& t) { 24 return t.end_compact(); 25 } 26 27 // Get the number of sides of the polygon sizeboost::polygon::polygon_90_traits28 static inline std::size_t size(const T& t) { 29 return t.size(); 30 } 31 32 // Get the winding direction of the polygon windingboost::polygon::polygon_90_traits33 static inline winding_direction winding(const T&) { 34 return unknown_winding; 35 } 36 }; 37 38 template <typename T> 39 struct polygon_traits_general { 40 typedef typename T::coordinate_type coordinate_type; 41 typedef typename T::iterator_type iterator_type; 42 typedef typename T::point_type point_type; 43 44 // Get the begin iterator begin_pointsboost::polygon::polygon_traits_general45 static inline iterator_type begin_points(const T& t) { 46 return t.begin(); 47 } 48 49 // Get the end iterator end_pointsboost::polygon::polygon_traits_general50 static inline iterator_type end_points(const T& t) { 51 return t.end(); 52 } 53 54 // Get the number of sides of the polygon sizeboost::polygon::polygon_traits_general55 static inline std::size_t size(const T& t) { 56 return t.size(); 57 } 58 59 // Get the winding direction of the polygon windingboost::polygon::polygon_traits_general60 static inline winding_direction winding(const T&) { 61 return unknown_winding; 62 } 63 }; 64 65 template <typename T> 66 struct polygon_traits_90 { 67 typedef typename polygon_90_traits<T>::coordinate_type coordinate_type; 68 typedef iterator_compact_to_points<typename polygon_90_traits<T>::compact_iterator_type, point_data<coordinate_type> > iterator_type; 69 typedef point_data<coordinate_type> point_type; 70 71 // Get the begin iterator begin_pointsboost::polygon::polygon_traits_9072 static inline iterator_type begin_points(const T& t) { 73 return iterator_type(polygon_90_traits<T>::begin_compact(t), 74 polygon_90_traits<T>::end_compact(t)); 75 } 76 77 // Get the end iterator end_pointsboost::polygon::polygon_traits_9078 static inline iterator_type end_points(const T& t) { 79 return iterator_type(polygon_90_traits<T>::end_compact(t), 80 polygon_90_traits<T>::end_compact(t)); 81 } 82 83 // Get the number of sides of the polygon sizeboost::polygon::polygon_traits_9084 static inline std::size_t size(const T& t) { 85 return polygon_90_traits<T>::size(t); 86 } 87 88 // Get the winding direction of the polygon windingboost::polygon::polygon_traits_9089 static inline winding_direction winding(const T& t) { 90 return polygon_90_traits<T>::winding(t); 91 } 92 }; 93 94 #ifndef BOOST_VERY_LITTLE_SFINAE 95 96 template <typename T, typename enable = gtl_yes> 97 struct polygon_traits {}; 98 99 template <typename T> 100 struct polygon_traits<T, 101 typename gtl_or_4< 102 typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type, 103 typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type, 104 typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type, 105 typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type 106 >::type> : public polygon_traits_general<T> {}; 107 108 template <typename T> 109 struct polygon_traits< T, 110 typename gtl_or< 111 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type, 112 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type 113 >::type > : public polygon_traits_90<T> {}; 114 115 #else 116 117 template <typename T, typename T_IF, typename T_ELSE> 118 struct gtl_ifelse {}; 119 template <typename T_IF, typename T_ELSE> 120 struct gtl_ifelse<gtl_no, T_IF, T_ELSE> { 121 typedef T_ELSE type; 122 }; 123 template <typename T_IF, typename T_ELSE> 124 struct gtl_ifelse<gtl_yes, T_IF, T_ELSE> { 125 typedef T_IF type; 126 }; 127 128 template <typename T, typename enable = gtl_yes> 129 struct polygon_traits {}; 130 131 template <typename T> 132 struct polygon_traits<T, typename gtl_or<typename gtl_or_4< 133 typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type, 134 typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type, 135 typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type, 136 typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type 137 >::type, typename gtl_or< 138 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type, 139 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type 140 >::type>::type > : public gtl_ifelse<typename gtl_or< 141 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type, 142 typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type >::type, 143 polygon_traits_90<T>, 144 polygon_traits_general<T> >::type { 145 }; 146 147 #endif 148 149 template <typename T, typename enable = void> 150 struct polygon_with_holes_traits { 151 typedef typename T::iterator_holes_type iterator_holes_type; 152 typedef typename T::hole_type hole_type; 153 154 // Get the begin iterator begin_holesboost::polygon::polygon_with_holes_traits155 static inline iterator_holes_type begin_holes(const T& t) { 156 return t.begin_holes(); 157 } 158 159 // Get the end iterator end_holesboost::polygon::polygon_with_holes_traits160 static inline iterator_holes_type end_holes(const T& t) { 161 return t.end_holes(); 162 } 163 164 // Get the number of holes size_holesboost::polygon::polygon_with_holes_traits165 static inline std::size_t size_holes(const T& t) { 166 return t.size_holes(); 167 } 168 }; 169 170 template <typename T, typename enable = void> 171 struct polygon_90_mutable_traits { 172 173 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x 174 template <typename iT> set_compactboost::polygon::polygon_90_mutable_traits175 static inline T& set_compact(T& t, iT input_begin, iT input_end) { 176 t.set_compact(input_begin, input_end); 177 return t; 178 } 179 180 }; 181 182 template <typename T, typename enable = void> 183 struct polygon_mutable_traits { 184 185 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x 186 template <typename iT> set_pointsboost::polygon::polygon_mutable_traits187 static inline T& set_points(T& t, iT input_begin, iT input_end) { 188 t.set(input_begin, input_end); 189 return t; 190 } 191 192 }; 193 194 template <typename T, typename enable = void> 195 struct polygon_with_holes_mutable_traits { 196 197 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x 198 template <typename iT> set_holesboost::polygon::polygon_with_holes_mutable_traits199 static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) { 200 t.set_holes(inputBegin, inputEnd); 201 return t; 202 } 203 204 }; 205 } 206 } 207 #include "isotropy.hpp" 208 209 //point 210 #include "point_data.hpp" 211 #include "point_traits.hpp" 212 #include "point_concept.hpp" 213 214 //interval 215 #include "interval_data.hpp" 216 #include "interval_traits.hpp" 217 #include "interval_concept.hpp" 218 219 //rectangle 220 #include "rectangle_data.hpp" 221 #include "rectangle_traits.hpp" 222 #include "rectangle_concept.hpp" 223 224 //algorithms needed by polygon types 225 #include "detail/iterator_points_to_compact.hpp" 226 #include "detail/iterator_compact_to_points.hpp" 227 228 //polygons 229 #include "polygon_45_data.hpp" 230 #include "polygon_data.hpp" 231 #include "polygon_90_data.hpp" 232 #include "polygon_90_with_holes_data.hpp" 233 #include "polygon_45_with_holes_data.hpp" 234 #include "polygon_with_holes_data.hpp" 235 236 namespace boost { namespace polygon{ 237 struct polygon_concept {}; 238 struct polygon_with_holes_concept {}; 239 struct polygon_45_concept {}; 240 struct polygon_45_with_holes_concept {}; 241 struct polygon_90_concept {}; 242 struct polygon_90_with_holes_concept {}; 243 244 245 template <typename T> 246 struct is_polygon_90_type { 247 typedef typename geometry_concept<T>::type GC; 248 typedef typename gtl_same_type<polygon_90_concept, GC>::type type; 249 }; 250 251 template <typename T> 252 struct is_polygon_45_type { 253 typedef typename geometry_concept<T>::type GC; 254 typedef typename gtl_or<typename is_polygon_90_type<T>::type, 255 typename gtl_same_type<polygon_45_concept, GC>::type>::type type; 256 }; 257 258 template <typename T> 259 struct is_polygon_type { 260 typedef typename geometry_concept<T>::type GC; 261 typedef typename gtl_or<typename is_polygon_45_type<T>::type, 262 typename gtl_same_type<polygon_concept, GC>::type>::type type; 263 }; 264 265 template <typename T> 266 struct is_polygon_90_with_holes_type { 267 typedef typename geometry_concept<T>::type GC; 268 typedef typename gtl_or<typename is_polygon_90_type<T>::type, 269 typename gtl_same_type<polygon_90_with_holes_concept, GC>::type>::type type; 270 }; 271 272 template <typename T> 273 struct is_polygon_45_with_holes_type { 274 typedef typename geometry_concept<T>::type GC; 275 typedef typename gtl_or_3<typename is_polygon_90_with_holes_type<T>::type, 276 typename is_polygon_45_type<T>::type, 277 typename gtl_same_type<polygon_45_with_holes_concept, GC>::type>::type type; 278 }; 279 280 template <typename T> 281 struct is_polygon_with_holes_type { 282 typedef typename geometry_concept<T>::type GC; 283 typedef typename gtl_or_3<typename is_polygon_45_with_holes_type<T>::type, 284 typename is_polygon_type<T>::type, 285 typename gtl_same_type<polygon_with_holes_concept, GC>::type>::type type; 286 }; 287 288 template <typename T> 289 struct is_mutable_polygon_90_type { 290 typedef typename geometry_concept<T>::type GC; 291 typedef typename gtl_same_type<polygon_90_concept, GC>::type type; 292 }; 293 294 template <typename T> 295 struct is_mutable_polygon_45_type { 296 typedef typename geometry_concept<T>::type GC; 297 typedef typename gtl_same_type<polygon_45_concept, GC>::type type; 298 }; 299 300 template <typename T> 301 struct is_mutable_polygon_type { 302 typedef typename geometry_concept<T>::type GC; 303 typedef typename gtl_same_type<polygon_concept, GC>::type type; 304 }; 305 306 template <typename T> 307 struct is_mutable_polygon_90_with_holes_type { 308 typedef typename geometry_concept<T>::type GC; 309 typedef typename gtl_same_type<polygon_90_with_holes_concept, GC>::type type; 310 }; 311 312 template <typename T> 313 struct is_mutable_polygon_45_with_holes_type { 314 typedef typename geometry_concept<T>::type GC; 315 typedef typename gtl_same_type<polygon_45_with_holes_concept, GC>::type type; 316 }; 317 318 template <typename T> 319 struct is_mutable_polygon_with_holes_type { 320 typedef typename geometry_concept<T>::type GC; 321 typedef typename gtl_same_type<polygon_with_holes_concept, GC>::type type; 322 }; 323 324 template <typename T> 325 struct is_any_mutable_polygon_with_holes_type { 326 typedef typename gtl_or_3<typename is_mutable_polygon_90_with_holes_type<T>::type, 327 typename is_mutable_polygon_45_with_holes_type<T>::type, 328 typename is_mutable_polygon_with_holes_type<T>::type>::type type; 329 }; 330 template <typename T> 331 struct is_any_mutable_polygon_without_holes_type { 332 typedef typename gtl_or_3< 333 typename is_mutable_polygon_90_type<T>::type, 334 typename is_mutable_polygon_45_type<T>::type, 335 typename is_mutable_polygon_type<T>::type>::type type; }; 336 337 template <typename T> 338 struct is_any_mutable_polygon_type { 339 typedef typename gtl_or<typename is_any_mutable_polygon_with_holes_type<T>::type, 340 typename is_any_mutable_polygon_without_holes_type<T>::type>::type type; 341 }; 342 343 template <typename T> 344 struct polygon_from_polygon_with_holes_type {}; 345 template <> 346 struct polygon_from_polygon_with_holes_type<polygon_with_holes_concept> { typedef polygon_concept type; }; 347 template <> 348 struct polygon_from_polygon_with_holes_type<polygon_45_with_holes_concept> { typedef polygon_45_concept type; }; 349 template <> 350 struct polygon_from_polygon_with_holes_type<polygon_90_with_holes_concept> { typedef polygon_90_concept type; }; 351 352 template <> 353 struct geometry_domain<polygon_45_concept> { typedef forty_five_domain type; }; 354 template <> 355 struct geometry_domain<polygon_45_with_holes_concept> { typedef forty_five_domain type; }; 356 template <> 357 struct geometry_domain<polygon_90_concept> { typedef manhattan_domain type; }; 358 template <> 359 struct geometry_domain<polygon_90_with_holes_concept> { typedef manhattan_domain type; }; 360 361 template <typename domain_type, typename coordinate_type> 362 struct distance_type_by_domain { typedef typename coordinate_traits<coordinate_type>::coordinate_distance type; }; 363 template <typename coordinate_type> 364 struct distance_type_by_domain<manhattan_domain, coordinate_type> { 365 typedef typename coordinate_traits<coordinate_type>::coordinate_difference type; }; 366 367 // \brief Sets the boundary of the polygon to the points in the iterator range 368 // \tparam T A type that models polygon_concept 369 // \tparam iT Iterator type over objects that model point_concept 370 // \param t The polygon to set 371 // \param begin_points The start of the range of points 372 // \param end_points The end of the range of points 373 374 /// \relatesalso polygon_concept 375 template <typename T, typename iT> 376 typename enable_if <typename is_any_mutable_polygon_type<T>::type, T>::type & set_points(T & t,iT begin_points,iT end_points)377 set_points(T& t, iT begin_points, iT end_points) { 378 polygon_mutable_traits<T>::set_points(t, begin_points, end_points); 379 return t; 380 } 381 382 // \brief Sets the boundary of the polygon to the non-redundant coordinates in the iterator range 383 // \tparam T A type that models polygon_90_concept 384 // \tparam iT Iterator type over objects that model coordinate_concept 385 // \param t The polygon to set 386 // \param begin_compact_coordinates The start of the range of coordinates 387 // \param end_compact_coordinates The end of the range of coordinates 388 389 /// \relatesalso polygon_90_concept 390 template <typename T, typename iT> 391 typename enable_if <typename gtl_or< 392 typename is_mutable_polygon_90_type<T>::type, 393 typename is_mutable_polygon_90_with_holes_type<T>::type>::type, T>::type & set_compact(T & t,iT begin_compact_coordinates,iT end_compact_coordinates)394 set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) { 395 polygon_90_mutable_traits<T>::set_compact(t, begin_compact_coordinates, end_compact_coordinates); 396 return t; 397 } 398 399 /// \relatesalso polygon_with_holes_concept 400 template <typename T, typename iT> 401 typename enable_if< typename gtl_and < 402 typename is_any_mutable_polygon_with_holes_type<T>::type, 403 typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, 404 manhattan_domain>::type>::type, 405 T>::type & set_compact(T & t,iT begin_compact_coordinates,iT end_compact_coordinates)406 set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) { 407 iterator_compact_to_points<iT, point_data<typename polygon_traits<T>::coordinate_type> > 408 itrb(begin_compact_coordinates, end_compact_coordinates), 409 itre(end_compact_coordinates, end_compact_coordinates); 410 return set_points(t, itrb, itre); 411 } 412 413 /// \relatesalso polygon_with_holes_concept 414 template <typename T, typename iT> 415 typename enable_if <typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type & set_holes(T & t,iT begin_holes,iT end_holes)416 set_holes(T& t, iT begin_holes, iT end_holes) { 417 polygon_with_holes_mutable_traits<T>::set_holes(t, begin_holes, end_holes); 418 return t; 419 } 420 421 /// \relatesalso polygon_90_concept 422 template <typename T> 423 typename polygon_90_traits<T>::compact_iterator_type begin_compact(const T & polygon,typename enable_if<typename gtl_and<typename is_polygon_with_holes_type<T>::type,typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,manhattan_domain>::type>::type>::type * =0)424 begin_compact(const T& polygon, 425 typename enable_if< 426 typename gtl_and <typename is_polygon_with_holes_type<T>::type, 427 typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type, 428 manhattan_domain>::type>::type>::type * = 0 429 ) { 430 return polygon_90_traits<T>::begin_compact(polygon); 431 } 432 433 /// \relatesalso polygon_90_concept 434 template <typename T> 435 typename polygon_90_traits<T>::compact_iterator_type end_compact(const T & polygon,typename enable_if<typename gtl_and<typename is_polygon_with_holes_type<T>::type,typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,manhattan_domain>::type>::type>::type * =0)436 end_compact(const T& polygon, 437 typename enable_if< 438 typename gtl_and <typename is_polygon_with_holes_type<T>::type, 439 typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type, 440 manhattan_domain>::type>::type>::type * = 0 441 ) { 442 return polygon_90_traits<T>::end_compact(polygon); 443 } 444 445 /// \relatesalso polygon_concept 446 template <typename T> 447 typename enable_if < typename gtl_if< 448 typename is_polygon_with_holes_type<T>::type>::type, 449 typename polygon_traits<T>::iterator_type>::type begin_points(const T & polygon)450 begin_points(const T& polygon) { 451 return polygon_traits<T>::begin_points(polygon); 452 } 453 454 /// \relatesalso polygon_concept 455 template <typename T> 456 typename enable_if < typename gtl_if< 457 typename is_polygon_with_holes_type<T>::type>::type, 458 typename polygon_traits<T>::iterator_type>::type end_points(const T & polygon)459 end_points(const T& polygon) { 460 return polygon_traits<T>::end_points(polygon); 461 } 462 463 /// \relatesalso polygon_concept 464 template <typename T> 465 typename enable_if <typename is_polygon_with_holes_type<T>::type, 466 std::size_t>::type size(const T & polygon)467 size(const T& polygon) { 468 return polygon_traits<T>::size(polygon); 469 } 470 471 /// \relatesalso polygon_with_holes_concept 472 template <typename T> 473 typename enable_if < typename gtl_if< 474 typename is_polygon_with_holes_type<T>::type>::type, 475 typename polygon_with_holes_traits<T>::iterator_holes_type>::type begin_holes(const T & polygon)476 begin_holes(const T& polygon) { 477 return polygon_with_holes_traits<T>::begin_holes(polygon); 478 } 479 480 /// \relatesalso polygon_with_holes_concept 481 template <typename T> 482 typename enable_if < typename gtl_if< 483 typename is_polygon_with_holes_type<T>::type>::type, 484 typename polygon_with_holes_traits<T>::iterator_holes_type>::type end_holes(const T & polygon)485 end_holes(const T& polygon) { 486 return polygon_with_holes_traits<T>::end_holes(polygon); 487 } 488 489 /// \relatesalso polygon_with_holes_concept 490 template <typename T> 491 typename enable_if <typename is_polygon_with_holes_type<T>::type, 492 std::size_t>::type size_holes(const T & polygon)493 size_holes(const T& polygon) { 494 return polygon_with_holes_traits<T>::size_holes(polygon); 495 } 496 497 // \relatesalso polygon_concept 498 template <typename T1, typename T2> 499 typename enable_if< 500 typename gtl_and< typename is_mutable_polygon_type<T1>::type, 501 typename is_polygon_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)502 assign(T1& lvalue, const T2& rvalue) { 503 polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue), 504 polygon_traits<T2>::end_points(rvalue)); 505 return lvalue; 506 } 507 508 // \relatesalso polygon_with_holes_concept 509 template <typename T1, typename T2> 510 typename enable_if< 511 typename gtl_and< typename is_mutable_polygon_with_holes_type<T1>::type, 512 typename is_polygon_with_holes_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)513 assign(T1& lvalue, const T2& rvalue) { 514 polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue), 515 polygon_traits<T2>::end_points(rvalue)); 516 polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue), 517 polygon_with_holes_traits<T2>::end_holes(rvalue)); 518 return lvalue; 519 } 520 521 // \relatesalso polygon_45_concept 522 template <typename T1, typename T2> 523 typename enable_if< typename gtl_and< typename is_mutable_polygon_45_type<T1>::type, typename is_polygon_45_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)524 assign(T1& lvalue, const T2& rvalue) { 525 polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue), 526 polygon_traits<T2>::end_points(rvalue)); 527 return lvalue; 528 } 529 530 // \relatesalso polygon_45_with_holes_concept 531 template <typename T1, typename T2> 532 typename enable_if< 533 typename gtl_and< typename is_mutable_polygon_45_with_holes_type<T1>::type, 534 typename is_polygon_45_with_holes_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)535 assign(T1& lvalue, const T2& rvalue) { 536 polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue), 537 polygon_traits<T2>::end_points(rvalue)); 538 polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue), 539 polygon_with_holes_traits<T2>::end_holes(rvalue)); 540 return lvalue; 541 } 542 543 // \relatesalso polygon_90_concept 544 template <typename T1, typename T2> 545 typename enable_if< 546 typename gtl_and< typename is_mutable_polygon_90_type<T1>::type, 547 typename is_polygon_90_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)548 assign(T1& lvalue, const T2& rvalue) { 549 polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue), 550 polygon_90_traits<T2>::end_compact(rvalue)); 551 return lvalue; 552 } 553 554 // \relatesalso polygon_90_with_holes_concept 555 template <typename T1, typename T2> 556 typename enable_if< 557 typename gtl_and< typename is_mutable_polygon_90_with_holes_type<T1>::type, 558 typename is_polygon_90_with_holes_type<T2>::type>::type, T1>::type & assign(T1 & lvalue,const T2 & rvalue)559 assign(T1& lvalue, const T2& rvalue) { 560 polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue), 561 polygon_90_traits<T2>::end_compact(rvalue)); 562 polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue), 563 polygon_with_holes_traits<T2>::end_holes(rvalue)); 564 return lvalue; 565 } 566 567 // \relatesalso polygon_90_concept 568 template <typename T1, typename T2> 569 typename enable_if< 570 typename gtl_and< typename is_any_mutable_polygon_type<T1>::type, 571 typename is_rectangle_concept<typename geometry_concept<T2>::type>::type>::type, T1>::type & assign(T1 & polygon,const T2 & rect)572 assign(T1& polygon, const T2& rect) { 573 typedef point_data<typename polygon_traits<T1>::coordinate_type> PT; 574 PT points[4] = {PT(xl(rect), yl(rect)), PT(xh(rect), yl(rect)), PT(xh(rect), yh(rect)), PT(xl(rect), yh(rect))}; 575 set_points(polygon, points, points+4); 576 return polygon; 577 } 578 579 /// \relatesalso polygon_90_concept 580 template <typename polygon_type, typename point_type> 581 typename enable_if< typename gtl_and< typename is_mutable_polygon_90_type<polygon_type>::type, 582 typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type, 583 polygon_type>::type & convolve(polygon_type & polygon,const point_type & point)584 convolve(polygon_type& polygon, const point_type& point) { 585 std::vector<typename polygon_90_traits<polygon_type>::coordinate_type> coords; 586 coords.reserve(::boost::polygon::size(polygon)); 587 bool pingpong = true; 588 for(typename polygon_90_traits<polygon_type>::compact_iterator_type iter = begin_compact(polygon); 589 iter != end_compact(polygon); ++iter) { 590 coords.push_back((*iter) + (pingpong ? x(point) : y(point))); 591 pingpong = !pingpong; 592 } 593 polygon_90_mutable_traits<polygon_type>::set_compact(polygon, coords.begin(), coords.end()); 594 return polygon; 595 } 596 597 /// \relatesalso polygon_concept 598 template <typename polygon_type, typename point_type> 599 typename enable_if< typename gtl_and< typename gtl_or< 600 typename is_mutable_polygon_45_type<polygon_type>::type, 601 typename is_mutable_polygon_type<polygon_type>::type>::type, 602 typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type, 603 polygon_type>::type & convolve(polygon_type & polygon,const point_type & point)604 convolve(polygon_type& polygon, const point_type& point) { 605 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 606 points.reserve(::boost::polygon::size(polygon)); 607 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 608 iter != end_points(polygon); ++iter) { 609 points.push_back(*iter); 610 convolve(points.back(), point); 611 } 612 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 613 return polygon; 614 } 615 616 /// \relatesalso polygon_with_holes_concept 617 template <typename polygon_type, typename point_type> 618 typename enable_if< 619 typename gtl_and< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type, 620 typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type, 621 polygon_type>::type & convolve(polygon_type & polygon,const point_type & point)622 convolve(polygon_type& polygon, const point_type& point) { 623 typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type; 624 hole_type h; 625 set_points(h, begin_points(polygon), end_points(polygon)); 626 convolve(h, point); 627 std::vector<hole_type> holes; 628 holes.reserve(size_holes(polygon)); 629 for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon); 630 itr != end_holes(polygon); ++itr) { 631 holes.push_back(*itr); 632 convolve(holes.back(), point); 633 } 634 assign(polygon, h); 635 set_holes(polygon, holes.begin(), holes.end()); 636 return polygon; 637 } 638 639 /// \relatesalso polygon_concept 640 template <typename T> 641 typename enable_if< typename is_any_mutable_polygon_type<T>::type, T>::type & move(T & polygon,orientation_2d orient,typename polygon_traits<T>::coordinate_type displacement)642 move(T& polygon, orientation_2d orient, typename polygon_traits<T>::coordinate_type displacement) { 643 typedef typename polygon_traits<T>::coordinate_type Unit; 644 if(orient == HORIZONTAL) return convolve(polygon, point_data<Unit>(displacement, Unit(0))); 645 return convolve(polygon, point_data<Unit>(Unit(0), displacement)); 646 } 647 648 /// \relatesalso polygon_concept 649 /// \brief Applies a transformation to the polygon. 650 /// \tparam polygon_type A type that models polygon_concept 651 /// \tparam transform_type A type that may be either axis_transformation or transformation or that overloads point_concept::transform 652 /// \param polygon The polygon to transform 653 /// \param tr The transformation to apply 654 template <typename polygon_type, typename transform_type> 655 typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type & transform(polygon_type & polygon,const transform_type & tr)656 transform(polygon_type& polygon, const transform_type& tr) { 657 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 658 points.reserve(::boost::polygon::size(polygon)); 659 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 660 iter != end_points(polygon); ++iter) { 661 points.push_back(*iter); 662 transform(points.back(), tr); 663 } 664 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 665 return polygon; 666 } 667 668 /// \relatesalso polygon_with_holes_concept 669 template <typename T, typename transform_type> 670 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type & transform(T & polygon,const transform_type & tr)671 transform(T& polygon, const transform_type& tr) { 672 typedef typename polygon_with_holes_traits<T>::hole_type hole_type; 673 hole_type h; 674 set_points(h, begin_points(polygon), end_points(polygon)); 675 transform(h, tr); 676 std::vector<hole_type> holes; 677 holes.reserve(size_holes(polygon)); 678 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon); 679 itr != end_holes(polygon); ++itr) { 680 holes.push_back(*itr); 681 transform(holes.back(), tr); 682 } 683 assign(polygon, h); 684 set_holes(polygon, holes.begin(), holes.end()); 685 return polygon; 686 } 687 688 template <typename polygon_type> 689 typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type & scale_up(polygon_type & polygon,typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor)690 scale_up(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) { 691 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 692 points.reserve(::boost::polygon::size(polygon)); 693 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 694 iter != end_points(polygon); ++iter) { 695 points.push_back(*iter); 696 scale_up(points.back(), factor); 697 } 698 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 699 return polygon; 700 } 701 702 template <typename T> 703 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type & scale_up(T & polygon,typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor)704 scale_up(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) { 705 typedef typename polygon_with_holes_traits<T>::hole_type hole_type; 706 hole_type h; 707 set_points(h, begin_points(polygon), end_points(polygon)); 708 scale_up(h, factor); 709 std::vector<hole_type> holes; 710 holes.reserve(size_holes(polygon)); 711 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon); 712 itr != end_holes(polygon); ++itr) { 713 holes.push_back(*itr); 714 scale_up(holes.back(), factor); 715 } 716 assign(polygon, h); 717 set_holes(polygon, holes.begin(), holes.end()); 718 return polygon; 719 } 720 721 //scale non-45 down 722 template <typename polygon_type> 723 typename enable_if< 724 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, 725 typename gtl_not<typename gtl_same_type 726 < forty_five_domain, 727 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type, 728 polygon_type>::type & scale_down(polygon_type & polygon,typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor)729 scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) { 730 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 731 points.reserve(::boost::polygon::size(polygon)); 732 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 733 iter != end_points(polygon); ++iter) { 734 points.push_back(*iter); 735 scale_down(points.back(), factor); 736 } 737 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 738 return polygon; 739 } 740 741 template <typename Unit> local_abs(Unit value)742 Unit local_abs(Unit value) { return value < 0 ? (Unit)-value : value; } 743 744 template <typename Unit> snap_point_vector_to_45(std::vector<point_data<Unit>> & pts)745 void snap_point_vector_to_45(std::vector<point_data<Unit> >& pts) { 746 typedef point_data<Unit> Point; 747 if(pts.size() < 3) { pts.clear(); return; } 748 typename std::vector<point_data<Unit> >::iterator endLocation = std::unique(pts.begin(), pts.end()); 749 if(endLocation != pts.end()){ 750 pts.resize(endLocation - pts.begin()); 751 } 752 if(pts.back() == pts[0]) pts.pop_back(); 753 //iterate over point triplets 754 int numPts = pts.size(); 755 bool wrap_around = false; 756 for(int i = 0; i < numPts; ++i) { 757 Point& pt1 = pts[i]; 758 Point& pt2 = pts[(i + 1) % numPts]; 759 Point& pt3 = pts[(i + 2) % numPts]; 760 //check if non-45 edge 761 Unit deltax = x(pt2) - x(pt1); 762 Unit deltay = y(pt2) - y(pt1); 763 if(deltax && deltay && 764 local_abs(deltax) != local_abs(deltay)) { 765 //adjust the middle point 766 Unit ndx = x(pt3) - x(pt2); 767 Unit ndy = y(pt3) - y(pt2); 768 if(ndx && ndy) { 769 Unit diff = local_abs(local_abs(deltax) - local_abs(deltay)); 770 Unit halfdiff = diff/2; 771 if((deltax > 0 && deltay > 0) || 772 (deltax < 0 && deltay < 0)) { 773 //previous edge is rising slope 774 if(local_abs(deltax + halfdiff + (diff % 2)) == 775 local_abs(deltay - halfdiff)) { 776 x(pt2, x(pt2) + halfdiff + (diff % 2)); 777 y(pt2, y(pt2) - halfdiff); 778 } else if(local_abs(deltax - halfdiff - (diff % 2)) == 779 local_abs(deltay + halfdiff)) { 780 x(pt2, x(pt2) - halfdiff - (diff % 2)); 781 y(pt2, y(pt2) + halfdiff); 782 } else{ 783 //std::cout << "fail1\n"; 784 } 785 } else { 786 //previous edge is falling slope 787 if(local_abs(deltax + halfdiff + (diff % 2)) == 788 local_abs(deltay + halfdiff)) { 789 x(pt2, x(pt2) + halfdiff + (diff % 2)); 790 y(pt2, y(pt2) + halfdiff); 791 } else if(local_abs(deltax - halfdiff - (diff % 2)) == 792 local_abs(deltay - halfdiff)) { 793 x(pt2, x(pt2) - halfdiff - (diff % 2)); 794 y(pt2, y(pt2) - halfdiff); 795 } else { 796 //std::cout << "fail2\n"; 797 } 798 } 799 if(i == numPts - 1 && (diff % 2)) { 800 //we have a wrap around effect 801 if(!wrap_around) { 802 wrap_around = true; 803 i = -1; 804 } 805 } 806 } else if(ndx) { 807 //next edge is horizontal 808 //find the x value for pt1 that would make the abs(deltax) == abs(deltay) 809 Unit newDeltaX = local_abs(deltay); 810 if(deltax < 0) newDeltaX *= -1; 811 x(pt2, x(pt1) + newDeltaX); 812 } else { //ndy 813 //next edge is vertical 814 //find the y value for pt1 that would make the abs(deltax) == abs(deltay) 815 Unit newDeltaY = local_abs(deltax); 816 if(deltay < 0) newDeltaY *= -1; 817 y(pt2, y(pt1) + newDeltaY); 818 } 819 } 820 } 821 } 822 823 template <typename polygon_type> 824 typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type & snap_to_45(polygon_type & polygon)825 snap_to_45(polygon_type& polygon) { 826 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 827 points.reserve(::boost::polygon::size(polygon)); 828 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 829 iter != end_points(polygon); ++iter) { 830 points.push_back(*iter); 831 } 832 snap_point_vector_to_45(points); 833 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 834 return polygon; 835 } 836 837 template <typename polygon_type> 838 typename enable_if< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type, polygon_type>::type & snap_to_45(polygon_type & polygon)839 snap_to_45(polygon_type& polygon) { 840 typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type; 841 hole_type h; 842 set_points(h, begin_points(polygon), end_points(polygon)); 843 snap_to_45(h); 844 std::vector<hole_type> holes; 845 holes.reserve(size_holes(polygon)); 846 for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon); 847 itr != end_holes(polygon); ++itr) { 848 holes.push_back(*itr); 849 snap_to_45(holes.back()); 850 } 851 assign(polygon, h); 852 set_holes(polygon, holes.begin(), holes.end()); 853 return polygon; 854 } 855 856 //scale specifically 45 down 857 template <typename polygon_type> 858 typename enable_if< 859 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, 860 typename gtl_same_type 861 < forty_five_domain, 862 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type, 863 polygon_type>::type & scale_down(polygon_type & polygon,typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor)864 scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) { 865 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 866 points.reserve(::boost::polygon::size(polygon)); 867 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 868 iter != end_points(polygon); ++iter) { 869 points.push_back(*iter); 870 scale_down(points.back(), factor); 871 } 872 snap_point_vector_to_45(points); 873 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 874 return polygon; 875 } 876 877 template <typename T> 878 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type & scale_down(T & polygon,typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor)879 scale_down(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) { 880 typedef typename polygon_with_holes_traits<T>::hole_type hole_type; 881 hole_type h; 882 set_points(h, begin_points(polygon), end_points(polygon)); 883 scale_down(h, factor); 884 std::vector<hole_type> holes; 885 holes.reserve(size_holes(polygon)); 886 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon); 887 itr != end_holes(polygon); ++itr) { 888 holes.push_back(*itr); 889 scale_down(holes.back(), factor); 890 } 891 assign(polygon, h); 892 set_holes(polygon, holes.begin(), holes.end()); 893 return polygon; 894 } 895 896 //scale non-45 897 template <typename polygon_type> 898 typename enable_if< 899 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, 900 typename gtl_not<typename gtl_same_type 901 < forty_five_domain, 902 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type, 903 polygon_type>::type & scale(polygon_type & polygon,double factor)904 scale(polygon_type& polygon, double factor) { 905 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 906 points.reserve(::boost::polygon::size(polygon)); 907 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 908 iter != end_points(polygon); ++iter) { 909 points.push_back(*iter); 910 scale(points.back(), anisotropic_scale_factor<double>(factor, factor)); 911 } 912 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 913 return polygon; 914 } 915 916 //scale specifically 45 917 template <typename polygon_type> 918 polygon_type& scale(polygon_type & polygon,double factor,typename enable_if<typename gtl_and<typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,typename gtl_same_type<forty_five_domain,typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type * =0)919 scale(polygon_type& polygon, double factor, 920 typename enable_if< 921 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, 922 typename gtl_same_type 923 < forty_five_domain, 924 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type * = 0 925 ) { 926 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points; 927 points.reserve(::boost::polygon::size(polygon)); 928 for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon); 929 iter != end_points(polygon); ++iter) { 930 points.push_back(*iter); 931 scale(points.back(), anisotropic_scale_factor<double>(factor, factor)); 932 } 933 snap_point_vector_to_45(points); 934 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end()); 935 return polygon; 936 } 937 938 template <typename T> 939 T& scale(T & polygon,double factor,typename enable_if<typename is_any_mutable_polygon_with_holes_type<T>::type>::type * =0)940 scale(T& polygon, double factor, 941 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type>::type * = 0 942 ) { 943 typedef typename polygon_with_holes_traits<T>::hole_type hole_type; 944 hole_type h; 945 set_points(h, begin_points(polygon), end_points(polygon)); 946 scale(h, factor); 947 std::vector<hole_type> holes; 948 holes.reserve(size_holes(polygon)); 949 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon); 950 itr != end_holes(polygon); ++itr) { 951 holes.push_back(*itr); 952 scale(holes.back(), factor); 953 } 954 assign(polygon, h); 955 set_holes(polygon, holes.begin(), holes.end()); 956 return polygon; 957 } 958 959 template <typename iterator_type, typename area_type> 960 static area_type point_sequence_area(iterator_type begin_range,iterator_type end_range)961 point_sequence_area(iterator_type begin_range, iterator_type end_range) { 962 typedef typename std::iterator_traits<iterator_type>::value_type point_type; 963 if(begin_range == end_range) return area_type(0); 964 point_type first = *begin_range; 965 point_type previous = first; 966 ++begin_range; 967 // Initialize trapezoid base line 968 area_type y_base = (area_type)y(first); 969 // Initialize area accumulator 970 971 area_type area(0); 972 while (begin_range != end_range) { 973 area_type x1 = (area_type)x(previous); 974 area_type x2 = (area_type)x(*begin_range); 975 #ifdef BOOST_POLYGON_ICC 976 #pragma warning (push) 977 #pragma warning (disable:1572) 978 #endif 979 if(x1 != x2) { 980 #ifdef BOOST_POLYGON_ICC 981 #pragma warning (pop) 982 #endif 983 // do trapezoid area accumulation 984 area += (x2 - x1) * (((area_type)y(*begin_range) - y_base) + 985 ((area_type)y(previous) - y_base)) / 2; 986 } 987 previous = *begin_range; 988 // go to next point 989 ++begin_range; 990 } 991 //wrap around to evaluate the edge between first and last if not closed 992 if(!equivalence(first, previous)) { 993 area_type x1 = (area_type)x(previous); 994 area_type x2 = (area_type)x(first); 995 area += (x2 - x1) * (((area_type)y(first) - y_base) + 996 ((area_type)y(previous) - y_base)) / 2; 997 } 998 return area; 999 } 1000 1001 template <typename T> 1002 typename enable_if< 1003 typename is_polygon_with_holes_type<T>::type, 1004 typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type, 1005 typename polygon_traits<T>::coordinate_type>::type>::type area(const T & polygon)1006 area(const T& polygon) { 1007 typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type, 1008 typename polygon_traits<T>::coordinate_type>::type area_type; 1009 area_type retval = point_sequence_area<typename polygon_traits<T>::iterator_type, area_type> 1010 (begin_points(polygon), end_points(polygon)); 1011 if(retval < 0) retval *= -1; 1012 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = 1013 polygon_with_holes_traits<T>::begin_holes(polygon); 1014 itr != polygon_with_holes_traits<T>::end_holes(polygon); ++itr) { 1015 area_type tmp_area = point_sequence_area 1016 <typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type, area_type> 1017 (begin_points(*itr), end_points(*itr)); 1018 if(tmp_area < 0) tmp_area *= -1; 1019 retval -= tmp_area; 1020 } 1021 return retval; 1022 } 1023 1024 template <typename iT> point_sequence_is_45(iT itr,iT itr_end)1025 bool point_sequence_is_45(iT itr, iT itr_end) { 1026 typedef typename std::iterator_traits<iT>::value_type Point; 1027 typedef typename point_traits<Point>::coordinate_type Unit; 1028 if(itr == itr_end) return true; 1029 Point firstPt = *itr; 1030 Point prevPt = firstPt; 1031 ++itr; 1032 while(itr != itr_end) { 1033 Point pt = *itr; 1034 Unit deltax = x(pt) - x(prevPt); 1035 Unit deltay = y(pt) - y(prevPt); 1036 if(deltax && deltay && 1037 local_abs(deltax) != local_abs(deltay)) 1038 return false; 1039 prevPt = pt; 1040 ++itr; 1041 } 1042 Unit deltax = x(firstPt) - x(prevPt); 1043 Unit deltay = y(firstPt) - y(prevPt); 1044 if(deltax && deltay && 1045 local_abs(deltax) != local_abs(deltay)) 1046 return false; 1047 return true; 1048 } 1049 1050 template <typename polygon_type> 1051 typename enable_if< typename is_polygon_with_holes_type<polygon_type>::type, bool>::type is_45(const polygon_type & polygon)1052 is_45(const polygon_type& polygon) { 1053 typename polygon_traits<polygon_type>::iterator_type itr = begin_points(polygon), itr_end = end_points(polygon); 1054 if(!point_sequence_is_45(itr, itr_end)) return false; 1055 typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itrh = begin_holes(polygon), itrh_end = end_holes(polygon); 1056 typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type; 1057 for(; itrh != itrh_end; ++ itrh) { 1058 typename polygon_traits<hole_type>::iterator_type itr1 = begin_points(polygon), itr1_end = end_points(polygon); 1059 if(!point_sequence_is_45(itr1, itr1_end)) return false; 1060 } 1061 return true; 1062 } 1063 1064 template <typename distance_type, typename iterator_type> 1065 distance_type point_sequence_distance(iterator_type itr, iterator_type itr_end) { 1066 typedef distance_type Unit; 1067 typedef iterator_type iterator; 1068 typedef typename std::iterator_traits<iterator>::value_type point_type; 1069 Unit return_value = Unit(0); 1070 point_type previous_point, first_point; 1071 if(itr == itr_end) return return_value; 1072 previous_point = first_point = *itr; 1073 ++itr; 1074 for( ; itr != itr_end; ++itr) { 1075 point_type current_point = *itr; 1076 return_value += (Unit)euclidean_distance(current_point, previous_point); 1077 previous_point = current_point; 1078 } 1079 return_value += (Unit)euclidean_distance(previous_point, first_point); 1080 return return_value; 1081 } 1082 1083 template <typename T> 1084 typename distance_type_by_domain 1085 <typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type perimeter(const T & polygon,typename enable_if<typename is_polygon_with_holes_type<T>::type>::type * =0)1086 perimeter(const T& polygon, 1087 typename enable_if< 1088 typename is_polygon_with_holes_type<T>::type>::type * = 0 1089 ) { 1090 typedef typename distance_type_by_domain 1091 <typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type Unit; 1092 typedef typename polygon_traits<T>::iterator_type iterator; 1093 iterator itr = begin_points(polygon); 1094 iterator itr_end = end_points(polygon); 1095 Unit return_value = point_sequence_distance<Unit, iterator>(itr, itr_end); 1096 for(typename polygon_with_holes_traits<T>::iterator_holes_type itr_holes = begin_holes(polygon); 1097 itr_holes != end_holes(polygon); ++itr_holes) { 1098 typedef typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type hitertype; 1099 return_value += point_sequence_distance<Unit, hitertype>(begin_points(*itr_holes), end_points(*itr_holes)); 1100 } 1101 return return_value; 1102 } 1103 1104 template <typename T> 1105 typename enable_if <typename is_polygon_with_holes_type<T>::type, 1106 direction_1d>::type winding(const T & polygon)1107 winding(const T& polygon) { 1108 winding_direction wd = polygon_traits<T>::winding(polygon); 1109 if(wd != unknown_winding) { 1110 return wd == clockwise_winding ? CLOCKWISE: COUNTERCLOCKWISE; 1111 } 1112 typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type, 1113 typename polygon_traits<T>::coordinate_type>::type area_type; 1114 return point_sequence_area<typename polygon_traits<T>::iterator_type, area_type>(begin_points(polygon), end_points(polygon)) < 0 ? 1115 COUNTERCLOCKWISE : CLOCKWISE; 1116 } 1117 1118 template <typename T, typename input_point_type> 1119 typename enable_if< 1120 typename gtl_and< 1121 typename is_polygon_90_type<T>::type, 1122 typename gtl_same_type< 1123 typename geometry_concept<input_point_type>::type, 1124 point_concept 1125 >::type 1126 >::type, 1127 bool contains(const T & polygon,const input_point_type & point,bool consider_touch=true)1128 >::type contains( 1129 const T& polygon, 1130 const input_point_type& point, 1131 bool consider_touch = true) { 1132 typedef T polygon_type; 1133 typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type; 1134 typedef typename polygon_traits<polygon_type>::iterator_type iterator; 1135 typedef typename std::iterator_traits<iterator>::value_type point_type; 1136 coordinate_type point_x = x(point); 1137 coordinate_type point_y = y(point); 1138 // Check how many intersections has the ray extended from the given 1139 // point in the x-axis negative direction with the polygon edges. 1140 // If the number is odd the point is within the polygon, otherwise not. 1141 // We can safely ignore horizontal edges, however intersections with 1142 // end points of the vertical edges require special handling. We should 1143 // add one intersection in case horizontal edges that extend vertical edge 1144 // point in the same direction. 1145 int num_full_intersections = 0; 1146 int num_half_intersections = 0; 1147 for (iterator iter = begin_points(polygon); iter != end_points(polygon);) { 1148 point_type curr_point = *iter; 1149 ++iter; 1150 point_type next_point = (iter == end_points(polygon)) ? *begin_points(polygon) : *iter; 1151 if (x(curr_point) == x(next_point)) { 1152 if (x(curr_point) > point_x) { 1153 continue; 1154 } 1155 coordinate_type min_y = (std::min)(y(curr_point), y(next_point)); 1156 coordinate_type max_y = (std::max)(y(curr_point), y(next_point)); 1157 if (point_y > min_y && point_y < max_y) { 1158 if (x(curr_point) == point_x) { 1159 return consider_touch; 1160 } 1161 ++num_full_intersections; 1162 } 1163 if (point_y == min_y || point_y == max_y) { 1164 num_half_intersections += (y(curr_point) < y(next_point) ? 1 : -1); 1165 } 1166 } else { 1167 coordinate_type min_x = (std::min)(x(curr_point), x(next_point)); 1168 coordinate_type max_x = (std::max)(x(curr_point), x(next_point)); 1169 if (point_x >= min_x && point_x <= max_x) { 1170 if (y(curr_point) == point_y) { 1171 return consider_touch; 1172 } 1173 } 1174 } 1175 } 1176 int total_intersections = num_full_intersections + (num_half_intersections >> 1); 1177 return total_intersections & 1; 1178 } 1179 1180 //TODO: refactor to expose as user APIs 1181 template <typename Unit> 1182 struct edge_utils { 1183 typedef point_data<Unit> Point; 1184 typedef std::pair<Point, Point> half_edge; 1185 1186 class less_point { 1187 public: 1188 typedef Point first_argument_type; 1189 typedef Point second_argument_type; 1190 typedef bool result_type; less_point()1191 inline less_point() {} operator ()(const Point & pt1,const Point & pt2) const1192 inline bool operator () (const Point& pt1, const Point& pt2) const { 1193 if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true; 1194 if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) { 1195 if(pt1.get(VERTICAL) < pt2.get(VERTICAL)) return true; 1196 } 1197 return false; 1198 } 1199 }; 1200 betweenboost::polygon::edge_utils1201 static inline bool between(Point pt, Point pt1, Point pt2) { 1202 less_point lp; 1203 if(lp(pt1, pt2)) 1204 return lp(pt, pt2) && lp(pt1, pt); 1205 return lp(pt, pt1) && lp(pt2, pt); 1206 } 1207 1208 template <typename area_type> equal_slopeboost::polygon::edge_utils1209 static inline bool equal_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) { 1210 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type; 1211 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1); 1212 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2); 1213 int dx1_sign = dx1 < 0 ? -1 : 1; 1214 int dx2_sign = dx2 < 0 ? -1 : 1; 1215 int dy1_sign = dy1 < 0 ? -1 : 1; 1216 int dy2_sign = dy2 < 0 ? -1 : 1; 1217 int cross_1_sign = dx2_sign * dy1_sign; 1218 int cross_2_sign = dx1_sign * dy2_sign; 1219 return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0); 1220 } 1221 equal_slopeboost::polygon::edge_utils1222 static inline bool equal_slope(const Unit& x, const Unit& y, 1223 const Point& pt1, const Point& pt2) { 1224 const Point* pts[2] = {&pt1, &pt2}; 1225 typedef typename coordinate_traits<Unit>::manhattan_area_type at; 1226 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y; 1227 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y; 1228 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x; 1229 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x; 1230 return equal_slope(dx1, dy1, dx2, dy2); 1231 } 1232 1233 template <typename area_type> less_slopeboost::polygon::edge_utils1234 static inline bool less_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) { 1235 //reflext x and y slopes to right hand side half plane 1236 if(dx1 < 0) { 1237 dy1 *= -1; 1238 dx1 *= -1; 1239 } else if(dx1 == 0) { 1240 //if the first slope is vertical the first cannot be less 1241 return false; 1242 } 1243 if(dx2 < 0) { 1244 dy2 *= -1; 1245 dx2 *= -1; 1246 } else if(dx2 == 0) { 1247 //if the second slope is vertical the first is always less unless it is also vertical, in which case they are equal 1248 return dx1 != 0; 1249 } 1250 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type; 1251 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1); 1252 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2); 1253 int dx1_sign = dx1 < 0 ? -1 : 1; 1254 int dx2_sign = dx2 < 0 ? -1 : 1; 1255 int dy1_sign = dy1 < 0 ? -1 : 1; 1256 int dy2_sign = dy2 < 0 ? -1 : 1; 1257 int cross_1_sign = dx2_sign * dy1_sign; 1258 int cross_2_sign = dx1_sign * dy2_sign; 1259 if(cross_1_sign < cross_2_sign) return true; 1260 if(cross_2_sign < cross_1_sign) return false; 1261 if(cross_1_sign == -1) return cross_2 < cross_1; 1262 return cross_1 < cross_2; 1263 } 1264 less_slopeboost::polygon::edge_utils1265 static inline bool less_slope(const Unit& x, const Unit& y, 1266 const Point& pt1, const Point& pt2) { 1267 const Point* pts[2] = {&pt1, &pt2}; 1268 //compute y value on edge from pt_ to pts[1] at the x value of pts[0] 1269 typedef typename coordinate_traits<Unit>::manhattan_area_type at; 1270 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y; 1271 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y; 1272 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x; 1273 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x; 1274 return less_slope(dx1, dy1, dx2, dy2); 1275 } 1276 1277 //return -1 below, 0 on and 1 above line 1278 //assumes point is on x interval of segment on_above_or_belowboost::polygon::edge_utils1279 static inline int on_above_or_below(Point pt, const half_edge& he) { 1280 if(pt == he.first || pt == he.second) return 0; 1281 if(equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second)) return 0; 1282 bool less_result = less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second); 1283 int retval = less_result ? -1 : 1; 1284 less_point lp; 1285 if(lp(he.second, he.first)) retval *= -1; 1286 if(!between(pt, he.first, he.second)) retval *= -1; 1287 return retval; 1288 } 1289 }; 1290 1291 template <typename T, typename input_point_type> 1292 typename enable_if< 1293 typename gtl_and< typename is_any_mutable_polygon_with_holes_type<T>::type, 1294 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type, 1295 bool>::type contains(const T & polygon,const input_point_type & point,bool consider_touch=true)1296 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) { 1297 typedef typename polygon_with_holes_traits<T>::iterator_holes_type holes_iterator; 1298 bool isInside = contains( view_as< typename polygon_from_polygon_with_holes_type< 1299 typename geometry_concept<T>::type>::type>( polygon ), point, consider_touch ); 1300 if(!isInside) return false; //no need to check holes 1301 holes_iterator itH = begin_holes( polygon ); 1302 while( itH != end_holes( polygon ) ) { 1303 if( contains( *itH, point, !consider_touch ) ) { 1304 isInside = false; 1305 break; 1306 } 1307 ++itH; 1308 } 1309 return isInside; 1310 } 1311 1312 template <typename T, typename input_point_type> 1313 typename enable_if< 1314 typename gtl_and_3< 1315 typename is_polygon_type<T>::type, 1316 typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type, 1317 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type, 1318 bool>::type contains(const T & polygon,const input_point_type & point,bool consider_touch=true)1319 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) { 1320 typedef typename point_traits<input_point_type>::coordinate_type Unit; 1321 typedef point_data<Unit> Point; 1322 typedef std::pair<Point, Point> half_edge; 1323 typedef typename polygon_traits<T>::iterator_type iterator; 1324 iterator itr = begin_points(polygon); 1325 iterator itrEnd = end_points(polygon); 1326 half_edge he; 1327 if(itr == itrEnd) return false; 1328 assign(he.first, *itr); 1329 Point firstPt; 1330 assign(firstPt, *itr); 1331 ++itr; 1332 if(itr == itrEnd) return false; 1333 bool done = false; 1334 int above = 0; 1335 while(!done) { 1336 Point currentPt; 1337 if(itr == itrEnd) { 1338 done = true; 1339 currentPt = firstPt; 1340 } else { 1341 assign(currentPt, *itr); 1342 ++itr; 1343 } 1344 if(currentPt == he.first) { 1345 continue; 1346 } else { 1347 he.second = currentPt; 1348 if(equivalence(point, currentPt)) return consider_touch; 1349 Unit xmin = (std::min)(x(he.first), x(he.second)); 1350 Unit xmax = (std::max)(x(he.first), x(he.second)); 1351 if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax 1352 Point tmppt; 1353 assign(tmppt, point); 1354 int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he); 1355 if(oabedge == 0) return consider_touch; 1356 if(oabedge == 1) ++above; 1357 } else if(x(point) == xmax) { 1358 if(x(point) == xmin) { 1359 Unit ymin = (std::min)(y(he.first), y(he.second)); 1360 Unit ymax = (std::max)(y(he.first), y(he.second)); 1361 Unit ypt = y(point); 1362 if(ypt <= ymax && ypt >= ymin) 1363 return consider_touch; 1364 } else { 1365 Point tmppt; 1366 assign(tmppt, point); 1367 if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) { 1368 return consider_touch; 1369 } 1370 } 1371 } 1372 } 1373 he.first = he.second; 1374 } 1375 return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon 1376 } 1377 1378 /* 1379 template <typename T, typename input_point_type> 1380 typename enable_if< 1381 typename gtl_and_3< 1382 typename is_polygon_with_holes_type<T>::type, 1383 typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type, 1384 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type, 1385 bool>::type 1386 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) { 1387 typedef typename point_traits<input_point_type>::coordinate_type Unit; 1388 typedef point_data<Unit> Point; 1389 typedef std::pair<Point, Point> half_edge; 1390 typedef typename polygon_traits<T>::iterator_type iterator; 1391 iterator itr = begin_points(polygon); 1392 iterator itrEnd = end_points(polygon); 1393 half_edge he; 1394 if(itr == itrEnd) return false; 1395 assign(he.first, *itr); 1396 Point firstPt; 1397 assign(firstPt, *itr); 1398 ++itr; 1399 if(itr == itrEnd) return false; 1400 bool done = false; 1401 int above = 0; 1402 while(!done) { 1403 Point currentPt; 1404 if(itr == itrEnd) { 1405 done = true; 1406 currentPt = firstPt; 1407 } else { 1408 assign(currentPt, *itr); 1409 ++itr; 1410 } 1411 if(currentPt == he.first) { 1412 continue; 1413 } else { 1414 he.second = currentPt; 1415 if(equivalence(point, currentPt)) return consider_touch; 1416 Unit xmin = (std::min)(x(he.first), x(he.second)); 1417 Unit xmax = (std::max)(x(he.first), x(he.second)); 1418 if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax 1419 Point tmppt; 1420 assign(tmppt, point); 1421 int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he); 1422 if(oabedge == 0) return consider_touch; 1423 if(oabedge == 1) ++above; 1424 } 1425 } 1426 he.first = he.second; 1427 } 1428 return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon 1429 } 1430 */ 1431 1432 template <typename T1, typename T2> 1433 typename enable_if< 1434 typename gtl_and< typename is_mutable_rectangle_concept<typename geometry_concept<T1>::type>::type, 1435 typename is_polygon_with_holes_type<T2>::type>::type, 1436 bool>::type extents(T1 & bounding_box,const T2 & polygon)1437 extents(T1& bounding_box, const T2& polygon) { 1438 typedef typename polygon_traits<T2>::iterator_type iterator; 1439 bool first_iteration = true; 1440 iterator itr_end = end_points(polygon); 1441 for(iterator itr = begin_points(polygon); itr != itr_end; ++itr) { 1442 if(first_iteration) { 1443 set_points(bounding_box, *itr, *itr); 1444 first_iteration = false; 1445 } else { 1446 encompass(bounding_box, *itr); 1447 } 1448 } 1449 if(first_iteration) return false; 1450 return true; 1451 } 1452 1453 template <typename T1, typename T2> 1454 typename enable_if< 1455 typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type, 1456 typename is_polygon_with_holes_type<T2>::type>::type, 1457 bool>::type center(T1 & center_point,const T2 & polygon)1458 center(T1& center_point, const T2& polygon) { 1459 typedef typename polygon_traits<T2>::coordinate_type coordinate_type; 1460 rectangle_data<coordinate_type> bbox; 1461 extents(bbox, polygon); 1462 return center(center_point, bbox); 1463 } 1464 1465 template <class T> 1466 template <class T2> operator =(const T2 & rvalue)1467 polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) { 1468 assign(*this, rvalue); 1469 return *this; 1470 } 1471 1472 template <class T> 1473 template <class T2> operator =(const T2 & rvalue)1474 polygon_45_data<T>& polygon_45_data<T>::operator=(const T2& rvalue) { 1475 assign(*this, rvalue); 1476 return *this; 1477 } 1478 1479 template <class T> 1480 template <class T2> operator =(const T2 & rvalue)1481 polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) { 1482 assign(*this, rvalue); 1483 return *this; 1484 } 1485 1486 template <class T> 1487 template <class T2> operator =(const T2 & rvalue)1488 polygon_90_with_holes_data<T>& polygon_90_with_holes_data<T>::operator=(const T2& rvalue) { 1489 assign(*this, rvalue); 1490 return *this; 1491 } 1492 1493 template <class T> 1494 template <class T2> operator =(const T2 & rvalue)1495 polygon_45_with_holes_data<T>& polygon_45_with_holes_data<T>::operator=(const T2& rvalue) { 1496 assign(*this, rvalue); 1497 return *this; 1498 } 1499 1500 template <class T> 1501 template <class T2> operator =(const T2 & rvalue)1502 polygon_with_holes_data<T>& polygon_with_holes_data<T>::operator=(const T2& rvalue) { 1503 assign(*this, rvalue); 1504 return *this; 1505 } 1506 1507 template <typename T> 1508 struct geometry_concept<polygon_data<T> > { 1509 typedef polygon_concept type; 1510 }; 1511 template <typename T> 1512 struct geometry_concept<polygon_45_data<T> > { 1513 typedef polygon_45_concept type; 1514 }; 1515 template <typename T> 1516 struct geometry_concept<polygon_90_data<T> > { 1517 typedef polygon_90_concept type; 1518 }; 1519 template <typename T> 1520 struct geometry_concept<polygon_with_holes_data<T> > { 1521 typedef polygon_with_holes_concept type; 1522 }; 1523 template <typename T> 1524 struct geometry_concept<polygon_45_with_holes_data<T> > { 1525 typedef polygon_45_with_holes_concept type; 1526 }; 1527 template <typename T> 1528 struct geometry_concept<polygon_90_with_holes_data<T> > { 1529 typedef polygon_90_with_holes_concept type; 1530 }; 1531 1532 // template <typename T> struct polygon_with_holes_traits<polygon_90_data<T> > { 1533 // typedef polygon_90_data<T> hole_type; 1534 // typedef const hole_type* iterator_holes_type; 1535 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; } 1536 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; } 1537 // static inline std::size_t size_holes(const hole_type& t) { return 0; } 1538 // }; 1539 // template <typename T> struct polygon_with_holes_traits<polygon_45_data<T> > { 1540 // typedef polygon_45_data<T> hole_type; 1541 // typedef const hole_type* iterator_holes_type; 1542 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; } 1543 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; } 1544 // static inline std::size_t size_holes(const hole_type& t) { return 0; } 1545 // }; 1546 // template <typename T> struct polygon_with_holes_traits<polygon_data<T> > { 1547 // typedef polygon_data<T> hole_type; 1548 // typedef const hole_type* iterator_holes_type; 1549 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; } 1550 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; } 1551 // static inline std::size_t size_holes(const hole_type& t) { return 0; } 1552 // }; 1553 template <typename T> struct get_void {}; 1554 template <> struct get_void<gtl_yes> { typedef void type; }; 1555 1556 template <typename T> struct polygon_with_holes_traits< 1557 T, typename get_void<typename is_any_mutable_polygon_without_holes_type<T>::type>::type > { 1558 typedef T hole_type; 1559 typedef const hole_type* iterator_holes_type; begin_holesboost::polygon::polygon_with_holes_traits1560 static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; } end_holesboost::polygon::polygon_with_holes_traits1561 static inline iterator_holes_type end_holes(const hole_type& t) { return &t; } 1562 }; 1563 1564 template <typename T> 1565 struct view_of<rectangle_concept, T> { 1566 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1567 typedef interval_data<coordinate_type> interval_type; 1568 rectangle_data<coordinate_type> rect; view_ofboost::polygon::view_of1569 view_of(const T& obj) : rect() { 1570 point_data<coordinate_type> pts[2]; 1571 typename polygon_traits<T>::iterator_type itr = 1572 begin_points(obj), itre = end_points(obj); 1573 if(itr == itre) return; 1574 assign(pts[0], *itr); 1575 ++itr; 1576 if(itr == itre) return; 1577 ++itr; 1578 if(itr == itre) return; 1579 assign(pts[1], *itr); 1580 set_points(rect, pts[0], pts[1]); 1581 } getboost::polygon::view_of1582 inline interval_type get(orientation_2d orient) const { 1583 return rect.get(orient); } 1584 }; 1585 1586 template <typename T> 1587 struct geometry_concept<view_of<rectangle_concept, T> > { 1588 typedef rectangle_concept type; 1589 }; 1590 1591 template <typename T> 1592 struct view_of<polygon_45_concept, T> { 1593 const T* t; view_ofboost::polygon::view_of1594 view_of(const T& obj) : t(&obj) {} 1595 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1596 typedef typename polygon_traits<T>::iterator_type iterator_type; 1597 typedef typename polygon_traits<T>::point_type point_type; 1598 1599 /// Get the begin iterator beginboost::polygon::view_of1600 inline iterator_type begin() const { 1601 return polygon_traits<T>::begin_points(*t); 1602 } 1603 1604 /// Get the end iterator endboost::polygon::view_of1605 inline iterator_type end() const { 1606 return polygon_traits<T>::end_points(*t); 1607 } 1608 1609 /// Get the number of sides of the polygon sizeboost::polygon::view_of1610 inline std::size_t size() const { 1611 return polygon_traits<T>::size(*t); 1612 } 1613 1614 /// Get the winding direction of the polygon windingboost::polygon::view_of1615 inline winding_direction winding() const { 1616 return polygon_traits<T>::winding(*t); 1617 } 1618 }; 1619 1620 template <typename T> 1621 struct geometry_concept<view_of<polygon_45_concept, T> > { 1622 typedef polygon_45_concept type; 1623 }; 1624 1625 template <typename T> 1626 struct view_of<polygon_90_concept, T> { 1627 const T* t; view_ofboost::polygon::view_of1628 view_of(const T& obj) : t(&obj) {} 1629 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1630 typedef typename polygon_traits<T>::iterator_type iterator_type; 1631 typedef typename polygon_traits<T>::point_type point_type; 1632 typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type; 1633 1634 /// Get the begin iterator begin_compactboost::polygon::view_of1635 inline compact_iterator_type begin_compact() const { 1636 return compact_iterator_type(polygon_traits<T>::begin_points(*t), 1637 polygon_traits<T>::end_points(*t)); 1638 } 1639 1640 /// Get the end iterator end_compactboost::polygon::view_of1641 inline compact_iterator_type end_compact() const { 1642 return compact_iterator_type(polygon_traits<T>::end_points(*t), 1643 polygon_traits<T>::end_points(*t)); 1644 } 1645 1646 /// Get the number of sides of the polygon sizeboost::polygon::view_of1647 inline std::size_t size() const { 1648 return polygon_traits<T>::size(*t); 1649 } 1650 1651 /// Get the winding direction of the polygon windingboost::polygon::view_of1652 inline winding_direction winding() const { 1653 return polygon_traits<T>::winding(*t); 1654 } 1655 }; 1656 1657 template <typename T> 1658 struct geometry_concept<view_of<polygon_90_concept, T> > { 1659 typedef polygon_90_concept type; 1660 }; 1661 1662 template <typename T> 1663 struct view_of<polygon_45_with_holes_concept, T> { 1664 const T* t; view_ofboost::polygon::view_of1665 view_of(const T& obj) : t(&obj) {} 1666 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1667 typedef typename polygon_traits<T>::iterator_type iterator_type; 1668 typedef typename polygon_traits<T>::point_type point_type; 1669 typedef view_of<polygon_45_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type; 1670 struct iterator_holes_type { 1671 typedef std::forward_iterator_tag iterator_category; 1672 typedef hole_type value_type; 1673 typedef std::ptrdiff_t difference_type; 1674 typedef const hole_type* pointer; //immutable 1675 typedef const hole_type& reference; //immutable 1676 typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht; 1677 iht internal_itr; iterator_holes_typeboost::polygon::view_of::iterator_holes_type1678 iterator_holes_type() : internal_itr() {} iterator_holes_typeboost::polygon::view_of::iterator_holes_type1679 iterator_holes_type(iht iht_in) : internal_itr(iht_in) {} operator ++boost::polygon::view_of::iterator_holes_type1680 inline iterator_holes_type& operator++() { 1681 ++internal_itr; 1682 return *this; 1683 } operator ++boost::polygon::view_of::iterator_holes_type1684 inline const iterator_holes_type operator++(int) { 1685 iterator_holes_type tmp(*this); 1686 ++(*this); 1687 return tmp; 1688 } operator ==boost::polygon::view_of::iterator_holes_type1689 inline bool operator==(const iterator_holes_type& that) const { 1690 return (internal_itr == that.internal_itr); 1691 } operator !=boost::polygon::view_of::iterator_holes_type1692 inline bool operator!=(const iterator_holes_type& that) const { 1693 return (internal_itr != that.internal_itr); 1694 } operator *boost::polygon::view_of::iterator_holes_type1695 inline value_type operator*() const { 1696 return view_as<polygon_45_concept>(*internal_itr); 1697 } 1698 }; 1699 1700 /// Get the begin iterator beginboost::polygon::view_of1701 inline iterator_type begin() const { 1702 return polygon_traits<T>::begin_points(*t); 1703 } 1704 1705 /// Get the end iterator endboost::polygon::view_of1706 inline iterator_type end() const { 1707 return polygon_traits<T>::end_points(*t); 1708 } 1709 1710 /// Get the number of sides of the polygon sizeboost::polygon::view_of1711 inline std::size_t size() const { 1712 return polygon_traits<T>::size(*t); 1713 } 1714 1715 /// Get the winding direction of the polygon windingboost::polygon::view_of1716 inline winding_direction winding() const { 1717 return polygon_traits<T>::winding(*t); 1718 } 1719 1720 /// Get the begin iterator begin_holesboost::polygon::view_of1721 inline iterator_holes_type begin_holes() const { 1722 return polygon_with_holes_traits<T>::begin_holes(*t); 1723 } 1724 1725 /// Get the end iterator end_holesboost::polygon::view_of1726 inline iterator_holes_type end_holes() const { 1727 return polygon_with_holes_traits<T>::end_holes(*t); 1728 } 1729 1730 /// Get the number of sides of the polygon size_holesboost::polygon::view_of1731 inline std::size_t size_holes() const { 1732 return polygon_with_holes_traits<T>::size_holes(*t); 1733 } 1734 1735 }; 1736 1737 template <typename T> 1738 struct geometry_concept<view_of<polygon_45_with_holes_concept, T> > { 1739 typedef polygon_45_with_holes_concept type; 1740 }; 1741 1742 template <typename T> 1743 struct view_of<polygon_90_with_holes_concept, T> { 1744 const T* t; view_ofboost::polygon::view_of1745 view_of(const T& obj) : t(&obj) {} 1746 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1747 typedef typename polygon_traits<T>::iterator_type iterator_type; 1748 typedef typename polygon_traits<T>::point_type point_type; 1749 typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type; 1750 typedef view_of<polygon_90_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type; 1751 struct iterator_holes_type { 1752 typedef std::forward_iterator_tag iterator_category; 1753 typedef hole_type value_type; 1754 typedef std::ptrdiff_t difference_type; 1755 typedef const hole_type* pointer; //immutable 1756 typedef const hole_type& reference; //immutable 1757 typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht; 1758 iht internal_itr; iterator_holes_typeboost::polygon::view_of::iterator_holes_type1759 iterator_holes_type() : internal_itr() {} iterator_holes_typeboost::polygon::view_of::iterator_holes_type1760 iterator_holes_type(iht iht_in) : internal_itr(iht_in) {} operator ++boost::polygon::view_of::iterator_holes_type1761 inline iterator_holes_type& operator++() { 1762 ++internal_itr; 1763 return *this; 1764 } operator ++boost::polygon::view_of::iterator_holes_type1765 inline const iterator_holes_type operator++(int) { 1766 iterator_holes_type tmp(*this); 1767 ++(*this); 1768 return tmp; 1769 } operator ==boost::polygon::view_of::iterator_holes_type1770 inline bool operator==(const iterator_holes_type& that) const { 1771 return (internal_itr == that.internal_itr); 1772 } operator !=boost::polygon::view_of::iterator_holes_type1773 inline bool operator!=(const iterator_holes_type& that) const { 1774 return (internal_itr != that.internal_itr); 1775 } operator *boost::polygon::view_of::iterator_holes_type1776 inline value_type operator*() const { 1777 return view_as<polygon_90_concept>(*internal_itr); 1778 } 1779 }; 1780 1781 /// Get the begin iterator begin_compactboost::polygon::view_of1782 inline compact_iterator_type begin_compact() const { 1783 return compact_iterator_type(polygon_traits<T>::begin_points(*t), 1784 polygon_traits<T>::end_points(*t)); 1785 } 1786 1787 /// Get the end iterator end_compactboost::polygon::view_of1788 inline compact_iterator_type end_compact() const { 1789 return compact_iterator_type(polygon_traits<T>::end_points(*t), 1790 polygon_traits<T>::end_points(*t)); 1791 } 1792 1793 /// Get the number of sides of the polygon sizeboost::polygon::view_of1794 inline std::size_t size() const { 1795 return polygon_traits<T>::size(*t); 1796 } 1797 1798 /// Get the winding direction of the polygon windingboost::polygon::view_of1799 inline winding_direction winding() const { 1800 return polygon_traits<T>::winding(*t); 1801 } 1802 1803 /// Get the begin iterator begin_holesboost::polygon::view_of1804 inline iterator_holes_type begin_holes() const { 1805 return polygon_with_holes_traits<T>::begin_holes(*t); 1806 } 1807 1808 /// Get the end iterator end_holesboost::polygon::view_of1809 inline iterator_holes_type end_holes() const { 1810 return polygon_with_holes_traits<T>::end_holes(*t); 1811 } 1812 1813 /// Get the number of sides of the polygon size_holesboost::polygon::view_of1814 inline std::size_t size_holes() const { 1815 return polygon_with_holes_traits<T>::size_holes(*t); 1816 } 1817 1818 }; 1819 1820 template <typename T> 1821 struct geometry_concept<view_of<polygon_90_with_holes_concept, T> > { 1822 typedef polygon_90_with_holes_concept type; 1823 }; 1824 1825 template <typename T> 1826 struct view_of<polygon_concept, T> { 1827 const T* t; view_ofboost::polygon::view_of1828 view_of(const T& obj) : t(&obj) {} 1829 typedef typename polygon_traits<T>::coordinate_type coordinate_type; 1830 typedef typename polygon_traits<T>::iterator_type iterator_type; 1831 typedef typename polygon_traits<T>::point_type point_type; 1832 1833 /// Get the begin iterator beginboost::polygon::view_of1834 inline iterator_type begin() const { 1835 return polygon_traits<T>::begin_points(*t); 1836 } 1837 1838 /// Get the end iterator endboost::polygon::view_of1839 inline iterator_type end() const { 1840 return polygon_traits<T>::end_points(*t); 1841 } 1842 1843 /// Get the number of sides of the polygon sizeboost::polygon::view_of1844 inline std::size_t size() const { 1845 return polygon_traits<T>::size(*t); 1846 } 1847 1848 /// Get the winding direction of the polygon windingboost::polygon::view_of1849 inline winding_direction winding() const { 1850 return polygon_traits<T>::winding(*t); 1851 } 1852 }; 1853 1854 template <typename T> 1855 struct geometry_concept<view_of<polygon_concept, T> > { 1856 typedef polygon_concept type; 1857 }; 1858 } 1859 } 1860 1861 #endif 1862