ceph/src/boost/libs/geometry/test/algorithms/set_operations/test_set_ops_linear_linear.hpp

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