]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland. | |
5 | ||
20effc67 TL |
6 | // This file was modified by Oracle on 2013-2020. |
7 | // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates. | |
b32b8144 FG |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
9 | ||
10 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
11 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
12 | ||
13 | // Use, modification and distribution is subject to the Boost Software License, | |
14 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
15 | // http://www.boost.org/LICENSE_1_0.txt) | |
16 | ||
17 | #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP | |
18 | #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP | |
19 | ||
20 | ||
21 | #include <boost/geometry/core/tags.hpp> | |
22 | ||
23 | #include <boost/geometry/util/math.hpp> | |
24 | #include <boost/geometry/util/select_calculation_type.hpp> | |
25 | ||
20effc67 TL |
26 | #include <boost/geometry/strategy/cartesian/expand_point.hpp> |
27 | ||
92f5a8d4 TL |
28 | #include <boost/geometry/strategies/cartesian/point_in_box.hpp> |
29 | #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp> | |
b32b8144 FG |
30 | #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp> |
31 | #include <boost/geometry/strategies/covered_by.hpp> | |
32 | #include <boost/geometry/strategies/within.hpp> | |
33 | ||
34 | ||
35 | namespace boost { namespace geometry | |
36 | { | |
37 | ||
38 | namespace strategy { namespace within | |
39 | { | |
40 | ||
41 | ||
42 | /*! | |
43 | \brief Within detection using winding rule in cartesian coordinate system. | |
44 | \ingroup strategies | |
92f5a8d4 TL |
45 | \tparam Point_ \tparam_point |
46 | \tparam PointOfSegment_ \tparam_segment_point | |
b32b8144 FG |
47 | \tparam CalculationType \tparam_calculation |
48 | \author Barend Gehrels | |
b32b8144 FG |
49 | |
50 | \qbk{ | |
51 | [heading See also] | |
52 | [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] | |
53 | } | |
54 | */ | |
55 | template | |
56 | < | |
92f5a8d4 TL |
57 | typename Point_ = void, // for backward compatibility |
58 | typename PointOfSegment_ = Point_, // for backward compatibility | |
b32b8144 FG |
59 | typename CalculationType = void |
60 | > | |
61 | class cartesian_winding | |
62 | { | |
92f5a8d4 TL |
63 | template <typename Point, typename PointOfSegment> |
64 | struct calculation_type | |
65 | : select_calculation_type | |
66 | < | |
67 | Point, | |
68 | PointOfSegment, | |
69 | CalculationType | |
70 | > | |
71 | {}; | |
b32b8144 FG |
72 | |
73 | /*! subclass to keep state */ | |
74 | class counter | |
75 | { | |
76 | int m_count; | |
77 | bool m_touches; | |
78 | ||
79 | inline int code() const | |
80 | { | |
81 | return m_touches ? 0 : m_count == 0 ? -1 : 1; | |
82 | } | |
83 | ||
84 | public : | |
85 | friend class cartesian_winding; | |
86 | ||
87 | inline counter() | |
88 | : m_count(0) | |
89 | , m_touches(false) | |
90 | {} | |
91 | ||
92 | }; | |
93 | ||
94 | public: | |
92f5a8d4 TL |
95 | typedef cartesian_tag cs_tag; |
96 | ||
97 | typedef side::side_by_triangle<CalculationType> side_strategy_type; | |
98 | ||
99 | static inline side_strategy_type get_side_strategy() | |
100 | { | |
101 | return side_strategy_type(); | |
102 | } | |
103 | ||
104 | typedef expand::cartesian_point expand_point_strategy_type; | |
105 | ||
b32b8144 FG |
106 | typedef typename side_strategy_type::envelope_strategy_type envelope_strategy_type; |
107 | ||
108 | static inline envelope_strategy_type get_envelope_strategy() | |
109 | { | |
110 | return side_strategy_type::get_envelope_strategy(); | |
111 | } | |
112 | ||
113 | typedef typename side_strategy_type::disjoint_strategy_type disjoint_strategy_type; | |
114 | ||
115 | static inline disjoint_strategy_type get_disjoint_strategy() | |
116 | { | |
117 | return side_strategy_type::get_disjoint_strategy(); | |
118 | } | |
119 | ||
92f5a8d4 TL |
120 | typedef typename side_strategy_type::equals_point_point_strategy_type equals_point_point_strategy_type; |
121 | static inline equals_point_point_strategy_type get_equals_point_point_strategy() | |
122 | { | |
123 | return side_strategy_type::get_equals_point_point_strategy(); | |
124 | } | |
125 | ||
126 | typedef disjoint::cartesian_box_box disjoint_box_box_strategy_type; | |
127 | static inline disjoint_box_box_strategy_type get_disjoint_box_box_strategy() | |
128 | { | |
129 | return disjoint_box_box_strategy_type(); | |
130 | } | |
131 | ||
132 | typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type; | |
133 | ||
b32b8144 | 134 | // Typedefs and static methods to fulfill the concept |
b32b8144 FG |
135 | typedef counter state_type; |
136 | ||
92f5a8d4 | 137 | template <typename Point, typename PointOfSegment> |
b32b8144 FG |
138 | static inline bool apply(Point const& point, |
139 | PointOfSegment const& s1, PointOfSegment const& s2, | |
140 | counter& state) | |
141 | { | |
142 | bool eq1 = false; | |
143 | bool eq2 = false; | |
144 | ||
145 | int count = check_segment(point, s1, s2, state, eq1, eq2); | |
146 | if (count != 0) | |
147 | { | |
148 | int side = 0; | |
149 | if (count == 1 || count == -1) | |
150 | { | |
151 | side = side_equal(point, eq1 ? s1 : s2, count); | |
152 | } | |
153 | else // count == 2 || count == -2 | |
154 | { | |
155 | // 1 left, -1 right | |
156 | side = side_strategy_type::apply(s1, s2, point); | |
157 | } | |
158 | ||
159 | if (side == 0) | |
160 | { | |
161 | // Point is lying on segment | |
162 | state.m_touches = true; | |
163 | state.m_count = 0; | |
164 | return false; | |
165 | } | |
166 | ||
167 | // Side is NEG for right, POS for left. | |
168 | // The count is -2 for left, 2 for right (or -1/1) | |
169 | // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE | |
170 | // See accompagnying figure (TODO) | |
171 | if (side * count > 0) | |
172 | { | |
173 | state.m_count += count; | |
174 | } | |
175 | } | |
176 | return ! state.m_touches; | |
177 | } | |
178 | ||
179 | static inline int result(counter const& state) | |
180 | { | |
181 | return state.code(); | |
182 | } | |
183 | ||
184 | private: | |
92f5a8d4 | 185 | template <typename Point, typename PointOfSegment> |
b32b8144 FG |
186 | static inline int check_segment(Point const& point, |
187 | PointOfSegment const& seg1, | |
188 | PointOfSegment const& seg2, | |
189 | counter& state, | |
190 | bool& eq1, bool& eq2) | |
191 | { | |
192 | if (check_touch(point, seg1, seg2, state, eq1, eq2)) | |
193 | { | |
194 | return 0; | |
195 | } | |
196 | ||
197 | return calculate_count(point, seg1, seg2, eq1, eq2); | |
198 | } | |
199 | ||
92f5a8d4 | 200 | template <typename Point, typename PointOfSegment> |
b32b8144 FG |
201 | static inline bool check_touch(Point const& point, |
202 | PointOfSegment const& seg1, | |
203 | PointOfSegment const& seg2, | |
204 | counter& state, | |
205 | bool& eq1, bool& eq2) | |
206 | { | |
92f5a8d4 TL |
207 | typedef typename calculation_type<Point, PointOfSegment>::type calc_t; |
208 | ||
209 | calc_t const px = get<0>(point); | |
210 | calc_t const s1x = get<0>(seg1); | |
211 | calc_t const s2x = get<0>(seg2); | |
b32b8144 FG |
212 | |
213 | eq1 = math::equals(s1x, px); | |
214 | eq2 = math::equals(s2x, px); | |
215 | ||
216 | // Both equal p -> segment vertical | |
217 | // The only thing which has to be done is check if point is ON segment | |
218 | if (eq1 && eq2) | |
219 | { | |
92f5a8d4 TL |
220 | calc_t const py = get<1>(point); |
221 | calc_t const s1y = get<1>(seg1); | |
222 | calc_t const s2y = get<1>(seg2); | |
b32b8144 FG |
223 | if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py)) |
224 | { | |
225 | state.m_touches = true; | |
226 | } | |
227 | return true; | |
228 | } | |
229 | return false; | |
230 | } | |
231 | ||
92f5a8d4 | 232 | template <typename Point, typename PointOfSegment> |
b32b8144 FG |
233 | static inline int calculate_count(Point const& point, |
234 | PointOfSegment const& seg1, | |
235 | PointOfSegment const& seg2, | |
236 | bool eq1, bool eq2) | |
237 | { | |
92f5a8d4 TL |
238 | typedef typename calculation_type<Point, PointOfSegment>::type calc_t; |
239 | ||
240 | calc_t const p = get<0>(point); | |
241 | calc_t const s1 = get<0>(seg1); | |
242 | calc_t const s2 = get<0>(seg2); | |
b32b8144 FG |
243 | |
244 | return eq1 ? (s2 > p ? 1 : -1) // Point on level s1, E/W depending on s2 | |
245 | : eq2 ? (s1 > p ? -1 : 1) // idem | |
246 | : s1 < p && s2 > p ? 2 // Point between s1 -> s2 --> E | |
247 | : s2 < p && s1 > p ? -2 // Point between s2 -> s1 --> W | |
248 | : 0; | |
249 | } | |
250 | ||
92f5a8d4 | 251 | template <typename Point, typename PointOfSegment> |
b32b8144 FG |
252 | static inline int side_equal(Point const& point, |
253 | PointOfSegment const& se, | |
254 | int count) | |
255 | { | |
256 | // NOTE: for D=0 the signs would be reversed | |
257 | return math::equals(get<1>(point), get<1>(se)) ? | |
258 | 0 : | |
259 | get<1>(point) < get<1>(se) ? | |
260 | // assuming count is equal to 1 or -1 | |
261 | -count : // ( count > 0 ? -1 : 1) : | |
262 | count; // ( count > 0 ? 1 : -1) ; | |
263 | } | |
264 | }; | |
265 | ||
266 | ||
267 | #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS | |
268 | ||
269 | namespace services | |
270 | { | |
271 | ||
272 | template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> | |
273 | struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
274 | { | |
92f5a8d4 | 275 | typedef cartesian_winding<> type; |
b32b8144 FG |
276 | }; |
277 | ||
278 | template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> | |
279 | struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag> | |
280 | { | |
92f5a8d4 | 281 | typedef cartesian_winding<> type; |
b32b8144 FG |
282 | }; |
283 | ||
284 | } // namespace services | |
285 | ||
286 | #endif | |
287 | ||
288 | ||
289 | }} // namespace strategy::within | |
290 | ||
291 | ||
292 | #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS | |
293 | namespace strategy { namespace covered_by { namespace services | |
294 | { | |
295 | ||
296 | template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> | |
297 | struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
298 | { | |
92f5a8d4 | 299 | typedef within::cartesian_winding<> type; |
b32b8144 FG |
300 | }; |
301 | ||
302 | template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> | |
303 | struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag> | |
304 | { | |
92f5a8d4 | 305 | typedef within::cartesian_winding<> type; |
b32b8144 FG |
306 | }; |
307 | ||
308 | }}} // namespace strategy::covered_by::services | |
309 | #endif | |
310 | ||
311 | ||
312 | }} // namespace boost::geometry | |
313 | ||
314 | ||
315 | #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP |