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-2021.
7// Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
8
9// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
10// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
12
13// Use, modification and distribution is subject to the Boost Software License,
14// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15// http://www.boost.org/LICENSE_1_0.txt)
16
17#ifndef BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
18#define BOOST_GEOMETRY_TEST_CONVEX_HULL_HPP
19
20#include <geometry_test_common.hpp>
21
22#include <boost/geometry/algorithms/convex_hull.hpp>
23#include <boost/geometry/algorithms/area.hpp>
24#include <boost/geometry/algorithms/is_empty.hpp>
25#include <boost/geometry/algorithms/num_points.hpp>
26#include <boost/geometry/algorithms/perimeter.hpp>
27
28#include <boost/geometry/geometries/adapted/boost_variant.hpp>
29#include <boost/geometry/geometries/geometry_collection.hpp>
30#include <boost/geometry/geometries/linestring.hpp>
31
32#include <boost/geometry/strategies/strategies.hpp>
33#include <boost/geometry/strategies/spherical/side_by_cross_track.hpp>
34
35#include <boost/geometry/strategy/cartesian/precise_area.hpp>
36#include <boost/geometry/strategy/cartesian/side_by_triangle.hpp>
37#include <boost/geometry/strategy/cartesian/side_non_robust.hpp>
38#include <boost/geometry/strategy/cartesian/side_robust.hpp>
39#include <boost/geometry/strategy/cartesian/precise_area.hpp>
40
41#include <boost/geometry/io/wkt/wkt.hpp>
42
43#include <boost/geometry/geometries/polygon.hpp>
44
45
46struct robust_cartesian : boost::geometry::strategies::convex_hull::cartesian<>
47{
48 static auto side()
49 {
50 return boost::geometry::strategy::side::side_robust
51 <
52 double,
53 boost::geometry::strategy::side::fp_equals_policy
54 >();
55 }
56};
57
58struct non_robust_cartesian_fast : boost::geometry::strategies::convex_hull::cartesian<>
59{
60 static auto side()
61 {
62 return boost::geometry::strategy::side::side_non_robust<>();
63 }
64};
65
66struct non_robust_cartesian_sbt : boost::geometry::strategies::convex_hull::cartesian<>
67{
68 static auto side()
69 {
70 return boost::geometry::strategy::side::side_by_triangle<>();
71 }
72};
73
74template <typename CalculationType = void>
75struct sphrerical_side_by_cross_track : boost::geometry::strategies::convex_hull::spherical<>
76{
77 static auto side()
78 {
79 return boost::geometry::strategy::side::side_by_cross_track<>();
80 }
81};
82
83struct precise_cartesian : boost::geometry::strategies::area::cartesian<>
84{
85 // Technically this should be enabled only for non-boxes
86 template <typename Geometry>
87 static auto area(Geometry const&)
88 {
89 return boost::geometry::strategy::area::precise_cartesian<>();
90 }
91};
92
93
94template <typename Geometry, typename Hull, typename AreaStrategy>
95void check_convex_hull(Geometry const& geometry, Hull const& hull,
96 std::size_t /*size_original*/, std::size_t size_hull,
97 double expected_area, double expected_perimeter,
98 bool reverse, AreaStrategy area_strategy)
99{
100 std::size_t n = bg::num_points(hull);
101
102 BOOST_CHECK_MESSAGE(n == size_hull,
103 "convex hull: " << bg::wkt(geometry)
104 << " -> " << bg::wkt(hull)
105 << " type "
106 << (typeid(typename bg::coordinate_type<Hull>::type).name())
107 << " -> Expected: " << size_hull
108 << " detected: " << n);
109
110
111 // We omit this check as it is not important for the hull algorithm
112 // BOOST_CHECK(bg::num_points(geometry) == size_original);
113
114 auto ah = bg::area(hull, area_strategy);
115
116 if (reverse)
117 {
118 ah = -ah;
119 }
120
121 BOOST_CHECK_CLOSE(ah, expected_area, 0.001);
122
123 if ( expected_perimeter >= 0 )
124 {
125 auto ph = bg::perimeter(hull);
126
127 BOOST_CHECK_CLOSE(ph, expected_perimeter, 0.001);
128 }
129}
130
131
132template
133<
134 typename Hull,
135 typename Strategy,
136 typename AreaStrategy
137>
138struct test_convex_hull
139{
140 template <typename Geometry>
141 static void apply(Geometry const& geometry,
142 std::size_t size_original,
143 std::size_t size_hull_closed,
144 double expected_area,
145 double expected_perimeter,
146 bool )
147 {
148 static bool const is_hull_closed = bg::closure<Hull>::value != bg::open;
149 std::size_t const size_hull = is_hull_closed ? size_hull_closed :
150 size_hull_closed - 1;
151
152 Hull hull;
153 bg::convex_hull(geometry, hull.outer(), Strategy());
154
155 check_convex_hull(geometry, hull, size_original, size_hull,
156 expected_area, expected_perimeter, false, AreaStrategy());
157
158 bg::clear(hull);
159 bg::convex_hull(geometry, hull, Strategy());
160
161 using point_t = typename bg::point_type<Hull>::type;
162 using var_t = boost::variant<Hull, bg::model::linestring<point_t>, point_t>;
163 using gc_t = bg::model::geometry_collection<var_t>;
164
165 var_t var;
166 bg::convex_hull(geometry, var, Strategy());
167
168 gc_t gc;
169 bg::convex_hull(geometry, gc, Strategy());
170
171 BOOST_CHECK(var.which() == gc[0].which());
172
173 if (bg::detail::equals::equals_point_point(hull.outer()[0], hull.outer()[1], Strategy()))
174 BOOST_CHECK(gc[0].which() == 2); // GC stores point
175 else if (bg::detail::equals::equals_point_point(hull.outer()[0], hull.outer()[2], Strategy()))
176 BOOST_CHECK(gc[0].which() == 1); // GC stores linestring
177 else
178 BOOST_CHECK(gc[0].which() == 0); // GC stores polygon
179 }
180};
181
182
183template
184<
185 typename Hull,
186 typename AreaStrategy
187>
188struct test_convex_hull<Hull, robust_cartesian, AreaStrategy>
189{
190 template <typename Geometry>
191 static void apply(Geometry const& geometry,
192 std::size_t size_original,
193 std::size_t size_hull_closed,
194 double expected_area,
195 double expected_perimeter,
196 bool )
197 {
198 static bool const is_hull_closed = bg::closure<Hull>::value != bg::open;
199 std::size_t const size_hull = is_hull_closed ? size_hull_closed :
200 size_hull_closed - 1;
201
202 // Test version with ring as output
203 Hull hull;
204 bg::convex_hull(geometry, hull.outer());
205 check_convex_hull(geometry, hull, size_original, size_hull, expected_area,
206 expected_perimeter, false, AreaStrategy());
207
208 // Test version with polygon as output
209 bg::clear(hull);
210 bg::convex_hull(geometry, hull);
211 check_convex_hull(geometry, hull, size_original, size_hull, expected_area,
212 expected_perimeter, false, AreaStrategy());
213
214 // Test version with strategy
215 bg::clear(hull);
216 bg::convex_hull(geometry, hull.outer(), robust_cartesian());
217 check_convex_hull(geometry, hull, size_original, size_hull, expected_area,
218 expected_perimeter, false, AreaStrategy());
219 }
220};
221
222
223template
224<
225 typename Hull
226>
227struct test_convex_hull<Hull, robust_cartesian, precise_cartesian>
228{
229 template <typename Geometry>
230 static void apply(Geometry const& geometry,
231 std::size_t size_original,
232 std::size_t size_hull_closed,
233 double expected_area,
234 double expected_perimeter,
235 bool )
236 {
237 static bool const is_hull_closed = bg::closure<Hull>::value != bg::open;
238 std::size_t const size_hull = is_hull_closed ? size_hull_closed :
239 size_hull_closed - 1;
240
241 // Test version with strategy
242 Hull hull;
243 bg::convex_hull(geometry, hull.outer(), robust_cartesian());
244
245 check_convex_hull(geometry, hull, size_original, size_hull, expected_area,
246 expected_perimeter, false, precise_cartesian());
247 }
248};
249
250
251template
252<
253 typename Geometry,
254 typename Strategy,
255 typename AreaStrategy,
256 bool Clockwise,
257 bool Closed
258>
259void test_geometry_order(std::string const& wkt,
260 std::size_t size_original,
261 std::size_t size_hull_closed,
262 double expected_area,
263 double expected_perimeter = -1.0)
264{
265 typedef bg::model::polygon
266 <
267 typename bg::point_type<Geometry>::type,
268 Clockwise,
269 Closed
270 > hull_type;
271
272 Geometry geometry;
273 bg::read_wkt(wkt, geometry);
274
275 test_convex_hull<hull_type, Strategy, AreaStrategy>::apply(geometry, size_original,
276 size_hull_closed, expected_area, expected_perimeter, !Clockwise);
277
278 using variant_t = boost::variant<Geometry>;
279
280 variant_t v(geometry);
281 test_convex_hull<hull_type, Strategy, AreaStrategy>::apply(v, size_original,
282 size_hull_closed, expected_area, expected_perimeter, !Clockwise);
283
284 bg::model::geometry_collection<variant_t> gc = { v };
285 test_convex_hull<hull_type, Strategy, AreaStrategy>::apply(gc, size_original,
286 size_hull_closed, expected_area, expected_perimeter, !Clockwise);
287}
288
289template
290<
291 typename Geometry,
292 typename Strategy,
293 typename AreaStrategy = typename bg::strategies::area::services::default_strategy
294 <
295 Geometry
296 >::type
297>
298void test_geometry(std::string const& wkt,
299 std::size_t size_original,
300 std::size_t size_hull_closed,
301 double expected_area,
302 double expected_perimeter = -1.0)
303{
304 test_geometry_order<Geometry, Strategy, AreaStrategy, true, true>(
305 wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
306 test_geometry_order<Geometry, Strategy, AreaStrategy, false, true>(
307 wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
308 test_geometry_order<Geometry, Strategy, AreaStrategy, true, false>(
309 wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
310 test_geometry_order<Geometry, Strategy, AreaStrategy, false, false>(
311 wkt, size_original, size_hull_closed, expected_area, expected_perimeter);
312}
313
314template <class SGeometry, class GGeometry>
315void test_geometry_sph_geo(std::string const& wkt,
316 std::size_t size_original,
317 std::size_t size_hull_closed,
318 double spherical_expected_area,
319 double geographic_expected_area)
320{
321 typedef boost::geometry::strategies::convex_hull::spherical<> SphericalStrategy;
322 test_geometry<SGeometry, SphericalStrategy>(wkt, size_original,
323 size_hull_closed, spherical_expected_area);
324
325 typedef boost::geometry::strategies::convex_hull::geographic<> GeoStrategy;
326 test_geometry<GGeometry, GeoStrategy>(wkt, size_original,
327 size_hull_closed, geographic_expected_area);
328}
329
330
331template <typename Geometry>
332void test_empty_input()
333{
334 Geometry geometry;
335 bg::model::polygon
336 <
337 typename bg::point_type<Geometry>::type
338 > hull;
339
340 bg::convex_hull(geometry, hull);
341 BOOST_CHECK_MESSAGE(bg::is_empty(hull), "Output convex hull should be empty" );
342}
343
344
345#endif
346

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

source code of boost/libs/geometry/test/algorithms/convex_hull/test_convex_hull.hpp