ceph/src/boost/boost/geometry/algorithms/centroid.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2014, 2015.
   9 // Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  13
  14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  16
  17 // Use, modification and distribution is subject to the Boost Software License,
  18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  19 // http://www.boost.org/LICENSE_1_0.txt)
  20
  21 #ifndef BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP
  22 #define BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP
  23
  24
  25 #include <cstddef>
  26
  27 #include <boost/core/ignore_unused.hpp>
  28 #include <boost/range.hpp>
  29 #include <boost/throw_exception.hpp>
  30
  31 #include <boost/variant/apply_visitor.hpp>
  32 #include <boost/variant/static_visitor.hpp>
  33 #include <boost/variant/variant_fwd.hpp>
  34
  35 #include <boost/geometry/core/closure.hpp>
  36 #include <boost/geometry/core/cs.hpp>
  37 #include <boost/geometry/core/coordinate_dimension.hpp>
  38 #include <boost/geometry/core/exception.hpp>
  39 #include <boost/geometry/core/exterior_ring.hpp>
  40 #include <boost/geometry/core/interior_rings.hpp>
  41 #include <boost/geometry/core/tag_cast.hpp>
  42 #include <boost/geometry/core/tags.hpp>
  43 #include <boost/geometry/core/point_type.hpp>
  44
  45 #include <boost/geometry/geometries/concepts/check.hpp>
  46
  47 #include <boost/geometry/algorithms/assign.hpp>
  48 #include <boost/geometry/algorithms/convert.hpp>
  49 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  50 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
  51 #include <boost/geometry/algorithms/not_implemented.hpp>
  52 #include <boost/geometry/strategies/centroid.hpp>
  53 #include <boost/geometry/strategies/concepts/centroid_concept.hpp>
  54 #include <boost/geometry/strategies/default_strategy.hpp>
  55 #include <boost/geometry/views/closeable_view.hpp>
  56
  57 #include <boost/geometry/util/for_each_coordinate.hpp>
  58 #include <boost/geometry/util/select_coordinate_type.hpp>
  59
  60 #include <boost/geometry/algorithms/is_empty.hpp>
  61
  62 #include <boost/geometry/algorithms/detail/centroid/translating_transformer.hpp>
  63
  64
  65 namespace boost { namespace geometry
  66 {
  67
  68
  69 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
  70
  71 /*!
  72 \brief Centroid Exception
  73 \ingroup centroid
  74 \details The centroid_exception is thrown if the free centroid function is called with
  75     geometries for which the centroid cannot be calculated. For example: a linestring
  76     without points, a polygon without points, an empty multi-geometry.
  77 \qbk{
  78 [heading See also]
  79 \* [link geometry.reference.algorithms.centroid the centroid function]
  80 }
  81
  82  */
  83 class centroid_exception : public geometry::exception
  84 {
  85 public:
  86
  87     /*!
  88     \brief The default constructor
  89     */
  90     inline centroid_exception() {}
  91
  92     /*!
  93     \brief Returns the explanatory string.
  94     \return Pointer to a null-terminated string with explanatory information.
  95     */
  96     virtual char const* what() const throw()
  97     {
  98         return "Boost.Geometry Centroid calculation exception";
  99     }
 100 };
 101
 102 #endif
 103
 104
 105 #ifndef DOXYGEN_NO_DETAIL
 106 namespace detail { namespace centroid
 107 {
 108
 109 struct centroid_point
 110 {
 111     template<typename Point, typename PointCentroid, typename Strategy>
 112     static inline void apply(Point const& point, PointCentroid& centroid,
 113             Strategy const&)
 114     {
 115         geometry::convert(point, centroid);
 116     }
 117 };
 118
 119 template
 120 <
 121     typename Indexed,
 122     typename Point,
 123     std::size_t Dimension = 0,
 124     std::size_t DimensionCount = dimension<Indexed>::type::value
 125 >
 126 struct centroid_indexed_calculator
 127 {
 128     typedef typename select_coordinate_type
 129         <
 130             Indexed, Point
 131         >::type coordinate_type;
 132     static inline void apply(Indexed const& indexed, Point& centroid)
 133     {
 134         coordinate_type const c1 = get<min_corner, Dimension>(indexed);
 135         coordinate_type const c2 = get<max_corner, Dimension>(indexed);
 136         coordinate_type m = c1 + c2;
 137         coordinate_type const two = 2;
 138         m /= two;
 139
 140         set<Dimension>(centroid, m);
 141
 142         centroid_indexed_calculator
 143             <
 144                 Indexed, Point, Dimension + 1
 145             >::apply(indexed, centroid);
 146     }
 147 };
 148
 149
 150 template<typename Indexed, typename Point, std::size_t DimensionCount>
 151 struct centroid_indexed_calculator<Indexed, Point, DimensionCount, DimensionCount>
 152 {
 153     static inline void apply(Indexed const& , Point& )
 154     {
 155     }
 156 };
 157
 158
 159 struct centroid_indexed
 160 {
 161     template<typename Indexed, typename Point, typename Strategy>
 162     static inline void apply(Indexed const& indexed, Point& centroid,
 163             Strategy const&)
 164     {
 165         centroid_indexed_calculator
 166             <
 167                 Indexed, Point
 168             >::apply(indexed, centroid);
 169     }
 170 };
 171
 172
 173 // There is one thing where centroid is different from e.g. within.
 174 // If the ring has only one point, it might make sense that
 175 // that point is the centroid.
 176 template<typename Point, typename Range>
 177 inline bool range_ok(Range const& range, Point& centroid)
 178 {
 179     std::size_t const n = boost::size(range);
 180     if (n > 1)
 181     {
 182         return true;
 183     }
 184     else if (n <= 0)
 185     {
 186 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
 187         BOOST_THROW_EXCEPTION(centroid_exception());
 188 #else
 189         return false;
 190 #endif
 191     }
 192     else // if (n == 1)
 193     {
 194         // Take over the first point in a "coordinate neutral way"
 195         geometry::convert(*boost::begin(range), centroid);
 196         return false;
 197     }
 198     //return true; // unreachable
 199 }
 200
 201 /*!
 202     \brief Calculate the centroid of a Ring or a Linestring.
 203 */
 204 template <closure_selector Closure>
 205 struct centroid_range_state
 206 {
 207     template<typename Ring, typename PointTransformer, typename Strategy>
 208     static inline void apply(Ring const& ring,
 209                              PointTransformer const& transformer,
 210                              Strategy const& strategy,
 211                              typename Strategy::state_type& state)
 212     {
 213         boost::ignore_unused(strategy);
 214
 215         typedef typename geometry::point_type<Ring const>::type point_type;
 216         typedef typename closeable_view<Ring const, Closure>::type view_type;
 217
 218         typedef typename boost::range_iterator<view_type const>::type iterator_type;
 219
 220         view_type view(ring);
 221         iterator_type it = boost::begin(view);
 222         iterator_type end = boost::end(view);
 223
 224         if (it != end)
 225         {
 226             typename PointTransformer::result_type
 227                 previous_pt = transformer.apply(*it);
 228
 229             for ( ++it ; it != end ; ++it)
 230             {
 231                 typename PointTransformer::result_type
 232                     pt = transformer.apply(*it);
 233
 234                 strategy.apply(static_cast<point_type const&>(previous_pt),
 235                                static_cast<point_type const&>(pt),
 236                                state);
 237
 238                 previous_pt = pt;
 239             }
 240         }
 241     }
 242 };
 243
 244 template <closure_selector Closure>
 245 struct centroid_range
 246 {
 247     template<typename Range, typename Point, typename Strategy>
 248     static inline bool apply(Range const& range, Point& centroid,
 249                              Strategy const& strategy)
 250     {
 251         if (range_ok(range, centroid))
 252         {
 253             // prepare translation transformer
 254             translating_transformer<Range> transformer(*boost::begin(range));
 255
 256             typename Strategy::state_type state;
 257             centroid_range_state<Closure>::apply(range, transformer,
 258                                                  strategy, state);
 259
 260             if ( strategy.result(state, centroid) )
 261             {
 262                 // translate the result back
 263                 transformer.apply_reverse(centroid);
 264                 return true;
 265             }
 266         }
 267
 268         return false;
 269     }
 270 };
 271
 272
 273 /*!
 274     \brief Centroid of a polygon.
 275     \note Because outer ring is clockwise, inners are counter clockwise,
 276     triangle approach is OK and works for polygons with rings.
 277 */
 278 struct centroid_polygon_state
 279 {
 280     template<typename Polygon, typename PointTransformer, typename Strategy>
 281     static inline void apply(Polygon const& poly,
 282                              PointTransformer const& transformer,
 283                              Strategy const& strategy,
 284                              typename Strategy::state_type& state)
 285     {
 286         typedef typename ring_type<Polygon>::type ring_type;
 287         typedef centroid_range_state<geometry::closure<ring_type>::value> per_ring;
 288
 289         per_ring::apply(exterior_ring(poly), transformer, strategy, state);
 290
 291         typename interior_return_type<Polygon const>::type
 292             rings = interior_rings(poly);
 293
 294         for (typename detail::interior_iterator<Polygon const>::type
 295                 it = boost::begin(rings); it != boost::end(rings); ++it)
 296         {
 297             per_ring::apply(*it, transformer, strategy, state);
 298         }
 299     }
 300 };
 301
 302 struct centroid_polygon
 303 {
 304     template<typename Polygon, typename Point, typename Strategy>
 305     static inline bool apply(Polygon const& poly, Point& centroid,
 306                              Strategy const& strategy)
 307     {
 308         if (range_ok(exterior_ring(poly), centroid))
 309         {
 310             // prepare translation transformer
 311             translating_transformer<Polygon>
 312                 transformer(*boost::begin(exterior_ring(poly)));
 313
 314             typename Strategy::state_type state;
 315             centroid_polygon_state::apply(poly, transformer, strategy, state);
 316
 317             if ( strategy.result(state, centroid) )
 318             {
 319                 // translate the result back
 320                 transformer.apply_reverse(centroid);
 321                 return true;
 322             }
 323         }
 324
 325         return false;
 326     }
 327 };
 328
 329
 330 /*!
 331     \brief Building block of a multi-point, to be used as Policy in the
 332         more generec centroid_multi
 333 */
 334 struct centroid_multi_point_state
 335 {
 336     template <typename Point, typename PointTransformer, typename Strategy>
 337     static inline void apply(Point const& point,
 338                              PointTransformer const& transformer,
 339                              Strategy const& strategy,
 340                              typename Strategy::state_type& state)
 341     {
 342         boost::ignore_unused(strategy);
 343         strategy.apply(static_cast<Point const&>(transformer.apply(point)),
 344                        state);
 345     }
 346 };
 347
 348
 349 /*!
 350     \brief Generic implementation which calls a policy to calculate the
 351         centroid of the total of its single-geometries
 352     \details The Policy is, in general, the single-version, with state. So
 353         detail::centroid::centroid_polygon_state is used as a policy for this
 354         detail::centroid::centroid_multi
 355
 356 */
 357 template <typename Policy>
 358 struct centroid_multi
 359 {
 360     template <typename Multi, typename Point, typename Strategy>
 361     static inline bool apply(Multi const& multi,
 362                              Point& centroid,
 363                              Strategy const& strategy)
 364     {
 365 #if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
 366         // If there is nothing in any of the ranges, it is not possible
 367         // to calculate the centroid
 368         if (geometry::is_empty(multi))
 369         {
 370             BOOST_THROW_EXCEPTION(centroid_exception());
 371         }
 372 #endif
 373
 374         // prepare translation transformer
 375         translating_transformer<Multi> transformer(multi);
 376
 377         typename Strategy::state_type state;
 378
 379         for (typename boost::range_iterator<Multi const>::type
 380                 it = boost::begin(multi);
 381             it != boost::end(multi);
 382             ++it)
 383         {
 384             Policy::apply(*it, transformer, strategy, state);
 385         }
 386
 387         if ( strategy.result(state, centroid) )
 388         {
 389             // translate the result back
 390             transformer.apply_reverse(centroid);
 391             return true;
 392         }
 393
 394         return false;
 395     }
 396 };
 397
 398
 399 template <typename Algorithm>
 400 struct centroid_linear_areal
 401 {
 402     template <typename Geometry, typename Point, typename Strategy>
 403     static inline void apply(Geometry const& geom,
 404                              Point& centroid,
 405                              Strategy const& strategy)
 406     {
 407         if ( ! Algorithm::apply(geom, centroid, strategy) )
 408         {
 409             geometry::point_on_border(centroid, geom);
 410         }
 411     }
 412 };
 413
 414
 415 }} // namespace detail::centroid
 416 #endif // DOXYGEN_NO_DETAIL
 417
 418
 419 #ifndef DOXYGEN_NO_DISPATCH
 420 namespace dispatch
 421 {
 422
 423 template
 424 <
 425     typename Geometry,
 426     typename Tag = typename tag<Geometry>::type
 427 >
 428 struct centroid: not_implemented<Tag>
 429 {};
 430
 431 template <typename Geometry>
 432 struct centroid<Geometry, point_tag>
 433     : detail::centroid::centroid_point
 434 {};
 435
 436 template <typename Box>
 437 struct centroid<Box, box_tag>
 438     : detail::centroid::centroid_indexed
 439 {};
 440
 441 template <typename Segment>
 442 struct centroid<Segment, segment_tag>
 443     : detail::centroid::centroid_indexed
 444 {};
 445
 446 template <typename Ring>
 447 struct centroid<Ring, ring_tag>
 448     : detail::centroid::centroid_linear_areal
 449         <
 450             detail::centroid::centroid_range<geometry::closure<Ring>::value>
 451         >
 452 {};
 453
 454 template <typename Linestring>
 455 struct centroid<Linestring, linestring_tag>
 456     : detail::centroid::centroid_linear_areal
 457         <
 458             detail::centroid::centroid_range<closed>
 459         >
 460 {};
 461
 462 template <typename Polygon>
 463 struct centroid<Polygon, polygon_tag>
 464     : detail::centroid::centroid_linear_areal
 465         <
 466             detail::centroid::centroid_polygon
 467         >
 468 {};
 469
 470 template <typename MultiLinestring>
 471 struct centroid<MultiLinestring, multi_linestring_tag>
 472     : detail::centroid::centroid_linear_areal
 473         <
 474             detail::centroid::centroid_multi
 475             <
 476                 detail::centroid::centroid_range_state<closed>
 477             >
 478         >
 479 {};
 480
 481 template <typename MultiPolygon>
 482 struct centroid<MultiPolygon, multi_polygon_tag>
 483     : detail::centroid::centroid_linear_areal
 484         <
 485             detail::centroid::centroid_multi
 486             <
 487                 detail::centroid::centroid_polygon_state
 488             >
 489         >
 490 {};
 491
 492 template <typename MultiPoint>
 493 struct centroid<MultiPoint, multi_point_tag>
 494     : detail::centroid::centroid_multi
 495         <
 496             detail::centroid::centroid_multi_point_state
 497         >
 498 {};
 499
 500
 501 } // namespace dispatch
 502 #endif // DOXYGEN_NO_DISPATCH
 503
 504
 505 namespace resolve_strategy {
 506
 507 template <typename Geometry>
 508 struct centroid
 509 {
 510     template <typename Point, typename Strategy>
 511     static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
 512     {
 513         dispatch::centroid<Geometry>::apply(geometry, out, strategy);
 514     }
 515
 516     template <typename Point>
 517     static inline void apply(Geometry const& geometry, Point& out, default_strategy)
 518     {
 519         typedef typename strategy::centroid::services::default_strategy
 520         <
 521             typename cs_tag<Geometry>::type,
 522             typename tag_cast
 523                 <
 524                     typename tag<Geometry>::type,
 525                     pointlike_tag,
 526                     linear_tag,
 527                     areal_tag
 528                 >::type,
 529             dimension<Geometry>::type::value,
 530             Point,
 531             Geometry
 532         >::type strategy_type;
 533
 534         dispatch::centroid<Geometry>::apply(geometry, out, strategy_type());
 535     }
 536 };
 537
 538 } // namespace resolve_strategy
 539
 540
 541 namespace resolve_variant {
 542
 543 template <typename Geometry>
 544 struct centroid
 545 {
 546     template <typename Point, typename Strategy>
 547     static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
 548     {
 549         concepts::check_concepts_and_equal_dimensions<Point, Geometry const>();
 550         resolve_strategy::centroid<Geometry>::apply(geometry, out, strategy);
 551     }
 552 };
 553
 554 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 555 struct centroid<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 556 {
 557     template <typename Point, typename Strategy>
 558     struct visitor: boost::static_visitor<void>
 559     {
 560         Point& m_out;
 561         Strategy const& m_strategy;
 562
 563         visitor(Point& out, Strategy const& strategy)
 564         : m_out(out), m_strategy(strategy)
 565         {}
 566
 567         template <typename Geometry>
 568         void operator()(Geometry const& geometry) const
 569         {
 570             centroid<Geometry>::apply(geometry, m_out, m_strategy);
 571         }
 572     };
 573
 574     template <typename Point, typename Strategy>
 575     static inline void
 576     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 577           Point& out,
 578           Strategy const& strategy)
 579     {
 580         boost::apply_visitor(visitor<Point, Strategy>(out, strategy), geometry);
 581     }
 582 };
 583
 584 } // namespace resolve_variant
 585
 586
 587 /*!
 588 \brief \brief_calc{centroid} \brief_strategy
 589 \ingroup centroid
 590 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_strategy_reasons
 591 \tparam Geometry \tparam_geometry
 592 \tparam Point \tparam_point
 593 \tparam Strategy \tparam_strategy{Centroid}
 594 \param geometry \param_geometry
 595 \param c \param_point \param_set{centroid}
 596 \param strategy \param_strategy{centroid}
 597
 598 \qbk{distinguish,with strategy}
 599 \qbk{[include reference/algorithms/centroid.qbk]}
 600 \qbk{[include reference/algorithms/centroid_strategies.qbk]}
 601 }
 602
 603 */
 604 template<typename Geometry, typename Point, typename Strategy>
 605 inline void centroid(Geometry const& geometry, Point& c,
 606         Strategy const& strategy)
 607 {
 608     resolve_variant::centroid<Geometry>::apply(geometry, c, strategy);
 609 }
 610
 611
 612 /*!
 613 \brief \brief_calc{centroid}
 614 \ingroup centroid
 615 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_default_strategy
 616 \tparam Geometry \tparam_geometry
 617 \tparam Point \tparam_point
 618 \param geometry \param_geometry
 619 \param c The calculated centroid will be assigned to this point reference
 620
 621 \qbk{[include reference/algorithms/centroid.qbk]}
 622 \qbk{
 623 [heading Example]
 624 [centroid]
 625 [centroid_output]
 626 }
 627  */
 628 template<typename Geometry, typename Point>
 629 inline void centroid(Geometry const& geometry, Point& c)
 630 {
 631     geometry::centroid(geometry, c, default_strategy());
 632 }
 633
 634
 635 /*!
 636 \brief \brief_calc{centroid}
 637 \ingroup centroid
 638 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}.
 639 \tparam Point \tparam_point
 640 \tparam Geometry \tparam_geometry
 641 \param geometry \param_geometry
 642 \return \return_calc{centroid}
 643
 644 \qbk{[include reference/algorithms/centroid.qbk]}
 645  */
 646 template<typename Point, typename Geometry>
 647 inline Point return_centroid(Geometry const& geometry)
 648 {
 649     Point c;
 650     geometry::centroid(geometry, c);
 651     return c;
 652 }
 653
 654 /*!
 655 \brief \brief_calc{centroid} \brief_strategy
 656 \ingroup centroid
 657 \details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}. \details_strategy_reasons
 658 \tparam Point \tparam_point
 659 \tparam Geometry \tparam_geometry
 660 \tparam Strategy \tparam_strategy{centroid}
 661 \param geometry \param_geometry
 662 \param strategy \param_strategy{centroid}
 663 \return \return_calc{centroid}
 664
 665 \qbk{distinguish,with strategy}
 666 \qbk{[include reference/algorithms/centroid.qbk]}
 667 \qbk{[include reference/algorithms/centroid_strategies.qbk]}
 668  */
 669 template<typename Point, typename Geometry, typename Strategy>
 670 inline Point return_centroid(Geometry const& geometry, Strategy const& strategy)
 671 {
 672     Point c;
 673     geometry::centroid(geometry, c, strategy);
 674     return c;
 675 }
 676
 677
 678 }} // namespace boost::geometry
 679
 680
 681 #endif // BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP