diff DEPENDENCIES/generic/include/boost/polygon/polygon_traits.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

--- a/DEPENDENCIES/generic/include/boost/polygon/polygon_traits.hpp	Fri Sep 04 12:01:02 2015 +0100
+++ b/DEPENDENCIES/generic/include/boost/polygon/polygon_traits.hpp	Mon Sep 07 11:12:49 2015 +0100
@@ -971,7 +971,6 @@
   static area_type
   point_sequence_area(iterator_type begin_range, iterator_type end_range) {
     typedef typename std::iterator_traits<iterator_type>::value_type point_type;
-    typedef typename point_traits<point_type>::coordinate_type Unit;
     if(begin_range == end_range) return area_type(0);
     point_type first = *begin_range;
     point_type previous = first;
@@ -1129,17 +1128,33 @@
 
   template <typename T, typename input_point_type>
   typename enable_if<
-    typename gtl_and< typename is_polygon_90_type<T>::type,
-                      typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
-    bool>::type
-  contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
+    typename gtl_and<
+      typename is_polygon_90_type<T>::type,
+      typename gtl_same_type<
+        typename geometry_concept<input_point_type>::type,
+        point_concept
+      >::type
+    >::type,
+    bool
+  >::type contains(
+      const T& polygon,
+      const input_point_type& point,
+      bool consider_touch = true) {
     typedef T polygon_type;
     typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
     typedef typename polygon_traits<polygon_type>::iterator_type iterator;
     typedef typename std::iterator_traits<iterator>::value_type point_type;
     coordinate_type point_x = x(point);
     coordinate_type point_y = y(point);
-    bool inside = false;
+    // Check how many intersections has the ray extended from the given
+    // point in the x-axis negative direction with the polygon edges.
+    // If the number is odd the point is within the polygon, otherwise not.
+    // We can safely ignore horizontal edges, however intersections with
+    // end points of the vertical edges require special handling. We should
+    // add one intersection in case horizontal edges that extend vertical edge
+    // point in the same direction.
+    int num_full_intersections = 0;
+    int num_half_intersections = 0;
     for (iterator iter = begin_points(polygon); iter != end_points(polygon);) {
       point_type curr_point = *iter;
       ++iter;
@@ -1154,7 +1169,10 @@
           if (x(curr_point) == point_x) {
             return consider_touch;
           }
-          inside ^= true;
+          ++num_full_intersections;
+        }
+        if (point_y == min_y || point_y == max_y) {
+          num_half_intersections += (y(curr_point) < y(next_point) ? 1 : -1);
         }
       } else {
         coordinate_type min_x = (std::min)(x(curr_point), x(next_point));
@@ -1166,7 +1184,8 @@
         }
       }
     }
-    return inside;
+    int total_intersections = num_full_intersections + (num_half_intersections >> 1);
+    return total_intersections & 1;
   }
 
   //TODO: refactor to expose as user APIs
@@ -1420,18 +1439,6 @@
 
   template <typename T1, typename T2>
   typename enable_if<
-    typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type,
-                      typename is_polygon_with_holes_type<T2>::type>::type,
-    bool>::type
-  center(T1& center_point, const T2& polygon) {
-    typedef typename polygon_traits<T2>::coordinate_type coordinate_type;
-    rectangle_data<coordinate_type> bbox;
-    extents(bbox, polygon);
-    return center(center_point, bbox);
-  }
-
-  template <typename T1, typename T2>
-  typename enable_if<
     typename gtl_and< typename is_mutable_rectangle_concept<typename geometry_concept<T1>::type>::type,
                       typename is_polygon_with_holes_type<T2>::type>::type,
     bool>::type
@@ -1451,6 +1458,18 @@
     return true;
   }
 
+  template <typename T1, typename T2>
+  typename enable_if<
+    typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type,
+                      typename is_polygon_with_holes_type<T2>::type>::type,
+    bool>::type
+  center(T1& center_point, const T2& polygon) {
+    typedef typename polygon_traits<T2>::coordinate_type coordinate_type;
+    rectangle_data<coordinate_type> bbox;
+    extents(bbox, polygon);
+    return center(center_point, bbox);
+  }
+
   template <class T>
   template <class T2>
   polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) {