]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |