2 Copyright 2008 Intel Corporation
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).
8 #ifndef BOOST_POLYGON_POLYGON_TRAITS_HPP
9 #define BOOST_POLYGON_POLYGON_TRAITS_HPP
10 namespace boost { namespace polygon{
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;
17 // Get the begin iterator
18 static inline compact_iterator_type begin_compact(const T& t) {
19 return t.begin_compact();
22 // Get the end iterator
23 static inline compact_iterator_type end_compact(const T& t) {
24 return t.end_compact();
27 // Get the number of sides of the polygon
28 static inline std::size_t size(const T& t) {
32 // Get the winding direction of the polygon
33 static inline winding_direction winding(const T&) {
34 return unknown_winding;
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;
44 // Get the begin iterator
45 static inline iterator_type begin_points(const T& t) {
49 // Get the end iterator
50 static inline iterator_type end_points(const T& t) {
54 // Get the number of sides of the polygon
55 static inline std::size_t size(const T& t) {
59 // Get the winding direction of the polygon
60 static inline winding_direction winding(const T&) {
61 return unknown_winding;
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;
71 // Get the begin iterator
72 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));
77 // Get the end iterator
78 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));
83 // Get the number of sides of the polygon
84 static inline std::size_t size(const T& t) {
85 return polygon_90_traits<T>::size(t);
88 // Get the winding direction of the polygon
89 static inline winding_direction winding(const T& t) {
90 return polygon_90_traits<T>::winding(t);
94 #ifndef BOOST_VERY_LITTLE_SFINAE
96 template <typename T, typename enable = gtl_yes>
97 struct polygon_traits {};
100 struct polygon_traits<T,
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> {};
108 template <typename T>
109 struct polygon_traits< T,
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> {};
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> {
123 template <typename T_IF, typename T_ELSE>
124 struct gtl_ifelse<gtl_yes, T_IF, T_ELSE> {
128 template <typename T, typename enable = gtl_yes>
129 struct polygon_traits {};
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 {
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;
154 // Get the begin iterator
155 static inline iterator_holes_type begin_holes(const T& t) {
156 return t.begin_holes();
159 // Get the end iterator
160 static inline iterator_holes_type end_holes(const T& t) {
161 return t.end_holes();
164 // Get the number of holes
165 static inline std::size_t size_holes(const T& t) {
166 return t.size_holes();
170 template <typename T, typename enable = void>
171 struct polygon_90_mutable_traits {
173 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
174 template <typename iT>
175 static inline T& set_compact(T& t, iT input_begin, iT input_end) {
176 t.set_compact(input_begin, input_end);
182 template <typename T, typename enable = void>
183 struct polygon_mutable_traits {
185 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
186 template <typename iT>
187 static inline T& set_points(T& t, iT input_begin, iT input_end) {
188 t.set(input_begin, input_end);
194 template <typename T, typename enable = void>
195 struct polygon_with_holes_mutable_traits {
197 // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
198 template <typename iT>
199 static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) {
200 t.set_holes(inputBegin, inputEnd);
207 #include "isotropy.hpp"
210 #include "point_data.hpp"
211 #include "point_traits.hpp"
212 #include "point_concept.hpp"
215 #include "interval_data.hpp"
216 #include "interval_traits.hpp"
217 #include "interval_concept.hpp"
220 #include "rectangle_data.hpp"
221 #include "rectangle_traits.hpp"
222 #include "rectangle_concept.hpp"
224 //algorithms needed by polygon types
225 #include "detail/iterator_points_to_compact.hpp"
226 #include "detail/iterator_compact_to_points.hpp"
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"
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 {};
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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; };
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;
343 template <typename T>
344 struct polygon_from_polygon_with_holes_type {};
346 struct polygon_from_polygon_with_holes_type<polygon_with_holes_concept> { typedef polygon_concept type; };
348 struct polygon_from_polygon_with_holes_type<polygon_45_with_holes_concept> { typedef polygon_45_concept type; };
350 struct polygon_from_polygon_with_holes_type<polygon_90_with_holes_concept> { typedef polygon_90_concept type; };
353 struct geometry_domain<polygon_45_concept> { typedef forty_five_domain type; };
355 struct geometry_domain<polygon_45_with_holes_concept> { typedef forty_five_domain type; };
357 struct geometry_domain<polygon_90_concept> { typedef manhattan_domain type; };
359 struct geometry_domain<polygon_90_with_holes_concept> { typedef manhattan_domain type; };
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; };
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
374 /// \relatesalso polygon_concept
375 template <typename T, typename iT>
376 typename enable_if <typename is_any_mutable_polygon_type<T>::type, T>::type &
377 set_points(T& t, iT begin_points, iT end_points) {
378 polygon_mutable_traits<T>::set_points(t, begin_points, end_points);
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
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 &
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);
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,
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);
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 &
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);
421 /// \relatesalso polygon_90_concept
422 template <typename T>
423 typename polygon_90_traits<T>::compact_iterator_type
424 begin_compact(const T& polygon,
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
430 return polygon_90_traits<T>::begin_compact(polygon);
433 /// \relatesalso polygon_90_concept
434 template <typename T>
435 typename polygon_90_traits<T>::compact_iterator_type
436 end_compact(const T& polygon,
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
442 return polygon_90_traits<T>::end_compact(polygon);
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
450 begin_points(const T& polygon) {
451 return polygon_traits<T>::begin_points(polygon);
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
459 end_points(const T& polygon) {
460 return polygon_traits<T>::end_points(polygon);
463 /// \relatesalso polygon_concept
464 template <typename T>
465 typename enable_if <typename is_polygon_with_holes_type<T>::type,
467 size(const T& polygon) {
468 return polygon_traits<T>::size(polygon);
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
476 begin_holes(const T& polygon) {
477 return polygon_with_holes_traits<T>::begin_holes(polygon);
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
485 end_holes(const T& polygon) {
486 return polygon_with_holes_traits<T>::end_holes(polygon);
489 /// \relatesalso polygon_with_holes_concept
490 template <typename T>
491 typename enable_if <typename is_polygon_with_holes_type<T>::type,
493 size_holes(const T& polygon) {
494 return polygon_with_holes_traits<T>::size_holes(polygon);
497 // \relatesalso polygon_concept
498 template <typename T1, typename T2>
500 typename gtl_and< typename is_mutable_polygon_type<T1>::type,
501 typename is_polygon_type<T2>::type>::type, T1>::type &
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));
508 // \relatesalso polygon_with_holes_concept
509 template <typename T1, typename T2>
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 &
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));
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 &
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));
530 // \relatesalso polygon_45_with_holes_concept
531 template <typename T1, typename T2>
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 &
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));
543 // \relatesalso polygon_90_concept
544 template <typename T1, typename T2>
546 typename gtl_and< typename is_mutable_polygon_90_type<T1>::type,
547 typename is_polygon_90_type<T2>::type>::type, T1>::type &
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));
554 // \relatesalso polygon_90_with_holes_concept
555 template <typename T1, typename T2>
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 &
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));
567 // \relatesalso polygon_90_concept
568 template <typename T1, typename T2>
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 &
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);
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 &
584 convolve(polygon_type& polygon, const point_type& point) {
585 std::vector<typename polygon_90_traits<polygon_type>::coordinate_type> coords;
586 coords.reserve(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;
593 polygon_90_mutable_traits<polygon_type>::set_compact(polygon, coords.begin(), coords.end());
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 &
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(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);
612 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
616 /// \relatesalso polygon_with_holes_concept
617 template <typename polygon_type, typename point_type>
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 &
622 convolve(polygon_type& polygon, const point_type& point) {
623 typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
625 set_points(h, begin_points(polygon), end_points(polygon));
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);
635 set_holes(polygon, holes.begin(), holes.end());
639 /// \relatesalso polygon_concept
640 template <typename T>
641 typename enable_if< typename is_any_mutable_polygon_type<T>::type, T>::type &
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));
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 &
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(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);
664 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
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 &
671 transform(T& polygon, const transform_type& tr) {
672 typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
674 set_points(h, begin_points(polygon), end_points(polygon));
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);
684 set_holes(polygon, holes.begin(), holes.end());
688 template <typename polygon_type>
689 typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
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(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);
698 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
702 template <typename T>
703 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
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;
707 set_points(h, begin_points(polygon), end_points(polygon));
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);
717 set_holes(polygon, holes.begin(), holes.end());
722 template <typename polygon_type>
724 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
725 typename gtl_not<typename gtl_same_type
727 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
728 polygon_type>::type &
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(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);
737 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
741 template <typename Unit>
742 Unit local_abs(Unit value) { return value < 0 ? (Unit)-value : value; }
744 template <typename Unit>
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());
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) {
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);
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);
783 //std::cout << "fail1\n";
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);
796 //std::cout << "fail2\n";
799 if(i == numPts - 1 && (diff % 2)) {
800 //we have a wrap around effect
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);
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);
823 template <typename polygon_type>
824 typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
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(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);
832 snap_point_vector_to_45(points);
833 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
837 template <typename polygon_type>
838 typename enable_if< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type, polygon_type>::type &
839 snap_to_45(polygon_type& polygon) {
840 typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
842 set_points(h, begin_points(polygon), end_points(polygon));
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());
852 set_holes(polygon, holes.begin(), holes.end());
856 //scale specifically 45 down
857 template <typename polygon_type>
859 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
860 typename gtl_same_type
862 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type,
863 polygon_type>::type &
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(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);
872 snap_point_vector_to_45(points);
873 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
877 template <typename T>
878 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
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;
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);
892 set_holes(polygon, holes.begin(), holes.end());
897 template <typename polygon_type>
899 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
900 typename gtl_not<typename gtl_same_type
902 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
903 polygon_type>::type &
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(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));
912 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
916 //scale specifically 45
917 template <typename polygon_type>
919 scale(polygon_type& polygon, double factor,
921 typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
922 typename gtl_same_type
924 typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type * = 0
926 std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
927 points.reserve(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));
933 snap_point_vector_to_45(points);
934 polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
938 template <typename T>
940 scale(T& polygon, double factor,
941 typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type>::type * = 0
943 typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
945 set_points(h, begin_points(polygon), end_points(polygon));
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);
955 set_holes(polygon, holes.begin(), holes.end());
959 template <typename iterator_type, typename area_type>
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;
967 // Initialize trapezoid base line
968 area_type y_base = (area_type)y(first);
969 // Initialize area accumulator
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)
980 #ifdef BOOST_POLYGON_ICC
981 #pragma warning (pop)
983 // do trapezoid area accumulation
984 area += (x2 - x1) * (((area_type)y(*begin_range) - y_base) +
985 ((area_type)y(previous) - y_base)) / 2;
987 previous = *begin_range;
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;
1001 template <typename T>
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
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;
1024 template <typename iT>
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;
1032 while(itr != itr_end) {
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))
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))
1050 template <typename polygon_type>
1051 typename enable_if< typename is_polygon_with_holes_type<polygon_type>::type, bool>::type
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;
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;
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;
1079 return_value += (Unit)euclidean_distance(previous_point, first_point);
1080 return return_value;
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
1086 perimeter(const T& polygon,
1088 typename is_polygon_with_holes_type<T>::type>::type * = 0
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));
1101 return return_value;
1104 template <typename T>
1105 typename enable_if <typename is_polygon_with_holes_type<T>::type,
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;
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;
1118 template <typename T, typename input_point_type>
1121 typename is_polygon_90_type<T>::type,
1122 typename gtl_same_type<
1123 typename geometry_concept<input_point_type>::type,
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;
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) {
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;
1161 ++num_full_intersections;
1163 if (point_y == min_y || point_y == max_y) {
1164 num_half_intersections += (y(curr_point) < y(next_point) ? 1 : -1);
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;
1176 int total_intersections = num_full_intersections + (num_half_intersections >> 1);
1177 return total_intersections & 1;
1180 //TODO: refactor to expose as user APIs
1181 template <typename Unit>
1183 typedef point_data<Unit> Point;
1184 typedef std::pair<Point, Point> half_edge;
1186 class less_point : public std::binary_function<Point, Point, bool> {
1188 inline less_point() {}
1189 inline bool operator () (const Point& pt1, const Point& pt2) const {
1190 if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true;
1191 if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) {
1192 if(pt1.get(VERTICAL) < pt2.get(VERTICAL)) return true;
1198 static inline bool between(Point pt, Point pt1, Point pt2) {
1201 return lp(pt, pt2) && lp(pt1, pt);
1202 return lp(pt, pt1) && lp(pt2, pt);
1205 template <typename area_type>
1206 static inline bool equal_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
1207 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
1208 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
1209 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
1210 int dx1_sign = dx1 < 0 ? -1 : 1;
1211 int dx2_sign = dx2 < 0 ? -1 : 1;
1212 int dy1_sign = dy1 < 0 ? -1 : 1;
1213 int dy2_sign = dy2 < 0 ? -1 : 1;
1214 int cross_1_sign = dx2_sign * dy1_sign;
1215 int cross_2_sign = dx1_sign * dy2_sign;
1216 return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0);
1219 static inline bool equal_slope(const Unit& x, const Unit& y,
1220 const Point& pt1, const Point& pt2) {
1221 const Point* pts[2] = {&pt1, &pt2};
1222 typedef typename coordinate_traits<Unit>::manhattan_area_type at;
1223 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
1224 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
1225 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
1226 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
1227 return equal_slope(dx1, dy1, dx2, dy2);
1230 template <typename area_type>
1231 static inline bool less_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
1232 //reflext x and y slopes to right hand side half plane
1236 } else if(dx1 == 0) {
1237 //if the first slope is vertical the first cannot be less
1243 } else if(dx2 == 0) {
1244 //if the second slope is vertical the first is always less unless it is also vertical, in which case they are equal
1247 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
1248 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
1249 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
1250 int dx1_sign = dx1 < 0 ? -1 : 1;
1251 int dx2_sign = dx2 < 0 ? -1 : 1;
1252 int dy1_sign = dy1 < 0 ? -1 : 1;
1253 int dy2_sign = dy2 < 0 ? -1 : 1;
1254 int cross_1_sign = dx2_sign * dy1_sign;
1255 int cross_2_sign = dx1_sign * dy2_sign;
1256 if(cross_1_sign < cross_2_sign) return true;
1257 if(cross_2_sign < cross_1_sign) return false;
1258 if(cross_1_sign == -1) return cross_2 < cross_1;
1259 return cross_1 < cross_2;
1262 static inline bool less_slope(const Unit& x, const Unit& y,
1263 const Point& pt1, const Point& pt2) {
1264 const Point* pts[2] = {&pt1, &pt2};
1265 //compute y value on edge from pt_ to pts[1] at the x value of pts[0]
1266 typedef typename coordinate_traits<Unit>::manhattan_area_type at;
1267 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
1268 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
1269 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
1270 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
1271 return less_slope(dx1, dy1, dx2, dy2);
1274 //return -1 below, 0 on and 1 above line
1275 //assumes point is on x interval of segment
1276 static inline int on_above_or_below(Point pt, const half_edge& he) {
1277 if(pt == he.first || pt == he.second) return 0;
1278 if(equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second)) return 0;
1279 bool less_result = less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second);
1280 int retval = less_result ? -1 : 1;
1282 if(lp(he.second, he.first)) retval *= -1;
1283 if(!between(pt, he.first, he.second)) retval *= -1;
1288 template <typename T, typename input_point_type>
1290 typename gtl_and< typename is_any_mutable_polygon_with_holes_type<T>::type,
1291 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1293 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1294 typedef typename polygon_with_holes_traits<T>::iterator_holes_type holes_iterator;
1295 bool isInside = contains( view_as< typename polygon_from_polygon_with_holes_type<
1296 typename geometry_concept<T>::type>::type>( polygon ), point, consider_touch );
1297 if(!isInside) return false; //no need to check holes
1298 holes_iterator itH = begin_holes( polygon );
1299 while( itH != end_holes( polygon ) ) {
1300 if( contains( *itH, point, !consider_touch ) ) {
1309 template <typename T, typename input_point_type>
1312 typename is_polygon_type<T>::type,
1313 typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
1314 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1316 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1317 typedef typename point_traits<input_point_type>::coordinate_type Unit;
1318 typedef point_data<Unit> Point;
1319 typedef std::pair<Point, Point> half_edge;
1320 typedef typename polygon_traits<T>::iterator_type iterator;
1321 iterator itr = begin_points(polygon);
1322 iterator itrEnd = end_points(polygon);
1324 if(itr == itrEnd) return false;
1325 assign(he.first, *itr);
1327 assign(firstPt, *itr);
1329 if(itr == itrEnd) return false;
1336 currentPt = firstPt;
1338 assign(currentPt, *itr);
1341 if(currentPt == he.first) {
1344 he.second = currentPt;
1345 if(equivalence(point, currentPt)) return consider_touch;
1346 Unit xmin = (std::min)(x(he.first), x(he.second));
1347 Unit xmax = (std::max)(x(he.first), x(he.second));
1348 if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
1350 assign(tmppt, point);
1351 int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
1352 if(oabedge == 0) return consider_touch;
1353 if(oabedge == 1) ++above;
1354 } else if(x(point) == xmax) {
1355 if(x(point) == xmin) {
1356 Unit ymin = (std::min)(y(he.first), y(he.second));
1357 Unit ymax = (std::max)(y(he.first), y(he.second));
1358 Unit ypt = y(point);
1359 if(ypt <= ymax && ypt >= ymin)
1360 return consider_touch;
1363 assign(tmppt, point);
1364 if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) {
1365 return consider_touch;
1370 he.first = he.second;
1372 return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
1376 template <typename T, typename input_point_type>
1379 typename is_polygon_with_holes_type<T>::type,
1380 typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
1381 typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1383 contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1384 typedef typename point_traits<input_point_type>::coordinate_type Unit;
1385 typedef point_data<Unit> Point;
1386 typedef std::pair<Point, Point> half_edge;
1387 typedef typename polygon_traits<T>::iterator_type iterator;
1388 iterator itr = begin_points(polygon);
1389 iterator itrEnd = end_points(polygon);
1391 if(itr == itrEnd) return false;
1392 assign(he.first, *itr);
1394 assign(firstPt, *itr);
1396 if(itr == itrEnd) return false;
1403 currentPt = firstPt;
1405 assign(currentPt, *itr);
1408 if(currentPt == he.first) {
1411 he.second = currentPt;
1412 if(equivalence(point, currentPt)) return consider_touch;
1413 Unit xmin = (std::min)(x(he.first), x(he.second));
1414 Unit xmax = (std::max)(x(he.first), x(he.second));
1415 if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
1417 assign(tmppt, point);
1418 int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
1419 if(oabedge == 0) return consider_touch;
1420 if(oabedge == 1) ++above;
1423 he.first = he.second;
1425 return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
1429 template <typename T1, typename T2>
1431 typename gtl_and< typename is_mutable_rectangle_concept<typename geometry_concept<T1>::type>::type,
1432 typename is_polygon_with_holes_type<T2>::type>::type,
1434 extents(T1& bounding_box, const T2& polygon) {
1435 typedef typename polygon_traits<T2>::iterator_type iterator;
1436 bool first_iteration = true;
1437 iterator itr_end = end_points(polygon);
1438 for(iterator itr = begin_points(polygon); itr != itr_end; ++itr) {
1439 if(first_iteration) {
1440 set_points(bounding_box, *itr, *itr);
1441 first_iteration = false;
1443 encompass(bounding_box, *itr);
1446 if(first_iteration) return false;
1450 template <typename T1, typename T2>
1452 typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type,
1453 typename is_polygon_with_holes_type<T2>::type>::type,
1455 center(T1& center_point, const T2& polygon) {
1456 typedef typename polygon_traits<T2>::coordinate_type coordinate_type;
1457 rectangle_data<coordinate_type> bbox;
1458 extents(bbox, polygon);
1459 return center(center_point, bbox);
1464 polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) {
1465 assign(*this, rvalue);
1471 polygon_45_data<T>& polygon_45_data<T>::operator=(const T2& rvalue) {
1472 assign(*this, rvalue);
1478 polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) {
1479 assign(*this, rvalue);
1485 polygon_90_with_holes_data<T>& polygon_90_with_holes_data<T>::operator=(const T2& rvalue) {
1486 assign(*this, rvalue);
1492 polygon_45_with_holes_data<T>& polygon_45_with_holes_data<T>::operator=(const T2& rvalue) {
1493 assign(*this, rvalue);
1499 polygon_with_holes_data<T>& polygon_with_holes_data<T>::operator=(const T2& rvalue) {
1500 assign(*this, rvalue);
1504 template <typename T>
1505 struct geometry_concept<polygon_data<T> > {
1506 typedef polygon_concept type;
1508 template <typename T>
1509 struct geometry_concept<polygon_45_data<T> > {
1510 typedef polygon_45_concept type;
1512 template <typename T>
1513 struct geometry_concept<polygon_90_data<T> > {
1514 typedef polygon_90_concept type;
1516 template <typename T>
1517 struct geometry_concept<polygon_with_holes_data<T> > {
1518 typedef polygon_with_holes_concept type;
1520 template <typename T>
1521 struct geometry_concept<polygon_45_with_holes_data<T> > {
1522 typedef polygon_45_with_holes_concept type;
1524 template <typename T>
1525 struct geometry_concept<polygon_90_with_holes_data<T> > {
1526 typedef polygon_90_with_holes_concept type;
1529 // template <typename T> struct polygon_with_holes_traits<polygon_90_data<T> > {
1530 // typedef polygon_90_data<T> hole_type;
1531 // typedef const hole_type* iterator_holes_type;
1532 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1533 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1534 // static inline std::size_t size_holes(const hole_type& t) { return 0; }
1536 // template <typename T> struct polygon_with_holes_traits<polygon_45_data<T> > {
1537 // typedef polygon_45_data<T> hole_type;
1538 // typedef const hole_type* iterator_holes_type;
1539 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1540 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1541 // static inline std::size_t size_holes(const hole_type& t) { return 0; }
1543 // template <typename T> struct polygon_with_holes_traits<polygon_data<T> > {
1544 // typedef polygon_data<T> hole_type;
1545 // typedef const hole_type* iterator_holes_type;
1546 // static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1547 // static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1548 // static inline std::size_t size_holes(const hole_type& t) { return 0; }
1550 template <typename T> struct get_void {};
1551 template <> struct get_void<gtl_yes> { typedef void type; };
1553 template <typename T> struct polygon_with_holes_traits<
1554 T, typename get_void<typename is_any_mutable_polygon_without_holes_type<T>::type>::type > {
1555 typedef 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; }
1561 template <typename T>
1562 struct view_of<rectangle_concept, T> {
1563 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1564 typedef interval_data<coordinate_type> interval_type;
1565 rectangle_data<coordinate_type> rect;
1566 view_of(const T& obj) : rect() {
1567 point_data<coordinate_type> pts[2];
1568 typename polygon_traits<T>::iterator_type itr =
1569 begin_points(obj), itre = end_points(obj);
1570 if(itr == itre) return;
1571 assign(pts[0], *itr);
1573 if(itr == itre) return;
1575 if(itr == itre) return;
1576 assign(pts[1], *itr);
1577 set_points(rect, pts[0], pts[1]);
1579 inline interval_type get(orientation_2d orient) const {
1580 return rect.get(orient); }
1583 template <typename T>
1584 struct geometry_concept<view_of<rectangle_concept, T> > {
1585 typedef rectangle_concept type;
1588 template <typename T>
1589 struct view_of<polygon_45_concept, T> {
1591 view_of(const T& obj) : t(&obj) {}
1592 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1593 typedef typename polygon_traits<T>::iterator_type iterator_type;
1594 typedef typename polygon_traits<T>::point_type point_type;
1596 /// Get the begin iterator
1597 inline iterator_type begin() const {
1598 return polygon_traits<T>::begin_points(*t);
1601 /// Get the end iterator
1602 inline iterator_type end() const {
1603 return polygon_traits<T>::end_points(*t);
1606 /// Get the number of sides of the polygon
1607 inline std::size_t size() const {
1608 return polygon_traits<T>::size(*t);
1611 /// Get the winding direction of the polygon
1612 inline winding_direction winding() const {
1613 return polygon_traits<T>::winding(*t);
1617 template <typename T>
1618 struct geometry_concept<view_of<polygon_45_concept, T> > {
1619 typedef polygon_45_concept type;
1622 template <typename T>
1623 struct view_of<polygon_90_concept, T> {
1625 view_of(const T& obj) : t(&obj) {}
1626 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1627 typedef typename polygon_traits<T>::iterator_type iterator_type;
1628 typedef typename polygon_traits<T>::point_type point_type;
1629 typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
1631 /// Get the begin iterator
1632 inline compact_iterator_type begin_compact() const {
1633 return compact_iterator_type(polygon_traits<T>::begin_points(*t),
1634 polygon_traits<T>::end_points(*t));
1637 /// Get the end iterator
1638 inline compact_iterator_type end_compact() const {
1639 return compact_iterator_type(polygon_traits<T>::end_points(*t),
1640 polygon_traits<T>::end_points(*t));
1643 /// Get the number of sides of the polygon
1644 inline std::size_t size() const {
1645 return polygon_traits<T>::size(*t);
1648 /// Get the winding direction of the polygon
1649 inline winding_direction winding() const {
1650 return polygon_traits<T>::winding(*t);
1654 template <typename T>
1655 struct geometry_concept<view_of<polygon_90_concept, T> > {
1656 typedef polygon_90_concept type;
1659 template <typename T>
1660 struct view_of<polygon_45_with_holes_concept, T> {
1662 view_of(const T& obj) : t(&obj) {}
1663 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1664 typedef typename polygon_traits<T>::iterator_type iterator_type;
1665 typedef typename polygon_traits<T>::point_type point_type;
1666 typedef view_of<polygon_45_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
1667 struct iterator_holes_type {
1668 typedef std::forward_iterator_tag iterator_category;
1669 typedef hole_type value_type;
1670 typedef std::ptrdiff_t difference_type;
1671 typedef const hole_type* pointer; //immutable
1672 typedef const hole_type& reference; //immutable
1673 typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
1675 iterator_holes_type() : internal_itr() {}
1676 iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
1677 inline iterator_holes_type& operator++() {
1681 inline const iterator_holes_type operator++(int) {
1682 iterator_holes_type tmp(*this);
1686 inline bool operator==(const iterator_holes_type& that) const {
1687 return (internal_itr == that.internal_itr);
1689 inline bool operator!=(const iterator_holes_type& that) const {
1690 return (internal_itr != that.internal_itr);
1692 inline value_type operator*() const {
1693 return view_as<polygon_45_concept>(*internal_itr);
1697 /// Get the begin iterator
1698 inline iterator_type begin() const {
1699 return polygon_traits<T>::begin_points(*t);
1702 /// Get the end iterator
1703 inline iterator_type end() const {
1704 return polygon_traits<T>::end_points(*t);
1707 /// Get the number of sides of the polygon
1708 inline std::size_t size() const {
1709 return polygon_traits<T>::size(*t);
1712 /// Get the winding direction of the polygon
1713 inline winding_direction winding() const {
1714 return polygon_traits<T>::winding(*t);
1717 /// Get the begin iterator
1718 inline iterator_holes_type begin_holes() const {
1719 return polygon_with_holes_traits<T>::begin_holes(*t);
1722 /// Get the end iterator
1723 inline iterator_holes_type end_holes() const {
1724 return polygon_with_holes_traits<T>::end_holes(*t);
1727 /// Get the number of sides of the polygon
1728 inline std::size_t size_holes() const {
1729 return polygon_with_holes_traits<T>::size_holes(*t);
1734 template <typename T>
1735 struct geometry_concept<view_of<polygon_45_with_holes_concept, T> > {
1736 typedef polygon_45_with_holes_concept type;
1739 template <typename T>
1740 struct view_of<polygon_90_with_holes_concept, T> {
1742 view_of(const T& obj) : t(&obj) {}
1743 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1744 typedef typename polygon_traits<T>::iterator_type iterator_type;
1745 typedef typename polygon_traits<T>::point_type point_type;
1746 typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
1747 typedef view_of<polygon_90_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
1748 struct iterator_holes_type {
1749 typedef std::forward_iterator_tag iterator_category;
1750 typedef hole_type value_type;
1751 typedef std::ptrdiff_t difference_type;
1752 typedef const hole_type* pointer; //immutable
1753 typedef const hole_type& reference; //immutable
1754 typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
1756 iterator_holes_type() : internal_itr() {}
1757 iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
1758 inline iterator_holes_type& operator++() {
1762 inline const iterator_holes_type operator++(int) {
1763 iterator_holes_type tmp(*this);
1767 inline bool operator==(const iterator_holes_type& that) const {
1768 return (internal_itr == that.internal_itr);
1770 inline bool operator!=(const iterator_holes_type& that) const {
1771 return (internal_itr != that.internal_itr);
1773 inline value_type operator*() const {
1774 return view_as<polygon_90_concept>(*internal_itr);
1778 /// Get the begin iterator
1779 inline compact_iterator_type begin_compact() const {
1780 return compact_iterator_type(polygon_traits<T>::begin_points(*t),
1781 polygon_traits<T>::end_points(*t));
1784 /// Get the end iterator
1785 inline compact_iterator_type end_compact() const {
1786 return compact_iterator_type(polygon_traits<T>::end_points(*t),
1787 polygon_traits<T>::end_points(*t));
1790 /// Get the number of sides of the polygon
1791 inline std::size_t size() const {
1792 return polygon_traits<T>::size(*t);
1795 /// Get the winding direction of the polygon
1796 inline winding_direction winding() const {
1797 return polygon_traits<T>::winding(*t);
1800 /// Get the begin iterator
1801 inline iterator_holes_type begin_holes() const {
1802 return polygon_with_holes_traits<T>::begin_holes(*t);
1805 /// Get the end iterator
1806 inline iterator_holes_type end_holes() const {
1807 return polygon_with_holes_traits<T>::end_holes(*t);
1810 /// Get the number of sides of the polygon
1811 inline std::size_t size_holes() const {
1812 return polygon_with_holes_traits<T>::size_holes(*t);
1817 template <typename T>
1818 struct geometry_concept<view_of<polygon_90_with_holes_concept, T> > {
1819 typedef polygon_90_with_holes_concept type;
1822 template <typename T>
1823 struct view_of<polygon_concept, T> {
1825 view_of(const T& obj) : t(&obj) {}
1826 typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1827 typedef typename polygon_traits<T>::iterator_type iterator_type;
1828 typedef typename polygon_traits<T>::point_type point_type;
1830 /// Get the begin iterator
1831 inline iterator_type begin() const {
1832 return polygon_traits<T>::begin_points(*t);
1835 /// Get the end iterator
1836 inline iterator_type end() const {
1837 return polygon_traits<T>::end_points(*t);
1840 /// Get the number of sides of the polygon
1841 inline std::size_t size() const {
1842 return polygon_traits<T>::size(*t);
1845 /// Get the winding direction of the polygon
1846 inline winding_direction winding() const {
1847 return polygon_traits<T>::winding(*t);
1851 template <typename T>
1852 struct geometry_concept<view_of<polygon_concept, T> > {
1853 typedef polygon_concept type;