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