detail/equals/collect_vectors.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2017-2021.
0009 // Modifications copyright (c) 2017-2021 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0013 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0014
0015 // Use, modification and distribution is subject to the Boost Software License,
0016 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0017 // http://www.boost.org/LICENSE_1_0.txt)
0018
0019 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
0020 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
0021
0022
0023 #include <boost/numeric/conversion/cast.hpp>
0024 #include <boost/range/size.hpp>
0025
0026 #include <boost/geometry/algorithms/detail/normalize.hpp>
0027 #include <boost/geometry/algorithms/not_implemented.hpp>
0028
0029 #include <boost/geometry/core/cs.hpp>
0030 #include <boost/geometry/core/interior_rings.hpp>
0031 #include <boost/geometry/core/tags.hpp>
0032
0033 #include <boost/geometry/formulas/spherical.hpp>
0034
0035 #include <boost/geometry/geometries/concepts/check.hpp>
0036
0037 #include <boost/geometry/util/math.hpp>
0038 #include <boost/geometry/util/range.hpp>
0039
0040 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0041
0042 #include <boost/geometry/strategies/spherical/ssf.hpp>
0043 #include <boost/geometry/strategies/normalize.hpp>
0044
0045
0046 namespace boost { namespace geometry
0047 {
0048
0049
0050 template <typename T>
0051 struct collected_vector_cartesian
0052 {
0053     typedef T type;
0054
0055     inline collected_vector_cartesian()
0056     {}
0057
0058     inline collected_vector_cartesian(T const& px, T const& py,
0059                                       T const& pdx, T const& pdy)
0060         : x(px)
0061         , y(py)
0062         , dx(pdx)
0063         , dy(pdy)
0064         //, dx_0(dx)
0065         //, dy_0(dy)
0066     {}
0067
0068     template <typename Point>
0069     inline collected_vector_cartesian(Point const& p1, Point const& p2)
0070         : x(get<0>(p1))
0071         , y(get<1>(p1))
0072         , dx(get<0>(p2) - x)
0073         , dy(get<1>(p2) - y)
0074         //, dx_0(dx)
0075         //, dy_0(dy)
0076     {}
0077
0078     bool normalize()
0079     {
0080         T magnitude = math::sqrt(boost::numeric_cast<T>(dx * dx + dy * dy));
0081
0082         // NOTE: shouldn't here math::equals() be called?
0083         if (magnitude > 0)
0084         {
0085             dx /= magnitude;
0086             dy /= magnitude;
0087             return true;
0088         }
0089
0090         return false;
0091     }
0092
0093     // For sorting
0094     inline bool operator<(collected_vector_cartesian const& other) const
0095     {
0096         if (math::equals(x, other.x))
0097         {
0098             if (math::equals(y, other.y))
0099             {
0100                 if (math::equals(dx, other.dx))
0101                 {
0102                     return dy < other.dy;
0103                 }
0104                 return dx < other.dx;
0105             }
0106             return y < other.y;
0107         }
0108         return x < other.x;
0109     }
0110
0111     inline bool next_is_collinear(collected_vector_cartesian const& other) const
0112     {
0113         return same_direction(other);
0114     }
0115
0116     // For std::equals
0117     inline bool operator==(collected_vector_cartesian const& other) const
0118     {
0119         return math::equals(x, other.x)
0120             && math::equals(y, other.y)
0121             && same_direction(other);
0122     }
0123
0124 private:
0125     inline bool same_direction(collected_vector_cartesian const& other) const
0126     {
0127         // For high precision arithmetic, we have to be
0128         // more relaxed then using ==
0129         // Because 2/sqrt( (0,0)<->(2,2) ) == 1/sqrt( (0,0)<->(1,1) )
0130         // is not always true (at least, not for some user defined types)
0131         return math::equals_with_epsilon(dx, other.dx)
0132             && math::equals_with_epsilon(dy, other.dy);
0133     }
0134
0135     T x, y;
0136     T dx, dy;
0137     //T dx_0, dy_0;
0138 };
0139
0140 // Compatible with spherical_side_formula which currently
0141 // is the default spherical_equatorial and geographic strategy
0142 // so CSTag is spherical_equatorial_tag or geographic_tag
0143 template <typename T, typename Point>
0144 struct collected_vector_spherical
0145 {
0146     typedef T type;
0147
0148     typedef model::point<T, 3, cs::cartesian> vector_type;
0149
0150     collected_vector_spherical()
0151     {}
0152
0153     collected_vector_spherical(Point const& p1, Point const& p2)
0154         : origin(get<0>(p1), get<1>(p1))
0155     {
0156         origin = detail::return_normalized<Point>(
0157                     origin,
0158                     strategy::normalize::spherical_point());
0159
0160         using namespace geometry::formula;
0161         prev = sph_to_cart3d<vector_type>(p1);
0162         next = sph_to_cart3d<vector_type>(p2);
0163         cross = direction = cross_product(prev, next);
0164     }
0165
0166     bool normalize()
0167     {
0168         T const magnitude_sqr = dot_product(direction, direction);
0169
0170         // NOTE: shouldn't here math::equals() be called?
0171         if (magnitude_sqr > 0)
0172         {
0173             divide_value(direction, math::sqrt(magnitude_sqr));
0174             return true;
0175         }
0176
0177         return false;
0178     }
0179
0180     bool operator<(collected_vector_spherical const& other) const
0181     {
0182         if (math::equals(get<0>(origin), get<0>(other.origin)))
0183         {
0184             if (math::equals(get<1>(origin), get<1>(other.origin)))
0185             {
0186                 if (math::equals(get<0>(direction), get<0>(other.direction)))
0187                 {
0188                     if (math::equals(get<1>(direction), get<1>(other.direction)))
0189                     {
0190                         return get<2>(direction) < get<2>(other.direction);
0191                     }
0192                     return get<1>(direction) < get<1>(other.direction);
0193                 }
0194                 return get<0>(direction) < get<0>(other.direction);
0195             }
0196             return get<1>(origin) < get<1>(other.origin);
0197         }
0198         return get<0>(origin) < get<0>(other.origin);
0199     }
0200
0201     // For consistency with side and intersection strategies used by relops
0202     // IMPORTANT: this method should be called for previous vector
0203     // and next vector should be passed as parameter
0204     bool next_is_collinear(collected_vector_spherical const& other) const
0205     {
0206         return formula::sph_side_value(cross, other.next) == 0;
0207     }
0208
0209     // For std::equals
0210     bool operator==(collected_vector_spherical const& other) const
0211     {
0212         return math::equals(get<0>(origin), get<0>(other.origin))
0213             && math::equals(get<1>(origin), get<1>(other.origin))
0214             && is_collinear(other);
0215     }
0216
0217 private:
0218     // For consistency with side and intersection strategies used by relops
0219     // NOTE: alternative would be to equal-compare direction's coordinates
0220     //       or to check if dot product of directions is equal to 1.
0221     bool is_collinear(collected_vector_spherical const& other) const
0222     {
0223         return formula::sph_side_value(cross, other.prev) == 0
0224             && formula::sph_side_value(cross, other.next) == 0;
0225     }
0226
0227     Point origin; // used for sorting and equality check
0228     vector_type direction; // used for sorting, only in operator<
0229     vector_type cross; // used for sorting, used for collinearity check
0230     vector_type prev; // used for collinearity check, only in operator==
0231     vector_type next; // used for collinearity check
0232 };
0233
0234 // Version for spherical polar
0235 template <typename T, typename Point>
0236 struct collected_vector_polar
0237     : public collected_vector_spherical<T, Point>
0238 {
0239     using type = T;
0240     using base_point_type
0241         = model::point<T, 2, cs::spherical_equatorial<geometry::degree>>;
0242     using base_type = collected_vector_spherical<T, base_point_type>;
0243
0244     collected_vector_polar() {}
0245
0246     collected_vector_polar(Point const& p1, Point const& p2)
0247         : base_type(to_equatorial(p1), to_equatorial(p2))
0248     {}
0249
0250 private:
0251     static base_point_type to_equatorial(Point const& p)
0252     {
0253         using coord_type = typename coordinate_type<Point>::type;
0254         using constants = math::detail::constants_on_spheroid
0255             <
0256                 coord_type,
0257                 typename coordinate_system<Point>::type::units
0258             > ;
0259
0260         constexpr coord_type pi_2 = constants::half_period() / 2;
0261
0262         base_point_type res;
0263         set<0>(res, get<0>(p));
0264         set<1>(res, pi_2 - get<1>(p));
0265         return res;
0266     }
0267 };
0268
0269 // TODO: implement collected_vector type for geographic
0270
0271
0272 #ifndef DOXYGEN_NO_DETAIL
0273 namespace detail { namespace collect_vectors
0274 {
0275
0276
0277 template <typename Range, typename Collection>
0278 struct range_collect_vectors
0279 {
0280     typedef typename boost::range_value<Collection>::type item_type;
0281     typedef typename item_type::type calculation_type;
0282
0283     static inline void apply(Collection& collection, Range const& range)
0284     {
0285         apply_impl(collection,
0286                    detail::closed_clockwise_view<Range const>(range));
0287     }
0288
0289 private:
0290     template <typename ClosedClockwiseRange>
0291     static inline void apply_impl(Collection& collection, ClosedClockwiseRange const& range)
0292     {
0293         if (boost::size(range) < 2)
0294         {
0295             return;
0296         }
0297
0298         auto c_old_size = boost::size(collection);
0299         bool is_first = true;
0300         auto it = boost::begin(range);
0301
0302         for (auto prev = it++; it != boost::end(range); prev = it++)
0303         {
0304             typename boost::range_value<Collection>::type v(*prev, *it);
0305
0306             // Normalize the vector -> this results in points+direction
0307             // and is comparible between geometries
0308             // Avoid non-duplicate points (AND division by zero)
0309             if (v.normalize())
0310             {
0311                 // Avoid non-direction changing points
0312                 if (is_first || ! collection.back().next_is_collinear(v))
0313                 {
0314                     collection.push_back(v);
0315                 }
0316                 is_first = false;
0317             }
0318         }
0319
0320         // If first one has same direction as last one, remove first one
0321         if (boost::size(collection) > c_old_size + 1)
0322         {
0323             auto first = range::pos(collection, c_old_size);
0324             if (collection.back().next_is_collinear(*first))
0325             {
0326                 //collection.erase(first);
0327                 // O(1) instead of O(N)
0328                 *first = collection.back();
0329                 collection.pop_back();
0330             }
0331         }
0332     }
0333 };
0334
0335
0336 // Default version (cartesian)
0337 template <typename Box, typename Collection, typename CSTag = typename cs_tag<Box>::type>
0338 struct box_collect_vectors
0339 {
0340     // Calculate on coordinate type, but if it is integer,
0341     // then use double
0342     typedef typename boost::range_value<Collection>::type item_type;
0343     typedef typename item_type::type calculation_type;
0344
0345     static inline void apply(Collection& collection, Box const& box)
0346     {
0347         typename point_type<Box>::type lower_left, lower_right,
0348             upper_left, upper_right;
0349         geometry::detail::assign_box_corners(box, lower_left, lower_right,
0350             upper_left, upper_right);
0351
0352         typedef typename boost::range_value<Collection>::type item;
0353
0354         collection.push_back(item(get<0>(lower_left), get<1>(lower_left), 0, 1));
0355         collection.push_back(item(get<0>(upper_left), get<1>(upper_left), 1, 0));
0356         collection.push_back(item(get<0>(upper_right), get<1>(upper_right), 0, -1));
0357         collection.push_back(item(get<0>(lower_right), get<1>(lower_right), -1, 0));
0358     }
0359 };
0360
0361 // NOTE: This is not fully correct because Box in spherical and geographic
0362 // cordinate systems cannot be seen as Polygon
0363 template <typename Box, typename Collection>
0364 struct box_collect_vectors<Box, Collection, spherical_equatorial_tag>
0365 {
0366     static inline void apply(Collection& collection, Box const& box)
0367     {
0368         typename point_type<Box>::type lower_left, lower_right,
0369                 upper_left, upper_right;
0370         geometry::detail::assign_box_corners(box, lower_left, lower_right,
0371                 upper_left, upper_right);
0372
0373         typedef typename boost::range_value<Collection>::type item;
0374
0375         collection.push_back(item(lower_left, upper_left));
0376         collection.push_back(item(upper_left, upper_right));
0377         collection.push_back(item(upper_right, lower_right));
0378         collection.push_back(item(lower_right, lower_left));
0379     }
0380 };
0381
0382 template <typename Box, typename Collection>
0383 struct box_collect_vectors<Box, Collection, spherical_polar_tag>
0384     : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
0385 {};
0386
0387 template <typename Box, typename Collection>
0388 struct box_collect_vectors<Box, Collection, geographic_tag>
0389     : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
0390 {};
0391
0392
0393 template <typename Polygon, typename Collection>
0394 struct polygon_collect_vectors
0395 {
0396     static inline void apply(Collection& collection, Polygon const& polygon)
0397     {
0398         typedef typename geometry::ring_type<Polygon>::type ring_type;
0399
0400         typedef range_collect_vectors<ring_type, Collection> per_range;
0401         per_range::apply(collection, exterior_ring(polygon));
0402
0403         auto const& rings = interior_rings(polygon);
0404         for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0405         {
0406             per_range::apply(collection, *it);
0407         }
0408     }
0409 };
0410
0411
0412 template <typename MultiGeometry, typename Collection, typename SinglePolicy>
0413 struct multi_collect_vectors
0414 {
0415     static inline void apply(Collection& collection, MultiGeometry const& multi)
0416     {
0417         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0418         {
0419             SinglePolicy::apply(collection, *it);
0420         }
0421     }
0422 };
0423
0424
0425 }} // namespace detail::collect_vectors
0426 #endif // DOXYGEN_NO_DETAIL
0427
0428
0429
0430 #ifndef DOXYGEN_NO_DISPATCH
0431 namespace dispatch
0432 {
0433
0434
0435 template
0436 <
0437     typename Tag,
0438     typename Collection,
0439     typename Geometry
0440 >
0441 struct collect_vectors
0442 {
0443     static inline void apply(Collection&, Geometry const&)
0444     {}
0445 };
0446
0447
0448 template <typename Collection, typename Box>
0449 struct collect_vectors<box_tag, Collection, Box>
0450     : detail::collect_vectors::box_collect_vectors<Box, Collection>
0451 {};
0452
0453
0454
0455 template <typename Collection, typename Ring>
0456 struct collect_vectors<ring_tag, Collection, Ring>
0457     : detail::collect_vectors::range_collect_vectors<Ring, Collection>
0458 {};
0459
0460
0461 template <typename Collection, typename LineString>
0462 struct collect_vectors<linestring_tag, Collection, LineString>
0463     : detail::collect_vectors::range_collect_vectors<LineString, Collection>
0464 {};
0465
0466
0467 template <typename Collection, typename Polygon>
0468 struct collect_vectors<polygon_tag, Collection, Polygon>
0469     : detail::collect_vectors::polygon_collect_vectors<Polygon, Collection>
0470 {};
0471
0472
0473 template <typename Collection, typename MultiPolygon>
0474 struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon>
0475     : detail::collect_vectors::multi_collect_vectors
0476         <
0477             MultiPolygon,
0478             Collection,
0479             detail::collect_vectors::polygon_collect_vectors
0480             <
0481                 typename boost::range_value<MultiPolygon>::type,
0482                 Collection
0483             >
0484         >
0485 {};
0486
0487
0488
0489 } // namespace dispatch
0490 #endif
0491
0492
0493 /*!
0494     \ingroup collect_vectors
0495     \tparam Collection Collection type, should be e.g. std::vector<>
0496     \tparam Geometry geometry type
0497     \param collection the collection of vectors
0498     \param geometry the geometry to make collect_vectors
0499 */
0500 template <typename Collection, typename Geometry>
0501 inline void collect_vectors(Collection& collection, Geometry const& geometry)
0502 {
0503     concepts::check<Geometry const>();
0504
0505     dispatch::collect_vectors
0506         <
0507             typename tag<Geometry>::type,
0508             Collection,
0509             Geometry
0510         >::apply(collection, geometry);
0511 }
0512
0513
0514 }} // namespace boost::geometry
0515
0516
0517 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP