]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
20effc67 | 3 | // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands. |
b32b8144 | 4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 5 | |
1e59de90 TL |
6 | // This file was modified by Oracle on 2016-2022. |
7 | // Modifications copyright (c) 2016-2022 Oracle and/or its affiliates. | |
7c673cae FG |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
20effc67 TL |
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP | |
7c673cae FG |
16 | |
17 | #include <boost/geometry/core/assert.hpp> | |
92f5a8d4 | 18 | #include <boost/geometry/core/config.hpp> |
7c673cae | 19 | |
7c673cae | 20 | #include <boost/geometry/algorithms/comparable_distance.hpp> |
20effc67 | 21 | #include <boost/geometry/algorithms/covered_by.hpp> |
7c673cae FG |
22 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> |
23 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
1e59de90 | 24 | #include <boost/geometry/algorithms/detail/dummy_geometries.hpp> |
7c673cae | 25 | #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> |
20effc67 | 26 | #include <boost/geometry/geometries/box.hpp> |
7c673cae FG |
27 | |
28 | ||
29 | namespace boost { namespace geometry | |
30 | { | |
31 | ||
7c673cae | 32 | #ifndef DOXYGEN_NO_DETAIL |
7c673cae | 33 | |
20effc67 | 34 | namespace detail { namespace buffer |
92f5a8d4 | 35 | { |
92f5a8d4 TL |
36 | |
37 | template | |
38 | < | |
39 | typename CsTag, | |
40 | typename Turns, | |
41 | typename Pieces, | |
1e59de90 TL |
42 | typename DistanceStrategy, |
43 | typename UmbrellaStrategy | |
92f5a8d4 TL |
44 | |
45 | > | |
46 | class turn_in_piece_visitor | |
47 | { | |
48 | Turns& m_turns; // because partition is currently operating on const input only | |
49 | Pieces const& m_pieces; // to check for piece-type | |
20effc67 | 50 | DistanceStrategy const& m_distance_strategy; // to check if point is on original or one_sided |
1e59de90 | 51 | UmbrellaStrategy const& m_umbrella_strategy; |
92f5a8d4 TL |
52 | |
53 | template <typename Operation, typename Piece> | |
54 | inline bool skip(Operation const& op, Piece const& piece) const | |
55 | { | |
56 | if (op.piece_index == piece.index) | |
57 | { | |
58 | return true; | |
59 | } | |
60 | Piece const& pc = m_pieces[op.piece_index]; | |
61 | if (pc.left_index == piece.index || pc.right_index == piece.index) | |
62 | { | |
63 | if (pc.type == strategy::buffer::buffered_flat_end) | |
64 | { | |
65 | // If it is a flat end, don't compare against its neighbor: | |
66 | // it will always be located on one of the helper segments | |
67 | return true; | |
68 | } | |
69 | if (pc.type == strategy::buffer::buffered_concave) | |
70 | { | |
71 | // If it is concave, the same applies: the IP will be | |
72 | // located on one of the helper segments | |
73 | return true; | |
74 | } | |
75 | } | |
76 | ||
77 | return false; | |
78 | } | |
7c673cae | 79 | |
20effc67 TL |
80 | template <typename NumericType> |
81 | inline bool is_one_sided(NumericType const& left, NumericType const& right) const | |
82 | { | |
83 | static NumericType const zero = 0; | |
84 | return geometry::math::equals(left, zero) | |
85 | || geometry::math::equals(right, zero); | |
86 | } | |
87 | ||
88 | template <typename Point> | |
89 | inline bool has_zero_distance_at(Point const& point) const | |
90 | { | |
91 | return is_one_sided(m_distance_strategy.apply(point, point, | |
92 | strategy::buffer::buffer_side_left), | |
93 | m_distance_strategy.apply(point, point, | |
94 | strategy::buffer::buffer_side_right)); | |
95 | } | |
7c673cae FG |
96 | |
97 | public: | |
98 | ||
92f5a8d4 | 99 | inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces, |
1e59de90 TL |
100 | DistanceStrategy const& distance_strategy, |
101 | UmbrellaStrategy const& umbrella_strategy) | |
7c673cae FG |
102 | : m_turns(turns) |
103 | , m_pieces(pieces) | |
92f5a8d4 | 104 | , m_distance_strategy(distance_strategy) |
1e59de90 | 105 | , m_umbrella_strategy(umbrella_strategy) |
7c673cae FG |
106 | {} |
107 | ||
108 | template <typename Turn, typename Piece> | |
20effc67 | 109 | inline bool apply(Turn const& turn, Piece const& piece) |
7c673cae | 110 | { |
20effc67 | 111 | if (! turn.is_turn_traversable) |
7c673cae | 112 | { |
20effc67 | 113 | // Already handled |
b32b8144 | 114 | return true; |
7c673cae FG |
115 | } |
116 | ||
117 | if (piece.type == strategy::buffer::buffered_flat_end | |
118 | || piece.type == strategy::buffer::buffered_concave) | |
119 | { | |
120 | // Turns cannot be located within flat-end or concave pieces | |
b32b8144 | 121 | return true; |
7c673cae FG |
122 | } |
123 | ||
20effc67 | 124 | if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece)) |
7c673cae | 125 | { |
b32b8144 | 126 | return true; |
7c673cae FG |
127 | } |
128 | ||
20effc67 TL |
129 | return apply(turn, piece, piece.m_piece_border); |
130 | } | |
131 | ||
132 | template <typename Turn, typename Piece, typename Border> | |
133 | inline bool apply(Turn const& turn, Piece const& piece, Border const& border) | |
134 | { | |
1e59de90 | 135 | if (! geometry::covered_by(turn.point, border.m_envelope, m_umbrella_strategy)) |
7c673cae | 136 | { |
20effc67 | 137 | // Easy check: if turn is not in the (expanded) envelope |
b32b8144 | 138 | return true; |
7c673cae FG |
139 | } |
140 | ||
7c673cae FG |
141 | if (piece.type == geometry::strategy::buffer::buffered_point) |
142 | { | |
20effc67 TL |
143 | // Optimization for a buffer around points: if distance from center |
144 | // is not between min/max radius, it is either inside or outside, | |
145 | // and more expensive checks are not necessary. | |
1e59de90 TL |
146 | auto const d = geometry::comparable_distance(piece.m_center, turn.point, |
147 | m_umbrella_strategy); | |
20effc67 TL |
148 | |
149 | if (d < border.m_min_comparable_radius) | |
7c673cae | 150 | { |
20effc67 TL |
151 | Turn& mutable_turn = m_turns[turn.turn_index]; |
152 | mutable_turn.is_turn_traversable = false; | |
b32b8144 | 153 | return true; |
7c673cae | 154 | } |
20effc67 | 155 | if (d > border.m_max_comparable_radius) |
7c673cae | 156 | { |
b32b8144 | 157 | return true; |
7c673cae FG |
158 | } |
159 | } | |
160 | ||
20effc67 TL |
161 | // Check if buffer is one-sided (at this point), because then a point |
162 | // on the original is not considered as within. | |
163 | bool const one_sided = has_zero_distance_at(turn.point); | |
92f5a8d4 | 164 | |
20effc67 | 165 | typename Border::state_type state; |
1e59de90 TL |
166 | if (! border.point_on_piece(turn.point, m_umbrella_strategy, one_sided, |
167 | turn.is_linear_end_point, state)) | |
7c673cae | 168 | { |
20effc67 | 169 | return true; |
7c673cae FG |
170 | } |
171 | ||
20effc67 | 172 | if (state.code() == 1) |
7c673cae | 173 | { |
20effc67 TL |
174 | // It is WITHIN a piece, or on the piece border, but not |
175 | // on the offsetted part of it. | |
176 | ||
177 | // TODO - at further removing rescaling, this threshold can be | |
178 | // adapted, or ideally, go. | |
179 | // This threshold is minimized to the point where fragile | |
180 | // unit tests of hard cases start to fail (5 in multi_polygon) | |
181 | // But it is acknowlegded that such a threshold depends on the | |
182 | // scale of the input. | |
1e59de90 | 183 | if (state.m_min_distance > 1.0e-4 || ! state.m_close_to_offset) |
20effc67 TL |
184 | { |
185 | Turn& mutable_turn = m_turns[turn.turn_index]; | |
186 | mutable_turn.is_turn_traversable = false; | |
187 | ||
188 | // Keep track of the information if this turn was close | |
189 | // to an offset (without threshold). Because if it was, | |
190 | // it might have been classified incorrectly and in the | |
191 | // pretraversal step, it can in hindsight be classified | |
192 | // as "outside". | |
193 | mutable_turn.close_to_offset = state.m_close_to_offset; | |
194 | } | |
7c673cae | 195 | } |
b32b8144 FG |
196 | |
197 | return true; | |
7c673cae FG |
198 | } |
199 | }; | |
200 | ||
201 | ||
202 | }} // namespace detail::buffer | |
203 | #endif // DOXYGEN_NO_DETAIL | |
204 | ||
205 | ||
206 | }} // namespace boost::geometry | |
207 | ||
20effc67 | 208 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP |