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