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 
operator ()ls_less41     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 {
operator ()ls_equal71     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>
get_max(T const & a,T const & b,T const & c)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>
check_close(T const & a,T const & b,T const & tol)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:
pt_equal(double tolerence)102     pt_equal(double tolerence) : m_tolerence(tolerence) {}
103 
operator ()(Point1 const & point1,Point2 const & point2) const104     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>
apply_to_rangemultilinestring_equals::unique125         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 
operator ()multilinestring_equals::unique132         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     {
operator ()multilinestring_equals::unique146         void operator()(MultiLinestring&, double)
147         {
148         }
149     };
150 
151     template <typename MultiLinestring1, typename MultiLinestring2>
152     static inline
applymultilinestring_equals153     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
isolated_point_to_segment(Linestring const & linestring,OutputIterator oit)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
convert_isolated_points_to_segments(MultiLinestring const & multilinestring,OutputIterator oit)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>
apply_base(MultiLinestring1 const & multilinestring1,MultiLinestring2 const & multilinestring2,double tolerance)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>
apply(MultiLinestring1 const & multilinestring1,MultiLinestring2 const & multilinestring2,double tolerance)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>
set_operation_output(std::string const & set_op_id,std::string const & caseid,G1 const & g1,G2 const & g2,Output const & output)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
382