1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
5 // Licensed under the Boost Software License version 1.0.
6 // http://www.boost.org/users/license.html
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 #ifndef BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP
11 #define BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP
19 #include <boost/core/ignore_unused.hpp>
20 #include <boost/range.hpp>
21 #include <boost/typeof/typeof.hpp>
23 #include <boost/geometry/policies/compare.hpp>
24 #include <boost/geometry/algorithms/equals.hpp>
25 #include <boost/geometry/algorithms/reverse.hpp>
27 #include "test_get_turns_ll_invariance.hpp"
29 namespace bg = ::boost::geometry;
33 template <typename Linestring1, typename Linestring2>
36 typedef typename boost::range_iterator<Linestring1 const>::type Iterator1;
37 typedef typename boost::range_iterator<Linestring2 const>::type Iterator2;
39 typedef bg::less<typename bg::point_type<Linestring1>::type> point_less;
41 bool operator()(Linestring1 const& linestring1,
42 Linestring2 const& linestring2) const
44 if (boost::size(linestring1) != boost::size(linestring2))
46 return boost::size(linestring1) < boost::size(linestring2);
49 Iterator1 it1 = boost::begin(linestring1);
50 Iterator2 it2 = boost::begin(linestring2);
52 for (; it1 != boost::end(linestring1); ++it1, ++it2)
68 template <typename Linestring1, typename Linestring2>
71 bool operator()(Linestring1 const& linestring1,
72 Linestring2 const& linestring2) const
74 ls_less<Linestring1, Linestring2> less;
76 return ! less(linestring1, linestring2)
77 && ! less(linestring2, linestring1);
82 template <typename Point1, typename Point2>
89 static inline T const& get_max(T const& a, T const& b, T const& c)
91 return (std::max)((std::max)(a, b), c);
95 static inline bool check_close(T const& a, T const& b, T const& tol)
98 || (std::abs(a - b) <= tol * get_max(std::abs(a), std::abs(b), 1.0));
102 pt_equal(double tolerence) : m_tolerence(tolerence) {}
104 bool operator()(Point1 const& point1, Point2 const& point2) const
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);
113 template <bool EnableUnique = false>
114 struct multilinestring_equals
116 template <typename MultiLinestring, bool Enable>
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;
124 template <typename Range, typename EqualTo>
125 void apply_to_range(Range& range, EqualTo const& equal_to)
127 range.erase(std::unique(boost::begin(range), boost::end(range),
132 void operator()(MultiLinestring& mls, double tolerance)
134 for (typename boost::range_iterator<MultiLinestring>::type it
135 = boost::begin(mls); it != boost::end(mls); ++it)
137 apply_to_range(*it, point_equal(tolerance));
139 apply_to_range(mls, linestring_equal());
143 template <typename MultiLinestring>
144 struct unique<MultiLinestring, false>
146 void operator()(MultiLinestring&, double)
151 template <typename MultiLinestring1, typename MultiLinestring2>
153 bool apply(MultiLinestring1 const& multilinestring1,
154 MultiLinestring2 const& multilinestring2,
157 typedef typename boost::range_iterator
159 MultiLinestring1 const
160 >::type ls1_iterator;
162 typedef typename boost::range_iterator
164 MultiLinestring2 const
165 >::type ls2_iterator;
167 typedef typename boost::range_value<MultiLinestring1>::type Linestring1;
169 typedef typename boost::range_value<MultiLinestring2>::type Linestring2;
171 typedef typename boost::range_iterator
174 >::type point1_iterator;
176 typedef typename boost::range_iterator
179 >::type point2_iterator;
181 typedef ls_less<Linestring1, Linestring2> linestring_less;
185 typename boost::range_value
187 typename boost::range_value<MultiLinestring1>::type
189 typename boost::range_value
191 typename boost::range_value<MultiLinestring2>::type
196 MultiLinestring1 mls1 = multilinestring1;
197 MultiLinestring2 mls2 = multilinestring2;
199 std::sort(boost::begin(mls1), boost::end(mls1), linestring_less());
200 std::sort(boost::begin(mls2), boost::end(mls2), linestring_less());
202 unique<MultiLinestring1, EnableUnique>()(mls1, tolerance);
203 unique<MultiLinestring2, EnableUnique>()(mls2, tolerance);
205 if (boost::size(mls1) != boost::size(mls2))
210 ls1_iterator it1 = boost::begin(mls1);
211 ls2_iterator it2 = boost::begin(mls2);
212 for (; it1 != boost::end(mls1); ++it1, ++it2)
214 if (boost::size(*it1) != boost::size(*it2))
218 point1_iterator pit1 = boost::begin(*it1);
219 point2_iterator pit2 = boost::begin(*it2);
220 for (; pit1 != boost::end(*it1); ++pit1, ++pit2)
222 if (! point_equal(tolerance)(*pit1, *pit2))
238 template <typename Linestring, typename OutputIterator>
239 static inline OutputIterator
240 isolated_point_to_segment(Linestring const& linestring, OutputIterator oit)
242 BOOST_ASSERT( boost::size(linestring) == 1 );
244 *oit++ = *boost::begin(linestring);
245 *oit++ = *boost::begin(linestring);
250 template <typename MultiLinestring, typename OutputIterator>
251 static inline OutputIterator
252 convert_isolated_points_to_segments(MultiLinestring const& multilinestring,
255 BOOST_AUTO_TPL(it, boost::begin(multilinestring));
257 for (; it != boost::end(multilinestring); ++it)
259 if (boost::size(*it) == 1)
261 typename boost::range_value<MultiLinestring>::type linestring;
262 isolated_point_to_segment(*it, std::back_inserter(linestring));
274 template <typename MultiLinestring1, typename MultiLinestring2>
275 static inline bool apply_base(MultiLinestring1 const& multilinestring1,
276 MultiLinestring2 const& multilinestring2,
279 typedef multilinestring_equals<true> mls_equals;
281 if (mls_equals::apply(multilinestring1, multilinestring2, tolerance))
286 MultiLinestring1 reverse_multilinestring1 = multilinestring1;
287 bg::reverse(reverse_multilinestring1);
288 if (mls_equals::apply(reverse_multilinestring1,
295 MultiLinestring2 reverse_multilinestring2 = multilinestring2;
296 bg::reverse(reverse_multilinestring2);
297 if (mls_equals::apply(multilinestring1,
298 reverse_multilinestring2,
304 return mls_equals::apply(reverse_multilinestring1,
305 reverse_multilinestring2,
312 template <typename MultiLinestring1, typename MultiLinestring2>
313 static inline bool apply(MultiLinestring1 const& multilinestring1,
314 MultiLinestring2 const& multilinestring2,
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);
327 return apply_base(multilinestring1, multilinestring2, tolerance);
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)
341 boost::ignore_unused(set_op_id, caseid, g1, g2, output);
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;
347 std::ostringstream filename;
348 filename << "svgs/" << set_op_id << "_" << caseid << ".svg";
350 std::ofstream svg(filename.str().c_str());
352 bg::svg_mapper<point_type> mapper(svg, 500, 500);
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");
360 BOOST_AUTO_TPL(it, output.begin());
361 for (; it != output.end(); ++it)
363 if ( boost::size(*it) == 2
364 && bg::equals(*boost::begin(*it), *++boost::begin(*it)) )
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",
374 "stroke-opacity:0.4;stroke:rgb(255,0,255);stroke-width:8");
381 #endif // BOOST_GEOMETRY_TEST_SET_OPS_LINEAR_LINEAR_HPP