1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
11
12
13 #include <boost/core/ignore_unused.hpp>
14
15 #include <boost/geometry/algorithms/expand.hpp>
16 #include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
17 #include <boost/geometry/strategies/buffer.hpp>
18
19
20 namespace boost { namespace geometry
21 {
22
23
24 #ifndef DOXYGEN_NO_DETAIL
25 namespace detail { namespace buffer
26 {
27
28 struct original_get_box
29 {
30 template <typename Box, typename Original>
applyboost::geometry::detail::buffer::original_get_box31 static inline void apply(Box& total, Original const& original)
32 {
33 geometry::expand(total, original.m_box);
34 }
35 };
36
37 struct original_ovelaps_box
38 {
39 template <typename Box, typename Original>
applyboost::geometry::detail::buffer::original_ovelaps_box40 static inline bool apply(Box const& box, Original const& original)
41 {
42 return ! detail::disjoint::disjoint_box_box(box, original.m_box);
43 }
44 };
45
46 struct include_turn_policy
47 {
48 template <typename Turn>
applyboost::geometry::detail::buffer::include_turn_policy49 static inline bool apply(Turn const& turn)
50 {
51 return turn.location == location_ok;
52 }
53 };
54
55 struct turn_in_original_ovelaps_box
56 {
57 template <typename Box, typename Turn>
applyboost::geometry::detail::buffer::turn_in_original_ovelaps_box58 static inline bool apply(Box const& box, Turn const& turn)
59 {
60 if (turn.location != location_ok || turn.within_original)
61 {
62 // Skip all points already processed
63 return false;
64 }
65
66 return ! geometry::detail::disjoint::disjoint_point_box(
67 turn.robust_point, box);
68 }
69 };
70
71 //! Check if specified is in range of specified iterators
72 //! Return value of strategy (true if we can bail out)
73 template
74 <
75 typename Strategy,
76 typename State,
77 typename Point,
78 typename Iterator
79 >
point_in_range(Strategy & strategy,State & state,Point const & point,Iterator begin,Iterator end)80 inline bool point_in_range(Strategy& strategy, State& state,
81 Point const& point, Iterator begin, Iterator end)
82 {
83 boost::ignore_unused(strategy);
84
85 Iterator it = begin;
86 for (Iterator previous = it++; it != end; ++previous, ++it)
87 {
88 if (! strategy.apply(point, *previous, *it, state))
89 {
90 // We're probably on the boundary
91 return false;
92 }
93 }
94 return true;
95 }
96
97 template
98 <
99 typename Strategy,
100 typename State,
101 typename Point,
102 typename CoordinateType,
103 typename Iterator
104 >
point_in_section(Strategy & strategy,State & state,Point const & point,CoordinateType const & point_y,Iterator begin,Iterator end,int direction)105 inline bool point_in_section(Strategy& strategy, State& state,
106 Point const& point, CoordinateType const& point_y,
107 Iterator begin, Iterator end,
108 int direction)
109 {
110 if (direction == 0)
111 {
112 // Not a monotonic section, or no change in Y-direction
113 return point_in_range(strategy, state, point, begin, end);
114 }
115
116 // We're in a monotonic section in y-direction
117 Iterator it = begin;
118
119 for (Iterator previous = it++; it != end; ++previous, ++it)
120 {
121 // Depending on sections.direction we can quit for this section
122 CoordinateType const previous_y = geometry::get<1>(*previous);
123
124 if (direction == 1 && point_y < previous_y)
125 {
126 // Section goes upwards, y increases, point is is below section
127 return true;
128 }
129 else if (direction == -1 && point_y > previous_y)
130 {
131 // Section goes downwards, y decreases, point is above section
132 return true;
133 }
134
135 if (! strategy.apply(point, *previous, *it, state))
136 {
137 // We're probably on the boundary
138 return false;
139 }
140 }
141 return true;
142 }
143
144
145 template <typename Point, typename Original>
point_in_original(Point const & point,Original const & original)146 inline int point_in_original(Point const& point, Original const& original)
147 {
148 typedef strategy::within::winding<Point> strategy_type;
149
150 typename strategy_type::state_type state;
151 strategy_type strategy;
152
153 if (boost::size(original.m_sections) == 0
154 || boost::size(original.m_ring) - boost::size(original.m_sections) < 16)
155 {
156 // There are no sections, or it does not profit to walk over sections
157 // instead of over points. Boundary of 16 is arbitrary but can influence
158 // performance
159 point_in_range(strategy, state, point,
160 original.m_ring.begin(), original.m_ring.end());
161 return strategy.result(state);
162 }
163
164 typedef typename Original::sections_type sections_type;
165 typedef typename boost::range_iterator<sections_type const>::type iterator_type;
166 typedef typename boost::range_value<sections_type const>::type section_type;
167 typedef typename geometry::coordinate_type<Point>::type coordinate_type;
168
169 coordinate_type const point_y = geometry::get<1>(point);
170
171 // Walk through all monotonic sections of this original
172 for (iterator_type it = boost::begin(original.m_sections);
173 it != boost::end(original.m_sections);
174 ++it)
175 {
176 section_type const& section = *it;
177
178 if (! section.duplicate
179 && section.begin_index < section.end_index
180 && point_y >= geometry::get<min_corner, 1>(section.bounding_box)
181 && point_y <= geometry::get<max_corner, 1>(section.bounding_box))
182 {
183 // y-coordinate of point overlaps with section
184 if (! point_in_section(strategy, state, point, point_y,
185 boost::begin(original.m_ring) + section.begin_index,
186 boost::begin(original.m_ring) + section.end_index + 1,
187 section.directions[0]))
188 {
189 // We're probably on the boundary
190 break;
191 }
192 }
193 }
194
195 return strategy.result(state);
196 }
197
198
199 template <typename Turns>
200 class turn_in_original_visitor
201 {
202 public:
turn_in_original_visitor(Turns & turns)203 turn_in_original_visitor(Turns& turns)
204 : m_mutable_turns(turns)
205 {}
206
207 template <typename Turn, typename Original>
apply(Turn const & turn,Original const & original,bool first=true)208 inline void apply(Turn const& turn, Original const& original, bool first = true)
209 {
210 boost::ignore_unused_variable_warning(first);
211
212 if (turn.location != location_ok || turn.within_original)
213 {
214 // Skip all points already processed
215 return;
216 }
217
218 if (geometry::disjoint(turn.robust_point, original.m_box))
219 {
220 // Skip all disjoint
221 return;
222 }
223
224 int const code = point_in_original(turn.robust_point, original);
225
226 if (code == -1)
227 {
228 return;
229 }
230
231 Turn& mutable_turn = m_mutable_turns[turn.turn_index];
232
233 if (code == 0)
234 {
235 // On border of original: always discard
236 mutable_turn.location = location_discard;
237 }
238
239 // Point is inside an original ring
240 if (original.m_is_interior)
241 {
242 mutable_turn.count_in_original--;
243 }
244 else if (original.m_has_interiors)
245 {
246 mutable_turn.count_in_original++;
247 }
248 else
249 {
250 // It is an exterior ring and there are no interior rings.
251 // Then we are completely ready with this turn
252 mutable_turn.within_original = true;
253 mutable_turn.count_in_original = 1;
254 }
255 }
256
257 private :
258 Turns& m_mutable_turns;
259 };
260
261
262 }} // namespace detail::buffer
263 #endif // DOXYGEN_NO_DETAIL
264
265
266 }} // namespace boost::geometry
267
268 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
269