Chris@16: /*
Chris@16:   Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:   Use, modification and distribution are subject to the Boost Software License,
Chris@16:   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:   http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: #ifndef BOOST_POLYGON_POLYGON_TRAITS_HPP
Chris@16: #define BOOST_POLYGON_POLYGON_TRAITS_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16:   template <typename T, typename enable = gtl_yes>
Chris@16:   struct polygon_90_traits {
Chris@16:     typedef typename T::coordinate_type coordinate_type;
Chris@16:     typedef typename T::compact_iterator_type compact_iterator_type;
Chris@16: 
Chris@16:     // Get the begin iterator
Chris@16:     static inline compact_iterator_type begin_compact(const T& t) {
Chris@16:       return t.begin_compact();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the end iterator
Chris@16:     static inline compact_iterator_type end_compact(const T& t) {
Chris@16:       return t.end_compact();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the number of sides of the polygon
Chris@16:     static inline std::size_t size(const T& t) {
Chris@16:       return t.size();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the winding direction of the polygon
Chris@16:     static inline winding_direction winding(const T&) {
Chris@16:       return unknown_winding;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_traits_general {
Chris@16:     typedef typename T::coordinate_type coordinate_type;
Chris@16:     typedef typename T::iterator_type iterator_type;
Chris@16:     typedef typename T::point_type point_type;
Chris@16: 
Chris@16:     // Get the begin iterator
Chris@16:     static inline iterator_type begin_points(const T& t) {
Chris@16:       return t.begin();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the end iterator
Chris@16:     static inline iterator_type end_points(const T& t) {
Chris@16:       return t.end();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the number of sides of the polygon
Chris@16:     static inline std::size_t size(const T& t) {
Chris@16:       return t.size();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the winding direction of the polygon
Chris@16:     static inline winding_direction winding(const T&) {
Chris@16:       return unknown_winding;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_traits_90 {
Chris@16:     typedef typename polygon_90_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef iterator_compact_to_points<typename polygon_90_traits<T>::compact_iterator_type, point_data<coordinate_type> > iterator_type;
Chris@16:     typedef point_data<coordinate_type> point_type;
Chris@16: 
Chris@16:     // Get the begin iterator
Chris@16:     static inline iterator_type begin_points(const T& t) {
Chris@16:       return iterator_type(polygon_90_traits<T>::begin_compact(t),
Chris@16:                            polygon_90_traits<T>::end_compact(t));
Chris@16:     }
Chris@16: 
Chris@16:     // Get the end iterator
Chris@16:     static inline iterator_type end_points(const T& t) {
Chris@16:       return iterator_type(polygon_90_traits<T>::end_compact(t),
Chris@16:                            polygon_90_traits<T>::end_compact(t));
Chris@16:     }
Chris@16: 
Chris@16:     // Get the number of sides of the polygon
Chris@16:     static inline std::size_t size(const T& t) {
Chris@16:       return polygon_90_traits<T>::size(t);
Chris@16:     }
Chris@16: 
Chris@16:     // Get the winding direction of the polygon
Chris@16:     static inline winding_direction winding(const T& t) {
Chris@16:       return polygon_90_traits<T>::winding(t);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: #ifndef BOOST_VERY_LITTLE_SFINAE
Chris@16: 
Chris@16:   template <typename T, typename enable = gtl_yes>
Chris@16:   struct polygon_traits {};
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_traits<T,
Chris@16:                         typename gtl_or_4<
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type
Chris@16:   >::type> : public polygon_traits_general<T> {};
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_traits< T,
Chris@16:                          typename gtl_or<
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type
Chris@16:   >::type > : public polygon_traits_90<T> {};
Chris@16: 
Chris@16: #else
Chris@16: 
Chris@16:   template <typename T, typename T_IF, typename T_ELSE>
Chris@16:   struct gtl_ifelse {};
Chris@16:   template <typename T_IF, typename T_ELSE>
Chris@16:   struct gtl_ifelse<gtl_no, T_IF, T_ELSE> {
Chris@16:     typedef T_ELSE type;
Chris@16:   };
Chris@16:   template <typename T_IF, typename T_ELSE>
Chris@16:   struct gtl_ifelse<gtl_yes, T_IF, T_ELSE> {
Chris@16:     typedef T_IF type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T, typename enable = gtl_yes>
Chris@16:   struct polygon_traits {};
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_traits<T, typename gtl_or<typename gtl_or_4<
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type
Chris@16:   >::type, typename gtl_or<
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type
Chris@16:   >::type>::type > : public gtl_ifelse<typename gtl_or<
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
Chris@16:     typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type >::type,
Chris@16:       polygon_traits_90<T>,
Chris@16:       polygon_traits_general<T> >::type {
Chris@16:   };
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16:   template <typename T, typename enable = void>
Chris@16:   struct polygon_with_holes_traits {
Chris@16:     typedef typename T::iterator_holes_type iterator_holes_type;
Chris@16:     typedef typename T::hole_type hole_type;
Chris@16: 
Chris@16:     // Get the begin iterator
Chris@16:     static inline iterator_holes_type begin_holes(const T& t) {
Chris@16:       return t.begin_holes();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the end iterator
Chris@16:     static inline iterator_holes_type end_holes(const T& t) {
Chris@16:       return t.end_holes();
Chris@16:     }
Chris@16: 
Chris@16:     // Get the number of holes
Chris@16:     static inline std::size_t size_holes(const T& t) {
Chris@16:       return t.size_holes();
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T, typename enable = void>
Chris@16:   struct polygon_90_mutable_traits {
Chris@16: 
Chris@16:     // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
Chris@16:     template <typename iT>
Chris@16:     static inline T& set_compact(T& t, iT input_begin, iT input_end) {
Chris@16:       t.set_compact(input_begin, input_end);
Chris@16:       return t;
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_90_mutable_traits<T, typename gtl_same_type<polygon_concept, typename geometry_concept<T>::type>::type> {
Chris@16:     // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
Chris@16:     template <typename iT>
Chris@16:     static inline T& set_compact(T& t, iT input_begin, iT input_end) {
Chris@16:       typedef iterator_points_to_compact<iT, typename polygon_traits<T>::point_type> iTp;
Chris@16:       t.set_points(iTp(polygon_traits<T>::begin_points(t)), iTp(polygon_traits<T>::end_points(t)));
Chris@16:       return t;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T, typename enable = void>
Chris@16:   struct polygon_mutable_traits {
Chris@16: 
Chris@16:     // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
Chris@16:     template <typename iT>
Chris@16:     static inline T& set_points(T& t, iT input_begin, iT input_end) {
Chris@16:       t.set(input_begin, input_end);
Chris@16:       return t;
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T, typename enable = void>
Chris@16:   struct polygon_with_holes_mutable_traits {
Chris@16: 
Chris@16:     // Set the data of a polygon with the unique coordinates in an iterator, starting with an x
Chris@16:     template <typename iT>
Chris@16:     static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) {
Chris@16:       t.set_holes(inputBegin, inputEnd);
Chris@16:       return t;
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: #include "isotropy.hpp"
Chris@16: 
Chris@16: //point
Chris@16: #include "point_data.hpp"
Chris@16: #include "point_traits.hpp"
Chris@16: #include "point_concept.hpp"
Chris@16: 
Chris@16: //interval
Chris@16: #include "interval_data.hpp"
Chris@16: #include "interval_traits.hpp"
Chris@16: #include "interval_concept.hpp"
Chris@16: 
Chris@16: //rectangle
Chris@16: #include "rectangle_data.hpp"
Chris@16: #include "rectangle_traits.hpp"
Chris@16: #include "rectangle_concept.hpp"
Chris@16: 
Chris@16: //algorithms needed by polygon types
Chris@16: #include "detail/iterator_points_to_compact.hpp"
Chris@16: #include "detail/iterator_compact_to_points.hpp"
Chris@16: 
Chris@16: //polygons
Chris@16: #include "polygon_45_data.hpp"
Chris@16: #include "polygon_data.hpp"
Chris@16: #include "polygon_90_data.hpp"
Chris@16: #include "polygon_90_with_holes_data.hpp"
Chris@16: #include "polygon_45_with_holes_data.hpp"
Chris@16: #include "polygon_with_holes_data.hpp"
Chris@16: 
Chris@16: namespace boost { namespace polygon{
Chris@16:   struct polygon_concept {};
Chris@16:   struct polygon_with_holes_concept {};
Chris@16:   struct polygon_45_concept {};
Chris@16:   struct polygon_45_with_holes_concept {};
Chris@16:   struct polygon_90_concept {};
Chris@16:   struct polygon_90_with_holes_concept {};
Chris@16: 
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_90_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_90_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_45_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_or<typename is_polygon_90_type<T>::type,
Chris@16:                             typename gtl_same_type<polygon_45_concept, GC>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_or<typename is_polygon_45_type<T>::type,
Chris@16:                             typename gtl_same_type<polygon_concept, GC>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_90_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_or<typename is_polygon_90_type<T>::type,
Chris@16:                             typename gtl_same_type<polygon_90_with_holes_concept, GC>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_45_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_or_3<typename is_polygon_90_with_holes_type<T>::type,
Chris@16:                               typename is_polygon_45_type<T>::type,
Chris@16:                               typename gtl_same_type<polygon_45_with_holes_concept, GC>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_polygon_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_or_3<typename is_polygon_45_with_holes_type<T>::type,
Chris@16:                               typename is_polygon_type<T>::type,
Chris@16:                               typename gtl_same_type<polygon_with_holes_concept, GC>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_90_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_90_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_45_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_45_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_90_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_90_with_holes_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_45_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_45_with_holes_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_mutable_polygon_with_holes_type {
Chris@16:     typedef typename geometry_concept<T>::type GC;
Chris@16:     typedef typename gtl_same_type<polygon_with_holes_concept, GC>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_any_mutable_polygon_with_holes_type {
Chris@16:     typedef typename gtl_or_3<typename is_mutable_polygon_90_with_holes_type<T>::type,
Chris@16:                               typename is_mutable_polygon_45_with_holes_type<T>::type,
Chris@16:                               typename is_mutable_polygon_with_holes_type<T>::type>::type type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct is_any_mutable_polygon_without_holes_type {
Chris@16:     typedef typename gtl_or_3<
Chris@16:       typename is_mutable_polygon_90_type<T>::type,
Chris@16:       typename is_mutable_polygon_45_type<T>::type,
Chris@16:       typename is_mutable_polygon_type<T>::type>::type type; };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct is_any_mutable_polygon_type {
Chris@16:     typedef typename gtl_or<typename is_any_mutable_polygon_with_holes_type<T>::type,
Chris@16:                             typename is_any_mutable_polygon_without_holes_type<T>::type>::type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct polygon_from_polygon_with_holes_type {};
Chris@16:   template <>
Chris@16:   struct polygon_from_polygon_with_holes_type<polygon_with_holes_concept> { typedef polygon_concept type; };
Chris@16:   template <>
Chris@16:   struct polygon_from_polygon_with_holes_type<polygon_45_with_holes_concept> { typedef polygon_45_concept type; };
Chris@16:   template <>
Chris@16:   struct polygon_from_polygon_with_holes_type<polygon_90_with_holes_concept> { typedef polygon_90_concept type; };
Chris@16: 
Chris@16:   template <>
Chris@16:   struct geometry_domain<polygon_45_concept> { typedef forty_five_domain type; };
Chris@16:   template <>
Chris@16:   struct geometry_domain<polygon_45_with_holes_concept> { typedef forty_five_domain type; };
Chris@16:   template <>
Chris@16:   struct geometry_domain<polygon_90_concept> { typedef manhattan_domain type; };
Chris@16:   template <>
Chris@16:   struct geometry_domain<polygon_90_with_holes_concept> { typedef manhattan_domain type; };
Chris@16: 
Chris@16:   template <typename domain_type, typename coordinate_type>
Chris@16:   struct distance_type_by_domain { typedef typename coordinate_traits<coordinate_type>::coordinate_distance type; };
Chris@16:   template <typename coordinate_type>
Chris@16:   struct distance_type_by_domain<manhattan_domain, coordinate_type> {
Chris@16:     typedef typename coordinate_traits<coordinate_type>::coordinate_difference type; };
Chris@16: 
Chris@16:   // \brief Sets the boundary of the polygon to the points in the iterator range
Chris@16:   // \tparam T A type that models polygon_concept
Chris@16:   // \tparam iT Iterator type over objects that model point_concept
Chris@16:   // \param t The polygon to set
Chris@16:   // \param begin_points The start of the range of points
Chris@16:   // \param end_points The end of the range of points
Chris@16: 
Chris@16:   /// \relatesalso polygon_concept
Chris@16:   template <typename T, typename iT>
Chris@16:   typename enable_if <typename is_any_mutable_polygon_type<T>::type, T>::type &
Chris@16:   set_points(T& t, iT begin_points, iT end_points) {
Chris@16:     polygon_mutable_traits<T>::set_points(t, begin_points, end_points);
Chris@16:     return t;
Chris@16:   }
Chris@16: 
Chris@16:   // \brief Sets the boundary of the polygon to the non-redundant coordinates in the iterator range
Chris@16:   // \tparam T A type that models polygon_90_concept
Chris@16:   // \tparam iT Iterator type over objects that model coordinate_concept
Chris@16:   // \param t The polygon to set
Chris@16:   // \param begin_compact_coordinates The start of the range of coordinates
Chris@16:   // \param end_compact_coordinates The end of the range of coordinates
Chris@16: 
Chris@16: /// \relatesalso polygon_90_concept
Chris@16:   template <typename T, typename iT>
Chris@16:   typename enable_if <typename gtl_or<
Chris@16:     typename is_mutable_polygon_90_type<T>::type,
Chris@16:     typename is_mutable_polygon_90_with_holes_type<T>::type>::type, T>::type &
Chris@16:   set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) {
Chris@16:     polygon_90_mutable_traits<T>::set_compact(t, begin_compact_coordinates, end_compact_coordinates);
Chris@16:     return t;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T, typename iT>
Chris@16:   typename enable_if< typename gtl_and <
Chris@16:     typename is_any_mutable_polygon_with_holes_type<T>::type,
Chris@16:     typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:                                 manhattan_domain>::type>::type,
Chris@16:                        T>::type &
Chris@16:   set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) {
Chris@16:     iterator_compact_to_points<iT, point_data<typename polygon_traits<T>::coordinate_type> >
Chris@16:       itrb(begin_compact_coordinates, end_compact_coordinates),
Chris@16:       itre(end_compact_coordinates, end_compact_coordinates);
Chris@16:     return set_points(t, itrb, itre);
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T, typename iT>
Chris@16:   typename enable_if <typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
Chris@16:   set_holes(T& t, iT begin_holes, iT end_holes) {
Chris@16:     polygon_with_holes_mutable_traits<T>::set_holes(t, begin_holes, end_holes);
Chris@16:     return t;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_90_concept
Chris@16:   template <typename T>
Chris@16:   typename polygon_90_traits<T>::compact_iterator_type
Chris@16:   begin_compact(const T& polygon,
Chris@16:     typename enable_if<
Chris@16:       typename gtl_and <typename is_polygon_with_holes_type<T>::type,
Chris@16:                         typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:                 manhattan_domain>::type>::type>::type * = 0
Chris@16:   ) {
Chris@16:     return polygon_90_traits<T>::begin_compact(polygon);
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_90_concept
Chris@16:   template <typename T>
Chris@16:   typename polygon_90_traits<T>::compact_iterator_type
Chris@16:   end_compact(const T& polygon,
Chris@16:     typename enable_if<
Chris@16:     typename gtl_and <typename is_polygon_with_holes_type<T>::type,
Chris@16:                       typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:               manhattan_domain>::type>::type>::type * = 0
Chris@16:   ) {
Chris@16:     return polygon_90_traits<T>::end_compact(polygon);
Chris@16:   }
Chris@16: 
Chris@16:   /// \relatesalso polygon_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if < typename gtl_if<
Chris@16:     typename is_polygon_with_holes_type<T>::type>::type,
Chris@16:                         typename polygon_traits<T>::iterator_type>::type
Chris@16:   begin_points(const T& polygon) {
Chris@16:     return polygon_traits<T>::begin_points(polygon);
Chris@16:   }
Chris@16: 
Chris@16:   /// \relatesalso polygon_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if < typename gtl_if<
Chris@16:     typename is_polygon_with_holes_type<T>::type>::type,
Chris@16:                         typename polygon_traits<T>::iterator_type>::type
Chris@16:   end_points(const T& polygon) {
Chris@16:     return polygon_traits<T>::end_points(polygon);
Chris@16:   }
Chris@16: 
Chris@16:   /// \relatesalso polygon_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if <typename is_polygon_with_holes_type<T>::type,
Chris@16:                        std::size_t>::type
Chris@16:   size(const T& polygon) {
Chris@16:     return polygon_traits<T>::size(polygon);
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if < typename gtl_if<
Chris@16:     typename is_polygon_with_holes_type<T>::type>::type,
Chris@16:                         typename polygon_with_holes_traits<T>::iterator_holes_type>::type
Chris@16:   begin_holes(const T& polygon) {
Chris@16:     return polygon_with_holes_traits<T>::begin_holes(polygon);
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if < typename gtl_if<
Chris@16:     typename is_polygon_with_holes_type<T>::type>::type,
Chris@16:                         typename polygon_with_holes_traits<T>::iterator_holes_type>::type
Chris@16:   end_holes(const T& polygon) {
Chris@16:     return polygon_with_holes_traits<T>::end_holes(polygon);
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if <typename is_polygon_with_holes_type<T>::type,
Chris@16:                        std::size_t>::type
Chris@16:   size_holes(const T& polygon) {
Chris@16:     return polygon_with_holes_traits<T>::size_holes(polygon);
Chris@16:   }
Chris@16: 
Chris@16:   // \relatesalso polygon_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_polygon_type<T1>::type,
Chris@16:                       typename is_polygon_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
Chris@16:                                            polygon_traits<T2>::end_points(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16: // \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_polygon_with_holes_type<T1>::type,
Chris@16:                       typename is_polygon_with_holes_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
Chris@16:                                            polygon_traits<T2>::end_points(rvalue));
Chris@16:     polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
Chris@16:                                                      polygon_with_holes_traits<T2>::end_holes(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16:   // \relatesalso polygon_45_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if< typename gtl_and< typename is_mutable_polygon_45_type<T1>::type, typename is_polygon_45_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
Chris@16:                                            polygon_traits<T2>::end_points(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16: // \relatesalso polygon_45_with_holes_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_polygon_45_with_holes_type<T1>::type,
Chris@16:                       typename is_polygon_45_with_holes_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
Chris@16:                                            polygon_traits<T2>::end_points(rvalue));
Chris@16:     polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
Chris@16:                                                      polygon_with_holes_traits<T2>::end_holes(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16:   // \relatesalso polygon_90_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_polygon_90_type<T1>::type,
Chris@16:                       typename is_polygon_90_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue),
Chris@16:                                                polygon_90_traits<T2>::end_compact(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16: // \relatesalso polygon_90_with_holes_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_polygon_90_with_holes_type<T1>::type,
Chris@16:                       typename is_polygon_90_with_holes_type<T2>::type>::type, T1>::type &
Chris@16:   assign(T1& lvalue, const T2& rvalue) {
Chris@16:     polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue),
Chris@16:                                                polygon_90_traits<T2>::end_compact(rvalue));
Chris@16:     polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
Chris@16:                                                      polygon_with_holes_traits<T2>::end_holes(rvalue));
Chris@16:     return lvalue;
Chris@16:   }
Chris@16: 
Chris@16:   // \relatesalso polygon_90_concept
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_type<T1>::type,
Chris@16:                       typename is_rectangle_concept<typename geometry_concept<T2>::type>::type>::type, T1>::type &
Chris@16:   assign(T1& polygon, const T2& rect) {
Chris@16:     typedef point_data<typename polygon_traits<T1>::coordinate_type> PT;
Chris@16:     PT points[4] = {PT(xl(rect), yl(rect)), PT(xh(rect), yl(rect)), PT(xh(rect), yh(rect)), PT(xl(rect), yh(rect))};
Chris@16:     set_points(polygon, points, points+4);
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_90_concept
Chris@16:   template <typename polygon_type, typename point_type>
Chris@16:   typename enable_if< typename gtl_and< typename is_mutable_polygon_90_type<polygon_type>::type,
Chris@16:                                          typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
Chris@16:                        polygon_type>::type &
Chris@16:   convolve(polygon_type& polygon, const point_type& point) {
Chris@16:     std::vector<typename polygon_90_traits<polygon_type>::coordinate_type> coords;
Chris@16:     coords.reserve(size(polygon));
Chris@16:     bool pingpong = true;
Chris@16:     for(typename polygon_90_traits<polygon_type>::compact_iterator_type iter = begin_compact(polygon);
Chris@16:         iter != end_compact(polygon); ++iter) {
Chris@16:       coords.push_back((*iter) + (pingpong ? x(point) : y(point)));
Chris@16:       pingpong = !pingpong;
Chris@16:     }
Chris@16:     polygon_90_mutable_traits<polygon_type>::set_compact(polygon, coords.begin(), coords.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_concept
Chris@16:   template <typename polygon_type, typename point_type>
Chris@16:   typename enable_if< typename gtl_and< typename gtl_or<
Chris@16:     typename is_mutable_polygon_45_type<polygon_type>::type,
Chris@16:     typename is_mutable_polygon_type<polygon_type>::type>::type,
Chris@16:                                          typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
Chris@16:                        polygon_type>::type &
Chris@16:   convolve(polygon_type& polygon, const point_type& point) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       convolve(points.back(), point);
Chris@16:     }
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename polygon_type, typename point_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type,
Chris@16:                       typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
Chris@16:     polygon_type>::type &
Chris@16:   convolve(polygon_type& polygon, const point_type& point) {
Chris@16:     typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     convolve(h, point);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       convolve(holes.back(), point);
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_concept
Chris@16:   template <typename T>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_type<T>::type, T>::type &
Chris@16:   move(T& polygon, orientation_2d orient, typename polygon_traits<T>::coordinate_type displacement) {
Chris@16:     typedef typename polygon_traits<T>::coordinate_type Unit;
Chris@16:     if(orient == HORIZONTAL) return convolve(polygon, point_data<Unit>(displacement, Unit(0)));
Chris@16:     return convolve(polygon, point_data<Unit>(Unit(0), displacement));
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_concept
Chris@16: /// \brief Applies a transformation to the polygon.
Chris@16: /// \tparam polygon_type A type that models polygon_concept
Chris@16: /// \tparam transform_type A type that may be either axis_transformation or transformation or that overloads point_concept::transform
Chris@16: /// \param polygon The polygon to transform
Chris@16: /// \param tr The transformation to apply
Chris@16:   template <typename polygon_type, typename transform_type>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
Chris@16:   transform(polygon_type& polygon, const transform_type& tr) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       transform(points.back(), tr);
Chris@16:     }
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16: /// \relatesalso polygon_with_holes_concept
Chris@16:   template <typename T, typename transform_type>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
Chris@16:   transform(T& polygon, const transform_type& tr) {
Chris@16:     typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     transform(h, tr);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       transform(holes.back(), tr);
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
Chris@16:   scale_up(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       scale_up(points.back(), factor);
Chris@16:     }
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
Chris@16:   scale_up(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) {
Chris@16:     typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     scale_up(h, factor);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       scale_up(holes.back(), factor);
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   //scale non-45 down
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
Chris@16:                       typename gtl_not<typename gtl_same_type
Chris@16:                                        < forty_five_domain,
Chris@16:                                          typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
Chris@16:     polygon_type>::type &
Chris@16:   scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       scale_down(points.back(), factor);
Chris@16:     }
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   Unit local_abs(Unit value) { return value < 0 ? (Unit)-value : value; }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   void snap_point_vector_to_45(std::vector<point_data<Unit> >& pts) {
Chris@16:     typedef point_data<Unit> Point;
Chris@16:     if(pts.size() < 3) { pts.clear(); return; }
Chris@16:     typename std::vector<point_data<Unit> >::iterator endLocation = std::unique(pts.begin(), pts.end());
Chris@16:     if(endLocation != pts.end()){
Chris@16:       pts.resize(endLocation - pts.begin());
Chris@16:     }
Chris@16:     if(pts.back() == pts[0]) pts.pop_back();
Chris@16:     //iterate over point triplets
Chris@16:     int numPts = pts.size();
Chris@16:     bool wrap_around = false;
Chris@16:     for(int i = 0; i < numPts; ++i) {
Chris@16:       Point& pt1 = pts[i];
Chris@16:       Point& pt2 = pts[(i + 1) % numPts];
Chris@16:       Point& pt3 = pts[(i + 2) % numPts];
Chris@16:       //check if non-45 edge
Chris@16:       Unit deltax = x(pt2) - x(pt1);
Chris@16:       Unit deltay = y(pt2) - y(pt1);
Chris@16:       if(deltax && deltay &&
Chris@16:          local_abs(deltax) != local_abs(deltay)) {
Chris@16:         //adjust the middle point
Chris@16:         Unit ndx = x(pt3) - x(pt2);
Chris@16:         Unit ndy = y(pt3) - y(pt2);
Chris@16:         if(ndx && ndy) {
Chris@16:           Unit diff = local_abs(local_abs(deltax) - local_abs(deltay));
Chris@16:           Unit halfdiff = diff/2;
Chris@16:           if((deltax > 0 && deltay > 0) ||
Chris@16:              (deltax < 0 && deltay < 0)) {
Chris@16:             //previous edge is rising slope
Chris@16:             if(local_abs(deltax + halfdiff + (diff % 2)) ==
Chris@16:                local_abs(deltay - halfdiff)) {
Chris@16:               x(pt2, x(pt2) + halfdiff + (diff % 2));
Chris@16:               y(pt2, y(pt2) - halfdiff);
Chris@16:             } else if(local_abs(deltax - halfdiff - (diff % 2)) ==
Chris@16:                       local_abs(deltay + halfdiff)) {
Chris@16:               x(pt2, x(pt2) - halfdiff - (diff % 2));
Chris@16:               y(pt2, y(pt2) + halfdiff);
Chris@16:             } else{
Chris@16:               //std::cout << "fail1\n";
Chris@16:             }
Chris@16:           } else {
Chris@16:             //previous edge is falling slope
Chris@16:             if(local_abs(deltax + halfdiff + (diff % 2)) ==
Chris@16:                local_abs(deltay + halfdiff)) {
Chris@16:               x(pt2, x(pt2) + halfdiff + (diff % 2));
Chris@16:               y(pt2, y(pt2) + halfdiff);
Chris@16:             } else if(local_abs(deltax - halfdiff - (diff % 2)) ==
Chris@16:                       local_abs(deltay - halfdiff)) {
Chris@16:               x(pt2, x(pt2) - halfdiff - (diff % 2));
Chris@16:               y(pt2, y(pt2) - halfdiff);
Chris@16:             } else {
Chris@16:               //std::cout << "fail2\n";
Chris@16:             }
Chris@16:           }
Chris@16:           if(i == numPts - 1 && (diff % 2)) {
Chris@16:             //we have a wrap around effect
Chris@16:             if(!wrap_around) {
Chris@16:               wrap_around = true;
Chris@16:               i = -1;
Chris@16:             }
Chris@16:           }
Chris@16:         } else if(ndx) {
Chris@16:           //next edge is horizontal
Chris@16:           //find the x value for pt1 that would make the abs(deltax) == abs(deltay)
Chris@16:           Unit newDeltaX = local_abs(deltay);
Chris@16:           if(deltax < 0) newDeltaX *= -1;
Chris@16:           x(pt2, x(pt1) + newDeltaX);
Chris@16:         } else { //ndy
Chris@16:           //next edge is vertical
Chris@16:           //find the y value for pt1 that would make the abs(deltax) == abs(deltay)
Chris@16:           Unit newDeltaY = local_abs(deltax);
Chris@16:           if(deltay < 0) newDeltaY *= -1;
Chris@16:           y(pt2, y(pt1) + newDeltaY);
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
Chris@16:   snap_to_45(polygon_type& polygon) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:     }
Chris@16:     snap_point_vector_to_45(points);
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type, polygon_type>::type &
Chris@16:   snap_to_45(polygon_type& polygon) {
Chris@16:     typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     snap_to_45(h);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       snap_to_45(holes.back());
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   //scale specifically 45 down
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
Chris@16:                       typename gtl_same_type
Chris@16:                       < forty_five_domain,
Chris@16:                         typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type,
Chris@16:     polygon_type>::type &
Chris@16:   scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       scale_down(points.back(), factor);
Chris@16:     }
Chris@16:     snap_point_vector_to_45(points);
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
Chris@16:   scale_down(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) {
Chris@16:     typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     scale_down(h, factor);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       scale_down(holes.back(), factor);
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   //scale non-45
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
Chris@16:                       typename gtl_not<typename gtl_same_type
Chris@16:                                        < forty_five_domain,
Chris@16:                                          typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
Chris@16:     polygon_type>::type &
Chris@16:   scale(polygon_type& polygon, double factor) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       scale(points.back(), anisotropic_scale_factor<double>(factor, factor));
Chris@16:     }
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   //scale specifically 45
Chris@16:   template <typename polygon_type>
Chris@16:   polygon_type&
Chris@16:   scale(polygon_type& polygon, double factor,
Chris@16:     typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
Chris@16:                       typename gtl_same_type
Chris@16:                       < forty_five_domain,
Chris@16:         typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type * = 0
Chris@16:   ) {
Chris@16:     std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
Chris@16:     points.reserve(size(polygon));
Chris@16:     for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
Chris@16:         iter != end_points(polygon); ++iter) {
Chris@16:       points.push_back(*iter);
Chris@16:       scale(points.back(), anisotropic_scale_factor<double>(factor, factor));
Chris@16:     }
Chris@16:     snap_point_vector_to_45(points);
Chris@16:     polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   T&
Chris@16:   scale(T& polygon, double factor,
Chris@16:   typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type>::type * = 0
Chris@16:   ) {
Chris@16:     typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
Chris@16:     hole_type h;
Chris@16:     set_points(h, begin_points(polygon), end_points(polygon));
Chris@16:     scale(h, factor);
Chris@16:     std::vector<hole_type> holes;
Chris@16:     holes.reserve(size_holes(polygon));
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
Chris@16:         itr != end_holes(polygon); ++itr) {
Chris@16:       holes.push_back(*itr);
Chris@16:       scale(holes.back(), factor);
Chris@16:     }
Chris@16:     assign(polygon, h);
Chris@16:     set_holes(polygon, holes.begin(), holes.end());
Chris@16:     return polygon;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename iterator_type, typename area_type>
Chris@16:   static area_type
Chris@16:   point_sequence_area(iterator_type begin_range, iterator_type end_range) {
Chris@16:     typedef typename std::iterator_traits<iterator_type>::value_type point_type;
Chris@16:     if(begin_range == end_range) return area_type(0);
Chris@16:     point_type first = *begin_range;
Chris@16:     point_type previous = first;
Chris@16:     ++begin_range;
Chris@16:     // Initialize trapezoid base line
Chris@16:     area_type y_base = (area_type)y(first);
Chris@16:     // Initialize area accumulator
Chris@16: 
Chris@16:     area_type area(0);
Chris@16:     while (begin_range != end_range) {
Chris@16:       area_type x1 = (area_type)x(previous);
Chris@16:       area_type x2 = (area_type)x(*begin_range);
Chris@16: #ifdef BOOST_POLYGON_ICC
Chris@16: #pragma warning (push)
Chris@16: #pragma warning (disable:1572)
Chris@16: #endif
Chris@16:       if(x1 != x2) {
Chris@16: #ifdef BOOST_POLYGON_ICC
Chris@16: #pragma warning (pop)
Chris@16: #endif
Chris@16:         // do trapezoid area accumulation
Chris@16:         area += (x2 - x1) * (((area_type)y(*begin_range) - y_base) +
Chris@16:                              ((area_type)y(previous) - y_base)) / 2;
Chris@16:       }
Chris@16:       previous = *begin_range;
Chris@16:       // go to next point
Chris@16:       ++begin_range;
Chris@16:     }
Chris@16:     //wrap around to evaluate the edge between first and last if not closed
Chris@16:     if(!equivalence(first, previous)) {
Chris@16:       area_type x1 = (area_type)x(previous);
Chris@16:       area_type x2 = (area_type)x(first);
Chris@16:       area += (x2 - x1) * (((area_type)y(first) - y_base) +
Chris@16:                            ((area_type)y(previous) - y_base)) / 2;
Chris@16:     }
Chris@16:     return area;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   typename enable_if<
Chris@16:     typename is_polygon_with_holes_type<T>::type,
Chris@16:                         typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:                                                       typename polygon_traits<T>::coordinate_type>::type>::type
Chris@16:   area(const T& polygon) {
Chris@16:     typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:       typename polygon_traits<T>::coordinate_type>::type area_type;
Chris@16:     area_type retval = point_sequence_area<typename polygon_traits<T>::iterator_type, area_type>
Chris@16:       (begin_points(polygon), end_points(polygon));
Chris@16:     if(retval < 0) retval *= -1;
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr =
Chris@16:           polygon_with_holes_traits<T>::begin_holes(polygon);
Chris@16:         itr != polygon_with_holes_traits<T>::end_holes(polygon); ++itr) {
Chris@16:       area_type tmp_area = point_sequence_area
Chris@16:         <typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type, area_type>
Chris@16:         (begin_points(*itr), end_points(*itr));
Chris@16:       if(tmp_area < 0) tmp_area *= -1;
Chris@16:       retval -= tmp_area;
Chris@16:     }
Chris@16:     return retval;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename iT>
Chris@16:   bool point_sequence_is_45(iT itr, iT itr_end) {
Chris@16:     typedef typename std::iterator_traits<iT>::value_type Point;
Chris@16:     typedef typename point_traits<Point>::coordinate_type Unit;
Chris@16:     if(itr == itr_end) return true;
Chris@16:     Point firstPt = *itr;
Chris@16:     Point prevPt = firstPt;
Chris@16:     ++itr;
Chris@16:     while(itr != itr_end) {
Chris@16:       Point pt = *itr;
Chris@16:       Unit deltax = x(pt) - x(prevPt);
Chris@16:       Unit deltay = y(pt) - y(prevPt);
Chris@16:       if(deltax && deltay &&
Chris@16:          local_abs(deltax) != local_abs(deltay))
Chris@16:         return false;
Chris@16:       prevPt = pt;
Chris@16:       ++itr;
Chris@16:     }
Chris@16:     Unit deltax = x(firstPt) - x(prevPt);
Chris@16:     Unit deltay = y(firstPt) - y(prevPt);
Chris@16:     if(deltax && deltay &&
Chris@16:        local_abs(deltax) != local_abs(deltay))
Chris@16:       return false;
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename polygon_type>
Chris@16:   typename enable_if< typename is_polygon_with_holes_type<polygon_type>::type, bool>::type
Chris@16:   is_45(const polygon_type& polygon) {
Chris@16:     typename polygon_traits<polygon_type>::iterator_type itr = begin_points(polygon), itr_end = end_points(polygon);
Chris@16:     if(!point_sequence_is_45(itr, itr_end)) return false;
Chris@16:     typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itrh = begin_holes(polygon), itrh_end = end_holes(polygon);
Chris@16:     typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
Chris@16:     for(; itrh != itrh_end; ++ itrh) {
Chris@16:       typename polygon_traits<hole_type>::iterator_type itr1 = begin_points(polygon), itr1_end = end_points(polygon);
Chris@16:       if(!point_sequence_is_45(itr1, itr1_end)) return false;
Chris@16:     }
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename distance_type, typename iterator_type>
Chris@16:   distance_type point_sequence_distance(iterator_type itr, iterator_type itr_end) {
Chris@16:     typedef distance_type Unit;
Chris@16:     typedef iterator_type iterator;
Chris@16:     typedef typename std::iterator_traits<iterator>::value_type point_type;
Chris@16:     Unit return_value = Unit(0);
Chris@16:     point_type previous_point, first_point;
Chris@16:     if(itr == itr_end) return return_value;
Chris@16:     previous_point = first_point = *itr;
Chris@16:     ++itr;
Chris@16:     for( ; itr != itr_end; ++itr) {
Chris@16:       point_type current_point = *itr;
Chris@16:       return_value += (Unit)euclidean_distance(current_point, previous_point);
Chris@16:       previous_point = current_point;
Chris@16:     }
Chris@16:     return_value += (Unit)euclidean_distance(previous_point, first_point);
Chris@16:     return return_value;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   typename distance_type_by_domain
Chris@16:   <typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type
Chris@16:   perimeter(const T& polygon,
Chris@16:   typename enable_if<
Chris@16:       typename is_polygon_with_holes_type<T>::type>::type * = 0
Chris@16:   ) {
Chris@16:     typedef typename distance_type_by_domain
Chris@16:       <typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type Unit;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator;
Chris@16:     iterator itr = begin_points(polygon);
Chris@16:     iterator itr_end = end_points(polygon);
Chris@16:     Unit return_value = point_sequence_distance<Unit, iterator>(itr, itr_end);
Chris@16:     for(typename polygon_with_holes_traits<T>::iterator_holes_type itr_holes = begin_holes(polygon);
Chris@16:         itr_holes != end_holes(polygon); ++itr_holes) {
Chris@16:       typedef typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type hitertype;
Chris@16:       return_value += point_sequence_distance<Unit, hitertype>(begin_points(*itr_holes), end_points(*itr_holes));
Chris@16:     }
Chris@16:     return return_value;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   typename enable_if <typename is_polygon_with_holes_type<T>::type,
Chris@16:                        direction_1d>::type
Chris@16:   winding(const T& polygon) {
Chris@16:     winding_direction wd = polygon_traits<T>::winding(polygon);
Chris@16:     if(wd != unknown_winding) {
Chris@16:       return wd == clockwise_winding ? CLOCKWISE: COUNTERCLOCKWISE;
Chris@16:     }
Chris@16:     typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
Chris@16:       typename polygon_traits<T>::coordinate_type>::type area_type;
Chris@16:     return point_sequence_area<typename polygon_traits<T>::iterator_type, area_type>(begin_points(polygon), end_points(polygon)) < 0 ?
Chris@16:       COUNTERCLOCKWISE : CLOCKWISE;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T, typename input_point_type>
Chris@16:   typename enable_if<
Chris@101:     typename gtl_and<
Chris@101:       typename is_polygon_90_type<T>::type,
Chris@101:       typename gtl_same_type<
Chris@101:         typename geometry_concept<input_point_type>::type,
Chris@101:         point_concept
Chris@101:       >::type
Chris@101:     >::type,
Chris@101:     bool
Chris@101:   >::type contains(
Chris@101:       const T& polygon,
Chris@101:       const input_point_type& point,
Chris@101:       bool consider_touch = true) {
Chris@16:     typedef T polygon_type;
Chris@16:     typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<polygon_type>::iterator_type iterator;
Chris@16:     typedef typename std::iterator_traits<iterator>::value_type point_type;
Chris@16:     coordinate_type point_x = x(point);
Chris@16:     coordinate_type point_y = y(point);
Chris@101:     // Check how many intersections has the ray extended from the given
Chris@101:     // point in the x-axis negative direction with the polygon edges.
Chris@101:     // If the number is odd the point is within the polygon, otherwise not.
Chris@101:     // We can safely ignore horizontal edges, however intersections with
Chris@101:     // end points of the vertical edges require special handling. We should
Chris@101:     // add one intersection in case horizontal edges that extend vertical edge
Chris@101:     // point in the same direction.
Chris@101:     int num_full_intersections = 0;
Chris@101:     int num_half_intersections = 0;
Chris@16:     for (iterator iter = begin_points(polygon); iter != end_points(polygon);) {
Chris@16:       point_type curr_point = *iter;
Chris@16:       ++iter;
Chris@16:       point_type next_point = (iter == end_points(polygon)) ? *begin_points(polygon) : *iter;
Chris@16:       if (x(curr_point) == x(next_point)) {
Chris@16:         if (x(curr_point) > point_x) {
Chris@16:           continue;
Chris@16:         }
Chris@16:         coordinate_type min_y = (std::min)(y(curr_point), y(next_point));
Chris@16:         coordinate_type max_y = (std::max)(y(curr_point), y(next_point));
Chris@16:         if (point_y > min_y && point_y < max_y) {
Chris@16:           if (x(curr_point) == point_x) {
Chris@16:             return consider_touch;
Chris@16:           }
Chris@101:           ++num_full_intersections;
Chris@101:         }
Chris@101:         if (point_y == min_y || point_y == max_y) {
Chris@101:           num_half_intersections += (y(curr_point) < y(next_point) ? 1 : -1);
Chris@16:         }
Chris@16:       } else {
Chris@16:         coordinate_type min_x = (std::min)(x(curr_point), x(next_point));
Chris@16:         coordinate_type max_x = (std::max)(x(curr_point), x(next_point));
Chris@16:         if (point_x >= min_x && point_x <= max_x) {
Chris@16:           if (y(curr_point) == point_y) {
Chris@16:             return consider_touch;
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@101:     int total_intersections = num_full_intersections + (num_half_intersections >> 1);
Chris@101:     return total_intersections & 1;
Chris@16:   }
Chris@16: 
Chris@16:   //TODO: refactor to expose as user APIs
Chris@16:   template <typename Unit>
Chris@16:   struct edge_utils {
Chris@16:     typedef point_data<Unit> Point;
Chris@16:     typedef std::pair<Point, Point> half_edge;
Chris@16: 
Chris@16:     class less_point : public std::binary_function<Point, Point, bool> {
Chris@16:     public:
Chris@16:       inline less_point() {}
Chris@16:       inline bool operator () (const Point& pt1, const Point& pt2) const {
Chris@16:         if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true;
Chris@16:         if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) {
Chris@16:           if(pt1.get(VERTICAL) < pt2.get(VERTICAL)) return true;
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     static inline bool between(Point pt, Point pt1, Point pt2) {
Chris@16:       less_point lp;
Chris@16:       if(lp(pt1, pt2))
Chris@16:         return lp(pt, pt2) && lp(pt1, pt);
Chris@16:       return lp(pt, pt1) && lp(pt2, pt);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename area_type>
Chris@16:     static inline bool equal_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
Chris@16:       typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
Chris@16:       unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
Chris@16:       unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
Chris@16:       int dx1_sign = dx1 < 0 ? -1 : 1;
Chris@16:       int dx2_sign = dx2 < 0 ? -1 : 1;
Chris@16:       int dy1_sign = dy1 < 0 ? -1 : 1;
Chris@16:       int dy2_sign = dy2 < 0 ? -1 : 1;
Chris@16:       int cross_1_sign = dx2_sign * dy1_sign;
Chris@16:       int cross_2_sign = dx1_sign * dy2_sign;
Chris@16:       return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0);
Chris@16:     }
Chris@16: 
Chris@16:     static inline bool equal_slope(const Unit& x, const Unit& y,
Chris@16:                                    const Point& pt1, const Point& pt2) {
Chris@16:       const Point* pts[2] = {&pt1, &pt2};
Chris@16:       typedef typename coordinate_traits<Unit>::manhattan_area_type at;
Chris@16:       at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
Chris@16:       at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
Chris@16:       at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
Chris@16:       at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
Chris@16:       return equal_slope(dx1, dy1, dx2, dy2);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename area_type>
Chris@16:     static inline bool less_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
Chris@16:       //reflext x and y slopes to right hand side half plane
Chris@16:       if(dx1 < 0) {
Chris@16:         dy1 *= -1;
Chris@16:         dx1 *= -1;
Chris@16:       } else if(dx1 == 0) {
Chris@16:         //if the first slope is vertical the first cannot be less
Chris@16:         return false;
Chris@16:       }
Chris@16:       if(dx2 < 0) {
Chris@16:         dy2 *= -1;
Chris@16:         dx2 *= -1;
Chris@16:       } else if(dx2 == 0) {
Chris@16:         //if the second slope is vertical the first is always less unless it is also vertical, in which case they are equal
Chris@16:         return dx1 != 0;
Chris@16:       }
Chris@16:       typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
Chris@16:       unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
Chris@16:       unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
Chris@16:       int dx1_sign = dx1 < 0 ? -1 : 1;
Chris@16:       int dx2_sign = dx2 < 0 ? -1 : 1;
Chris@16:       int dy1_sign = dy1 < 0 ? -1 : 1;
Chris@16:       int dy2_sign = dy2 < 0 ? -1 : 1;
Chris@16:       int cross_1_sign = dx2_sign * dy1_sign;
Chris@16:       int cross_2_sign = dx1_sign * dy2_sign;
Chris@16:       if(cross_1_sign < cross_2_sign) return true;
Chris@16:       if(cross_2_sign < cross_1_sign) return false;
Chris@16:       if(cross_1_sign == -1) return cross_2 < cross_1;
Chris@16:       return cross_1 < cross_2;
Chris@16:     }
Chris@16: 
Chris@16:     static inline bool less_slope(const Unit& x, const Unit& y,
Chris@16:                                   const Point& pt1, const Point& pt2) {
Chris@16:       const Point* pts[2] = {&pt1, &pt2};
Chris@16:       //compute y value on edge from pt_ to pts[1] at the x value of pts[0]
Chris@16:       typedef typename coordinate_traits<Unit>::manhattan_area_type at;
Chris@16:       at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
Chris@16:       at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
Chris@16:       at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
Chris@16:       at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
Chris@16:       return less_slope(dx1, dy1, dx2, dy2);
Chris@16:     }
Chris@16: 
Chris@16:     //return -1 below, 0 on and 1 above line
Chris@16:     //assumes point is on x interval of segment
Chris@16:     static inline int on_above_or_below(Point pt, const half_edge& he) {
Chris@16:       if(pt == he.first || pt == he.second) return 0;
Chris@16:       if(equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second)) return 0;
Chris@16:       bool less_result = less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second);
Chris@16:       int retval = less_result ? -1 : 1;
Chris@16:       less_point lp;
Chris@16:       if(lp(he.second, he.first)) retval *= -1;
Chris@16:       if(!between(pt, he.first, he.second)) retval *= -1;
Chris@16:       return retval;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T, typename input_point_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_any_mutable_polygon_with_holes_type<T>::type,
Chris@16:                       typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
Chris@16:     bool>::type
Chris@16:   contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
Chris@16:     typedef typename polygon_with_holes_traits<T>::iterator_holes_type holes_iterator;
Chris@16:     bool isInside = contains( view_as< typename polygon_from_polygon_with_holes_type<
Chris@16:                               typename geometry_concept<T>::type>::type>( polygon ), point, consider_touch );
Chris@16:     if(!isInside) return false; //no need to check holes
Chris@16:     holes_iterator itH = begin_holes( polygon );
Chris@16:     while( itH != end_holes( polygon ) ) {
Chris@16:       if(  contains( *itH, point, !consider_touch )  ) {
Chris@16:         isInside = false;
Chris@16:         break;
Chris@16:       }
Chris@16:       ++itH;
Chris@16:     }
Chris@16:     return isInside;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T, typename input_point_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and_3<
Chris@16:       typename is_polygon_type<T>::type,
Chris@16:       typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
Chris@16:       typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
Chris@16:     bool>::type
Chris@16:   contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
Chris@16:     typedef typename point_traits<input_point_type>::coordinate_type Unit;
Chris@16:     typedef point_data<Unit> Point;
Chris@16:     typedef std::pair<Point, Point> half_edge;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator;
Chris@16:     iterator itr = begin_points(polygon);
Chris@16:     iterator itrEnd = end_points(polygon);
Chris@16:     half_edge he;
Chris@16:     if(itr == itrEnd) return false;
Chris@16:     assign(he.first, *itr);
Chris@16:     Point firstPt;
Chris@16:     assign(firstPt, *itr);
Chris@16:     ++itr;
Chris@16:     if(itr == itrEnd) return false;
Chris@16:     bool done = false;
Chris@16:     int above = 0;
Chris@16:     while(!done) {
Chris@16:       Point currentPt;
Chris@16:       if(itr == itrEnd) {
Chris@16:         done = true;
Chris@16:         currentPt = firstPt;
Chris@16:       } else {
Chris@16:         assign(currentPt, *itr);
Chris@16:         ++itr;
Chris@16:       }
Chris@16:       if(currentPt == he.first) {
Chris@16:         continue;
Chris@16:       } else {
Chris@16:         he.second = currentPt;
Chris@16:         if(equivalence(point, currentPt)) return consider_touch;
Chris@16:         Unit xmin = (std::min)(x(he.first), x(he.second));
Chris@16:         Unit xmax = (std::max)(x(he.first), x(he.second));
Chris@16:         if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
Chris@16:           Point tmppt;
Chris@16:           assign(tmppt, point);
Chris@16:           int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
Chris@16:           if(oabedge == 0) return consider_touch;
Chris@16:           if(oabedge == 1) ++above;
Chris@16:         } else if(x(point) == xmax) {
Chris@16:           if(x(point) == xmin) {
Chris@16:             Unit ymin = (std::min)(y(he.first), y(he.second));
Chris@16:             Unit ymax = (std::max)(y(he.first), y(he.second));
Chris@16:             Unit ypt = y(point);
Chris@16:             if(ypt <= ymax && ypt >= ymin)
Chris@16:               return consider_touch;
Chris@16:           } else {
Chris@16:             Point tmppt;
Chris@16:             assign(tmppt, point);
Chris@16:             if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) {
Chris@16:               return consider_touch;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:       he.first = he.second;
Chris@16:     }
Chris@16:     return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
Chris@16:   }
Chris@16: 
Chris@16:   /*
Chris@16:   template <typename T, typename input_point_type>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and_3<
Chris@16:       typename is_polygon_with_holes_type<T>::type,
Chris@16:       typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
Chris@16:       typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
Chris@16:     bool>::type
Chris@16:   contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
Chris@16:     typedef typename point_traits<input_point_type>::coordinate_type Unit;
Chris@16:     typedef point_data<Unit> Point;
Chris@16:     typedef std::pair<Point, Point> half_edge;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator;
Chris@16:     iterator itr = begin_points(polygon);
Chris@16:     iterator itrEnd = end_points(polygon);
Chris@16:     half_edge he;
Chris@16:     if(itr == itrEnd) return false;
Chris@16:     assign(he.first, *itr);
Chris@16:     Point firstPt;
Chris@16:     assign(firstPt, *itr);
Chris@16:     ++itr;
Chris@16:     if(itr == itrEnd) return false;
Chris@16:     bool done = false;
Chris@16:     int above = 0;
Chris@16:     while(!done) {
Chris@16:       Point currentPt;
Chris@16:       if(itr == itrEnd) {
Chris@16:         done = true;
Chris@16:         currentPt = firstPt;
Chris@16:       } else {
Chris@16:         assign(currentPt, *itr);
Chris@16:         ++itr;
Chris@16:       }
Chris@16:       if(currentPt == he.first) {
Chris@16:         continue;
Chris@16:       } else {
Chris@16:         he.second = currentPt;
Chris@16:         if(equivalence(point, currentPt)) return consider_touch;
Chris@16:         Unit xmin = (std::min)(x(he.first), x(he.second));
Chris@16:         Unit xmax = (std::max)(x(he.first), x(he.second));
Chris@16:         if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
Chris@16:           Point tmppt;
Chris@16:           assign(tmppt, point);
Chris@16:           int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
Chris@16:           if(oabedge == 0) return consider_touch;
Chris@16:           if(oabedge == 1) ++above;
Chris@16:         }
Chris@16:       }
Chris@16:       he.first = he.second;
Chris@16:     }
Chris@16:     return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
Chris@16:   }
Chris@16:   */
Chris@16: 
Chris@16:   template <typename T1, typename T2>
Chris@16:   typename enable_if<
Chris@16:     typename gtl_and< typename is_mutable_rectangle_concept<typename geometry_concept<T1>::type>::type,
Chris@16:                       typename is_polygon_with_holes_type<T2>::type>::type,
Chris@16:     bool>::type
Chris@16:   extents(T1& bounding_box, const T2& polygon) {
Chris@16:     typedef typename polygon_traits<T2>::iterator_type iterator;
Chris@16:     bool first_iteration = true;
Chris@16:     iterator itr_end = end_points(polygon);
Chris@16:     for(iterator itr = begin_points(polygon); itr != itr_end; ++itr) {
Chris@16:       if(first_iteration) {
Chris@16:         set_points(bounding_box, *itr, *itr);
Chris@16:         first_iteration = false;
Chris@16:       } else {
Chris@16:         encompass(bounding_box, *itr);
Chris@16:       }
Chris@16:     }
Chris@16:     if(first_iteration) return false;
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@101:   template <typename T1, typename T2>
Chris@101:   typename enable_if<
Chris@101:     typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type,
Chris@101:                       typename is_polygon_with_holes_type<T2>::type>::type,
Chris@101:     bool>::type
Chris@101:   center(T1& center_point, const T2& polygon) {
Chris@101:     typedef typename polygon_traits<T2>::coordinate_type coordinate_type;
Chris@101:     rectangle_data<coordinate_type> bbox;
Chris@101:     extents(bbox, polygon);
Chris@101:     return center(center_point, bbox);
Chris@101:   }
Chris@101: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_45_data<T>& polygon_45_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_90_with_holes_data<T>& polygon_90_with_holes_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_45_with_holes_data<T>& polygon_45_with_holes_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class T2>
Chris@16:   polygon_with_holes_data<T>& polygon_with_holes_data<T>::operator=(const T2& rvalue) {
Chris@16:     assign(*this, rvalue);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_data<T> > {
Chris@16:     typedef polygon_concept type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_45_data<T> > {
Chris@16:     typedef polygon_45_concept type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_90_data<T> > {
Chris@16:     typedef polygon_90_concept type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_with_holes_data<T> > {
Chris@16:     typedef polygon_with_holes_concept type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_45_with_holes_data<T> > {
Chris@16:     typedef polygon_45_with_holes_concept type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_90_with_holes_data<T> > {
Chris@16:     typedef polygon_90_with_holes_concept type;
Chris@16:   };
Chris@16: 
Chris@16: //   template <typename T> struct polygon_with_holes_traits<polygon_90_data<T> > {
Chris@16: //     typedef polygon_90_data<T> hole_type;
Chris@16: //     typedef const hole_type* iterator_holes_type;
Chris@16: //     static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline std::size_t size_holes(const hole_type& t) { return 0; }
Chris@16: //   };
Chris@16: //   template <typename T> struct polygon_with_holes_traits<polygon_45_data<T> > {
Chris@16: //     typedef polygon_45_data<T> hole_type;
Chris@16: //     typedef const hole_type* iterator_holes_type;
Chris@16: //     static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline std::size_t size_holes(const hole_type& t) { return 0; }
Chris@16: //   };
Chris@16: //   template <typename T> struct polygon_with_holes_traits<polygon_data<T> > {
Chris@16: //     typedef polygon_data<T> hole_type;
Chris@16: //     typedef const hole_type* iterator_holes_type;
Chris@16: //     static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
Chris@16: //     static inline std::size_t size_holes(const hole_type& t) { return 0; }
Chris@16: //   };
Chris@16:   template <typename T> struct get_void {};
Chris@16:   template <> struct get_void<gtl_yes> { typedef void type; };
Chris@16: 
Chris@16:   template <typename T> struct polygon_with_holes_traits<
Chris@16:     T, typename get_void<typename is_any_mutable_polygon_without_holes_type<T>::type>::type > {
Chris@16:     typedef T hole_type;
Chris@16:     typedef const hole_type* iterator_holes_type;
Chris@16:     static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
Chris@16:     static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
Chris@16:     static inline std::size_t size_holes(const hole_type& t) { return 0; }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<rectangle_concept, T> {
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef interval_data<coordinate_type> interval_type;
Chris@16:     rectangle_data<coordinate_type> rect;
Chris@16:     view_of(const T& obj) : rect() {
Chris@16:       point_data<coordinate_type> pts[2];
Chris@16:       typename polygon_traits<T>::iterator_type itr =
Chris@16:         begin_points(obj), itre = end_points(obj);
Chris@16:       if(itr == itre) return;
Chris@16:       assign(pts[0], *itr);
Chris@16:       ++itr;
Chris@16:       if(itr == itre) return;
Chris@16:       ++itr;
Chris@16:       if(itr == itre) return;
Chris@16:       assign(pts[1], *itr);
Chris@16:       set_points(rect, pts[0], pts[1]);
Chris@16:     }
Chris@16:     inline interval_type get(orientation_2d orient) const {
Chris@16:       return rect.get(orient); }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<rectangle_concept, T> > {
Chris@16:     typedef rectangle_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<polygon_45_concept, T> {
Chris@16:     const T* t;
Chris@16:     view_of(const T& obj) : t(&obj) {}
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator_type;
Chris@16:     typedef typename polygon_traits<T>::point_type point_type;
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline iterator_type begin() const {
Chris@16:       return polygon_traits<T>::begin_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline iterator_type end() const {
Chris@16:       return polygon_traits<T>::end_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size() const {
Chris@16:       return polygon_traits<T>::size(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the winding direction of the polygon
Chris@16:     inline winding_direction winding() const {
Chris@16:       return polygon_traits<T>::winding(*t);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<polygon_45_concept, T> > {
Chris@16:     typedef polygon_45_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<polygon_90_concept, T> {
Chris@16:     const T* t;
Chris@16:     view_of(const T& obj) : t(&obj) {}
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator_type;
Chris@16:     typedef typename polygon_traits<T>::point_type point_type;
Chris@16:     typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline compact_iterator_type begin_compact() const {
Chris@16:       return compact_iterator_type(polygon_traits<T>::begin_points(*t),
Chris@16:                                    polygon_traits<T>::end_points(*t));
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline compact_iterator_type end_compact() const {
Chris@16:       return compact_iterator_type(polygon_traits<T>::end_points(*t),
Chris@16:                                    polygon_traits<T>::end_points(*t));
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size() const {
Chris@16:       return polygon_traits<T>::size(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the winding direction of the polygon
Chris@16:     inline winding_direction winding() const {
Chris@16:       return polygon_traits<T>::winding(*t);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<polygon_90_concept, T> > {
Chris@16:     typedef polygon_90_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<polygon_45_with_holes_concept, T> {
Chris@16:     const T* t;
Chris@16:     view_of(const T& obj) : t(&obj) {}
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator_type;
Chris@16:     typedef typename polygon_traits<T>::point_type point_type;
Chris@16:     typedef view_of<polygon_45_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
Chris@16:     struct iterator_holes_type {
Chris@16:       typedef std::forward_iterator_tag iterator_category;
Chris@16:       typedef hole_type value_type;
Chris@16:       typedef std::ptrdiff_t difference_type;
Chris@16:       typedef const hole_type* pointer; //immutable
Chris@16:       typedef const hole_type& reference; //immutable
Chris@16:       typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
Chris@16:       iht internal_itr;
Chris@16:       iterator_holes_type() : internal_itr() {}
Chris@16:       iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
Chris@16:       inline iterator_holes_type& operator++() {
Chris@16:         ++internal_itr;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline const iterator_holes_type operator++(int) {
Chris@16:         iterator_holes_type tmp(*this);
Chris@16:         ++(*this);
Chris@16:         return tmp;
Chris@16:       }
Chris@16:       inline bool operator==(const iterator_holes_type& that) const {
Chris@16:         return (internal_itr == that.internal_itr);
Chris@16:       }
Chris@16:       inline bool operator!=(const iterator_holes_type& that) const {
Chris@16:         return (internal_itr != that.internal_itr);
Chris@16:       }
Chris@16:       inline value_type operator*() const {
Chris@16:         return view_as<polygon_45_concept>(*internal_itr);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline iterator_type begin() const {
Chris@16:       return polygon_traits<T>::begin_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline iterator_type end() const {
Chris@16:       return polygon_traits<T>::end_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size() const {
Chris@16:       return polygon_traits<T>::size(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the winding direction of the polygon
Chris@16:     inline winding_direction winding() const {
Chris@16:       return polygon_traits<T>::winding(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline iterator_holes_type begin_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::begin_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline iterator_holes_type end_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::end_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::size_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<polygon_45_with_holes_concept, T> > {
Chris@16:     typedef polygon_45_with_holes_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<polygon_90_with_holes_concept, T> {
Chris@16:     const T* t;
Chris@16:     view_of(const T& obj) : t(&obj) {}
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator_type;
Chris@16:     typedef typename polygon_traits<T>::point_type point_type;
Chris@16:     typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
Chris@16:     typedef view_of<polygon_90_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
Chris@16:     struct iterator_holes_type {
Chris@16:       typedef std::forward_iterator_tag iterator_category;
Chris@16:       typedef hole_type value_type;
Chris@16:       typedef std::ptrdiff_t difference_type;
Chris@16:       typedef const hole_type* pointer; //immutable
Chris@16:       typedef const hole_type& reference; //immutable
Chris@16:       typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
Chris@16:       iht internal_itr;
Chris@16:       iterator_holes_type() : internal_itr() {}
Chris@16:       iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
Chris@16:       inline iterator_holes_type& operator++() {
Chris@16:         ++internal_itr;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline const iterator_holes_type operator++(int) {
Chris@16:         iterator_holes_type tmp(*this);
Chris@16:         ++(*this);
Chris@16:         return tmp;
Chris@16:       }
Chris@16:       inline bool operator==(const iterator_holes_type& that) const {
Chris@16:         return (internal_itr == that.internal_itr);
Chris@16:       }
Chris@16:       inline bool operator!=(const iterator_holes_type& that) const {
Chris@16:         return (internal_itr != that.internal_itr);
Chris@16:       }
Chris@16:       inline value_type operator*() const {
Chris@16:         return view_as<polygon_90_concept>(*internal_itr);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline compact_iterator_type begin_compact() const {
Chris@16:       return compact_iterator_type(polygon_traits<T>::begin_points(*t),
Chris@16:                                    polygon_traits<T>::end_points(*t));
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline compact_iterator_type end_compact() const {
Chris@16:       return compact_iterator_type(polygon_traits<T>::end_points(*t),
Chris@16:                                    polygon_traits<T>::end_points(*t));
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size() const {
Chris@16:       return polygon_traits<T>::size(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the winding direction of the polygon
Chris@16:     inline winding_direction winding() const {
Chris@16:       return polygon_traits<T>::winding(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline iterator_holes_type begin_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::begin_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline iterator_holes_type end_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::end_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size_holes() const {
Chris@16:       return polygon_with_holes_traits<T>::size_holes(*t);
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<polygon_90_with_holes_concept, T> > {
Chris@16:     typedef polygon_90_with_holes_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct view_of<polygon_concept, T> {
Chris@16:     const T* t;
Chris@16:     view_of(const T& obj) : t(&obj) {}
Chris@16:     typedef typename polygon_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef typename polygon_traits<T>::iterator_type iterator_type;
Chris@16:     typedef typename polygon_traits<T>::point_type point_type;
Chris@16: 
Chris@16:     /// Get the begin iterator
Chris@16:     inline iterator_type begin() const {
Chris@16:       return polygon_traits<T>::begin_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the end iterator
Chris@16:     inline iterator_type end() const {
Chris@16:       return polygon_traits<T>::end_points(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the number of sides of the polygon
Chris@16:     inline std::size_t size() const {
Chris@16:       return polygon_traits<T>::size(*t);
Chris@16:     }
Chris@16: 
Chris@16:     /// Get the winding direction of the polygon
Chris@16:     inline winding_direction winding() const {
Chris@16:       return polygon_traits<T>::winding(*t);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<view_of<polygon_concept, T> > {
Chris@16:     typedef polygon_concept type;
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: 
Chris@16: #endif