Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:35:03 

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002 
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0007 
0008 // This file was modified by Oracle on 2014-2021.
0009 // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
0010 
0011 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0012 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0013 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0014 
0015 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0016 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0017 
0018 // Use, modification and distribution is subject to the Boost Software License,
0019 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0020 // http://www.boost.org/LICENSE_1_0.txt)
0021 
0022 #ifndef BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_INTERFACE_HPP
0023 #define BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_INTERFACE_HPP
0024 
0025 #include <array>
0026 
0027 #include <boost/range/size.hpp>
0028 
0029 #include <boost/geometry/algorithms/detail/assign_box_corners.hpp>
0030 #include <boost/geometry/algorithms/detail/convex_hull/graham_andrew.hpp>
0031 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0032 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
0033 #include <boost/geometry/algorithms/detail/select_geometry_type.hpp>
0034 #include <boost/geometry/algorithms/detail/visit.hpp>
0035 #include <boost/geometry/algorithms/is_empty.hpp>
0036 
0037 #include <boost/geometry/core/closure.hpp>
0038 #include <boost/geometry/core/cs.hpp>
0039 #include <boost/geometry/core/exterior_ring.hpp>
0040 #include <boost/geometry/core/geometry_types.hpp>
0041 #include <boost/geometry/core/point_order.hpp>
0042 #include <boost/geometry/core/ring_type.hpp>
0043 #include <boost/geometry/core/tag.hpp>
0044 #include <boost/geometry/core/tags.hpp>
0045 #include <boost/geometry/core/visit.hpp>
0046 
0047 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
0048 #include <boost/geometry/geometries/concepts/check.hpp>
0049 #include <boost/geometry/geometries/ring.hpp>
0050 
0051 #include <boost/geometry/strategies/convex_hull/cartesian.hpp>
0052 #include <boost/geometry/strategies/convex_hull/geographic.hpp>
0053 #include <boost/geometry/strategies/convex_hull/spherical.hpp>
0054 #include <boost/geometry/strategies/default_strategy.hpp>
0055 
0056 #include <boost/geometry/util/condition.hpp>
0057 #include <boost/geometry/util/range.hpp>
0058 #include <boost/geometry/util/sequence.hpp>
0059 #include <boost/geometry/util/type_traits.hpp>
0060 
0061 
0062 namespace boost { namespace geometry
0063 {
0064 
0065 // TODO: This file is named interface.hpp but the code below is not the interface.
0066 //       It's the implementation of the algorithm.
0067 
0068 #ifndef DOXYGEN_NO_DETAIL
0069 namespace detail { namespace convex_hull
0070 {
0071 
0072 // Abstraction representing ranges/rings of a geometry
0073 template <typename Geometry>
0074 struct input_geometry_proxy
0075 {
0076     input_geometry_proxy(Geometry const& geometry)
0077         : m_geometry(geometry)
0078     {}
0079 
0080     template <typename UnaryFunction>
0081     inline void for_each_range(UnaryFunction fun) const
0082     {
0083         geometry::detail::for_each_range(m_geometry, fun);
0084     }
0085 
0086     Geometry const& m_geometry;
0087 };
0088 
0089 // Abstraction representing ranges/rings of subgeometries of geometry collection
0090 // with boxes converted to rings
0091 template <typename Geometry, typename BoxRings>
0092 struct input_geometry_collection_proxy
0093 {
0094     input_geometry_collection_proxy(Geometry const& geometry, BoxRings const& box_rings)
0095         : m_geometry(geometry)
0096         , m_box_rings(box_rings)
0097     {}
0098 
0099     template <typename UnaryFunction>
0100     inline void for_each_range(UnaryFunction fun) const
0101     {
0102         detail::visit_breadth_first([&](auto const& g)
0103         {
0104             input_geometry_collection_proxy::call_for_non_boxes(g, fun);
0105             return true;
0106         }, m_geometry);
0107 
0108         for (auto const& r : m_box_rings)
0109         {
0110             geometry::detail::for_each_range(r, fun);
0111         }
0112     }
0113 
0114 private:
0115     template <typename G, typename F, std::enable_if_t<! util::is_box<G>::value, int> = 0>
0116     static inline void call_for_non_boxes(G const& g, F & f)
0117     {
0118         geometry::detail::for_each_range(g, f);
0119     }
0120     template <typename G, typename F, std::enable_if_t<util::is_box<G>::value, int> = 0>
0121     static inline void call_for_non_boxes(G const&, F &)
0122     {}
0123 
0124     Geometry const& m_geometry;
0125     BoxRings const& m_box_rings;
0126 };
0127 
0128 
0129 // TODO: Or just implement point_type<> for GeometryCollection
0130 //   and enforce the same point_type used in the whole sequence in check().
0131 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0132 struct default_strategy
0133 {
0134     using type = typename strategies::convex_hull::services::default_strategy
0135         <
0136             Geometry
0137         >::type;
0138 };
0139 
0140 template <typename Geometry>
0141 struct default_strategy<Geometry, geometry_collection_tag>
0142     : default_strategy<typename detail::first_geometry_type<Geometry>::type>
0143 {};
0144 
0145 
0146 // Utilities for output GC and DG
0147 template <typename G1, typename G2>
0148 struct output_polygonal_less
0149 {
0150     template <typename G>
0151     using priority = std::integral_constant
0152         <
0153             int,
0154             (util::is_ring<G>::value ? 0 :
0155              util::is_polygon<G>::value ? 1 :
0156              util::is_multi_polygon<G>::value ? 2 : 3)
0157         >;
0158 
0159     static const bool value = priority<G1>::value < priority<G2>::value;
0160 };
0161 
0162 template <typename G1, typename G2>
0163 struct output_linear_less
0164 {
0165     template <typename G>
0166     using priority = std::integral_constant
0167         <
0168             int,
0169             (util::is_segment<G>::value ? 0 :
0170              util::is_linestring<G>::value ? 1 :
0171              util::is_multi_linestring<G>::value ? 2 : 3)
0172         >;
0173 
0174     static const bool value = priority<G1>::value < priority<G2>::value;
0175 };
0176 
0177 template <typename G1, typename G2>
0178 struct output_pointlike_less
0179 {
0180     template <typename G>
0181     using priority = std::integral_constant
0182         <
0183             int,
0184             (util::is_point<G>::value ? 0 :
0185              util::is_multi_point<G>::value ? 1 : 2)
0186         >;
0187 
0188     static const bool value = priority<G1>::value < priority<G2>::value;
0189 };
0190 
0191 
0192 }} // namespace detail::convex_hull
0193 #endif // DOXYGEN_NO_DETAIL
0194 
0195 
0196 #ifndef DOXYGEN_NO_DISPATCH
0197 namespace dispatch
0198 {
0199 
0200 
0201 template
0202 <
0203     typename Geometry,
0204     typename Tag = typename tag<Geometry>::type
0205 >
0206 struct convex_hull
0207 {
0208     template <typename OutputGeometry, typename Strategy>
0209     static inline void apply(Geometry const& geometry,
0210                              OutputGeometry& out,
0211                              Strategy const& strategy)
0212     {
0213         detail::convex_hull::input_geometry_proxy<Geometry> in_proxy(geometry);
0214         detail::convex_hull::graham_andrew
0215             <
0216                 typename point_type<Geometry>::type
0217             >::apply(in_proxy, out, strategy);
0218     }
0219 };
0220 
0221 
0222 // A hull for boxes is trivial. Any strategy is (currently) skipped.
0223 // TODO: This is not correct in spherical and geographic CS.
0224 template <typename Box>
0225 struct convex_hull<Box, box_tag>
0226 {
0227     template <typename OutputGeometry, typename Strategy>
0228     static inline void apply(Box const& box,
0229                              OutputGeometry& out,
0230                              Strategy const& )
0231     {
0232         static bool const Close
0233             = geometry::closure<OutputGeometry>::value == closed;
0234         static bool const Reverse
0235             = geometry::point_order<OutputGeometry>::value == counterclockwise;
0236 
0237         std::array<typename point_type<OutputGeometry>::type, 4> arr;
0238         // TODO: This assigns only 2d cooridnates!
0239         //       And it is also used in box_view<>!
0240         geometry::detail::assign_box_corners_oriented<Reverse>(box, arr);
0241 
0242         std::move(arr.begin(), arr.end(), range::back_inserter(out));
0243         if (BOOST_GEOMETRY_CONDITION(Close))
0244         {
0245             range::push_back(out, range::front(out));
0246         }
0247     }
0248 };
0249 
0250 
0251 template <typename GeometryCollection>
0252 struct convex_hull<GeometryCollection, geometry_collection_tag>
0253 {
0254     template <typename OutputGeometry, typename Strategy>
0255     static inline void apply(GeometryCollection const& geometry,
0256                              OutputGeometry& out,
0257                              Strategy const& strategy)
0258     {
0259         // Assuming that single point_type is used by the GeometryCollection
0260         using subgeometry_type = typename detail::first_geometry_type<GeometryCollection>::type;
0261         using point_type = typename geometry::point_type<subgeometry_type>::type;
0262         using ring_type = model::ring<point_type, true, false>;
0263 
0264         // Calculate box rings once
0265         std::vector<ring_type> box_rings;
0266         detail::visit_breadth_first([&](auto const& g)
0267         {
0268             convex_hull::add_ring_for_box(box_rings, g, strategy);
0269             return true;
0270         }, geometry);
0271 
0272         detail::convex_hull::input_geometry_collection_proxy
0273             <
0274                 GeometryCollection, std::vector<ring_type>
0275             > in_proxy(geometry, box_rings);
0276 
0277         detail::convex_hull::graham_andrew
0278             <
0279                 point_type
0280             >::apply(in_proxy, out, strategy);
0281     }
0282 
0283 private:
0284     template
0285     <
0286         typename Ring, typename SubGeometry, typename Strategy,
0287         std::enable_if_t<util::is_box<SubGeometry>::value, int> = 0
0288     >
0289     static inline void add_ring_for_box(std::vector<Ring> & rings, SubGeometry const& box,
0290                                         Strategy const& strategy)
0291     {
0292         Ring ring;
0293         convex_hull<SubGeometry>::apply(box, ring, strategy);
0294         rings.push_back(std::move(ring));
0295     }
0296     template
0297     <
0298         typename Ring, typename SubGeometry, typename Strategy,
0299         std::enable_if_t<! util::is_box<SubGeometry>::value, int> = 0
0300     >
0301     static inline void add_ring_for_box(std::vector<Ring> & , SubGeometry const& ,
0302                                         Strategy const& )
0303     {}
0304 };
0305 
0306 
0307 template <typename OutputGeometry, typename Tag = typename tag<OutputGeometry>::type>
0308 struct convex_hull_out
0309 {
0310     BOOST_GEOMETRY_STATIC_ASSERT_FALSE("This OutputGeometry is not supported.", OutputGeometry, Tag);
0311 };
0312 
0313 template <typename OutputGeometry>
0314 struct convex_hull_out<OutputGeometry, ring_tag>
0315 {
0316     template <typename Geometry, typename Strategies>
0317     static inline void apply(Geometry const& geometry,
0318                              OutputGeometry& out,
0319                              Strategies const& strategies)
0320     {
0321         dispatch::convex_hull<Geometry>::apply(geometry, out, strategies);
0322     }
0323 };
0324 
0325 template <typename OutputGeometry>
0326 struct convex_hull_out<OutputGeometry, polygon_tag>
0327 {
0328     template <typename Geometry, typename Strategies>
0329     static inline void apply(Geometry const& geometry,
0330                              OutputGeometry& out,
0331                              Strategies const& strategies)
0332     {
0333         auto&& ring = exterior_ring(out);
0334         dispatch::convex_hull<Geometry>::apply(geometry, ring, strategies);
0335     }
0336 };
0337 
0338 template <typename OutputGeometry>
0339 struct convex_hull_out<OutputGeometry, multi_polygon_tag>
0340 {
0341     template <typename Geometry, typename Strategies>
0342     static inline void apply(Geometry const& geometry,
0343                              OutputGeometry& out,
0344                              Strategies const& strategies)
0345     {
0346         typename boost::range_value<OutputGeometry>::type polygon;
0347         auto&& ring = exterior_ring(polygon);
0348         dispatch::convex_hull<Geometry>::apply(geometry, ring, strategies);
0349         // Empty input is checked so the output shouldn't be empty
0350         range::push_back(out, std::move(polygon));
0351     }
0352 };
0353 
0354 template <typename OutputGeometry>
0355 struct convex_hull_out<OutputGeometry, geometry_collection_tag>
0356 {
0357     using polygonal_t = typename util::sequence_min_element
0358         <
0359             typename traits::geometry_types<OutputGeometry>::type,
0360             detail::convex_hull::output_polygonal_less
0361         >::type;
0362     using linear_t = typename util::sequence_min_element
0363         <
0364             typename traits::geometry_types<OutputGeometry>::type,
0365             detail::convex_hull::output_linear_less
0366         >::type;
0367     using pointlike_t = typename util::sequence_min_element
0368         <
0369             typename traits::geometry_types<OutputGeometry>::type,
0370             detail::convex_hull::output_pointlike_less
0371         >::type;
0372 
0373     // select_element may define different kind of geometry than the one that is desired
0374     BOOST_GEOMETRY_STATIC_ASSERT(util::is_polygonal<polygonal_t>::value,
0375         "It must be possible to store polygonal geometry in OutputGeometry.", polygonal_t);
0376     BOOST_GEOMETRY_STATIC_ASSERT(util::is_linear<linear_t>::value,
0377         "It must be possible to store linear geometry in OutputGeometry.", linear_t);
0378     BOOST_GEOMETRY_STATIC_ASSERT(util::is_pointlike<pointlike_t>::value,
0379         "It must be possible to store pointlike geometry in OutputGeometry.", pointlike_t);
0380 
0381     template <typename Geometry, typename Strategies>
0382     static inline void apply(Geometry const& geometry,
0383                              OutputGeometry& out,
0384                              Strategies const& strategies)
0385     {
0386         polygonal_t polygonal;
0387         convex_hull_out<polygonal_t>::apply(geometry, polygonal, strategies);
0388         // Empty input is checked so the output shouldn't be empty
0389         auto&& out_ring = ring(polygonal);
0390 
0391         if (boost::size(out_ring) == detail::minimum_ring_size<polygonal_t>::value)
0392         {
0393             using detail::equals::equals_point_point;
0394             if (equals_point_point(range::front(out_ring), range::at(out_ring, 1), strategies))
0395             {
0396                 pointlike_t pointlike;
0397                 move_to_pointlike(out_ring, pointlike);
0398                 move_to_out(pointlike, out);
0399                 return;
0400             }
0401             if (equals_point_point(range::front(out_ring), range::at(out_ring, 2), strategies))
0402             {
0403                 linear_t linear;
0404                 move_to_linear(out_ring, linear);
0405                 move_to_out(linear, out);
0406                 return;
0407             }
0408         }
0409 
0410         move_to_out(polygonal, out);
0411     }
0412 
0413 private:
0414     template <typename Polygonal, util::enable_if_ring_t<Polygonal, int> = 0>
0415     static decltype(auto) ring(Polygonal const& polygonal)
0416     {
0417         return polygonal;
0418     }
0419     template <typename Polygonal, util::enable_if_polygon_t<Polygonal, int> = 0>
0420     static decltype(auto) ring(Polygonal const& polygonal)
0421     {
0422         return exterior_ring(polygonal);
0423     }
0424     template <typename Polygonal, util::enable_if_multi_polygon_t<Polygonal, int> = 0>
0425     static decltype(auto) ring(Polygonal const& polygonal)
0426     {
0427         return exterior_ring(range::front(polygonal));
0428     }
0429 
0430     template <typename Range, typename Linear, util::enable_if_segment_t<Linear, int> = 0>
0431     static void move_to_linear(Range & out_range, Linear & seg)
0432     {
0433         detail::assign_point_to_index<0>(range::front(out_range), seg);
0434         detail::assign_point_to_index<1>(range::at(out_range, 1), seg);
0435     }
0436     template <typename Range, typename Linear, util::enable_if_linestring_t<Linear, int> = 0>
0437     static void move_to_linear(Range & out_range, Linear & ls)
0438     {
0439         std::move(boost::begin(out_range), boost::begin(out_range) + 2, range::back_inserter(ls));
0440     }
0441     template <typename Range, typename Linear, util::enable_if_multi_linestring_t<Linear, int> = 0>
0442     static void move_to_linear(Range & out_range, Linear & mls)
0443     {
0444         typename boost::range_value<Linear>::type ls;
0445         std::move(boost::begin(out_range), boost::begin(out_range) + 2, range::back_inserter(ls));
0446         range::push_back(mls, std::move(ls));
0447     }
0448 
0449     template <typename Range, typename PointLike, util::enable_if_point_t<PointLike, int> = 0>
0450     static void move_to_pointlike(Range & out_range, PointLike & pt)
0451     {
0452         pt = range::front(out_range);
0453     }
0454     template <typename Range, typename PointLike, util::enable_if_multi_point_t<PointLike, int> = 0>
0455     static void move_to_pointlike(Range & out_range, PointLike & mpt)
0456     {
0457         range::push_back(mpt, std::move(range::front(out_range)));
0458     }
0459 
0460     template
0461     <
0462         typename Geometry, typename OutputGeometry_,
0463         util::enable_if_geometry_collection_t<OutputGeometry_, int> = 0
0464     >
0465     static void move_to_out(Geometry & g, OutputGeometry_ & out)
0466     {
0467         range::emplace_back(out, std::move(g));
0468     }
0469     template
0470     <
0471         typename Geometry, typename OutputGeometry_,
0472         util::enable_if_dynamic_geometry_t<OutputGeometry_, int> = 0
0473     >
0474     static void move_to_out(Geometry & g, OutputGeometry_ & out)
0475     {
0476         out = std::move(g);
0477     }
0478 };
0479 
0480 template <typename OutputGeometry>
0481 struct convex_hull_out<OutputGeometry, dynamic_geometry_tag>
0482     : convex_hull_out<OutputGeometry, geometry_collection_tag>
0483 {};
0484 
0485 
0486 // For backward compatibility
0487 template <typename OutputGeometry>
0488 struct convex_hull_out<OutputGeometry, linestring_tag>
0489     : convex_hull_out<OutputGeometry, ring_tag>
0490 {};
0491 
0492 
0493 } // namespace dispatch
0494 #endif // DOXYGEN_NO_DISPATCH
0495 
0496 
0497 namespace resolve_strategy {
0498 
0499 template <typename Strategies>
0500 struct convex_hull
0501 {
0502     template <typename Geometry, typename OutputGeometry>
0503     static inline void apply(Geometry const& geometry,
0504                              OutputGeometry& out,
0505                              Strategies const& strategies)
0506     {
0507         dispatch::convex_hull_out<OutputGeometry>::apply(geometry, out, strategies);
0508     }
0509 };
0510 
0511 template <>
0512 struct convex_hull<default_strategy>
0513 {
0514     template <typename Geometry, typename OutputGeometry>
0515     static inline void apply(Geometry const& geometry,
0516                              OutputGeometry& out,
0517                              default_strategy const&)
0518     {
0519         using strategy_type = typename detail::convex_hull::default_strategy
0520             <
0521                 Geometry
0522             >::type;
0523 
0524         dispatch::convex_hull_out<OutputGeometry>::apply(geometry, out, strategy_type());
0525     }
0526 };
0527 
0528 
0529 } // namespace resolve_strategy
0530 
0531 
0532 namespace resolve_dynamic {
0533 
0534 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0535 struct convex_hull
0536 {
0537     template <typename OutputGeometry, typename Strategy>
0538     static inline void apply(Geometry const& geometry,
0539                              OutputGeometry& out,
0540                              Strategy const& strategy)
0541     {
0542         concepts::check_concepts_and_equal_dimensions<
0543             const Geometry,
0544             OutputGeometry
0545         >();
0546 
0547         resolve_strategy::convex_hull<Strategy>::apply(geometry, out, strategy);
0548     }
0549 };
0550 
0551 template <typename Geometry>
0552 struct convex_hull<Geometry, dynamic_geometry_tag>
0553 {
0554     template <typename OutputGeometry, typename Strategy>
0555     static inline void apply(Geometry const& geometry,
0556                              OutputGeometry& out,
0557                              Strategy const& strategy)
0558     {
0559         traits::visit<Geometry>::apply([&](auto const& g)
0560         {
0561             convex_hull<util::remove_cref_t<decltype(g)>>::apply(g, out, strategy);
0562         }, geometry);
0563     }
0564 };
0565 
0566 
0567 } // namespace resolve_dynamic
0568 
0569 
0570 /*!
0571 \brief \brief_calc{convex hull} \brief_strategy
0572 \ingroup convex_hull
0573 \details \details_calc{convex_hull,convex hull} \brief_strategy.
0574 \tparam Geometry the input geometry type
0575 \tparam OutputGeometry the output geometry type
0576 \tparam Strategy the strategy type
0577 \param geometry \param_geometry,  input geometry
0578 \param out \param_geometry \param_set{convex hull}
0579 \param strategy \param_strategy{area}
0580 
0581 \qbk{distinguish,with strategy}
0582 
0583 \qbk{[include reference/algorithms/convex_hull.qbk]}
0584  */
0585 template<typename Geometry, typename OutputGeometry, typename Strategy>
0586 inline void convex_hull(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy)
0587 {
0588     if (geometry::is_empty(geometry))
0589     {
0590         // Leave output empty
0591         return;
0592     }
0593 
0594     resolve_dynamic::convex_hull<Geometry>::apply(geometry, out, strategy);
0595 }
0596 
0597 
0598 /*!
0599 \brief \brief_calc{convex hull}
0600 \ingroup convex_hull
0601 \details \details_calc{convex_hull,convex hull}.
0602 \tparam Geometry the input geometry type
0603 \tparam OutputGeometry the output geometry type
0604 \param geometry \param_geometry,  input geometry
0605 \param hull \param_geometry \param_set{convex hull}
0606 
0607 \qbk{[include reference/algorithms/convex_hull.qbk]}
0608  */
0609 template<typename Geometry, typename OutputGeometry>
0610 inline void convex_hull(Geometry const& geometry, OutputGeometry& hull)
0611 {
0612     geometry::convex_hull(geometry, hull, default_strategy());
0613 }
0614 
0615 
0616 }} // namespace boost::geometry
0617 
0618 
0619 #endif // BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_INTERFACE_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!