xref: /third_party/boost/boost/geometry/algorithms/detail/buffer/piece_border.hpp

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

// Copyright (c) 2020 Barend Gehrels, 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_DETAIL_BUFFER_PIECE_BORDER_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_PIECE_BORDER_HPP


#include <boost/array.hpp>
#include <boost/core/addressof.hpp>

#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/config.hpp>

#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/algorithms/comparable_distance.hpp>
#include <boost/geometry/algorithms/equals.hpp>
#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/algorithms/detail/buffer/buffer_box.hpp>
#include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
#include <boost/geometry/strategies/cartesian/turn_in_ring_winding.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/segment.hpp>


namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail
{
template <typename It, typename T, typename Compare>
inline bool get_range_around(It begin, It end, T const& value, Compare const& compare, It& lower, It& upper)
{
    lower = end;
    upper = end;

    // Get first element not smaller than value
    if (begin == end)
    {
        return false;
    }
    if (compare(value, *begin))
    {
        // The value is smaller than the first item, therefore not in range
        return false;
    }
    // *(begin + std::distance(begin, end) - 1))
    if (compare(*(end - 1), value))
    {
        // The last item is larger than the value, therefore not in range
        return false;
    }

    // Assign the iterators.
    // lower >= begin and lower < end
    // upper > lower and upper <= end
    // lower_bound points to first element NOT LESS than value - but because
    // we want the first value LESS than value, we decrease it
    lower = std::lower_bound(begin, end, value, compare);
    // upper_bound points to first element of which value is LESS
    upper = std::upper_bound(begin, end, value, compare);

    if (lower != begin)
    {
        --lower;
    }
    if (upper != end)
    {
        ++upper;
    }
    return true;
}

}


namespace detail { namespace buffer
{

//! Contains the border of the piece, consisting of 4 parts:
//! 1: the part of the offsetted ring (referenced, not copied)
//! 2: the part of the original (one or two points)
//! 3: the left part (from original to offsetted)
//! 4: the right part (from offsetted to original)
//! Besides that, it contains some properties of the piece(border);
//!   - convexity
//!   - envelope
//!   - monotonicity of the offsetted ring
//!   - min/max radius of a point buffer
//!   - if it is a "reversed" piece (linear features with partly negative buffers)
template <typename Ring, typename Point>
struct piece_border
{
    typedef typename geometry::coordinate_type<Point>::type coordinate_type;
    typedef typename default_comparable_distance_result<Point>::type radius_type;
    typedef typename geometry::strategy::buffer::turn_in_ring_winding<coordinate_type>::state_type state_type;

    bool m_reversed;

    // Points from the offsetted ring. They are not copied, this structure
    // refers to those points
    Ring const* m_ring;
    std::size_t m_begin;
    std::size_t m_end;

    // Points from the original (one or two, depending on piece shape)
    // Note, if there are 2 points, they are REVERSED w.r.t. the original
    // Therefore here we can walk in its order.
    boost::array<Point, 2> m_originals;
    std::size_t m_original_size;

    geometry::model::box<Point> m_envelope;
    bool m_has_envelope;

    // True if piece is determined as "convex"
    bool m_is_convex;

    // True if offsetted part is monotonically changing in x-direction
    bool m_is_monotonic_increasing;
    bool m_is_monotonic_decreasing;

    radius_type m_min_comparable_radius;
    radius_type m_max_comparable_radius;

    piece_border()
        : m_reversed(false)
        , m_ring(NULL)
        , m_begin(0)
        , m_end(0)
        , m_original_size(0)
        , m_has_envelope(false)
        , m_is_convex(false)
        , m_is_monotonic_increasing(false)
        , m_is_monotonic_decreasing(false)
        , m_min_comparable_radius(0)
        , m_max_comparable_radius(0)
    {
    }

    // Only used for debugging (SVG)
    Ring get_full_ring() const
    {
        Ring result;
        if (ring_or_original_empty())
        {
            return result;
        }
        std::copy(m_ring->begin() + m_begin,
                  m_ring->begin() + m_end,
                  std::back_inserter(result));
        std::copy(m_originals.begin(),
                  m_originals.begin() + m_original_size,
                  std::back_inserter(result));
        // Add the closing point
        result.push_back(*(m_ring->begin() + m_begin));

        return result;
    }

    void get_properties_of_border(bool is_point_buffer, Point const& center)
    {
        m_has_envelope = calculate_envelope(m_envelope);
        if (m_has_envelope)
        {
            // Take roundings into account, enlarge box
            geometry::detail::expand_by_epsilon(m_envelope);
        }
        if (! ring_or_original_empty() && is_point_buffer)
        {
            // Determine min/max radius
            calculate_radii(center, m_ring->begin() + m_begin, m_ring->begin() + m_end);
        }
    }

    template <typename SideStrategy>
    void get_properties_of_offsetted_ring_part(SideStrategy const& strategy)
    {
        if (! ring_or_original_empty())
        {
            m_is_convex = is_convex(strategy);
            check_monotonicity(m_ring->begin() + m_begin, m_ring->begin() + m_end);
        }
    }

    void set_offsetted(Ring const& ring, std::size_t begin, std::size_t end)
    {
        BOOST_GEOMETRY_ASSERT(begin <= end);
        BOOST_GEOMETRY_ASSERT(begin < boost::size(ring));
        BOOST_GEOMETRY_ASSERT(end <= boost::size(ring));

        m_ring = boost::addressof(ring);
        m_begin = begin;
        m_end = end;
    }

    void add_original_point(Point const& point)
    {
        BOOST_GEOMETRY_ASSERT(m_original_size < 2);
        m_originals[m_original_size++] = point;
    }

    template <typename Box>
    bool calculate_envelope(Box& envelope) const
    {
        geometry::assign_inverse(envelope);
        if (ring_or_original_empty())
        {
            return false;
        }
        expand_envelope(envelope, m_ring->begin() + m_begin, m_ring->begin() + m_end);
        expand_envelope(envelope, m_originals.begin(), m_originals.begin() + m_original_size);
        return true;
    }


    // Whatever the return value, the state should be checked.
    template <typename TurnPoint, typename State>
    bool point_on_piece(TurnPoint const& point,
                        bool one_sided, bool is_linear_end_point,
                        State& state) const
    {
        if (ring_or_original_empty())
        {
            return false;
        }

        // Walk over the different parts of the ring, in clockwise order
        // For performance reasons: start with the helper part (one segment)
        // then the original part (one segment, if any), then the other helper
        // part (one segment), and only then the offsetted part
        // (probably more segments, check monotonicity)
        geometry::strategy::buffer::turn_in_ring_winding<coordinate_type> tir;

        Point const offsetted_front = *(m_ring->begin() + m_begin);
        Point const offsetted_back = *(m_ring->begin() + m_end - 1);

        // For onesided buffers, or turns colocated with linear end points,
        // the place on the ring is changed to offsetted (because of colocation)
        geometry::strategy::buffer::place_on_ring_type const por_original
            = adapted_place_on_ring(geometry::strategy::buffer::place_on_ring_original,
                                    one_sided, is_linear_end_point);
        geometry::strategy::buffer::place_on_ring_type const por_from_offsetted
            = adapted_place_on_ring(geometry::strategy::buffer::place_on_ring_from_offsetted,
                                    one_sided, is_linear_end_point);
        geometry::strategy::buffer::place_on_ring_type const por_to_offsetted
            = adapted_place_on_ring(geometry::strategy::buffer::place_on_ring_to_offsetted,
                                    one_sided, is_linear_end_point);

        bool continue_processing = true;
        if (m_original_size == 1)
        {
            // One point. Walk from last offsetted to point, and from point to first offsetted
            continue_processing = step(point, offsetted_back, m_originals[0], tir, por_from_offsetted, state)
                && step(point, m_originals[0], offsetted_front, tir, por_to_offsetted, state);
        }
        else if (m_original_size == 2)
        {
            // Two original points. Walk from last offsetted point to first original point,
            // then along original, then from second oginal to first offsetted point
            continue_processing = step(point, offsetted_back, m_originals[0], tir, por_from_offsetted, state)
                    && step(point, m_originals[0], m_originals[1], tir, por_original, state)
                    && step(point, m_originals[1], offsetted_front, tir, por_to_offsetted, state);
        }

        if (continue_processing)
        {
            // Check the offsetted ring (in rounded joins, these might be
            // several segments)
            walk_offsetted(point, m_ring->begin() + m_begin, m_ring->begin() + m_end,
                           tir, state);
        }

        return true;
    }

