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