// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
// Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.

// This file was modified by Oracle on 2014, 2015.
// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.

// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle

// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.

// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP
#define BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP


#include <cstddef>

#include <boost/core/ignore_unused.hpp>
#include <boost/range.hpp>

#include <boost/variant/apply_visitor.hpp>
#include <boost/variant/static_visitor.hpp>
#include <boost/variant/variant_fwd.hpp>

#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
#include <boost/geometry/core/exception.hpp>
#include <boost/geometry/core/exterior_ring.hpp>
#include <boost/geometry/core/interior_rings.hpp>
#include <boost/geometry/core/tag_cast.hpp>
#include <boost/geometry/core/tags.hpp>
#include <boost/geometry/core/point_type.hpp>

#include <boost/geometry/geometries/concepts/check.hpp>

#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/not_implemented.hpp>
#include <boost/geometry/strategies/centroid.hpp>
#include <boost/geometry/strategies/concepts/centroid_concept.hpp>
#include <boost/geometry/strategies/default_strategy.hpp>
#include <boost/geometry/views/closeable_view.hpp>

#include <boost/geometry/util/for_each_coordinate.hpp>
#include <boost/geometry/util/select_coordinate_type.hpp>

#include <boost/geometry/algorithms/is_empty.hpp>

#include <boost/geometry/algorithms/detail/centroid/translating_transformer.hpp>


namespace boost { namespace geometry
{


#if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)

/*!
\brief Centroid Exception
\ingroup centroid
\details The centroid_exception is thrown if the free centroid function is called with
    geometries for which the centroid cannot be calculated. For example: a linestring
    without points, a polygon without points, an empty multi-geometry.
\qbk{
[heading See also]
\* [link geometry.reference.algorithms.centroid the centroid function]
}

 */
class centroid_exception : public geometry::exception
{
public:

    /*!
    \brief The default constructor
    */
    inline centroid_exception() {}

    /*!
    \brief Returns the explanatory string.
    \return Pointer to a null-terminated string with explanatory information.
    */
    virtual char const* what() const throw()
    {
        return "Boost.Geometry Centroid calculation exception";
    }
};

#endif


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace centroid
{

struct centroid_point
{
    template<typename Point, typename PointCentroid, typename Strategy>
    static inline void apply(Point const& point, PointCentroid& centroid,
            Strategy const&)
    {
        geometry::convert(point, centroid);
    }
};

template
<
    typename Indexed,
    typename Point,
    std::size_t Dimension = 0,
    std::size_t DimensionCount = dimension<Indexed>::type::value
>
struct centroid_indexed_calculator
{
    typedef typename select_coordinate_type
        <
            Indexed, Point
        >::type coordinate_type;
    static inline void apply(Indexed const& indexed, Point& centroid)
    {
        coordinate_type const c1 = get<min_corner, Dimension>(indexed);
        coordinate_type const c2 = get<max_corner, Dimension>(indexed);
        coordinate_type m = c1 + c2;
        coordinate_type const two = 2;
        m /= two;

        set<Dimension>(centroid, m);

        centroid_indexed_calculator
            <
                Indexed, Point, Dimension + 1
            >::apply(indexed, centroid);
    }
};


template<typename Indexed, typename Point, std::size_t DimensionCount>
struct centroid_indexed_calculator<Indexed, Point, DimensionCount, DimensionCount>
{
    static inline void apply(Indexed const& , Point& )
    {
    }
};


struct centroid_indexed
{
    template<typename Indexed, typename Point, typename Strategy>
    static inline void apply(Indexed const& indexed, Point& centroid,
            Strategy const&)
    {
        centroid_indexed_calculator
            <
                Indexed, Point
            >::apply(indexed, centroid);
    }
};


// There is one thing where centroid is different from e.g. within.
// If the ring has only one point, it might make sense that
// that point is the centroid.
template<typename Point, typename Range>
inline bool range_ok(Range const& range, Point& centroid)
{
    std::size_t const n = boost::size(range);
    if (n > 1)
    {
        return true;
    }
    else if (n <= 0)
    {
#if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
        throw centroid_exception();
#else
        return false;
#endif
    }
    else // if (n == 1)
    {
        // Take over the first point in a "coordinate neutral way"
        geometry::convert(*boost::begin(range), centroid);
        return false;
    }
    //return true; // unreachable
}

/*!
    \brief Calculate the centroid of a Ring or a Linestring.
*/
template <closure_selector Closure>
struct centroid_range_state
{
    template<typename Ring, typename PointTransformer, typename Strategy>
    static inline void apply(Ring const& ring,
                             PointTransformer const& transformer,
                             Strategy const& strategy,
                             typename Strategy::state_type& state)
    {
        boost::ignore_unused(strategy);

        typedef typename geometry::point_type<Ring const>::type point_type;
        typedef typename closeable_view<Ring const, Closure>::type view_type;

        typedef typename boost::range_iterator<view_type const>::type iterator_type;

        view_type view(ring);
        iterator_type it = boost::begin(view);
        iterator_type end = boost::end(view);

        if (it != end)
        {
            typename PointTransformer::result_type
                previous_pt = transformer.apply(*it);

            for ( ++it ; it != end ; ++it)
            {
                typename PointTransformer::result_type
                    pt = transformer.apply(*it);

                strategy.apply(static_cast<point_type const&>(previous_pt),
                               static_cast<point_type const&>(pt),
                               state);

                previous_pt = pt;
            }
        }
    }
};

template <closure_selector Closure>
struct centroid_range
{
    template<typename Range, typename Point, typename Strategy>
    static inline bool apply(Range const& range, Point& centroid,
                             Strategy const& strategy)
    {
        if (range_ok(range, centroid))
        {
            // prepare translation transformer
            translating_transformer<Range> transformer(*boost::begin(range));
            
            typename Strategy::state_type state;
            centroid_range_state<Closure>::apply(range, transformer,
                                                 strategy, state);
            
            if ( strategy.result(state, centroid) )
            {
                // translate the result back
                transformer.apply_reverse(centroid);
                return true;
            }
        }

        return false;
    }
};


/*!
    \brief Centroid of a polygon.
    \note Because outer ring is clockwise, inners are counter clockwise,
    triangle approach is OK and works for polygons with rings.
*/
struct centroid_polygon_state
{
    template<typename Polygon, typename PointTransformer, typename Strategy>
    static inline void apply(Polygon const& poly,
                             PointTransformer const& transformer,
                             Strategy const& strategy,
                             typename Strategy::state_type& state)
    {
        typedef typename ring_type<Polygon>::type ring_type;
        typedef centroid_range_state<geometry::closure<ring_type>::value> per_ring;

        per_ring::apply(exterior_ring(poly), transformer, strategy, state);

        typename interior_return_type<Polygon const>::type
            rings = interior_rings(poly);

        for (typename detail::interior_iterator<Polygon const>::type
                it = boost::begin(rings); it != boost::end(rings); ++it)
        {
            per_ring::apply(*it, transformer, strategy, state);
        }
    }
};

struct centroid_polygon
{
    template<typename Polygon, typename Point, typename Strategy>
    static inline bool apply(Polygon const& poly, Point& centroid,
                             Strategy const& strategy)
    {
        if (range_ok(exterior_ring(poly), centroid))
        {
            // prepare translation transformer
            translating_transformer<Polygon>
                transformer(*boost::begin(exterior_ring(poly)));
            
            typename Strategy::state_type state;
            centroid_polygon_state::apply(poly, transformer, strategy, state);
            
            if ( strategy.result(state, centroid) )
            {
                // translate the result back
                transformer.apply_reverse(centroid);
                return true;
            }
        }

        return false;
    }
};


/*!
    \brief Building block of a multi-point, to be used as Policy in the
        more generec centroid_multi
*/
struct centroid_multi_point_state
{
    template <typename Point, typename PointTransformer, typename Strategy>
    static inline void apply(Point const& point,
                             PointTransformer const& transformer,
                             Strategy const& strategy,
                             typename Strategy::state_type& state)
    {
        boost::ignore_unused(strategy);
        strategy.apply(static_cast<Point const&>(transformer.apply(point)),
                       state);
    }
};


/*!
    \brief Generic implementation which calls a policy to calculate the
        centroid of the total of its single-geometries
    \details The Policy is, in general, the single-version, with state. So
        detail::centroid::centroid_polygon_state is used as a policy for this
        detail::centroid::centroid_multi

*/
template <typename Policy>
struct centroid_multi
{
    template <typename Multi, typename Point, typename Strategy>
    static inline bool apply(Multi const& multi,
                             Point& centroid,
                             Strategy const& strategy)
    {
#if ! defined(BOOST_GEOMETRY_CENTROID_NO_THROW)
        // If there is nothing in any of the ranges, it is not possible
        // to calculate the centroid
        if (geometry::is_empty(multi))
        {
            throw centroid_exception();
        }
#endif

        // prepare translation transformer
        translating_transformer<Multi> transformer(multi);

        typename Strategy::state_type state;

        for (typename boost::range_iterator<Multi const>::type
                it = boost::begin(multi);
            it != boost::end(multi);
            ++it)
        {
            Policy::apply(*it, transformer, strategy, state);
        }

        if ( strategy.result(state, centroid) )
        {
            // translate the result back
            transformer.apply_reverse(centroid);
            return true;
        }
        
        return false;
    }
};


template <typename Algorithm>
struct centroid_linear_areal
{
    template <typename Geometry, typename Point, typename Strategy>
    static inline void apply(Geometry const& geom,
                             Point& centroid,
                             Strategy const& strategy)
    {
        if ( ! Algorithm::apply(geom, centroid, strategy) )
        {
            geometry::point_on_border(centroid, geom);
        }
    }
};


}} // namespace detail::centroid
#endif // DOXYGEN_NO_DETAIL


#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{

template
<
    typename Geometry,
    typename Tag = typename tag<Geometry>::type
>
struct centroid: not_implemented<Tag>
{};

template <typename Geometry>
struct centroid<Geometry, point_tag>
    : detail::centroid::centroid_point
{};

template <typename Box>
struct centroid<Box, box_tag>
    : detail::centroid::centroid_indexed
{};

template <typename Segment>
struct centroid<Segment, segment_tag>
    : detail::centroid::centroid_indexed
{};

template <typename Ring>
struct centroid<Ring, ring_tag>
    : detail::centroid::centroid_linear_areal
        <
            detail::centroid::centroid_range<geometry::closure<Ring>::value>
        >
{};

template <typename Linestring>
struct centroid<Linestring, linestring_tag>
    : detail::centroid::centroid_linear_areal
        <
            detail::centroid::centroid_range<closed>
        >
{};

template <typename Polygon>
struct centroid<Polygon, polygon_tag>
    : detail::centroid::centroid_linear_areal
        <
            detail::centroid::centroid_polygon
        >
{};

template <typename MultiLinestring>
struct centroid<MultiLinestring, multi_linestring_tag>
    : detail::centroid::centroid_linear_areal
        <
            detail::centroid::centroid_multi
            <
                detail::centroid::centroid_range_state<closed>
            >
        >
{};

template <typename MultiPolygon>
struct centroid<MultiPolygon, multi_polygon_tag>
    : detail::centroid::centroid_linear_areal
        <
            detail::centroid::centroid_multi
            <
                detail::centroid::centroid_polygon_state
            >
        >
{};

template <typename MultiPoint>
struct centroid<MultiPoint, multi_point_tag>
    : detail::centroid::centroid_multi
        <
            detail::centroid::centroid_multi_point_state
        >
{};


} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH


namespace resolve_strategy {

template <typename Geometry>
struct centroid
{
    template <typename Point, typename Strategy>
    static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
    {
        dispatch::centroid<Geometry>::apply(geometry, out, strategy);
    }

    template <typename Point>
    static inline void apply(Geometry const& geometry, Point& out, default_strategy)
    {
        typedef typename strategy::centroid::services::default_strategy
        <
            typename cs_tag<Geometry>::type,
            typename tag_cast
                <
                    typename tag<Geometry>::type,
                    pointlike_tag,
                    linear_tag,
                    areal_tag
                >::type,
            dimension<Geometry>::type::value,
            Point,
            Geometry
        >::type strategy_type;

        dispatch::centroid<Geometry>::apply(geometry, out, strategy_type());
    }
};

} // namespace resolve_strategy


namespace resolve_variant {

template <typename Geometry>
struct centroid
{
    template <typename Point, typename Strategy>
    static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy)
    {
        concepts::check_concepts_and_equal_dimensions<Point, Geometry const>();
        resolve_strategy::centroid<Geometry>::apply(geometry, out, strategy);
    }
};

template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
struct centroid<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
{
    template <typename Point, typename Strategy>
    struct visitor: boost::static_visitor<void>
    {
        Point& m_out;
        Strategy const& m_strategy;

        visitor(Point& out, Strategy const& strategy)
        : m_out(out), m_strategy(strategy)
        {}

        template <typename Geometry>
        void operator()(Geometry const& geometry) const
        {
            centroid<Geometry>::apply(geometry, m_out, m_strategy);
        }
    };

    template <typename Point, typename Strategy>
    static inline void
    apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
          Point& out,
          Strategy const& strategy)
    {
        boost::apply_visitor(visitor<Point, Strategy>(out, strategy), geometry);
    }
};

} // namespace resolve_variant


/*!
\brief \brief_calc{centroid} \brief_strategy
\ingroup centroid
\details \details_calc{centroid,geometric center (or: center of mass)}. \details_strategy_reasons
\tparam Geometry \tparam_geometry
\tparam Point \tparam_point
\tparam Strategy \tparam_strategy{Centroid}
\param geometry \param_geometry
\param c \param_point \param_set{centroid}
\param strategy \param_strategy{centroid}

\qbk{distinguish,with strategy}
\qbk{[include reference/algorithms/centroid.qbk]}
\qbk{[include reference/algorithms/centroid_strategies.qbk]}
}

*/
template<typename Geometry, typename Point, typename Strategy>
inline void centroid(Geometry const& geometry, Point& c,
        Strategy const& strategy)
{
    resolve_variant::centroid<Geometry>::apply(geometry, c, strategy);
}


/*!
\brief \brief_calc{centroid}
\ingroup centroid
\details \details_calc{centroid,geometric center (or: center of mass)}. \details_default_strategy
\tparam Geometry \tparam_geometry
\tparam Point \tparam_point
\param geometry \param_geometry
\param c The calculated centroid will be assigned to this point reference

\qbk{[include reference/algorithms/centroid.qbk]}
\qbk{
[heading Example]
[centroid]
[centroid_output]
}
 */
template<typename Geometry, typename Point>
inline void centroid(Geometry const& geometry, Point& c)
{
    geometry::centroid(geometry, c, default_strategy());
}


/*!
\brief \brief_calc{centroid}
\ingroup centroid
\details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}.
\tparam Point \tparam_point
\tparam Geometry \tparam_geometry
\param geometry \param_geometry
\return \return_calc{centroid}

\qbk{[include reference/algorithms/centroid.qbk]}
 */
template<typename Point, typename Geometry>
inline Point return_centroid(Geometry const& geometry)
{
    Point c;
    geometry::centroid(geometry, c);
    return c;
}

/*!
\brief \brief_calc{centroid} \brief_strategy
\ingroup centroid
\details \details_calc{centroid,geometric center (or: center of mass)}. \details_return{centroid}. \details_strategy_reasons
\tparam Point \tparam_point
\tparam Geometry \tparam_geometry
\tparam Strategy \tparam_strategy{centroid}
\param geometry \param_geometry
\param strategy \param_strategy{centroid}
\return \return_calc{centroid}

\qbk{distinguish,with strategy}
\qbk{[include reference/algorithms/centroid.qbk]}
\qbk{[include reference/algorithms/centroid_strategies.qbk]}
 */
template<typename Point, typename Geometry, typename Strategy>
inline Point return_centroid(Geometry const& geometry, Strategy const& strategy)
{
    Point c;
    geometry::centroid(geometry, c, strategy);
    return c;
}


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_CENTROID_HPP