]>
Commit | Line | Data |
---|---|---|
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) | |
2 | ||
3 | // Copyright (c) 2014-2015, Oracle and/or its affiliates. | |
4 | ||
5 | // Licensed under the Boost Software License version 1.0. | |
6 | // http://www.boost.org/users/license.html | |
7 | ||
8 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP | |
11 | #define BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP | |
12 | ||
13 | ||
14 | #include <string> | |
15 | #include <fstream> | |
16 | #include <sstream> | |
17 | #include <algorithm> | |
18 | ||
19 | #include <boost/core/ignore_unused.hpp> | |
20 | #include <boost/range.hpp> | |
21 | #include <boost/typeof/typeof.hpp> | |
22 | ||
23 | #include <boost/geometry/policies/compare.hpp> | |
24 | #include <boost/geometry/algorithms/equals.hpp> | |
25 | #include <boost/geometry/algorithms/reverse.hpp> | |
26 | ||
27 | #include "test_get_turns_ll_invariance.hpp" | |
28 | ||
29 | namespace bg = ::boost::geometry; | |
30 | ||
31 | ||
32 | ||
33 | template <typename Linestring1, typename Linestring2> | |
34 | struct ls_less | |
35 | { | |
36 | typedef typename boost::range_iterator<Linestring1 const>::type Iterator1; | |
37 | typedef typename boost::range_iterator<Linestring2 const>::type Iterator2; | |
38 | ||
39 | typedef bg::less<typename bg::point_type<Linestring1>::type> point_less; | |
40 | ||
41 | bool operator()(Linestring1 const& linestring1, | |
42 | Linestring2 const& linestring2) const | |
43 | { | |
44 | if (boost::size(linestring1) != boost::size(linestring2)) | |
45 | { | |
46 | return boost::size(linestring1) < boost::size(linestring2); | |
47 | } | |
48 | ||
49 | Iterator1 it1 = boost::begin(linestring1); | |
50 | Iterator2 it2 = boost::begin(linestring2); | |
51 | point_less less; | |
52 | for (; it1 != boost::end(linestring1); ++it1, ++it2) | |
53 | { | |
54 | if (less(*it1, *it2)) | |
55 | { | |
56 | return true; | |
57 | } | |
58 | if (less(*it2, *it1)) | |
59 | { | |
60 | return false; | |
61 | } | |
62 | } | |
63 | return false; | |
64 | } | |
65 | }; | |
66 | ||
67 | ||
68 | template <typename Linestring1, typename Linestring2> | |
69 | struct ls_equal | |
70 | { | |
71 | bool operator()(Linestring1 const& linestring1, | |
72 | Linestring2 const& linestring2) const | |
73 | { | |
74 | ls_less<Linestring1, Linestring2> less; | |
75 | ||
76 | return ! less(linestring1, linestring2) | |
77 | && ! less(linestring2, linestring1); | |
78 | } | |
79 | }; | |
80 | ||
81 | ||
82 | template <typename Point1, typename Point2> | |
83 | class pt_equal | |
84 | { | |
85 | private: | |
86 | double m_tolerence; | |
87 | ||
88 | template <typename T> | |
89 | static inline T const& get_max(T const& a, T const& b, T const& c) | |
90 | { | |
91 | return (std::max)((std::max)(a, b), c); | |
92 | } | |
93 | ||
94 | template <typename T> | |
95 | static inline bool check_close(T const& a, T const& b, T const& tol) | |
96 | { | |
97 | return (a == b) | |
98 | || (std::abs(a - b) <= tol * get_max(std::abs(a), std::abs(b), 1.0)); | |
99 | } | |
100 | ||
101 | public: | |
102 | pt_equal(double tolerence) : m_tolerence(tolerence) {} | |
103 | ||
104 | bool operator()(Point1 const& point1, Point2 const& point2) const | |
105 | { | |
106 | // allow for some tolerence in testing equality of points | |
107 | return check_close(bg::get<0>(point1), bg::get<0>(point2), m_tolerence) | |
108 | && check_close(bg::get<1>(point1), bg::get<1>(point2), m_tolerence); | |
109 | } | |
110 | }; | |
111 | ||
112 | ||
113 | template <bool EnableUnique = false> | |
114 | struct multilinestring_equals | |
115 | { | |
116 | template <typename MultiLinestring, bool Enable> | |
117 | struct unique | |
118 | { | |
119 | typedef typename boost::range_value<MultiLinestring>::type Linestring; | |
120 | typedef typename bg::point_type<MultiLinestring>::type point_type; | |
121 | typedef ls_equal<Linestring, Linestring> linestring_equal; | |
122 | typedef pt_equal<point_type, point_type> point_equal; | |
123 | ||
124 | template <typename Range, typename EqualTo> | |
125 | void apply_to_range(Range& range, EqualTo const& equal_to) | |
126 | { | |
127 | range.erase(std::unique(boost::begin(range), boost::end(range), | |
128 | equal_to), | |
129 | boost::end(range)); | |
130 | } | |
131 | ||
132 | void operator()(MultiLinestring& mls, double tolerance) | |
133 | { | |
134 | for (typename boost::range_iterator<MultiLinestring>::type it | |
135 | = boost::begin(mls); it != boost::end(mls); ++it) | |
136 | { | |
137 | apply_to_range(*it, point_equal(tolerance)); | |
138 | } | |
139 | apply_to_range(mls, linestring_equal()); | |
140 | } | |
141 | }; | |
142 | ||
143 | template <typename MultiLinestring> | |
144 | struct unique<MultiLinestring, false> | |
145 | { | |
146 | void operator()(MultiLinestring&, double) | |
147 | { | |
148 | } | |
149 | }; | |
150 | ||
151 | template <typename MultiLinestring1, typename MultiLinestring2> | |
152 | static inline | |
153 | bool apply(MultiLinestring1 const& multilinestring1, | |
154 | MultiLinestring2 const& multilinestring2, | |
155 | double tolerance) | |
156 | { | |
157 | typedef typename boost::range_iterator | |
158 | < | |
159 | MultiLinestring1 const | |
160 | >::type ls1_iterator; | |
161 | ||
162 | typedef typename boost::range_iterator | |
163 | < | |
164 | MultiLinestring2 const | |
165 | >::type ls2_iterator; | |
166 | ||
167 | typedef typename boost::range_value<MultiLinestring1>::type Linestring1; | |
168 | ||
169 | typedef typename boost::range_value<MultiLinestring2>::type Linestring2; | |
170 | ||
171 | typedef typename boost::range_iterator | |
172 | < | |
173 | Linestring1 const | |
174 | >::type point1_iterator; | |
175 | ||
176 | typedef typename boost::range_iterator | |
177 | < | |
178 | Linestring2 const | |
179 | >::type point2_iterator; | |
180 | ||
181 | typedef ls_less<Linestring1, Linestring2> linestring_less; | |
182 | ||
183 | typedef pt_equal | |
184 | < | |
185 | typename boost::range_value | |
186 | < | |
187 | typename boost::range_value<MultiLinestring1>::type | |
188 | >::type, | |
189 | typename boost::range_value | |
190 | < | |
191 | typename boost::range_value<MultiLinestring2>::type | |
192 | >::type | |
193 | > point_equal; | |
194 | ||
195 | ||
196 | MultiLinestring1 mls1 = multilinestring1; | |
197 | MultiLinestring2 mls2 = multilinestring2; | |
198 | ||
199 | std::sort(boost::begin(mls1), boost::end(mls1), linestring_less()); | |
200 | std::sort(boost::begin(mls2), boost::end(mls2), linestring_less()); | |
201 | ||
202 | unique<MultiLinestring1, EnableUnique>()(mls1, tolerance); | |
203 | unique<MultiLinestring2, EnableUnique>()(mls2, tolerance); | |
204 | ||
205 | if (boost::size(mls1) != boost::size(mls2)) | |
206 | { | |
207 | return false; | |
208 | } | |
209 | ||
210 | ls1_iterator it1 = boost::begin(mls1); | |
211 | ls2_iterator it2 = boost::begin(mls2); | |
212 | for (; it1 != boost::end(mls1); ++it1, ++it2) | |
213 | { | |
214 | if (boost::size(*it1) != boost::size(*it2)) | |
215 | { | |
216 | return false; | |
217 | } | |
218 | point1_iterator pit1 = boost::begin(*it1); | |
219 | point2_iterator pit2 = boost::begin(*it2); | |
220 | for (; pit1 != boost::end(*it1); ++pit1, ++pit2) | |
221 | { | |
222 | if (! point_equal(tolerance)(*pit1, *pit2)) | |
223 | { | |
224 | return false; | |
225 | } | |
226 | } | |
227 | } | |
228 | return true; | |
229 | } | |
230 | }; | |
231 | ||
232 | ||
233 | ||
234 | ||
235 | class equals | |
236 | { | |
237 | private: | |
238 | template <typename Linestring, typename OutputIterator> | |
239 | static inline OutputIterator | |
240 | isolated_point_to_segment(Linestring const& linestring, OutputIterator oit) | |
241 | { | |
242 | BOOST_ASSERT( boost::size(linestring) == 1 ); | |
243 | ||
244 | *oit++ = *boost::begin(linestring); | |
245 | *oit++ = *boost::begin(linestring); | |
246 | return oit; | |
247 | } | |
248 | ||
249 | ||
250 | template <typename MultiLinestring, typename OutputIterator> | |
251 | static inline OutputIterator | |
252 | convert_isolated_points_to_segments(MultiLinestring const& multilinestring, | |
253 | OutputIterator oit) | |
254 | { | |
255 | BOOST_AUTO_TPL(it, boost::begin(multilinestring)); | |
256 | ||
257 | for (; it != boost::end(multilinestring); ++it) | |
258 | { | |
259 | if (boost::size(*it) == 1) | |
260 | { | |
261 | typename boost::range_value<MultiLinestring>::type linestring; | |
262 | isolated_point_to_segment(*it, std::back_inserter(linestring)); | |
263 | *oit++ = linestring; | |
264 | } | |
265 | else | |
266 | { | |
267 | *oit++ = *it; | |
268 | } | |
269 | } | |
270 | return oit; | |
271 | } | |
272 | ||
273 | ||
274 | template <typename MultiLinestring1, typename MultiLinestring2> | |
275 | static inline bool apply_base(MultiLinestring1 const& multilinestring1, | |
276 | MultiLinestring2 const& multilinestring2, | |
277 | double tolerance) | |
278 | { | |
279 | typedef multilinestring_equals<true> mls_equals; | |
280 | ||
281 | if (mls_equals::apply(multilinestring1, multilinestring2, tolerance)) | |
282 | { | |
283 | return true; | |
284 | } | |
285 | ||
286 | MultiLinestring1 reverse_multilinestring1 = multilinestring1; | |
287 | bg::reverse(reverse_multilinestring1); | |
288 | if (mls_equals::apply(reverse_multilinestring1, | |
289 | multilinestring2, | |
290 | tolerance)) | |
291 | { | |
292 | return true; | |
293 | } | |
294 | ||
295 | MultiLinestring2 reverse_multilinestring2 = multilinestring2; | |
296 | bg::reverse(reverse_multilinestring2); | |
297 | if (mls_equals::apply(multilinestring1, | |
298 | reverse_multilinestring2, | |
299 | tolerance)) | |
300 | { | |
301 | return true; | |
302 | } | |
303 | ||
304 | return mls_equals::apply(reverse_multilinestring1, | |
305 | reverse_multilinestring2, | |
306 | tolerance); | |
307 | } | |
308 | ||
309 | ||
310 | ||
311 | public: | |
312 | template <typename MultiLinestring1, typename MultiLinestring2> | |
313 | static inline bool apply(MultiLinestring1 const& multilinestring1, | |
314 | MultiLinestring2 const& multilinestring2, | |
315 | double tolerance) | |
316 | { | |
317 | #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS | |
318 | MultiLinestring1 converted_multilinestring1; | |
319 | convert_isolated_points_to_segments | |
320 | (multilinestring1, std::back_inserter(converted_multilinestring1)); | |
321 | MultiLinestring2 converted_multilinestring2; | |
322 | convert_isolated_points_to_segments | |
323 | (multilinestring2, std::back_inserter(converted_multilinestring2)); | |
324 | return apply_base(converted_multilinestring1, | |
325 | converted_multilinestring2, tolerance); | |
326 | #else | |
327 | return apply_base(multilinestring1, multilinestring2, tolerance); | |
328 | #endif | |
329 | } | |
330 | }; | |
331 | ||
332 | ||
333 | ||
334 | ||
335 | template <typename Output, typename G1, typename G2> | |
336 | void set_operation_output(std::string const& set_op_id, | |
337 | std::string const& caseid, | |
338 | G1 const& g1, G2 const& g2, | |
339 | Output const& output) | |
340 | { | |
341 | boost::ignore_unused(set_op_id, caseid, g1, g2, output); | |
342 | ||
343 | #if defined(TEST_WITH_SVG) | |
344 | typedef typename bg::coordinate_type<G1>::type coordinate_type; | |
345 | typedef typename bg::point_type<G1>::type point_type; | |
346 | ||
347 | std::ostringstream filename; | |
348 | filename << "svgs/" << set_op_id << "_" << caseid << ".svg"; | |
349 | ||
350 | std::ofstream svg(filename.str().c_str()); | |
351 | ||
352 | bg::svg_mapper<point_type> mapper(svg, 500, 500); | |
353 | ||
354 | mapper.add(g1); | |
355 | mapper.add(g2); | |
356 | ||
357 | mapper.map(g2, "stroke-opacity:1;stroke:rgb(153,204,0);stroke-width:4"); | |
358 | mapper.map(g1, "stroke-opacity:1;stroke:rgb(51,51,153);stroke-width:2"); | |
359 | ||
360 | BOOST_AUTO_TPL(it, output.begin()); | |
361 | for (; it != output.end(); ++it) | |
362 | { | |
363 | if ( boost::size(*it) == 2 | |
364 | && bg::equals(*boost::begin(*it), *++boost::begin(*it)) ) | |
365 | { | |
366 | // draw isolated points (generated by the intersection operation) | |
367 | mapper.map(*boost::begin(*it), | |
368 | "fill:rgb(255,0,255);stroke:rgb(0,0,0);stroke-width:1", | |
369 | 4); | |
370 | } | |
371 | else | |
372 | { | |
373 | mapper.map(*it, | |
374 | "stroke-opacity:0.4;stroke:rgb(255,0,255);stroke-width:8"); | |
375 | } | |
376 | } | |
377 | #endif | |
378 | } | |
379 | ||
380 | ||
381 | #endif // BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP |