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