geometry/algorithms/centroid.hpp

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) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2014-2023.
0009 // Modifications copyright (c) 2014-2023 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0011 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0012 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0013
0014 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0015 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0016
0017 // Use, modification and distribution is subject to the Boost Software License,
0018 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0019 // http://www.boost.org/LICENSE_1_0.txt)
0020
0021 #ifndef BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP
0022 #define BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP
0023
0024
0025 #include <cstddef>
0026
0027 #include <boost/core/ignore_unused.hpp>
0028 #include <boost/range/begin.hpp>
0029 #include <boost/range/end.hpp>
0030 #include <boost/range/size.hpp>
0031 #include <boost/throw_exception.hpp>
0032
0033 #include <boost/geometry/core/exception.hpp>
0034 #include <boost/geometry/core/exterior_ring.hpp>
0035 #include <boost/geometry/core/interior_rings.hpp>
0036 #include <boost/geometry/core/tags.hpp>
0037 #include <boost/geometry/core/point_type.hpp>
0038 #include <boost/geometry/core/visit.hpp>
0039
0040 #include <boost/geometry/algorithms/convert.hpp>
0041 #include <boost/geometry/algorithms/detail/centroid/translating_transformer.hpp>
0042 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0043 #include <boost/geometry/algorithms/is_empty.hpp>
0044 #include <boost/geometry/algorithms/not_implemented.hpp>
0045
0046 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
0047 #include <boost/geometry/geometries/concepts/check.hpp>
0048
0049 #include <boost/geometry/strategies/centroid/cartesian.hpp>
0050 #include <boost/geometry/strategies/centroid/geographic.hpp>
0051 #include <boost/geometry/strategies/centroid/spherical.hpp>
0052 #include <boost/geometry/strategies/concepts/centroid_concept.hpp>
0053 #include <boost/geometry/strategies/default_strategy.hpp>
0054 #include <boost/geometry/strategies/detail.hpp>
0055
0056 #include <boost/geometry/util/algorithm.hpp>
0057 #include <boost/geometry/util/select_coordinate_type.hpp>
0058 #include <boost/geometry/util/type_traits_std.hpp>
0059
0060 #include <boost/geometry/views/closeable_view.hpp>
0061
0062
0063 namespace boost { namespace geometry
0064 {
0065
0066
0067 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
0068
0069 /*!
0070 \brief Centroid Exception
0071 \ingroup centroid
0072 \details The centroid_exception is thrown if the free centroid function is called with
0073     geometries for which the centroid cannot be calculated. For example: a linestring
0074     without points, a polygon without points, an empty multi-geometry.
0075 \qbk{
0076 [heading See also]
0077 \* [link geometry.reference.algorithms.centroid the centroid function]
0078 }
0079
0080  */
0081 class centroid_exception : public geometry::exception
0082 {
0083 public:
0084
0085     inline centroid_exception() {}
0086
0087     char const* what() const noexcept override
0088     {
0089         return "Boost.Geometry Centroid calculation exception";
0090     }
0091 };
0092
0093 #endif
0094
0095
0096 #ifndef DOXYGEN_NO_DETAIL
0097 namespace detail { namespace centroid
0098 {
0099
0100 struct centroid_point
0101 {
0102     template<typename Point, typename PointCentroid, typename Strategy>
0103     static inline void apply(Point const& point, PointCentroid& centroid,
0104             Strategy const&)
0105     {
0106         geometry::convert(point, centroid);
0107     }
0108 };
0109
0110 struct centroid_indexed
0111 {
0112     template<typename Indexed, typename Point, typename Strategy>
0113     static inline void apply(Indexed const& indexed, Point& centroid,
0114             Strategy const&)
0115     {
0116         typedef typename select_coordinate_type
0117             <
0118                 Indexed, Point
0119             >::type coordinate_type;
0120
0121         detail::for_each_dimension<Indexed>([&](auto dimension)
0122         {
0123             coordinate_type const c1 = get<min_corner, dimension>(indexed);
0124             coordinate_type const c2 = get<max_corner, dimension>(indexed);
0125             coordinate_type const two = 2;
0126             set<dimension>(centroid, (c1 + c2) / two);
0127         });
0128     }
0129 };
0130
0131
0132 // There is one thing where centroid is different from e.g. within.
0133 // If the ring has only one point, it might make sense that
0134 // that point is the centroid.
0135 template<typename Point, typename Range>
0136 inline bool range_ok(Range const& range, Point& centroid)
0137 {
0138     std::size_t const n = boost::size(range);
0139     if (n > 1)
0140     {
0141         return true;
0142     }
0143     else if (n <= 0)
0144     {
0145 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
0146         BOOST_THROW_EXCEPTION(centroid_exception());
0147 #else
0148         return false;
0149 #endif
0150     }
0151     else // if (n == 1)
0152     {
0153         // Take over the first point in a "coordinate neutral way"
0154         geometry::convert(*boost::begin(range), centroid);
0155         return false;
0156     }
0157     //return true; // unreachable
0158 }
0159
0160 /*!
0161     \brief Calculate the centroid of a Ring or a Linestring.
0162 */
0163 struct centroid_range_state
0164 {
0165     template<typename Ring, typename PointTransformer, typename Strategy, typename State>
0166     static inline void apply(Ring const& ring,
0167                              PointTransformer const& transformer,
0168                              Strategy const& strategy,
0169                              State& state)
0170     {
0171         boost::ignore_unused(strategy);
0172
0173         detail::closed_view<Ring const> const view(ring);
0174         auto it = boost::begin(view);
0175         auto const end = boost::end(view);
0176
0177         if (it != end)
0178         {
0179             typename PointTransformer::result_type
0180                 previous_pt = transformer.apply(*it);
0181
0182             for ( ++it ; it != end ; ++it)
0183             {
0184                 typename PointTransformer::result_type
0185                     pt = transformer.apply(*it);
0186
0187                 using point_type = typename geometry::point_type<Ring const>::type;
0188                 strategy.apply(static_cast<point_type const&>(previous_pt),
0189                                static_cast<point_type const&>(pt),
0190                                state);
0191
0192                 previous_pt = pt;
0193             }
0194         }
0195     }
0196 };
0197
0198 struct centroid_range
0199 {
0200     template<typename Range, typename Point, typename Strategy>
0201     static inline bool apply(Range const& range, Point& centroid,
0202                              Strategy const& strategy)
0203     {
0204         if (range_ok(range, centroid))
0205         {
0206             // prepare translation transformer
0207             translating_transformer<Range> transformer(*boost::begin(range));
0208
0209             typename Strategy::template state_type
0210                 <
0211                     typename geometry::point_type<Range>::type,
0212                     Point
0213                 >::type state;
0214
0215             centroid_range_state::apply(range, transformer, strategy, state);
0216
0217             if ( strategy.result(state, centroid) )
0218             {
0219                 // translate the result back
0220                 transformer.apply_reverse(centroid);
0221                 return true;
0222             }
0223         }
0224
0225         return false;
0226     }
0227 };
0228
0229
0230 /*!
0231     \brief Centroid of a polygon.
0232     \note Because outer ring is clockwise, inners are counter clockwise,
0233     triangle approach is OK and works for polygons with rings.
0234 */
0235 struct centroid_polygon_state
0236 {
0237     template<typename Polygon, typename PointTransformer, typename Strategy, typename State>
0238     static inline void apply(Polygon const& poly,
0239                              PointTransformer const& transformer,
0240                              Strategy const& strategy,
0241                              State& state)
0242     {
0243         centroid_range_state::apply(exterior_ring(poly), transformer, strategy, state);
0244
0245         auto const& rings = interior_rings(poly);
0246         auto const end = boost::end(rings);
0247         for (auto it = boost::begin(rings); it != end; ++it)
0248         {
0249             centroid_range_state::apply(*it, transformer, strategy, state);
0250         }
0251     }
0252 };
0253
0254 struct centroid_polygon
0255 {
0256     template<typename Polygon, typename Point, typename Strategy>
0257     static inline bool apply(Polygon const& poly, Point& centroid,
0258                              Strategy const& strategy)
0259     {
0260         if (range_ok(exterior_ring(poly), centroid))
0261         {
0262             // prepare translation transformer
0263             translating_transformer<Polygon>
0264                 transformer(*boost::begin(exterior_ring(poly)));
0265
0266             typename Strategy::template state_type
0267                 <
0268                     typename geometry::point_type<Polygon>::type,
0269                     Point
0270                 >::type state;
0271
0272             centroid_polygon_state::apply(poly, transformer, strategy, state);
0273
0274             if ( strategy.result(state, centroid) )
0275             {
0276                 // translate the result back
0277                 transformer.apply_reverse(centroid);
0278                 return true;
0279             }
0280         }
0281
0282         return false;
0283     }
0284 };
0285
0286
0287 /*!
0288     \brief Building block of a multi-point, to be used as Policy in the
0289         more generec centroid_multi
0290 */
0291 struct centroid_multi_point_state
0292 {
0293     template <typename Point, typename PointTransformer, typename Strategy, typename State>
0294     static inline void apply(Point const& point,
0295                              PointTransformer const& transformer,
0296                              Strategy const& strategy,
0297                              State& state)
0298     {
0299         boost::ignore_unused(strategy);
0300         strategy.apply(static_cast<Point const&>(transformer.apply(point)),
0301                        state);
0302     }
0303 };
0304
0305
0306 /*!
0307     \brief Generic implementation which calls a policy to calculate the
0308         centroid of the total of its single-geometries
0309     \details The Policy is, in general, the single-version, with state. So
0310         detail::centroid::centroid_polygon_state is used as a policy for this
0311         detail::centroid::centroid_multi
0312
0313 */
0314 template <typename Policy>
0315 struct centroid_multi
0316 {
0317     template <typename Multi, typename Point, typename Strategy>
0318     static inline bool apply(Multi const& multi,
0319                              Point& centroid,
0320                              Strategy const& strategy)
0321     {
0322 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
0323         // If there is nothing in any of the ranges, it is not possible
0324         // to calculate the centroid
0325         if (geometry::is_empty(multi))
0326         {
0327             BOOST_THROW_EXCEPTION(centroid_exception());
0328         }
0329 #endif
0330
0331         // prepare translation transformer
0332         translating_transformer<Multi> transformer(multi);
0333
0334         typename Strategy::template state_type
0335             <
0336                 typename geometry::point_type<Multi>::type,
0337                 Point
0338             >::type state;
0339
0340         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0341         {
0342             Policy::apply(*it, transformer, strategy, state);
0343         }
0344
0345         if (strategy.result(state, centroid))
0346         {
0347             // translate the result back
0348             transformer.apply_reverse(centroid);
0349             return true;
0350         }
0351
0352         return false;
0353     }
0354 };
0355
0356
0357 template <typename Algorithm>
0358 struct centroid_linear_areal
0359 {
0360     template <typename Geometry, typename Point, typename Strategies>
0361     static inline void apply(Geometry const& geom,
0362                              Point& centroid,
0363                              Strategies const& strategies)
0364     {
0365         if ( ! Algorithm::apply(geom, centroid, strategies.centroid(geom)) )
0366         {
0367             geometry::point_on_border(centroid, geom);
0368         }
0369     }
0370 };
0371
0372 template <typename Algorithm>
0373 struct centroid_pointlike
0374 {
0375     template <typename Geometry, typename Point, typename Strategies>
0376     static inline void apply(Geometry const& geom,
0377                              Point& centroid,
0378                              Strategies const& strategies)
0379     {
0380         Algorithm::apply(geom, centroid, strategies.centroid(geom));
0381     }
0382 };
0383
0384
0385 }} // namespace detail::centroid
0386 #endif // DOXYGEN_NO_DETAIL
0387
0388
0389 #ifndef DOXYGEN_NO_DISPATCH
0390 namespace dispatch
0391 {
0392
0393 template
0394 <
0395     typename Geometry,
0396     typename Tag = typename tag<Geometry>::type
0397 >
0398 struct centroid: not_implemented<Tag>
0399 {};
0400
0401 template <typename Geometry>
0402 struct centroid<Geometry, point_tag>
0403     : detail::centroid::centroid_point
0404 {};
0405
0406 template <typename Box>
0407 struct centroid<Box, box_tag>
0408     : detail::centroid::centroid_indexed
0409 {};
0410
0411 template <typename Segment>
0412 struct centroid<Segment, segment_tag>
0413     : detail::centroid::centroid_indexed
0414 {};
0415
0416 template <typename Ring>
0417 struct centroid<Ring, ring_tag>
0418     : detail::centroid::centroid_linear_areal
0419         <
0420             detail::centroid::centroid_range
0421         >
0422 {};
0423
0424 template <typename Linestring>
0425 struct centroid<Linestring, linestring_tag>
0426     : detail::centroid::centroid_linear_areal
0427         <
0428             detail::centroid::centroid_range
0429         >
0430 {};
0431
0432 template <typename Polygon>
0433 struct centroid<Polygon, polygon_tag>
0434     : detail::centroid::centroid_linear_areal
0435         <
0436             detail::centroid::centroid_polygon
0437         >
0438 {};
0439
0440 template <typename MultiLinestring>
0441 struct centroid<MultiLinestring, multi_linestring_tag>
0442     : detail::centroid::centroid_linear_areal
0443         <
0444             detail::centroid::centroid_multi
0445             <
0446                 detail::centroid::centroid_range_state
0447             >
0448         >
0449 {};
0450
0451 template <typename MultiPolygon>
0452 struct centroid<MultiPolygon, multi_polygon_tag>
0453     : detail::centroid::centroid_linear_areal
0454         <
0455             detail::centroid::centroid_multi
0456             <
0457                 detail::centroid::centroid_polygon_state
0458             >
0459         >
0460 {};
0461
0462 template <typename MultiPoint>
0463 struct centroid<MultiPoint, multi_point_tag>
0464     : detail::centroid::centroid_pointlike
0465         <
0466             detail::centroid::centroid_multi
0467             <
0468                 detail::centroid::centroid_multi_point_state
0469             >
0470         >
0471 {};
0472
0473
0474 } // namespace dispatch
0475 #endif // DOXYGEN_NO_DISPATCH
0476
0477
0478 namespace resolve_strategy {
0479
0480 template
0481 <
0482     typename Strategies,
0483     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0484 >
0485 struct centroid
0486 {
0487     template <typename Geometry, typename Point>
0488     static inline void apply(Geometry const& geometry, Point& out, Strategies const& strategies)
0489     {
0490         dispatch::centroid<Geometry>::apply(geometry, out, strategies);
0491     }
0492 };
0493
0494 template <typename Strategy>
0495 struct centroid<Strategy, false>
0496 {
0497     template <typename Geometry, typename Point>
0498     static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
0499     {
0500         using strategies::centroid::services::strategy_converter;
0501         dispatch::centroid
0502             <
0503                 Geometry
0504             >::apply(geometry, out, strategy_converter<Strategy>::get(strategy));
0505     }
0506 };
0507
0508 template <>
0509 struct centroid<default_strategy, false>
0510 {
0511     template <typename Geometry, typename Point>
0512     static inline void apply(Geometry const& geometry, Point& out, default_strategy)
0513     {
0514         typedef typename strategies::centroid::services::default_strategy
0515             <
0516                 Geometry
0517             >::type strategies_type;
0518
0519         dispatch::centroid<Geometry>::apply(geometry, out, strategies_type());
0520     }
0521 };
0522
0523 } // namespace resolve_strategy
0524
0525
0526 namespace resolve_dynamic {
0527
0528 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0529 struct centroid
0530 {
0531     template <typename Point, typename Strategy>
0532     static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
0533     {
0534         concepts::check_concepts_and_equal_dimensions<Point, Geometry const>();
0535         resolve_strategy::centroid<Strategy>::apply(geometry, out, strategy);
0536     }
0537 };
0538
0539 template <typename Geometry>
0540 struct centroid<Geometry, dynamic_geometry_tag>
0541 {
0542     template <typename Point, typename Strategy>
0543     static inline void apply(Geometry const& geometry,
0544                              Point& out,
0545                              Strategy const& strategy)
0546     {
0547         traits::visit<Geometry>::apply([&](auto const& g)
0548         {
0549             centroid<util::remove_cref_t<decltype(g)>>::apply(g, out, strategy);
0550         }, geometry);
0551     }
0552 };
0553
0554 } // namespace resolve_dynamic
0555
0556
0557 /*!
0558 \brief \brief_calc{centroid} \brief_strategy
0559 \ingroup centroid
0560 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_strategy_reasons
0561 \tparam Geometry \tparam_geometry
0562 \tparam Point \tparam_point
0563 \tparam Strategy \tparam_strategy{Centroid}
0564 \param geometry \param_geometry
0565 \param c \param_point \param_set{centroid}
0566 \param strategy \param_strategy{centroid}
0567
0568 \qbk{distinguish,with strategy}
0569 \qbk{[include reference/algorithms/centroid.qbk]}
0570 \qbk{[include reference/algorithms/centroid_strategies.qbk]}
0571 }
0572
0573 */
0574 template<typename Geometry, typename Point, typename Strategy>
0575 inline void centroid(Geometry const& geometry, Point& c, Strategy const& strategy)
0576 {
0577     resolve_dynamic::centroid<Geometry>::apply(geometry, c, strategy);
0578 }
0579
0580
0581 /*!
0582 \brief \brief_calc{centroid}
0583 \ingroup centroid
0584 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_default_strategy
0585 \tparam Geometry \tparam_geometry
0586 \tparam Point \tparam_point
0587 \param geometry \param_geometry
0588 \param c The calculated centroid will be assigned to this point reference
0589
0590 \qbk{[include reference/algorithms/centroid.qbk]}
0591 \qbk{
0592 [heading Example]
0593 [centroid]
0594 [centroid_output]
0595 }
0596  */
0597 template<typename Geometry, typename Point>
0598 inline void centroid(Geometry const& geometry, Point& c)
0599 {
0600     geometry::centroid(geometry, c, default_strategy());
0601 }
0602
0603
0604 /*!
0605 \brief \brief_calc{centroid}
0606 \ingroup centroid
0607 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}.
0608 \tparam Point \tparam_point
0609 \tparam Geometry \tparam_geometry
0610 \param geometry \param_geometry
0611 \return \return_calc{centroid}
0612
0613 \qbk{[include reference/algorithms/centroid.qbk]}
0614  */
0615 template<typename Point, typename Geometry>
0616 inline Point return_centroid(Geometry const& geometry)
0617 {
0618     Point c;
0619     geometry::centroid(geometry, c);
0620     return c;
0621 }
0622
0623 /*!
0624 \brief \brief_calc{centroid} \brief_strategy
0625 \ingroup centroid
0626 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}. \details_strategy_reasons
0627 \tparam Point \tparam_point
0628 \tparam Geometry \tparam_geometry
0629 \tparam Strategy \tparam_strategy{centroid}
0630 \param geometry \param_geometry
0631 \param strategy \param_strategy{centroid}
0632 \return \return_calc{centroid}
0633
0634 \qbk{distinguish,with strategy}
0635 \qbk{[include reference/algorithms/centroid.qbk]}
0636 \qbk{[include reference/algorithms/centroid_strategies.qbk]}
0637  */
0638 template<typename Point, typename Geometry, typename Strategy>
0639 inline Point return_centroid(Geometry const& geometry, Strategy const& strategy)
0640 {
0641     Point c;
0642     geometry::centroid(geometry, c, strategy);
0643     return c;
0644 }
0645
0646
0647 }} // namespace boost::geometry
0648
0649
0650 #endif // BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP