path: root/boost/geometry/algorithms/detail/extreme_points.hpp

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

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

// 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_DETAIL_EXTREME_POINTS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP


#include <cstddef>

#include <boost/range.hpp>

#include <boost/geometry/algorithms/detail/interior_iterator.hpp>

#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/core/point_type.hpp>
#include <boost/geometry/core/ring_type.hpp>
#include <boost/geometry/core/tags.hpp>

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

#include <boost/geometry/algorithms/detail/assign_box_corners.hpp>

#include <boost/geometry/strategies/side.hpp>

#include <boost/geometry/util/math.hpp>


namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace extreme_points
{

template <std::size_t Dimension>
struct compare
{
    template <typename Point>
    inline bool operator()(Point const& lhs, Point const& rhs)
    {
        return geometry::get<Dimension>(lhs) < geometry::get<Dimension>(rhs);
    }
};


template <std::size_t Dimension, typename PointType, typename CoordinateType>
inline void move_along_vector(PointType& point, PointType const& extreme, CoordinateType const& base_value)
{
    // Moves a point along the vector (point, extreme) in the direction of the extreme  point
    // This adapts the possibly uneven legs of the triangle (or trapezium-like shape)
    //      _____extreme            _____
    //     /     \                 /     \                                    .
    //    /base   \         =>    /       \ point                             .
    //             \ point                                                    .
    //
    // For so-called intruders, it can be used to adapt both legs to the level of "base"
    // For the base, it can be used to adapt both legs to the level of the max-value of the intruders
    // If there are 2 or more extreme values, use the one close to 'point' to have a correct vector

    CoordinateType const value = geometry::get<Dimension>(point);
    //if (geometry::math::equals(value, base_value))
    if (value >= base_value)
    {
        return;
    }

    PointType vector = point;
    subtract_point(vector, extreme);

    CoordinateType const diff = geometry::get<Dimension>(vector);

    // diff should never be zero
    // because of the way our triangle/trapezium is build.
    // We just return if it would be the case.
    if (geometry::math::equals(diff, 0))
    {
        return;
    }

    CoordinateType const base_diff = base_value - geometry::get<Dimension>(extreme);

    multiply_value(vector, base_diff);
    divide_value(vector, diff);

    // The real move:
    point = extreme;
    add_point(point, vector);
}


template <std::size_t Dimension, typename Range, typename CoordinateType>
inline void move_along_vector(Range& range, CoordinateType const& base_value)
{
    if (range.size() >= 3)
    {
        move_along_vector<Dimension>(range.front(), *(range.begin() + 1), base_value);
        move_along_vector<Dimension>(range.back(), *(range.rbegin() + 1), base_value);
    }
}


template<typename Ring, std::size_t Dimension>
struct extreme_points_on_ring
{

    typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
    typedef typename boost::range_iterator<Ring const>::type range_iterator;
    typedef typename geometry::point_type<Ring>::type point_type;

    typedef typename geometry::strategy::side::services::default_strategy
        <
            typename geometry::cs_tag<point_type>::type
        >::type side_strategy;


    template <typename CirclingIterator, typename Points>
    static inline bool extend(CirclingIterator& it,
            std::size_t n,
            coordinate_type max_coordinate_value,
            Points& points, int direction)
    {
        std::size_t safe_index = 0;
        do
        {
            it += direction;

            points.push_back(*it);

            if (safe_index++ >= n)
            {
                // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop)
                return false;
            }
        } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value));

        return true;
    }

    // Overload without adding to poinst
    template <typename CirclingIterator>
    static inline bool extend(CirclingIterator& it,
            std::size_t n,
            coordinate_type max_coordinate_value,
            int direction)
    {
        std::size_t safe_index = 0;
        do
        {
            it += direction;

            if (safe_index++ >= n)
            {
                // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop)
                return false;
            }
        } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value));

        return true;
    }

    template <typename CirclingIterator>
    static inline bool extent_both_sides(Ring const& ring,
            point_type extreme,
            CirclingIterator& left,
            CirclingIterator& right)
    {
        std::size_t const n = boost::size(ring);
        coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme);

        if (! extend(left, n, max_coordinate_value, -1))
        {
            return false;
        }
        if (! extend(right, n, max_coordinate_value, +1))
        {
            return false;
        }

        return true;
    }

    template <typename Collection, typename CirclingIterator>
    static inline bool collect(Ring const& ring,
            point_type extreme,
            Collection& points,
            CirclingIterator& left,
            CirclingIterator& right)
    {
        std::size_t const n = boost::size(ring);
        coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme);

        // Collects first left, which is reversed (if more than one point) then adds the top itself, then right
        if (! extend(left, n, max_coordinate_value, points, -1))
        {
            return false;
        }
        std::reverse(points.begin(), points.end());
        points.push_back(extreme);
        if (! extend(right, n, max_coordinate_value, points, +1))
        {
            return false;
        }

        return true;
    }

    template <typename Extremes, typename Intruders, typename CirclingIterator>
    static inline void get_intruders(Ring const& ring, CirclingIterator left, CirclingIterator right,
            Extremes const& extremes,
            Intruders& intruders)
    {
        if (boost::size(extremes) < 3)
        {
            return;
        }
        coordinate_type const min_value = geometry::get<Dimension>(*std::min_element(boost::begin(extremes), boost::end(extremes), compare<Dimension>()));

        // Also select left/right (if Dimension=1)
        coordinate_type const other_min = geometry::get<1 - Dimension>(*std::min_element(boost::begin(extremes), boost::end(extremes), compare<1 - Dimension>()));
        coordinate_type const other_max = geometry::get<1 - Dimension>(*std::max_element(boost::begin(extremes), boost::end(extremes), compare<1 - Dimension>()));

        std::size_t defensive_check_index = 0; // in case we skip over left/right check, collect modifies right too
        std::size_t const n = boost::size(ring);
        while (left != right && defensive_check_index < n)
        {
            coordinate_type const coordinate = geometry::get<Dimension>(*right);
            coordinate_type const other_coordinate = geometry::get<1 - Dimension>(*right);
            if (coordinate > min_value && other_coordinate > other_min && other_coordinate < other_max)
            {
                int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
                int const first_side = side_strategy::apply(*right, extremes.front(), *(extremes.begin() + 1)) * factor;
                int const last_side = side_strategy::apply(*right, *(extremes.rbegin() + 1), extremes.back()) * factor;

                // If not lying left from any of the extemes side
                if (first_side != 1 && last_side != 1)
                {
                    //std::cout << "first " << first_side << " last " << last_side << std::endl;

                    // we start at this intrusion until it is handled, and don't affect our initial left iterator
                    CirclingIterator left_intrusion_it = right;
                    typename boost::range_value<Intruders>::type intruder;
                    collect(ring, *right, intruder, left_intrusion_it, right);

                    // Also moves these to base-level, makes sorting possible which can be done in case of self-tangencies
                    // (we might postpone this action, it is often not necessary. However it is not time-consuming)
                    move_along_vector<Dimension>(intruder, min_value);
                    intruders.push_back(intruder);
                    --right;
                }
            }
            ++right;
            defensive_check_index++;
        }
    }

    template <typename Extremes, typename Intruders>
    static inline void get_intruders(Ring const& ring,
            Extremes const& extremes,
            Intruders& intruders)
    {
        std::size_t const n = boost::size(ring);
        if (n >= 3)
        {
            geometry::ever_circling_range_iterator<Ring const> left(ring);
            geometry::ever_circling_range_iterator<Ring const> right(ring);
            ++right;

            get_intruders(ring, left, right, extremes, intruders);
        }
    }

    template <typename Iterator>
    static inline bool right_turn(Ring const& ring, Iterator it)
    {
        typename std::iterator_traits<Iterator>::difference_type const index
            = std::distance(boost::begin(ring), it);
        geometry::ever_circling_range_iterator<Ring const> left(ring);
        geometry::ever_circling_range_iterator<Ring const> right(ring);
        left += index;
        right += index;

        if (! extent_both_sides(ring, *it, left, right))
        {
            return false;
        }

        int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
        int const first_side = side_strategy::apply(*(right - 1), *right, *left) * factor;
        int const last_side = side_strategy::apply(*left, *(left + 1), *right) * factor;

//std::cout << "Candidate at " << geometry::wkt(*it) << " first=" << first_side << " last=" << last_side << std::endl;

        // Turn should not be left (actually, it should be right because extent removes horizontal/collinear cases)
        return first_side != 1 && last_side != 1;
    }


    // Gets the extreme segments (top point plus neighbouring points), plus intruders, if any, on the same ring
    template <typename Extremes, typename Intruders>
    static inline bool apply(Ring const& ring, Extremes& extremes, Intruders& intruders)
    {
        std::size_t const n = boost::size(ring);
        if (n < 3)
        {
            return false;
        }

        // Get all maxima, usually one. In case of self-tangencies, or self-crossings,
        // the max might be is not valid. A valid max should make a right turn
        range_iterator max_it = boost::begin(ring);
        compare<Dimension> smaller;
        for (range_iterator it = max_it + 1; it != boost::end(ring); ++it)
        {
            if (smaller(*max_it, *it) && right_turn(ring, it))
            {
                max_it = it;
            }
        }

        if (max_it == boost::end(ring))
        {
            return false;
        }

        typename std::iterator_traits<range_iterator>::difference_type const
            index = std::distance(boost::begin(ring), max_it);
//std::cout << "Extreme point lies at " << index << " having " << geometry::wkt(*max_it) << std::endl;

        geometry::ever_circling_range_iterator<Ring const> left(ring);
        geometry::ever_circling_range_iterator<Ring const> right(ring);
        left += index;
        right += index;

        // Collect all points (often 3) in a temporary vector
        std::vector<point_type> points;
        points.reserve(3);
        if (! collect(ring, *max_it, points, left, right))
        {
            return false;
        }

//std::cout << "Built vector of " << points.size() << std::endl;

        coordinate_type const front_value = geometry::get<Dimension>(points.front());
        coordinate_type const back_value = geometry::get<Dimension>(points.back());
        coordinate_type const base_value = (std::max)(front_value, back_value);
        if (front_value < back_value)
        {
            move_along_vector<Dimension>(points.front(), *(points.begin() + 1), base_value);
        }
        else
        {
            move_along_vector<Dimension>(points.back(), *(points.rbegin() + 1), base_value);
        }

        std::copy(points.begin(), points.end(), std::back_inserter(extremes));

        get_intruders(ring, left, right, extremes, intruders);

        return true;
    }
};





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


#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{


template
<
    typename Geometry,
    std::size_t Dimension,
    typename GeometryTag = typename tag<Geometry>::type
>
struct extreme_points
{};


template<typename Ring, std::size_t Dimension>
struct extreme_points<Ring, Dimension, ring_tag>
    : detail::extreme_points::extreme_points_on_ring<Ring, Dimension>
{};


template<typename Polygon, std::size_t Dimension>
struct extreme_points<Polygon, Dimension, polygon_tag>
{
    template <typename Extremes, typename Intruders>
    static inline bool apply(Polygon const& polygon, Extremes& extremes, Intruders& intruders)
    {
        typedef typename geometry::ring_type<Polygon>::type ring_type;
        typedef detail::extreme_points::extreme_points_on_ring
            <
                ring_type, Dimension
            > ring_implementation;

        if (! ring_implementation::apply(geometry::exterior_ring(polygon), extremes, intruders))
        {
            return false;
        }

        // For a polygon, its interior rings can contain intruders
        typename interior_return_type<Polygon const>::type
            rings = interior_rings(polygon);
        for (typename detail::interior_iterator<Polygon const>::type
                it = boost::begin(rings); it != boost::end(rings); ++it)
        {
            ring_implementation::get_intruders(*it, extremes,  intruders);
        }

        return true;
    }
};

template<typename Box>
struct extreme_points<Box, 1, box_tag>
{
    template <typename Extremes, typename Intruders>
    static inline bool apply(Box const& box, Extremes& extremes, Intruders& )
    {
        extremes.resize(4);
        geometry::detail::assign_box_corners_oriented<false>(box, extremes);
        // ll,ul,ur,lr, contains too exactly the right info
        return true;
    }
};

template<typename Box>
struct extreme_points<Box, 0, box_tag>
{
    template <typename Extremes, typename Intruders>
    static inline bool apply(Box const& box, Extremes& extremes, Intruders& )
    {
        extremes.resize(4);
        geometry::detail::assign_box_corners_oriented<false>(box, extremes);
        // ll,ul,ur,lr, rotate one to start with UL and end with LL
        std::rotate(extremes.begin(), extremes.begin() + 1, extremes.end());
        return true;
    }
};

template<typename MultiPolygon, std::size_t Dimension>
struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag>
{
    template <typename Extremes, typename Intruders>
    static inline bool apply(MultiPolygon const& multi, Extremes& extremes, Intruders& intruders)
    {
        // Get one for the very first polygon, that is (for the moment) enough.
        // It is not guaranteed the "extreme" then, but for the current purpose
        // (point_on_surface) it can just be this point.
        if (boost::size(multi) >= 1)
        {
            return extreme_points
                <
                    typename boost::range_value<MultiPolygon const>::type,
                    Dimension,
                    polygon_tag
                >::apply(*boost::begin(multi), extremes, intruders);
        }

        return false;
    }
};

} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH


/*!
\brief Returns extreme points (for Edge=1 in dimension 1, so the top,
       for Edge=0 in dimension 0, the right side)
\note We could specify a strategy (less/greater) to get bottom/left side too. However, until now we don't need that.
 */
template <std::size_t Edge, typename Geometry, typename Extremes, typename Intruders>
inline bool extreme_points(Geometry const& geometry, Extremes& extremes, Intruders& intruders)
{
    concepts::check<Geometry const>();

    // Extremes is not required to follow a geometry concept (but it should support an output iterator),
    // but its elements should fulfil the point-concept
    concepts::check<typename boost::range_value<Extremes>::type>();

    // Intruders should contain collections which value type is point-concept
    // Extremes might be anything (supporting an output iterator), but its elements should fulfil the point-concept
    concepts::check
        <
            typename boost::range_value
                <
                    typename boost::range_value<Intruders>::type
                >::type
            const
        >();

    return dispatch::extreme_points<Geometry, Edge>::apply(geometry, extremes, intruders);
}



}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP