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