ceph/src/boost/libs/geometry/test/algorithms/test_convex_hull.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   5
   6 // This file was modified by Oracle on 2014, 2015.
   7 // Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  11
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #ifndef BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
  17 #define BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
  18
  19 #include <boost/variant/variant.hpp>
  20
  21 #include <geometry_test_common.hpp>
  22
  23 #include <boost/geometry/algorithms/convex_hull.hpp>
  24 #include <boost/geometry/algorithms/area.hpp>
  25 #include <boost/geometry/algorithms/is_empty.hpp>
  26 #include <boost/geometry/algorithms/num_points.hpp>
  27 #include <boost/geometry/algorithms/perimeter.hpp>
  28
  29 #include <boost/geometry/strategies/strategies.hpp>
  30
  31 #include <boost/geometry/io/wkt/wkt.hpp>
  32
  33 #include <boost/geometry/geometries/polygon.hpp>
  34
  35
  36 template <typename Geometry, typename Hull>
  37 void check_convex_hull(Geometry const& geometry, Hull const& hull,
  38                       std::size_t /*size_original*/, std::size_t size_hull,
  39                       double expected_area, double expected_perimeter,
  40                       bool reverse)
  41 {
  42     std::size_t n = bg::num_points(hull);
  43
  44     BOOST_CHECK_MESSAGE(n == size_hull,
  45         "convex hull: " << bg::wkt(geometry)
  46         << " -> " << bg::wkt(hull)
  47         << " type "
  48         << (typeid(typename bg::coordinate_type<Hull>::type).name())
  49         << " -> Expected: " << size_hull
  50         << " detected: " << n);
  51
  52
  53     // We omit this check as it is not important for the hull algorithm
  54     // BOOST_CHECK(bg::num_points(geometry) == size_original);
  55
  56     typename bg::default_area_result<Geometry>::type ah = bg::area(hull);
  57     if (reverse)
  58     {
  59         ah = -ah;
  60     }
  61
  62     BOOST_CHECK_CLOSE(ah, expected_area, 0.001);
  63
  64     if ( expected_perimeter >= 0 )
  65     {
  66         typename bg::default_length_result<Geometry>::type
  67             ph = bg::perimeter(hull);
  68
  69         BOOST_CHECK_CLOSE(ph, expected_perimeter, 0.001);
  70     }
  71 }
  72
  73 namespace resolve_variant {
  74
  75 struct closure_visitor : public boost::static_visitor<bg::closure_selector>
  76 {
  77     template <typename Geometry>
  78     bg::closure_selector operator()(Geometry const&) const
  79     {
  80         return bg::closure<Geometry>::value;
  81     }
  82 };
  83
  84 template <typename Geometry>
  85 inline bg::closure_selector get_closure(Geometry const&)
  86 {
  87     return bg::closure<Geometry>::value;
  88 }
  89
  90 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
  91 inline bg::closure_selector get_closure(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& v)
  92 {
  93     return boost::apply_visitor(closure_visitor(), v);
  94 }
  95
  96 } // namespace resolve_variant
  97
  98 template <typename Hull, typename Strategy, typename Geometry>
  99 void test_convex_hull(Geometry const& geometry,
 100                       std::size_t size_original, std::size_t size_hull_closed,
 101                       double expected_area, double expected_perimeter,
 102                       bool reverse)
 103 {
 104     bool const is_original_closed = resolve_variant::get_closure(geometry) != bg::open;
 105     static bool const is_hull_closed = bg::closure<Hull>::value != bg::open;
 106
 107     // convex_hull_insert() uses the original Geometry as a source of the info about the order and closure
 108     std::size_t const size_hull_from_orig = is_original_closed ? size_hull_closed : size_hull_closed - 1;
 109     std::size_t const size_hull = is_hull_closed ? size_hull_closed : size_hull_closed - 1;
 110
 111     Hull hull;
 112
 113     // Test version with output iterator
 114     bg::detail::convex_hull::convex_hull_insert(geometry, std::back_inserter(hull.outer()));
 115     check_convex_hull(geometry, hull, size_original, size_hull_from_orig, expected_area, expected_perimeter, reverse);
 116
 117     // Test version with ring as output
 118     bg::clear(hull);
 119     bg::convex_hull(geometry, hull.outer());
 120     check_convex_hull(geometry, hull, size_original, size_hull, expected_area, expected_perimeter, false);
 121
 122     // Test version with polygon as output
 123     bg::clear(hull);
 124     bg::convex_hull(geometry, hull);
 125     check_convex_hull(geometry, hull, size_original, size_hull, expected_area, expected_perimeter, false);
 126
 127     // Test version with strategy
 128     bg::clear(hull);
 129     bg::convex_hull(geometry, hull.outer(), Strategy());
 130     check_convex_hull(geometry, hull, size_original, size_hull, expected_area, expected_perimeter, false);
 131
 132     // Test version with output iterator and strategy
 133     bg::clear(hull);
 134     bg::detail::convex_hull::convex_hull_insert(geometry, std::back_inserter(hull.outer()), Strategy());
 135     check_convex_hull(geometry, hull, size_original, size_hull_from_orig, expected_area, expected_perimeter, reverse);
 136 }
 137
 138
 139 template <typename Geometry, bool Clockwise, bool Closed>
 140 void test_geometry_order(std::string const& wkt,
 141                       std::size_t size_original, std::size_t size_hull_closed,
 142                       double expected_area, double expected_perimeter = -1.0)
 143 {
 144     typedef bg::model::polygon
 145         <
 146             typename bg::point_type<Geometry>::type,
 147             Clockwise,
 148             Closed
 149         > hull_type;
 150
 151     typedef bg::strategy::convex_hull::graham_andrew
 152         <
 153             Geometry,
 154             typename bg::point_type<Geometry>::type
 155         > strategy_type;
 156
 157     Geometry geometry;
 158     bg::read_wkt(wkt, geometry);
 159     boost::variant<Geometry> v(geometry);
 160
 161     test_convex_hull<hull_type, strategy_type>(geometry, size_original, size_hull_closed, expected_area, expected_perimeter, !Clockwise);
 162     test_convex_hull<hull_type, strategy_type>(v, size_original, size_hull_closed, expected_area, expected_perimeter, !Clockwise);
 163 }
 164
 165 template <typename Geometry>
 166 void test_geometry(std::string const& wkt,
 167                       std::size_t size_original, std::size_t size_hull_closed,
 168                       double expected_area, double expected_perimeter = -1.0)
 169 {
 170     test_geometry_order<Geometry, true, true>(wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
 171     test_geometry_order<Geometry, false, true>(wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
 172     test_geometry_order<Geometry, true, false>(wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
 173     test_geometry_order<Geometry, false, false>(wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
 174 }
 175
 176 template <typename Geometry>
 177 void test_empty_input()
 178 {
 179     Geometry geometry;
 180     bg::model::polygon
 181         <
 182             typename bg::point_type<Geometry>::type
 183         > hull;
 184
 185     bg::convex_hull(geometry, hull);
 186     BOOST_CHECK_MESSAGE(bg::is_empty(hull), "Output convex hull should be empty" );
 187 }
 188
 189
 190
 191 #endif