[Boost-commit] svn:boost r86401 - in trunk: boost/geometry/algorithms libs/geometry/test/algorithms

Subject: [Boost-commit] svn:boost r86401 - in trunk: boost/geometry/algorithms libs/geometry/test/algorithms
From: bruno.lalande_at_[hidden]
Date: 2013-10-23 06:13:29

Author: bruno.lalande
Date: 2013-10-23 06:13:28 EDT (Wed, 23 Oct 2013)
New Revision: 86401
URL: http://svn.boost.org/trac/boost/changeset/86401

Log:
Converted convex_hull to the multi-stage approach and made it variant-aware.

Text files modified: 
   trunk/boost/geometry/algorithms/convex_hull.hpp          |   204 +++++++++++++++++++++++++++++++-------- 
   trunk/libs/geometry/test/algorithms/test_convex_hull.hpp |    69 ++++++++-----                           
   2 files changed, 200 insertions(+), 73 deletions(-)

Modified: trunk/boost/geometry/algorithms/convex_hull.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/convex_hull.hpp	Tue Oct 22 16:07:27 2013	(r86400)
+++ trunk/boost/geometry/algorithms/convex_hull.hpp	2013-10-23 06:13:28 EDT (Wed, 23 Oct 2013)	(r86401)
@@ -15,6 +15,9 @@
 #define BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_HPP
 
 #include <boost/array.hpp>
+#include <boost/variant/static_visitor.hpp>
+#include <boost/variant/apply_visitor.hpp>
+#include <boost/variant/variant_fwd.hpp>
 
 #include <boost/geometry/core/cs.hpp>
 #include <boost/geometry/core/point_order.hpp>
@@ -24,6 +27,7 @@
 
 #include <boost/geometry/strategies/convex_hull.hpp>
 #include <boost/geometry/strategies/concepts/convex_hull_concept.hpp>
+#include <boost/geometry/strategies/default_strategy.hpp>
 
 #include <boost/geometry/views/detail/range_type.hpp>
 
@@ -77,18 +81,6 @@
     }
 };
 
-
-// Helper metafunction for default strategy retrieval
-template <typename Geometry>
-struct default_strategy
-    : strategy_convex_hull
-          <
-              Geometry,
-              typename point_type<Geometry>::type
-          >
-{};
-
-
 }} // namespace detail::convex_hull
 #endif // DOXYGEN_NO_DETAIL
 
@@ -142,25 +134,169 @@
 #endif // DOXYGEN_NO_DISPATCH
 
 
-template<typename Geometry, typename OutputGeometry, typename Strategy>
-inline void convex_hull(Geometry const& geometry,
-            OutputGeometry& out, Strategy const& strategy)
+namespace resolve_strategy {
+
+struct convex_hull
+{
+    template <typename Geometry, typename OutputGeometry, typename Strategy>
+    static inline void apply(Geometry const& geometry,
+                             OutputGeometry& out,
+                             Strategy const& strategy)
+    {
+        BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) );
+        dispatch::convex_hull<Geometry>::apply(geometry, out, strategy);
+    }
+
+    template <typename Geometry, typename OutputGeometry>
+    static inline void apply(Geometry const& geometry,
+                             OutputGeometry& out,
+                             default_strategy)
+    {
+        typedef typename strategy_convex_hull<
+            Geometry,
+            typename point_type<Geometry>::type
+        >::type strategy_type;
+
+        apply(geometry, out, strategy_type());
+    }
+};
+
+struct convex_hull_insert
+{
+    template <typename Geometry, typename OutputIterator, typename Strategy>
+    static inline OutputIterator apply(Geometry const& geometry,
+                                       OutputIterator& out,
+                                       Strategy const& strategy)
+    {
+        BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) );
+
+        return dispatch::convex_hull_insert<
+                   geometry::point_order<Geometry>::value
+               >::apply(geometry, out, strategy);
+    }
+
+    template <typename Geometry, typename OutputIterator>
+    static inline OutputIterator apply(Geometry const& geometry,
+                                       OutputIterator& out,
+                                       default_strategy)
+    {
+        typedef typename strategy_convex_hull<
+            Geometry,
+            typename point_type<Geometry>::type
+        >::type strategy_type;
+
+        return apply(geometry, out, strategy_type());
+    }
+};
+
+}; // namespace resolve_strategy
+
+
+namespace resolve_variant {
+
+template <typename Geometry>
+struct convex_hull
 {
-    concept::check_concepts_and_equal_dimensions
-        <
+    template <typename OutputGeometry, typename Strategy>
+    static inline void apply(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy)
+    {
+        concept::check_concepts_and_equal_dimensions<
             const Geometry,
             OutputGeometry
         >();
 
-    BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) );
+        resolve_strategy::convex_hull::apply(geometry, out, strategy);
+    }
+};
+
+template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
+struct convex_hull<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
+{
+    template <typename OutputGeometry, typename Strategy>
+    struct visitor: boost::static_visitor<void>
+    {
+        OutputGeometry& m_out;
+        Strategy const& m_strategy;
+
+        visitor(OutputGeometry& out, Strategy const& strategy)
+        : m_out(out), m_strategy(strategy)
+        {}
+
+        template <typename Geometry>
+        void operator()(Geometry const& geometry) const
+        {
+            convex_hull<Geometry>::apply(geometry, m_out, m_strategy);
+        }
+    };
+
+    template <typename OutputGeometry, typename Strategy>
+    static inline void 
+    apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
+          OutputGeometry& out,
+          Strategy const& strategy)
+    {
+        boost::apply_visitor(visitor<OutputGeometry, Strategy>(out, strategy), geometry);
+    }
+};
+
+template <typename Geometry>
+struct convex_hull_insert
+{
+    template <typename OutputIterator, typename Strategy>
+    static inline OutputIterator apply(Geometry const& geometry, OutputIterator& out, Strategy const& strategy)
+    {
+        // Concept: output point type = point type of input geometry
+        concept::check<Geometry const>();
+        concept::check<typename point_type<Geometry>::type>();
+
+        return resolve_strategy::convex_hull_insert::apply(geometry, out, strategy);
+    }
+};
+
+template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
+struct convex_hull_insert<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
+{
+    template <typename OutputIterator, typename Strategy>
+    struct visitor: boost::static_visitor<OutputIterator>
+    {
+        OutputIterator& m_out;
+        Strategy const& m_strategy;
+
+        visitor(OutputIterator& out, Strategy const& strategy)
+        : m_out(out), m_strategy(strategy)
+        {}
+
+        template <typename Geometry>
+        OutputIterator operator()(Geometry const& geometry) const
+        {
+            return convex_hull_insert<Geometry>::apply(geometry, m_out, m_strategy);
+        }
+    };
+
+    template <typename OutputIterator, typename Strategy>
+    static inline OutputIterator
+    apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
+          OutputIterator& out,
+          Strategy const& strategy)
+    {
+        return boost::apply_visitor(visitor<OutputIterator, Strategy>(out, strategy), geometry);
+    }
+};
+
+} // namespace resolve_variant
+
 
+template<typename Geometry, typename OutputGeometry, typename Strategy>
+inline void convex_hull(Geometry const& geometry,
+            OutputGeometry& out, Strategy const& strategy)
+{
     if (geometry::num_points(geometry) == 0)
     {
         // Leave output empty
         return;
     }
 
-    dispatch::convex_hull<Geometry>::apply(geometry, out, strategy);
+    resolve_variant::convex_hull<Geometry>::apply(geometry, out, strategy);
 }
 
 
@@ -179,15 +315,7 @@
 inline void convex_hull(Geometry const& geometry,
             OutputGeometry& hull)
 {
-    concept::check_concepts_and_equal_dimensions
-        <
-            const Geometry,
-            OutputGeometry
-        >();
-
-    typedef typename detail::convex_hull::default_strategy<Geometry>::type strategy_type;
-
-    convex_hull(geometry, hull, strategy_type());
+    convex_hull(geometry, hull, default_strategy());
 }
 
 #ifndef DOXYGEN_NO_DETAIL
@@ -199,16 +327,8 @@
 inline OutputIterator convex_hull_insert(Geometry const& geometry,
             OutputIterator out, Strategy const& strategy)
 {
-    // Concept: output point type = point type of input geometry
-    concept::check<Geometry const>();
-    concept::check<typename point_type<Geometry>::type>();
-
-    BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) );
-
-    return dispatch::convex_hull_insert
-        <
-            geometry::point_order<Geometry>::value
-        >::apply(geometry, out, strategy);
+    return resolve_variant::convex_hull_insert<Geometry>
+                          ::apply(geometry, out, strategy);
 }
 
 
@@ -229,13 +349,7 @@
 inline OutputIterator convex_hull_insert(Geometry const& geometry,
             OutputIterator out)
 {
-    // Concept: output point type = point type of input geometry
-    concept::check<Geometry const>();
-    concept::check<typename point_type<Geometry>::type>();
-
-    typedef typename detail::convex_hull::default_strategy<Geometry>::type strategy_type;
-
-    return convex_hull_insert(geometry, out, strategy_type());
+    return convex_hull_insert(geometry, out, default_strategy());
 }
 
 

Modified: trunk/libs/geometry/test/algorithms/test_convex_hull.hpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/test_convex_hull.hpp	Tue Oct 22 16:07:27 2013	(r86400)
+++ trunk/libs/geometry/test/algorithms/test_convex_hull.hpp	2013-10-23 06:13:28 EDT (Wed, 23 Oct 2013)	(r86401)
@@ -9,6 +9,8 @@
 #ifndef BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
 #define BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
 
+#include <boost/variant/variant.hpp>
+
 #include <geometry_test_common.hpp>
 
 #include <boost/geometry/algorithms/convex_hull.hpp>
@@ -24,11 +26,10 @@
 
 
 template <typename Geometry, typename Hull>
-void test_convex_hull(Geometry const& geometry, Hull const& hull,
+void check_convex_hull(Geometry const& geometry, Hull const& hull,
                       std::size_t size_original, std::size_t size_hull,
                       double expected_area, bool reverse)
 {
-
     std::size_t n = bg::num_points(hull);
 
     BOOST_CHECK_MESSAGE(n == size_hull,
@@ -49,55 +50,67 @@
         ah = -ah;
     }
 
-//std::cout << "Area: " << bg::area(geometry) << std::endl;
-//std::cout << bg::wkt(hull) << std::endl;
-
     BOOST_CHECK_CLOSE(ah, expected_area, 0.001);
 }
 
-template <typename Geometry, bool Clockwise>
-void test_geometry_order(std::string const& wkt,
+template <typename Hull, typename Strategy, typename Geometry>
+void test_convex_hull(Geometry const& geometry,
                       std::size_t size_original, std::size_t size_hull,
-                      double expected_area)
+                      double expected_area,
+                      bool reverse)
 {
-    Geometry geometry;
-    bg::read_wkt(wkt, geometry);
-
-    bg::model::polygon
-        <
-            typename bg::point_type<Geometry>::type,
-            Clockwise
-        > hull;
+    Hull hull;
 
     // Test version with output iterator
     bg::detail::convex_hull::convex_hull_insert(geometry, std::back_inserter(hull.outer()));
-    test_convex_hull(geometry, hull,
-        size_original, size_hull, expected_area, ! Clockwise);
+    check_convex_hull(geometry, hull,
+        size_original, size_hull, expected_area, reverse);
 
     // Test version with ring as output
     bg::clear(hull);
     bg::convex_hull(geometry, hull.outer());
-    test_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
+    check_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
 
     // Test version with polygon as output
     bg::clear(hull);
     bg::convex_hull(geometry, hull);
-    test_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
+    check_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
 
     // Test version with strategy
     bg::clear(hull);
-    bg::strategy::convex_hull::graham_andrew
+    bg::convex_hull(geometry, hull.outer(), Strategy());
+    check_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
+
+    // Test version with output iterator and strategy
+    bg::clear(hull);
+    bg::detail::convex_hull::convex_hull_insert(geometry, std::back_inserter(hull.outer()), Strategy());
+    check_convex_hull(geometry, hull, size_original, size_hull, expected_area, reverse);
+}
+
+
+template <typename Geometry, bool Clockwise>
+void test_geometry_order(std::string const& wkt,
+                      std::size_t size_original, std::size_t size_hull,
+                      double expected_area)
+{
+    typedef bg::model::polygon
+        <
+            typename bg::point_type<Geometry>::type,
+            Clockwise
+        > hull_type;
+
+    typedef bg::strategy::convex_hull::graham_andrew
         <
             Geometry,
             typename bg::point_type<Geometry>::type
-        > graham;
-    bg::convex_hull(geometry, hull.outer(), graham);
-    test_convex_hull(geometry, hull, size_original, size_hull, expected_area, false);
+        > strategy_type;
 
-    // Test version with output iterator and strategy
-    bg::clear(hull);
-    bg::detail::convex_hull::convex_hull_insert(geometry, std::back_inserter(hull.outer()), graham);
-    test_convex_hull(geometry, hull, size_original, size_hull, expected_area, ! Clockwise);
+    Geometry geometry;
+    bg::read_wkt(wkt, geometry);
+    boost::variant<Geometry> v(geometry);
+
+    test_convex_hull<hull_type, strategy_type>(geometry, size_original, size_hull, expected_area, !Clockwise);
+    test_convex_hull<hull_type, strategy_type>(v, size_original, size_hull, expected_area, !Clockwise);
 }
 
 template <typename Geometry>