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-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