    //! Returns true if empty (no ring, or no points, or no original)
    bool ring_or_original_empty() const
    {
        return m_ring == NULL || m_begin >= m_end || m_original_size == 0;
    }

private :

    static geometry::strategy::buffer::place_on_ring_type
        adapted_place_on_ring(geometry::strategy::buffer::place_on_ring_type target,
                              bool one_sided, bool is_linear_end_point)
    {
        return one_sided || is_linear_end_point
               ? geometry::strategy::buffer::place_on_ring_offsetted
               : target;
    }

    template <typename TurnPoint, typename Iterator, typename Strategy, typename State>
    bool walk_offsetted(TurnPoint const& point, Iterator begin, Iterator end, Strategy const & strategy, State& state) const
    {
        Iterator it = begin;
        Iterator beyond = end;

        // Move iterators if the offsetted ring is monotonic increasing or decreasing
        if (m_is_monotonic_increasing)
        {
            if (! get_range_around(begin, end, point, geometry::less<Point, 0>(), it, beyond))
            {
                return true;
            }
        }
        else if (m_is_monotonic_decreasing)
        {
            if (! get_range_around(begin, end, point, geometry::greater<Point, 0>(), it, beyond))
            {
                return true;
            }
        }

        for (Iterator previous = it++ ; it != beyond ; ++previous, ++it )
        {
            if (! step(point, *previous, *it, strategy,
                 geometry::strategy::buffer::place_on_ring_offsetted, state))
            {
                return false;
            }
        }
        return true;
    }

    template <typename TurnPoint, typename Strategy, typename State>
    bool step(TurnPoint const& point, Point const& p1, Point const& p2, Strategy const & strategy,
              geometry::strategy::buffer::place_on_ring_type place_on_ring, State& state) const
    {
        // A step between original/offsetted ring is always convex
        // (unless the join strategy generates points left of it -
        //  future: convexity might be added to the buffer-join-strategy)
        // Therefore, if the state count > 0, it means the point is left of it,
        // and because it is convex, we can stop

        typedef typename geometry::coordinate_type<Point>::type coordinate_type;
        typedef geometry::detail::distance_measure<coordinate_type> dm_type;
        dm_type const dm = geometry::detail::get_distance_measure(point, p1, p2);
        if (m_is_convex && dm.measure > 0)
        {
            // The point is left of this segment of a convex piece
            state.m_count = 0;
            return false;
        }
        // Call strategy, and if it is on the border, return false
        // to stop further processing.
        return strategy.apply(point, p1, p2, dm, place_on_ring, state);
    }

    template <typename It, typename Box>
    void expand_envelope(Box& envelope, It begin, It end) const
    {
        typedef typename strategy::expand::services::default_strategy
            <
                point_tag, typename cs_tag<Box>::type
            >::type expand_strategy_type;

        for (It it = begin; it != end; ++it)
        {
            geometry::expand(envelope, *it, expand_strategy_type());
        }
    }

