[Boost-commit] svn:boost r72874 - in trunk/boost/geometry/algorithms: . detail/overlay

Subject: [Boost-commit] svn:boost r72874 - in trunk/boost/geometry/algorithms: . detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-07-03 10:20:21

Author: barendgehrels
Date: 2011-07-03 10:20:20 EDT (Sun, 03 Jul 2011)
New Revision: 72874
URL: http://svn.boost.org/trac/boost/changeset/72874

Log:
Moved within_code from within_util.hpp to within.hpp, and implemented for point/box and box/box
Removed:
   trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp |     8                                         
   trunk/boost/geometry/algorithms/within.hpp                        |   246 +++++++++++++++++++++++++++++---------- 
   2 files changed, 188 insertions(+), 66 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/assign_parents.hpp	2011-07-03 10:20:20 EDT (Sun, 03 Jul 2011)
@@ -14,7 +14,7 @@
 #include <boost/geometry/algorithms/expand.hpp>
 #include <boost/geometry/algorithms/detail/partition.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
-#include <boost/geometry/algorithms/detail/overlay/within_util.hpp>
+#include <boost/geometry/algorithms/within.hpp>
 
 #include <boost/geometry/geometries/box.hpp>
 
@@ -46,15 +46,15 @@
     switch (ring_id.source_index)
     {
         case 0 :
-            code = point_in_ring(item2.point,
+            code = within_code(item2.point,
                 get_ring<tag1>::apply(ring_id, geometry1));
             break;
         case 1 :
-            code = point_in_ring(item2.point,
+            code = within_code(item2.point,
                 get_ring<tag2>::apply(ring_id, geometry2));
             break;
         case 2 :
-            code = point_in_ring(item2.point,
+            code = within_code(item2.point,
                 get_ring<void>::apply(ring_id, collection));
             break;
     }

Deleted: trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/within_util.hpp	2011-07-03 10:20:20 EDT (Sun, 03 Jul 2011)
+++ (empty file)
@@ -1,98 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-
-// Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands.
-
-// Use, modification and distribution is subject to the Boost Software License,
-// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_WITHIN_UTIL_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_WITHIN_UTIL_HPP
-
-
-
-#include <boost/geometry/algorithms/within.hpp>
-#include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace overlay
-{
-
-
-template<typename Tag, typename Point, typename Geometry>
-struct within_code
-{};
-
-template<typename Point, typename Box>
-struct within_code<box_tag, Point, Box>
-{
-    static inline int apply(Point const& point, Box const& box)
-    {
-        // 1. Check outside
-        if (get<0>(point) < get<min_corner, 0>(box)
-            || get<0>(point) > get<max_corner, 0>(box)
-            || get<1>(point) < get<min_corner, 1>(box)
-            || get<1>(point) > get<max_corner, 1>(box))
-        {
-            return -1;
-        }
-        // 2. Check border
-        if (geometry::math::equals(get<0>(point), get<min_corner, 0>(box))
-            || geometry::math::equals(get<0>(point), get<max_corner, 0>(box))
-            || geometry::math::equals(get<1>(point), get<min_corner, 1>(box))
-            || geometry::math::equals(get<1>(point), get<max_corner, 1>(box)))
-        {
-            return 0;
-        }
-        return 1;
-    }
-};
-template<typename Point, typename Ring>
-struct within_code<ring_tag, Point, Ring>
-{
-    static inline int apply(Point const& point, Ring const& ring)
-    {
-        // Same as point_in_ring but here ALWAYS with winding.
-        typedef strategy::within::winding<Point> strategy_type;
-
-        return detail::within::point_in_ring
-            <
-                Point,
-                Ring,
-                order_as_direction<geometry::point_order<Ring>::value>::value,
-                geometry::closure<Ring>::value,
-                strategy_type
-            >::apply(point, ring, strategy_type());
-    }
-};
-
-
-template<typename Point, typename Geometry>
-inline int point_in_ring(Point const& point, Geometry const& geometry)
-{
-    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
-        ::apply(point, geometry);
-}
-
-template<typename Point, typename Geometry>
-inline bool within_or_touch(Point const& point, Geometry const& geometry)
-{
-    return within_code<typename geometry::tag<Geometry>::type, Point, Geometry>
-        ::apply(point, geometry) >= 0;
-}
-
-
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_WITHIN_UTIL_HPP

Modified: trunk/boost/geometry/algorithms/within.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/within.hpp	(original)
+++ trunk/boost/geometry/algorithms/within.hpp	2011-07-03 10:20:20 EDT (Sun, 03 Jul 2011)
@@ -35,6 +35,7 @@
 #include <boost/geometry/geometries/concepts/check.hpp>
 #include <boost/geometry/strategies/within.hpp>
 #include <boost/geometry/strategies/concepts/within_concept.hpp>
+#include <boost/geometry/util/math.hpp>
 #include <boost/geometry/util/order_as_direction.hpp>
 #include <boost/geometry/views/closeable_view.hpp>
 #include <boost/geometry/views/reversible_view.hpp>
@@ -48,6 +49,28 @@
 {
 
 
+struct within_state
+{
+    bool outside, inside, on_border;
+    inline within_state()
+        : outside(false)
+        , on_border(false)
+    {}
+
+    inline int code() const
+    {
+        // Note the order: 1) outside 2) on_border 3) inside
+        // If one dim. is outside, it IS outside, else
+        // if one dim is on border, it IS on border,
+        // if it only inside if inside=true and the rest is false
+        return outside ? -1
+            : on_border ? 0
+            : 1
+            ;
+    }
+
+};
+
 /*!
     \brief Implementation for boxes
     \ingroup boolean_relations
@@ -61,26 +84,36 @@
     std::size_t Dimension,
     std::size_t DimensionCount
 >
-struct point_in_box
+struct point_in_box_helper
 {
-    static inline int apply(Point const& p, Box const& b, Strategy const& s)
+    static inline void apply(Point const& p, Box const& b, Strategy const& s, within_state& state)
     {
-        assert_dimension_equal<Point, Box>();
-
-        if (get<Dimension>(p) <= get<min_corner, Dimension>(b)
-            || get<Dimension>(p) >= get<max_corner, Dimension>(b))
+        typename geometry::coordinate_type<Point>::type const v
+                    = get<Dimension>(p);
+        typename geometry::coordinate_type<Box>::type const b_min
+                    = get<min_corner, Dimension>(b);
+        typename geometry::coordinate_type<Box>::type const b_max
+                    = get<max_corner, Dimension>(b);
+                    
+        if (geometry::math::equals(v, b_min) 
+                || geometry::math::equals(v, b_max))
         {
-            return -1;
+            state.on_border = true;
         }
-
-        return point_in_box
+        else if (v < b_min || v > b_max)
+        {
+            state.outside = true;
+            return;
+        }
+        
+        point_in_box_helper
             <
                 Point,
                 Box,
                 Strategy,
                 Dimension + 1,
                 DimensionCount
-            >::apply(p, b, s);
+            >::apply(p, b, s, state);
     }
 };
 
@@ -91,11 +124,31 @@
     typename Strategy,
     std::size_t DimensionCount
 >
-struct point_in_box<Point, Box, Strategy, DimensionCount, DimensionCount>
+struct point_in_box_helper<Point, Box, Strategy, DimensionCount, DimensionCount>
 {
-    static inline int apply(Point const& , Box const& , Strategy const& )
+    static inline void apply(Point const& , Box const& , Strategy const&, within_state& )
     {
-        return 1;
+    }
+};
+
+template
+<
+    typename Point,
+    typename Box,
+    typename Strategy
+>
+struct point_in_box
+{
+    static inline int apply(Point const& point, Box const& box, Strategy const& strategy)
+    {
+        assert_dimension_equal<Point, Box>();
+        within_state state;
+        point_in_box_helper
+            <
+                Point, Box, Strategy, 
+                0, dimension<Point>::type::value
+            >::apply(point, box, strategy, state);
+        return state.code();
     }
 };
 
@@ -108,26 +161,50 @@
     std::size_t Dimension,
     std::size_t DimensionCount
 >
-struct box_in_box
+struct box_in_box_helper
 {
-    static inline int apply(Box1 const& b1, Box2 const& b2, Strategy const& s)
+    static inline void apply(Box1 const& b_contained, Box2 const& b_containing,
+                Strategy const& strategy, within_state& state)
     {
         assert_dimension_equal<Box1, Box2>();
 
-        if (get<min_corner, Dimension>(b1) <= get<min_corner, Dimension>(b2)
-            || get<max_corner, Dimension>(b1) >= get<max_corner, Dimension>(b2))
+        typename geometry::coordinate_type<Box1>::type const ced_min
+                    = get<min_corner, Dimension>(b_contained);
+        typename geometry::coordinate_type<Box1>::type const ced_max
+                    = get<max_corner, Dimension>(b_contained);
+        typename geometry::coordinate_type<Box2>::type const cing_min
+                    = get<min_corner, Dimension>(b_containing);
+        typename geometry::coordinate_type<Box2>::type const cing_max
+                    = get<max_corner, Dimension>(b_containing);
+
+        if (geometry::math::equals(ced_min, cing_min))
         {
-            return -1;
+            state.on_border = true;
+        }
+        else if (ced_min < cing_min)
+        {
+            state.outside = true;
+            return;
         }
 
-        return box_in_box
+        if (geometry::math::equals(ced_max, cing_max))
+        {
+            state.on_border = true;
+        }
+        else if (ced_max > cing_max)
+        {
+            state.outside = true;
+            return;
+        }
+
+        box_in_box_helper
             <
                 Box1,
                 Box2,
                 Strategy,
                 Dimension + 1,
                 DimensionCount
-            >::apply(b1, b2, s);
+            >::apply(b_contained, b_containing, strategy, state);
     }
 };
 
@@ -138,11 +215,31 @@
     typename Strategy,
     std::size_t DimensionCount
 >
-struct box_in_box<Box1, Box2, Strategy, DimensionCount, DimensionCount>
+struct box_in_box_helper<Box1, Box2, Strategy, DimensionCount, DimensionCount>
 {
-    static inline int apply(Box1 const& , Box2 const& , Strategy const&)
+    static inline void apply(Box1 const& , Box2 const& , Strategy const&, within_state&)
     {
-        return 1;
+    }
+};
+
+template
+<
+    typename Box1,
+    typename Box2,
+    typename Strategy
+>
+struct box_in_box
+{
+    static inline int apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
+    {
+        assert_dimension_equal<Box1, Box2>();
+        within_state state;
+        box_in_box_helper
+            <
+                Box1, Box1, Strategy,
+                0, dimension<Box1>::type::value
+            >::apply(box1, box2, strategy, state);
+        return state.code();
     }
 };
 
@@ -181,13 +278,14 @@
         iterator_type it = boost::begin(view);
         iterator_type end = boost::end(view);
 
+        bool stop = false;
         for (iterator_type previous = it++;
-            it != end;
+            it != end && ! stop;
             ++previous, ++it)
         {
             if (! strategy.apply(point, *previous, *it, state))
             {
-                return false;
+                stop = true;
             }
         }
 
@@ -284,9 +382,7 @@
             <
                 Point,
                 Box,
-                Strategy,
-                0,
-                dimension<Point>::type::value
+                Strategy
             >
 {};
 
@@ -296,9 +392,7 @@
             <
                 Box1,
                 Box2,
-                Strategy,
-                0,
-                dimension<Box1>::type::value
+                Strategy
             >
 {};
 
@@ -359,6 +453,63 @@
 
 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 
+
+namespace detail
+{
+
+template<typename Geometry1, typename Geometry2>
+inline int within_code(Geometry1 const& geometry1, Geometry2 const& geometry2)
+{
+    concept::check<Geometry1 const>();
+    concept::check<Geometry2 const>();
+
+    typedef typename point_type<Geometry1>::type point_type1;
+    typedef typename point_type<Geometry2>::type point_type2;
+
+    typedef typename strategy::within::services::default_strategy
+        <
+            typename tag<Geometry1>::type,
+            typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
+            typename cs_tag<point_type1>::type,
+            typename cs_tag<point_type2>::type,
+            point_type1,
+            point_type2
+        >::type strategy_type;
+
+    return dispatch::within
+        <
+            typename tag<Geometry1>::type,
+            typename tag<Geometry2>::type,
+            Geometry1,
+            Geometry2,
+            strategy_type
+        >::apply(geometry1, geometry2, strategy_type());
+}
+
+
+template<typename Geometry1, typename Geometry2, typename Strategy>
+inline int within_code(Geometry1 const& geometry1, Geometry2 const& geometry2,
+        Strategy const& strategy)
+{
+    // Always assume a point-in-polygon strategy here.
+    // Because for point-in-box, it makes no sense to specify one.
+    BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategy<Strategy>) );
+
+    concept::check<Geometry1 const>();
+    concept::check<Geometry2 const>();
+
+    return dispatch::within
+        <
+            typename tag<Geometry1>::type,
+            typename tag<Geometry2>::type,
+            Geometry1,
+            Geometry2,
+            Strategy
+        >::apply(geometry1, geometry2, strategy);
+}
+
+}
+
 /*!
 \brief \brief_check12{is completely inside}
 \ingroup within
@@ -387,28 +538,7 @@
 {
     concept::check<Geometry1 const>();
     concept::check<Geometry2 const>();
-
-    typedef typename point_type<Geometry1>::type point_type1;
-    typedef typename point_type<Geometry2>::type point_type2;
-
-    typedef typename strategy::within::services::default_strategy
-        <
-            typename tag<Geometry1>::type,
-            typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
-            typename cs_tag<point_type1>::type,
-            typename cs_tag<point_type2>::type,
-            point_type1,
-            point_type2
-        >::type strategy_type;
-
-    return dispatch::within
-        <
-            typename tag<Geometry1>::type,
-            typename tag<Geometry2>::type,
-            Geometry1,
-            Geometry2,
-            strategy_type
-        >::apply(geometry1, geometry2, strategy_type()) == 1;
+    return detail::within_code(geometry1, geometry2) == 1;
 }
 
 /*!
@@ -449,15 +579,7 @@
 
     concept::check<Geometry1 const>();
     concept::check<Geometry2 const>();
-
-    return dispatch::within
-        <
-            typename tag<Geometry1>::type,
-            typename tag<Geometry2>::type,
-            Geometry1,
-            Geometry2,
-            Strategy
-        >::apply(geometry1, geometry2, strategy) == 1;
+    return detail::within_code(geometry1, geometry2, strategy) == 1;
 }
 
 }} // namespace boost::geometry