EIC code displayed by LXR master/​include/​boost/​geometry/​algorithms/​detail/​buffer/​piece_border.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-12-16 09:49:48

 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
 // Copyright (c) 2020-2021 Barend Gehrels, Amsterdam, the Netherlands.
 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
 
 // This file was modified by Oracle on 2020-2022.
 // Modifications copyright (c) 2020-2022, Oracle and/or its affiliates.
 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
 
 // 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 <array>
 
 #include <boost/core/addressof.hpp>
 #include <boost/range/size.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_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
 {
     using coordinate_type = geometry::coordinate_type_t<Point>;
     using radius_type = typename default_comparable_distance_result<Point>::type;
     using state_type = typename geometry::strategy::buffer::turn_in_ring_winding<coordinate_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.
     std::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;
     }
 
     template <typename Strategy>
     void get_properties_of_border(bool is_point_buffer, Point const& center,
                                   Strategy const& strategy)
     {
         m_has_envelope = calculate_envelope(m_envelope, strategy);
         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 Strategy>
     void get_properties_of_offsetted_ring_part(Strategy 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, typename Strategy>
     bool calculate_envelope(Box& envelope, Strategy const& strategy) 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, strategy);
         expand_envelope(envelope, m_originals.begin(), m_originals.begin() + m_original_size, strategy);
         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 TiRStrategy,
         typename State
     >
     bool walk_offsetted(TurnPoint const& point, Iterator begin, Iterator end,
                         TiRStrategy 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 TiRStrategy, typename State>
     bool step(TurnPoint const& point, Point const& p1, Point const& p2,
               TiRStrategy const& strategy,
               geometry::strategy::buffer::place_on_ring_type place_on_ring, State& state) const
     {
         return strategy.apply(point, p1, p2, place_on_ring, m_is_convex, state);
     }
 
     template <typename It, typename Box, typename Strategy>
     void expand_envelope(Box& envelope, It begin, It end, Strategy const& strategy) const
     {
         for (It it = begin; it != end; ++it)
         {
             geometry::expand(envelope, *it, strategy);
         }
     }
 
     template <typename Strategy>
     bool is_convex(Strategy 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 Strategy>
     bool is_convex(Point& previous, Point& current, It begin, It end, Strategy const& strategy) const
     {
         for (It it = begin; it != end; ++it)
         {
             if (! is_convex(previous, current, *it, strategy))
             {
                 return false;
             }
         }
         return true;
     }
 
     template <typename Strategy>
     bool is_convex(Point& previous, Point& current, Point const& next, Strategy const& strategy) const
     {
         int const side = strategy.side().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, 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)
     {
         using segment_type = geometry::model::referring_segment<Point const>;
 
         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)
         {
             Point const& p0 = *previous;
             Point const& p1 = *it;
             segment_type const s(p0, p1);
             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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team