    template <typename SideStrategy>
    bool is_convex(SideStrategy const& strategy) const
    {
        if (ring_or_original_empty())
        {
            // Convexity is undetermined, and for this case it does not matter,
            // because it is only used for optimization in point_on_piece,
            // but that is not called if the piece border is not valid
            return false;
        }

        if (m_end - m_begin <= 2)
        {
            // The offsetted ring part of this piece has only two points.
            // If this is true, and the original ring part has only one point,
            // a triangle and it is convex. If the original ring part has two
            // points, it is a rectangle and theoretically could be concave,
            // but because of the way the buffer is generated, that is never
            // the case.
            return true;
        }

        // The offsetted ring part of thie piece has at least three points
        // (this is often the case in a piece marked as "join")

        // We can assume all points of the offset ring are different, and also
        // that all points on the original are different, and that the offsetted
        // ring is different from the original(s)
        Point const offsetted_front = *(m_ring->begin() + m_begin);
        Point const offsetted_second = *(m_ring->begin() + m_begin + 1);

        // These two points will be reassigned in every is_convex call
        Point previous = offsetted_front;
        Point current = offsetted_second;

        // Verify the offsetted range (from the second point on), the original,
        // and loop through the first two points of the offsetted range
        bool const result = is_convex(previous, current, m_ring->begin() + m_begin + 2, m_ring->begin() + m_end, strategy)
            && is_convex(previous, current, m_originals.begin(), m_originals.begin() + m_original_size, strategy)
            && is_convex(previous, current, offsetted_front, strategy)
            && is_convex(previous, current, offsetted_second, strategy);

        return result;
    }

    template <typename It, typename SideStrategy>
    bool is_convex(Point& previous, Point& current, It begin, It end, SideStrategy const& strategy) const
    {
        for (It it = begin; it != end; ++it)
        {
            if (! is_convex(previous, current, *it, strategy))
            {
                return false;
            }
        }
        return true;
    }

    template <typename SideStrategy>
    bool is_convex(Point& previous, Point& current, Point const& next, SideStrategy const& strategy) const
    {
        typename SideStrategy::equals_point_point_strategy_type const
            eq_pp_strategy = strategy.get_equals_point_point_strategy();

        int const side = strategy.apply(previous, current, next);
        if (side == 1)
        {
            // Next is on the left side of clockwise ring: piece is not convex
            return false;
        }
        if (! equals::equals_point_point(current, next, eq_pp_strategy))
        {
            previous = current;
            current = next;
        }
        return true;
    }

    template <int Direction>
    inline void step_for_monotonicity(Point const& current, Point const& next)
    {
        if (geometry::get<Direction>(current) >= geometry::get<Direction>(next))
        {
            m_is_monotonic_increasing = false;
        }
        if (geometry::get<Direction>(current) <= geometry::get<Direction>(next))
        {
            m_is_monotonic_decreasing = false;
        }
    }

    template <typename It>
    void check_monotonicity(It begin, It end)
    {
        m_is_monotonic_increasing = true;
        m_is_monotonic_decreasing = true;

        if (begin == end || begin + 1 == end)
        {
            return;
        }

        It it = begin;
        for (It previous = it++; it != end; ++previous, ++it)
        {
            step_for_monotonicity<0>(*previous, *it);
        }
    }

    template <typename It>
    inline void calculate_radii(Point const& center, It begin, It end)
    {
        typedef geometry::model::referring_segment<Point const> segment_type;

        bool first = true;

        // An offsetted point-buffer ring around a point is supposed to be closed,
        // therefore walking from start to end is fine.
        It it = begin;
        for (It previous = it++; it != end; ++previous, ++it)
        {
            segment_type const s(*previous, *it);
            radius_type const d = geometry::comparable_distance(center, s);

            if (first || d < m_min_comparable_radius)
            {
                m_min_comparable_radius = d;
            }
            if (first || d > m_max_comparable_radius)
            {
                m_max_comparable_radius = d;
            }
            first = false;
        }
    }

};

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


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_PIECE_BORDER_HPP