ceph/src/boost/boost/geometry/algorithms/detail/equals/collect_vectors.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2017-2021.
   9 // Modifications copyright (c) 2017-2021 Oracle and/or its affiliates.
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  14
  15 // Use, modification and distribution is subject to the Boost Software License,
  16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 // http://www.boost.org/LICENSE_1_0.txt)
  18
  19 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
  20 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
  21
  22
  23 #include <boost/numeric/conversion/cast.hpp>
  24
  25 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  26 #include <boost/geometry/algorithms/detail/normalize.hpp>
  27 #include <boost/geometry/algorithms/not_implemented.hpp>
  28
  29 #include <boost/geometry/core/cs.hpp>
  30 #include <boost/geometry/core/interior_rings.hpp>
  31 #include <boost/geometry/core/tags.hpp>
  32
  33 #include <boost/geometry/formulas/spherical.hpp>
  34
  35 #include <boost/geometry/geometries/concepts/check.hpp>
  36
  37 #include <boost/geometry/util/math.hpp>
  38 #include <boost/geometry/util/range.hpp>
  39
  40 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
  41
  42 #include <boost/geometry/strategies/spherical/ssf.hpp>
  43 #include <boost/geometry/strategies/normalize.hpp>
  44
  45
  46 namespace boost { namespace geometry
  47 {
  48
  49
  50 template <typename T>
  51 struct collected_vector_cartesian
  52 {
  53     typedef T type;
  54
  55     inline collected_vector_cartesian()
  56     {}
  57
  58     inline collected_vector_cartesian(T const& px, T const& py,
  59                                       T const& pdx, T const& pdy)
  60         : x(px)
  61         , y(py)
  62         , dx(pdx)
  63         , dy(pdy)
  64         //, dx_0(dx)
  65         //, dy_0(dy)
  66     {}
  67
  68     template <typename Point>
  69     inline collected_vector_cartesian(Point const& p1, Point const& p2)
  70         : x(get<0>(p1))
  71         , y(get<1>(p1))
  72         , dx(get<0>(p2) - x)
  73         , dy(get<1>(p2) - y)
  74         //, dx_0(dx)
  75         //, dy_0(dy)
  76     {}
  77
  78     bool normalize()
  79     {
  80         T magnitude = math::sqrt(boost::numeric_cast<T>(dx * dx + dy * dy));
  81
  82         // NOTE: shouldn't here math::equals() be called?
  83         if (magnitude > 0)
  84         {
  85             dx /= magnitude;
  86             dy /= magnitude;
  87             return true;
  88         }
  89
  90         return false;
  91     }
  92
  93     // For sorting
  94     inline bool operator<(collected_vector_cartesian const& other) const
  95     {
  96         if (math::equals(x, other.x))
  97         {
  98             if (math::equals(y, other.y))
  99             {
 100                 if (math::equals(dx, other.dx))
 101                 {
 102                     return dy < other.dy;
 103                 }
 104                 return dx < other.dx;
 105             }
 106             return y < other.y;
 107         }
 108         return x < other.x;
 109     }
 110
 111     inline bool next_is_collinear(collected_vector_cartesian const& other) const
 112     {
 113         return same_direction(other);
 114     }
 115
 116     // For std::equals
 117     inline bool operator==(collected_vector_cartesian const& other) const
 118     {
 119         return math::equals(x, other.x)
 120             && math::equals(y, other.y)
 121             && same_direction(other);
 122     }
 123
 124 private:
 125     inline bool same_direction(collected_vector_cartesian const& other) const
 126     {
 127         // For high precision arithmetic, we have to be
 128         // more relaxed then using ==
 129         // Because 2/sqrt( (0,0)<->(2,2) ) == 1/sqrt( (0,0)<->(1,1) )
 130         // is not always true (at least, not for some user defined types)
 131         return math::equals_with_epsilon(dx, other.dx)
 132             && math::equals_with_epsilon(dy, other.dy);
 133     }
 134
 135     T x, y;
 136     T dx, dy;
 137     //T dx_0, dy_0;
 138 };
 139
 140 // Compatible with spherical_side_formula which currently
 141 // is the default spherical_equatorial and geographic strategy
 142 // so CSTag is spherical_equatorial_tag or geographic_tag
 143 template <typename T, typename Point>
 144 struct collected_vector_spherical
 145 {
 146     typedef T type;
 147
 148     typedef model::point<T, 3, cs::cartesian> vector_type;
 149
 150     collected_vector_spherical()
 151     {}
 152
 153     collected_vector_spherical(Point const& p1, Point const& p2)
 154         : origin(get<0>(p1), get<1>(p1))
 155     {
 156         origin = detail::return_normalized<Point>(
 157                     origin,
 158                     strategy::normalize::spherical_point());
 159
 160         using namespace geometry::formula;
 161         prev = sph_to_cart3d<vector_type>(p1);
 162         next = sph_to_cart3d<vector_type>(p2);
 163         cross = direction = cross_product(prev, next);
 164     }
 165
 166     bool normalize()
 167     {
 168         T const magnitude_sqr = dot_product(direction, direction);
 169
 170         // NOTE: shouldn't here math::equals() be called?
 171         if (magnitude_sqr > 0)
 172         {
 173             divide_value(direction, math::sqrt(magnitude_sqr));
 174             return true;
 175         }
 176
 177         return false;
 178     }
 179
 180     bool operator<(collected_vector_spherical const& other) const
 181     {
 182         if (math::equals(get<0>(origin), get<0>(other.origin)))
 183         {
 184             if (math::equals(get<1>(origin), get<1>(other.origin)))
 185             {
 186                 if (math::equals(get<0>(direction), get<0>(other.direction)))
 187                 {
 188                     if (math::equals(get<1>(direction), get<1>(other.direction)))
 189                     {
 190                         return get<2>(direction) < get<2>(other.direction);
 191                     }
 192                     return get<1>(direction) < get<1>(other.direction);
 193                 }
 194                 return get<0>(direction) < get<0>(other.direction);
 195             }
 196             return get<1>(origin) < get<1>(other.origin);
 197         }
 198         return get<0>(origin) < get<0>(other.origin);
 199     }
 200
 201     // For consistency with side and intersection strategies used by relops
 202     // IMPORTANT: this method should be called for previous vector
 203     // and next vector should be passed as parameter
 204     bool next_is_collinear(collected_vector_spherical const& other) const
 205     {
 206         return formula::sph_side_value(cross, other.next) == 0;
 207     }
 208
 209     // For std::equals
 210     bool operator==(collected_vector_spherical const& other) const
 211     {
 212         return math::equals(get<0>(origin), get<0>(other.origin))
 213             && math::equals(get<1>(origin), get<1>(other.origin))
 214             && is_collinear(other);
 215     }
 216
 217 private:
 218     // For consistency with side and intersection strategies used by relops
 219     // NOTE: alternative would be to equal-compare direction's coordinates
 220     //       or to check if dot product of directions is equal to 1.
 221     bool is_collinear(collected_vector_spherical const& other) const
 222     {
 223         return formula::sph_side_value(cross, other.prev) == 0
 224             && formula::sph_side_value(cross, other.next) == 0;
 225     }
 226
 227     Point origin; // used for sorting and equality check
 228     vector_type direction; // used for sorting, only in operator<
 229     vector_type cross; // used for sorting, used for collinearity check
 230     vector_type prev; // used for collinearity check, only in operator==
 231     vector_type next; // used for collinearity check
 232 };
 233
 234 // Version for spherical polar
 235 template <typename T, typename Point>
 236 struct collected_vector_polar
 237     : public collected_vector_spherical<T, Point>
 238 {
 239     using type = T;
 240     using base_point_type
 241         = model::point<T, 2, cs::spherical_equatorial<geometry::degree>>;
 242     using base_type = collected_vector_spherical<T, base_point_type>;
 243
 244     collected_vector_polar() {}
 245
 246     collected_vector_polar(Point const& p1, Point const& p2)
 247         : base_type(to_equatorial(p1), to_equatorial(p2))
 248     {}
 249
 250 private:
 251     static base_point_type to_equatorial(Point const& p)
 252     {
 253         using coord_type = typename coordinate_type<Point>::type;
 254         using constants = math::detail::constants_on_spheroid
 255             <
 256                 coord_type,
 257                 typename coordinate_system<Point>::type::units
 258             > ;
 259
 260         constexpr coord_type pi_2 = constants::half_period() / 2;
 261
 262         base_point_type res;
 263         set<0>(res, get<0>(p));
 264         set<1>(res, pi_2 - get<1>(p));
 265         return res;
 266     }
 267 };
 268
 269 // TODO: implement collected_vector type for geographic
 270
 271
 272 #ifndef DOXYGEN_NO_DETAIL
 273 namespace detail { namespace collect_vectors
 274 {
 275
 276
 277 template <typename Range, typename Collection>
 278 struct range_collect_vectors
 279 {
 280     typedef typename boost::range_value<Collection>::type item_type;
 281     typedef typename item_type::type calculation_type;
 282
 283     static inline void apply(Collection& collection, Range const& range)
 284     {
 285         apply_impl(collection,
 286                    detail::closed_clockwise_view<Range const>(range));
 287     }
 288
 289 private:
 290     template <typename ClosedClockwiseRange>
 291     static inline void apply_impl(Collection& collection, ClosedClockwiseRange const& range)
 292     {
 293         if (boost::size(range) < 2)
 294         {
 295             return;
 296         }
 297
 298         auto c_old_size = boost::size(collection);
 299         bool is_first = true;
 300         auto it = boost::begin(range);
 301
 302         for (auto prev = it++; it != boost::end(range); prev = it++)
 303         {
 304             typename boost::range_value<Collection>::type v(*prev, *it);
 305
 306             // Normalize the vector -> this results in points+direction
 307             // and is comparible between geometries
 308             // Avoid non-duplicate points (AND division by zero)
 309             if (v.normalize())
 310             {
 311                 // Avoid non-direction changing points
 312                 if (is_first || ! collection.back().next_is_collinear(v))
 313                 {
 314                     collection.push_back(v);
 315                 }
 316                 is_first = false;
 317             }
 318         }
 319
 320         // If first one has same direction as last one, remove first one
 321         if (boost::size(collection) > c_old_size + 1)
 322         {
 323             auto first = range::pos(collection, c_old_size);
 324             if (collection.back().next_is_collinear(*first))
 325             {
 326                 //collection.erase(first);
 327                 // O(1) instead of O(N)
 328                 *first = collection.back();
 329                 collection.pop_back();
 330             }
 331         }
 332     }
 333 };
 334
 335
 336 // Default version (cartesian)
 337 template <typename Box, typename Collection, typename CSTag = typename cs_tag<Box>::type>
 338 struct box_collect_vectors
 339 {
 340     // Calculate on coordinate type, but if it is integer,
 341     // then use double
 342     typedef typename boost::range_value<Collection>::type item_type;
 343     typedef typename item_type::type calculation_type;
 344
 345     static inline void apply(Collection& collection, Box const& box)
 346     {
 347         typename point_type<Box>::type lower_left, lower_right,
 348             upper_left, upper_right;
 349         geometry::detail::assign_box_corners(box, lower_left, lower_right,
 350             upper_left, upper_right);
 351
 352         typedef typename boost::range_value<Collection>::type item;
 353
 354         collection.push_back(item(get<0>(lower_left), get<1>(lower_left), 0, 1));
 355         collection.push_back(item(get<0>(upper_left), get<1>(upper_left), 1, 0));
 356         collection.push_back(item(get<0>(upper_right), get<1>(upper_right), 0, -1));
 357         collection.push_back(item(get<0>(lower_right), get<1>(lower_right), -1, 0));
 358     }
 359 };
 360
 361 // NOTE: This is not fully correct because Box in spherical and geographic
 362 // cordinate systems cannot be seen as Polygon
 363 template <typename Box, typename Collection>
 364 struct box_collect_vectors<Box, Collection, spherical_equatorial_tag>
 365 {
 366     static inline void apply(Collection& collection, Box const& box)
 367     {
 368         typename point_type<Box>::type lower_left, lower_right,
 369                 upper_left, upper_right;
 370         geometry::detail::assign_box_corners(box, lower_left, lower_right,
 371                 upper_left, upper_right);
 372
 373         typedef typename boost::range_value<Collection>::type item;
 374
 375         collection.push_back(item(lower_left, upper_left));
 376         collection.push_back(item(upper_left, upper_right));
 377         collection.push_back(item(upper_right, lower_right));
 378         collection.push_back(item(lower_right, lower_left));
 379     }
 380 };
 381
 382 template <typename Box, typename Collection>
 383 struct box_collect_vectors<Box, Collection, spherical_polar_tag>
 384     : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
 385 {};
 386
 387 template <typename Box, typename Collection>
 388 struct box_collect_vectors<Box, Collection, geographic_tag>
 389     : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
 390 {};
 391
 392
 393 template <typename Polygon, typename Collection>
 394 struct polygon_collect_vectors
 395 {
 396     static inline void apply(Collection& collection, Polygon const& polygon)
 397     {
 398         typedef typename geometry::ring_type<Polygon>::type ring_type;
 399
 400         typedef range_collect_vectors<ring_type, Collection> per_range;
 401         per_range::apply(collection, exterior_ring(polygon));
 402
 403         typename interior_return_type<Polygon const>::type
 404             rings = interior_rings(polygon);
 405         for (typename detail::interior_iterator<Polygon const>::type
 406                 it = boost::begin(rings); it != boost::end(rings); ++it)
 407         {
 408             per_range::apply(collection, *it);
 409         }
 410     }
 411 };
 412
 413
 414 template <typename MultiGeometry, typename Collection, typename SinglePolicy>
 415 struct multi_collect_vectors
 416 {
 417     static inline void apply(Collection& collection, MultiGeometry const& multi)
 418     {
 419         for (typename boost::range_iterator<MultiGeometry const>::type
 420                 it = boost::begin(multi);
 421             it != boost::end(multi);
 422             ++it)
 423         {
 424             SinglePolicy::apply(collection, *it);
 425         }
 426     }
 427 };
 428
 429
 430 }} // namespace detail::collect_vectors
 431 #endif // DOXYGEN_NO_DETAIL
 432
 433
 434
 435 #ifndef DOXYGEN_NO_DISPATCH
 436 namespace dispatch
 437 {
 438
 439
 440 template
 441 <
 442     typename Tag,
 443     typename Collection,
 444     typename Geometry
 445 >
 446 struct collect_vectors
 447 {
 448     static inline void apply(Collection&, Geometry const&)
 449     {}
 450 };
 451
 452
 453 template <typename Collection, typename Box>
 454 struct collect_vectors<box_tag, Collection, Box>
 455     : detail::collect_vectors::box_collect_vectors<Box, Collection>
 456 {};
 457
 458
 459
 460 template <typename Collection, typename Ring>
 461 struct collect_vectors<ring_tag, Collection, Ring>
 462     : detail::collect_vectors::range_collect_vectors<Ring, Collection>
 463 {};
 464
 465
 466 template <typename Collection, typename LineString>
 467 struct collect_vectors<linestring_tag, Collection, LineString>
 468     : detail::collect_vectors::range_collect_vectors<LineString, Collection>
 469 {};
 470
 471
 472 template <typename Collection, typename Polygon>
 473 struct collect_vectors<polygon_tag, Collection, Polygon>
 474     : detail::collect_vectors::polygon_collect_vectors<Polygon, Collection>
 475 {};
 476
 477
 478 template <typename Collection, typename MultiPolygon>
 479 struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon>
 480     : detail::collect_vectors::multi_collect_vectors
 481         <
 482             MultiPolygon,
 483             Collection,
 484             detail::collect_vectors::polygon_collect_vectors
 485             <
 486                 typename boost::range_value<MultiPolygon>::type,
 487                 Collection
 488             >
 489         >
 490 {};
 491
 492
 493
 494 } // namespace dispatch
 495 #endif
 496
 497
 498 /*!
 499     \ingroup collect_vectors
 500     \tparam Collection Collection type, should be e.g. std::vector<>
 501     \tparam Geometry geometry type
 502     \param collection the collection of vectors
 503     \param geometry the geometry to make collect_vectors
 504 */
 505 template <typename Collection, typename Geometry>
 506 inline void collect_vectors(Collection& collection, Geometry const& geometry)
 507 {
 508     concepts::check<Geometry const>();
 509
 510     dispatch::collect_vectors
 511         <
 512             typename tag<Geometry>::type,
 513             Collection,
 514             Geometry
 515         >::apply(collection, geometry);
 516 }
 517
 518
 519 }} // namespace boost::geometry
 520
 521
 522 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP