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>
check_convex_hull(Geometry const & geometry,Hull const & hull,std::size_t,std::size_t size_hull,double expected_area,double expected_perimeter,bool reverse)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>
operator ()resolve_variant::closure_visitor78 bg::closure_selector operator()(Geometry const&) const
79 {
80 return bg::closure<Geometry>::value;
81 }
82 };
83
84 template <typename Geometry>
get_closure(Geometry const &)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)>
get_closure(boost::variant<BOOST_VARIANT_ENUM_PARAMS (T)> const & v)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>
test_convex_hull(Geometry const & geometry,std::size_t size_original,std::size_t size_hull_closed,double expected_area,double expected_perimeter,bool reverse)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>
test_geometry_order(std::string const & wkt,std::size_t size_original,std::size_t size_hull_closed,double expected_area,double expected_perimeter=-1.0)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>
test_geometry(std::string const & wkt,std::size_t size_original,std::size_t size_hull_closed,double expected_area,double expected_perimeter=-1.0)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>
test_empty_input()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
192