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 2015, 2016, 2017.
7 // Modifications copyright (c) 2015-2017 Oracle and/or its affiliates.
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_TEST_UNION_HPP
16 #define BOOST_GEOMETRY_TEST_UNION_HPP
17
18 #include <fstream>
19
20 #include <geometry_test_common.hpp>
21 #include <algorithms/check_validity.hpp>
22 #include "../setop_output_type.hpp"
23
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/foreach.hpp>
26 #include <boost/range/algorithm/copy.hpp>
27
28 #include <boost/geometry/algorithms/union.hpp>
29
30 #include <boost/geometry/algorithms/area.hpp>
31 #include <boost/geometry/algorithms/correct.hpp>
32 #include <boost/geometry/algorithms/is_empty.hpp>
33 #include <boost/geometry/algorithms/length.hpp>
34 #include <boost/geometry/algorithms/num_points.hpp>
35 #include <boost/geometry/algorithms/is_valid.hpp>
36
37 #include <boost/geometry/geometries/geometries.hpp>
38
39 #include <boost/geometry/strategies/strategies.hpp>
40
41 #include <boost/geometry/io/wkt/wkt.hpp>
42
43
44 #if defined(TEST_WITH_SVG)
45 # include <boost/geometry/io/svg/svg_mapper.hpp>
46 #endif
47
48 struct ut_settings : public ut_base_settings
49 {
ut_settingsut_settings50 ut_settings()
51 : percentage(0.001)
52 {}
53
54 double percentage;
55 };
56
57 #if defined(BOOST_GEOMETRY_TEST_CHECK_VALID_INPUT)
58 template <typename Geometry>
check_input_validity(std::string const & caseid,int case_index,Geometry const & geometry)59 inline void check_input_validity(std::string const& caseid, int case_index,
60 Geometry const& geometry)
61 {
62 std::string message;
63 if (!bg::is_valid(geometry, message))
64 {
65 std::cout << caseid << " Input ["
66 << case_index << "] not valid" << std::endl
67 << " (" << message << ")" << std::endl;
68 }
69 }
70 #endif
71
72
73
74 template <typename Range>
num_points(Range const & rng,bool add_for_open=false)75 inline std::size_t num_points(Range const& rng, bool add_for_open = false)
76 {
77 std::size_t result = 0;
78 for (typename boost::range_iterator<Range const>::type it = boost::begin(rng);
79 it != boost::end(rng); ++it)
80 {
81 result += bg::num_points(*it, add_for_open);
82 }
83 return result;
84 }
85
86 template <typename OutputType, typename G1, typename G2>
test_union(std::string const & caseid,G1 const & g1,G2 const & g2,int expected_count,int expected_hole_count,int expected_point_count,double expected_area,ut_settings const & settings)87 void test_union(std::string const& caseid, G1 const& g1, G2 const& g2,
88 int expected_count, int expected_hole_count,
89 int expected_point_count, double expected_area,
90 ut_settings const& settings)
91 {
92 typedef typename bg::coordinate_type<G1>::type coordinate_type;
93 boost::ignore_unused<coordinate_type>();
94 boost::ignore_unused(expected_point_count);
95
96 // Declare output (vector of rings or multi_polygon)
97 typedef typename setop_output_type<OutputType>::type result_type;
98 result_type clip;
99
100 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
101 std::cout << "*** UNION " << caseid << std::endl;
102 #endif
103
104 #if defined(BOOST_GEOMETRY_TEST_CHECK_VALID_INPUT)
105 check_input_validity(caseid, 0, g1);
106 check_input_validity(caseid, 1, g2);
107 #endif
108
109 // Check normal behaviour
110 bg::union_(g1, g2, clip);
111
112 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
113 {
114 // Check strategy passed explicitly
115 result_type clip_s;
116 typedef typename bg::strategy::intersection::services::default_strategy
117 <
118 typename bg::cs_tag<OutputType>::type
119 >::type strategy_type;
120 bg::union_(g1, g2, clip_s, strategy_type());
121 BOOST_CHECK_EQUAL(num_points(clip), num_points(clip_s));
122 }
123 #endif
124
125 if (settings.test_validity())
126 {
127 std::string message;
128 bool const valid = check_validity<result_type>::apply(clip, caseid, g1, g2, message);
129 BOOST_CHECK_MESSAGE(valid,
130 "union: " << caseid << " not valid: " << message
131 << " type: " << (type_for_assert_message<G1, G2>()));
132 }
133
134 typename bg::default_area_result<OutputType>::type area = 0;
135 std::size_t n = 0;
136 std::size_t holes = 0;
137 for (typename result_type::iterator it = clip.begin();
138 it != clip.end(); ++it)
139 {
140 area += bg::area(*it);
141 holes += bg::num_interior_rings(*it);
142 n += bg::num_points(*it, true);
143 }
144
145
146 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
147 {
148 // Test inserter functionality
149 // Test if inserter returns output-iterator (using Boost.Range copy)
150 result_type inserted, array_with_one_empty_geometry;
151 array_with_one_empty_geometry.push_back(OutputType());
152 boost::copy(array_with_one_empty_geometry, bg::detail::union_::union_insert<OutputType>(g1, g2, std::back_inserter(inserted)));
153
154 typename bg::default_area_result<OutputType>::type area_inserted = 0;
155 int index = 0;
156 for (typename result_type::iterator it = inserted.begin();
157 it != inserted.end();
158 ++it, ++index)
159 {
160 // Skip the empty polygon created above to avoid the empty_input_exception
161 if (! bg::is_empty(*it))
162 {
163 area_inserted += bg::area(*it);
164 }
165 }
166 BOOST_CHECK_EQUAL(boost::size(clip), boost::size(inserted) - 1);
167 BOOST_CHECK_CLOSE(area_inserted, expected_area, settings.percentage);
168 }
169 #endif
170
171
172
173 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
174 std::cout << "*** case: " << caseid
175 << " area: " << area
176 << " points: " << n
177 << " polygons: " << boost::size(clip)
178 << " holes: " << holes
179 << std::endl;
180 #endif
181
182 BOOST_CHECK_MESSAGE(expected_count < 0 || int(clip.size()) == expected_count,
183 "union: " << caseid
184 << " #clips expected: " << expected_count
185 << " detected: " << clip.size()
186 << " type: " << (type_for_assert_message<G1, G2>())
187 );
188
189 BOOST_CHECK_MESSAGE(expected_hole_count < 0 || int(holes) == expected_hole_count,
190 "union: " << caseid
191 << " #holes expected: " << expected_hole_count
192 << " detected: " << holes
193 << " type: " << (type_for_assert_message<G1, G2>())
194 );
195
196 #if defined(BOOST_GEOMETRY_USE_RESCALING)
197 // Without rescaling, point count might easily differ (which is no problem)
198 BOOST_CHECK_MESSAGE(expected_point_count < 0 || std::abs(int(n) - expected_point_count) < 3,
199 "union: " << caseid
200 << " #points expected: " << expected_point_count
201 << " detected: " << n
202 << " type: " << (type_for_assert_message<G1, G2>())
203 );
204 #endif
205
206 BOOST_CHECK_CLOSE(area, expected_area, settings.percentage);
207
208 #if defined(TEST_WITH_SVG)
209 {
210 bool const ccw =
211 bg::point_order<G1>::value == bg::counterclockwise
212 || bg::point_order<G2>::value == bg::counterclockwise;
213 bool const open =
214 bg::closure<G1>::value == bg::open
215 || bg::closure<G2>::value == bg::open;
216
217 std::ostringstream filename;
218 filename << "union_"
219 << caseid << "_"
220 << string_from_type<coordinate_type>::name()
221 << (ccw ? "_ccw" : "")
222 << (open ? "_open" : "")
223 #if defined(BOOST_GEOMETRY_USE_RESCALING)
224 << "_rescaled"
225 #endif
226 << ".svg";
227
228 std::ofstream svg(filename.str().c_str());
229
230 bg::svg_mapper
231 <
232 typename bg::point_type<G2>::type
233 > mapper(svg, 500, 500);
234 mapper.add(g1);
235 mapper.add(g2);
236
237 mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
238 "stroke:rgb(153,204,0);stroke-width:3");
239 mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
240 "stroke:rgb(51,51,153);stroke-width:3");
241 //mapper.map(g1, "opacity:0.6;fill:rgb(0,0,255);stroke:rgb(0,0,0);stroke-width:1");
242 //mapper.map(g2, "opacity:0.6;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
243
244 for (typename result_type::const_iterator it = clip.begin();
245 it != clip.end(); ++it)
246 {
247 mapper.map(*it, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
248 "stroke:rgb(255,0,255);stroke-width:8");
249 //mapper.map(*it, "opacity:0.6;fill:none;stroke:rgb(255,0,0);stroke-width:5");
250 }
251 }
252 #endif
253 }
254
255 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,int expected_count,int expected_hole_count,int expected_point_count,double expected_area,ut_settings const & settings=ut_settings ())256 void test_one(std::string const& caseid,
257 std::string const& wkt1, std::string const& wkt2,
258 int expected_count, int expected_hole_count,
259 int expected_point_count, double expected_area,
260 ut_settings const& settings = ut_settings())
261 {
262 G1 g1;
263 bg::read_wkt(wkt1, g1);
264
265 G2 g2;
266 bg::read_wkt(wkt2, g2);
267
268 // Reverse/close if necessary (e.g. G1/G2 are ccw and/or open)
269 bg::correct(g1);
270 bg::correct(g2);
271
272 test_union<OutputType>(caseid, g1, g2,
273 expected_count, expected_hole_count, expected_point_count,
274 expected_area, settings);
275 }
276
277 #endif
278