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