detail/buffer/turn_in_piece_visitor.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2016-2022.
0007 // Modifications copyright (c) 2016-2022 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP
0016
0017 #include <boost/geometry/core/assert.hpp>
0018 #include <boost/geometry/core/config.hpp>
0019
0020 #include <boost/geometry/algorithms/comparable_distance.hpp>
0021 #include <boost/geometry/algorithms/covered_by.hpp>
0022 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
0023 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
0024 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
0025 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
0026 #include <boost/geometry/geometries/box.hpp>
0027
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032 #ifndef DOXYGEN_NO_DETAIL
0033
0034 namespace detail { namespace buffer
0035 {
0036
0037 template
0038 <
0039     typename CsTag,
0040     typename Turns,
0041     typename Pieces,
0042     typename DistanceStrategy,
0043     typename UmbrellaStrategy
0044
0045 >
0046 class turn_in_piece_visitor
0047 {
0048     Turns& m_turns; // because partition is currently operating on const input only
0049     Pieces const& m_pieces; // to check for piece-type
0050     DistanceStrategy const& m_distance_strategy; // to check if point is on original or one_sided
0051     UmbrellaStrategy const& m_umbrella_strategy;
0052
0053     template <typename Operation, typename Piece>
0054     inline bool skip(Operation const& op, Piece const& piece) const
0055     {
0056         if (op.piece_index == piece.index)
0057         {
0058             return true;
0059         }
0060         Piece const& pc = m_pieces[op.piece_index];
0061         if (pc.left_index == piece.index || pc.right_index == piece.index)
0062         {
0063             if (pc.type == strategy::buffer::buffered_flat_end)
0064             {
0065                 // If it is a flat end, don't compare against its neighbor:
0066                 // it will always be located on one of the helper segments
0067                 return true;
0068             }
0069             if (pc.type == strategy::buffer::buffered_concave)
0070             {
0071                 // If it is concave, the same applies: the IP will be
0072                 // located on one of the helper segments
0073                 return true;
0074             }
0075         }
0076
0077         return false;
0078     }
0079
0080     template <typename NumericType>
0081     inline bool is_one_sided(NumericType const& left, NumericType const& right) const
0082     {
0083         static NumericType const zero = 0;
0084         return geometry::math::equals(left, zero)
0085             || geometry::math::equals(right, zero);
0086     }
0087
0088     template <typename Point>
0089     inline bool has_zero_distance_at(Point const& point) const
0090     {
0091         return is_one_sided(m_distance_strategy.apply(point, point,
0092                 strategy::buffer::buffer_side_left),
0093             m_distance_strategy.apply(point, point,
0094                 strategy::buffer::buffer_side_right));
0095     }
0096
0097 public:
0098
0099     inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces,
0100                                  DistanceStrategy const& distance_strategy,
0101                                  UmbrellaStrategy const& umbrella_strategy)
0102         : m_turns(turns)
0103         , m_pieces(pieces)
0104         , m_distance_strategy(distance_strategy)
0105         , m_umbrella_strategy(umbrella_strategy)
0106     {}
0107
0108     template <typename Turn, typename Piece>
0109     inline bool apply(Turn const& turn, Piece const& piece)
0110     {
0111         if (! turn.is_turn_traversable)
0112         {
0113             // Already handled
0114             return true;
0115         }
0116
0117         if (piece.type == strategy::buffer::buffered_flat_end
0118             || piece.type == strategy::buffer::buffered_concave)
0119         {
0120             // Turns cannot be located within flat-end or concave pieces
0121             return true;
0122         }
0123
0124         if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece))
0125         {
0126             return true;
0127         }
0128
0129         return apply(turn, piece, piece.m_piece_border);
0130     }
0131
0132     template <typename Turn, typename Piece, typename Border>
0133     inline bool apply(Turn const& turn, Piece const& piece, Border const& border)
0134     {
0135         if (! geometry::covered_by(turn.point, border.m_envelope, m_umbrella_strategy))
0136         {
0137             // Easy check: if turn is not in the (expanded) envelope
0138             return true;
0139         }
0140
0141         if (piece.type == geometry::strategy::buffer::buffered_empty_side)
0142         {
0143             return false;
0144         }
0145
0146         if (piece.type == geometry::strategy::buffer::buffered_point)
0147         {
0148             // Optimization for a buffer around points: if distance from center
0149             // is not between min/max radius, it is either inside or outside,
0150             // and more expensive checks are not necessary.
0151             auto const d = geometry::comparable_distance(piece.m_center, turn.point,
0152                                                          m_umbrella_strategy);
0153
0154             if (d < border.m_min_comparable_radius)
0155             {
0156                 Turn& mutable_turn = m_turns[turn.turn_index];
0157                 mutable_turn.is_turn_traversable = false;
0158                 return true;
0159             }
0160             if (d > border.m_max_comparable_radius)
0161             {
0162                 return true;
0163             }
0164         }
0165
0166         // Check if buffer is one-sided (at this point), because then a point
0167         // on the original border is not considered as within.
0168         bool const one_sided = has_zero_distance_at(turn.point);
0169
0170         typename Border::state_type state;
0171         if (! border.point_on_piece(turn.point, one_sided,
0172                                     turn.is_linear_end_point, state))
0173         {
0174             return true;
0175         }
0176
0177         if (state.is_inside() && ! state.is_on_boundary())
0178         {
0179             Turn& mutable_turn = m_turns[turn.turn_index];
0180             mutable_turn.is_turn_traversable = false;
0181         }
0182
0183         return true;
0184     }
0185 };
0186
0187
0188 }} // namespace detail::buffer
0189 #endif // DOXYGEN_NO_DETAIL
0190
0191
0192 }} // namespace boost::geometry
0193
0194 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP