1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
6 
7 // This file was modified by Oracle on 2013, 2014, 2017, 2019.
8 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
9 
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 
12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
14 
15 // Use, modification and distribution is subject to the Boost Software License,
16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
17 // http://www.boost.org/LICENSE_1_0.txt)
18 
19 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_IMPLEMENTATION_HPP
20 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_IMPLEMENTATION_HPP
21 
22 #include <cstddef>
23 
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/range.hpp>
26 
27 #include <boost/geometry/algorithms/detail/within/interface.hpp>
28 
29 #include <boost/geometry/core/access.hpp>
30 #include <boost/geometry/core/closure.hpp>
31 #include <boost/geometry/core/cs.hpp>
32 #include <boost/geometry/core/exterior_ring.hpp>
33 #include <boost/geometry/core/interior_rings.hpp>
34 #include <boost/geometry/core/point_order.hpp>
35 #include <boost/geometry/core/ring_type.hpp>
36 #include <boost/geometry/core/interior_rings.hpp>
37 #include <boost/geometry/core/tags.hpp>
38 
39 #include <boost/geometry/util/math.hpp>
40 #include <boost/geometry/util/order_as_direction.hpp>
41 #include <boost/geometry/views/closeable_view.hpp>
42 #include <boost/geometry/views/reversible_view.hpp>
43 
44 #include <boost/geometry/algorithms/detail/within/multi_point.hpp>
45 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
46 #include <boost/geometry/algorithms/relate.hpp>
47 
48 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
49 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
50 #include <deque>
51 
52 
53 namespace boost { namespace geometry
54 {
55 
56 #ifndef DOXYGEN_NO_DETAIL
57 namespace detail { namespace within {
58 
59 struct use_point_in_geometry
60 {
61     template <typename Geometry1, typename Geometry2, typename Strategy>
applyboost::geometry::detail::within::use_point_in_geometry62     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
63     {
64         return detail::within::within_point_geometry(geometry1, geometry2, strategy);
65     }
66 };
67 
68 struct use_relate
69 {
70     template <typename Geometry1, typename Geometry2, typename Strategy>
applyboost::geometry::detail::within::use_relate71     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
72     {
73         typedef typename detail::de9im::static_mask_within_type
74             <
75                 Geometry1, Geometry2
76             >::type within_mask;
77         return geometry::relate(geometry1, geometry2, within_mask(), strategy);
78     }
79 };
80 
81 }} // namespace detail::within
82 #endif // DOXYGEN_NO_DETAIL
83 
84 #ifndef DOXYGEN_NO_DISPATCH
85 namespace dispatch
86 {
87 
88 template <typename Point, typename Box>
89 struct within<Point, Box, point_tag, box_tag>
90 {
91     template <typename Strategy>
applyboost::geometry::dispatch::within92     static inline bool apply(Point const& point, Box const& box, Strategy const& strategy)
93     {
94         boost::ignore_unused(strategy);
95         return strategy.apply(point, box);
96     }
97 };
98 
99 template <typename Box1, typename Box2>
100 struct within<Box1, Box2, box_tag, box_tag>
101 {
102     template <typename Strategy>
applyboost::geometry::dispatch::within103     static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
104     {
105         assert_dimension_equal<Box1, Box2>();
106         boost::ignore_unused(strategy);
107         return strategy.apply(box1, box2);
108     }
109 };
110 
111 // P/P
112 
113 template <typename Point1, typename Point2>
114 struct within<Point1, Point2, point_tag, point_tag>
115     : public detail::within::use_point_in_geometry
116 {};
117 
118 template <typename Point, typename MultiPoint>
119 struct within<Point, MultiPoint, point_tag, multi_point_tag>
120     : public detail::within::use_point_in_geometry
121 {};
122 
123 template <typename MultiPoint, typename Point>
124 struct within<MultiPoint, Point, multi_point_tag, point_tag>
125     : public detail::within::multi_point_point
126 {};
127 
128 template <typename MultiPoint1, typename MultiPoint2>
129 struct within<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag>
130     : public detail::within::multi_point_multi_point
131 {};
132 
133 // P/L
134 
135 template <typename Point, typename Segment>
136 struct within<Point, Segment, point_tag, segment_tag>
137     : public detail::within::use_point_in_geometry
138 {};
139 
140 template <typename Point, typename Linestring>
141 struct within<Point, Linestring, point_tag, linestring_tag>
142     : public detail::within::use_point_in_geometry
143 {};
144 
145 template <typename Point, typename MultiLinestring>
146 struct within<Point, MultiLinestring, point_tag, multi_linestring_tag>
147     : public detail::within::use_point_in_geometry
148 {};
149 
150 template <typename MultiPoint, typename Segment>
151 struct within<MultiPoint, Segment, multi_point_tag, segment_tag>
152     : public detail::within::multi_point_single_geometry<true>
153 {};
154 
155 template <typename MultiPoint, typename Linestring>
156 struct within<MultiPoint, Linestring, multi_point_tag, linestring_tag>
157     : public detail::within::multi_point_single_geometry<true>
158 {};
159 
160 template <typename MultiPoint, typename MultiLinestring>
161 struct within<MultiPoint, MultiLinestring, multi_point_tag, multi_linestring_tag>
162     : public detail::within::multi_point_multi_geometry<true>
163 {};
164 
165 // P/A
166 
167 template <typename Point, typename Ring>
168 struct within<Point, Ring, point_tag, ring_tag>
169     : public detail::within::use_point_in_geometry
170 {};
171 
172 template <typename Point, typename Polygon>
173 struct within<Point, Polygon, point_tag, polygon_tag>
174     : public detail::within::use_point_in_geometry
175 {};
176 
177 template <typename Point, typename MultiPolygon>
178 struct within<Point, MultiPolygon, point_tag, multi_polygon_tag>
179     : public detail::within::use_point_in_geometry
180 {};
181 
182 template <typename MultiPoint, typename Ring>
183 struct within<MultiPoint, Ring, multi_point_tag, ring_tag>
184     : public detail::within::multi_point_single_geometry<true>
185 {};
186 
187 template <typename MultiPoint, typename Polygon>
188 struct within<MultiPoint, Polygon, multi_point_tag, polygon_tag>
189     : public detail::within::multi_point_single_geometry<true>
190 {};
191 
192 template <typename MultiPoint, typename MultiPolygon>
193 struct within<MultiPoint, MultiPolygon, multi_point_tag, multi_polygon_tag>
194     : public detail::within::multi_point_multi_geometry<true>
195 {};
196 
197 // L/L
198 
199 template <typename Linestring1, typename Linestring2>
200 struct within<Linestring1, Linestring2, linestring_tag, linestring_tag>
201     : public detail::within::use_relate
202 {};
203 
204 template <typename Linestring, typename MultiLinestring>
205 struct within<Linestring, MultiLinestring, linestring_tag, multi_linestring_tag>
206     : public detail::within::use_relate
207 {};
208 
209 template <typename MultiLinestring, typename Linestring>
210 struct within<MultiLinestring, Linestring, multi_linestring_tag, linestring_tag>
211     : public detail::within::use_relate
212 {};
213 
214 template <typename MultiLinestring1, typename MultiLinestring2>
215 struct within<MultiLinestring1, MultiLinestring2, multi_linestring_tag, multi_linestring_tag>
216     : public detail::within::use_relate
217 {};
218 
219 // L/A
220 
221 template <typename Linestring, typename Ring>
222 struct within<Linestring, Ring, linestring_tag, ring_tag>
223     : public detail::within::use_relate
224 {};
225 
226 template <typename MultiLinestring, typename Ring>
227 struct within<MultiLinestring, Ring, multi_linestring_tag, ring_tag>
228     : public detail::within::use_relate
229 {};
230 
231 template <typename Linestring, typename Polygon>
232 struct within<Linestring, Polygon, linestring_tag, polygon_tag>
233     : public detail::within::use_relate
234 {};
235 
236 template <typename MultiLinestring, typename Polygon>
237 struct within<MultiLinestring, Polygon, multi_linestring_tag, polygon_tag>
238     : public detail::within::use_relate
239 {};
240 
241 template <typename Linestring, typename MultiPolygon>
242 struct within<Linestring, MultiPolygon, linestring_tag, multi_polygon_tag>
243     : public detail::within::use_relate
244 {};
245 
246 template <typename MultiLinestring, typename MultiPolygon>
247 struct within<MultiLinestring, MultiPolygon, multi_linestring_tag, multi_polygon_tag>
248     : public detail::within::use_relate
249 {};
250 
251 // A/A
252 
253 template <typename Ring1, typename Ring2>
254 struct within<Ring1, Ring2, ring_tag, ring_tag>
255     : public detail::within::use_relate
256 {};
257 
258 template <typename Ring, typename Polygon>
259 struct within<Ring, Polygon, ring_tag, polygon_tag>
260     : public detail::within::use_relate
261 {};
262 
263 template <typename Polygon, typename Ring>
264 struct within<Polygon, Ring, polygon_tag, ring_tag>
265     : public detail::within::use_relate
266 {};
267 
268 template <typename Polygon1, typename Polygon2>
269 struct within<Polygon1, Polygon2, polygon_tag, polygon_tag>
270     : public detail::within::use_relate
271 {};
272 
273 template <typename Ring, typename MultiPolygon>
274 struct within<Ring, MultiPolygon, ring_tag, multi_polygon_tag>
275     : public detail::within::use_relate
276 {};
277 
278 template <typename MultiPolygon, typename Ring>
279 struct within<MultiPolygon, Ring, multi_polygon_tag, ring_tag>
280     : public detail::within::use_relate
281 {};
282 
283 template <typename Polygon, typename MultiPolygon>
284 struct within<Polygon, MultiPolygon, polygon_tag, multi_polygon_tag>
285     : public detail::within::use_relate
286 {};
287 
288 template <typename MultiPolygon, typename Polygon>
289 struct within<MultiPolygon, Polygon, multi_polygon_tag, polygon_tag>
290     : public detail::within::use_relate
291 {};
292 
293 template <typename MultiPolygon1, typename MultiPolygon2>
294 struct within<MultiPolygon1, MultiPolygon2, multi_polygon_tag, multi_polygon_tag>
295     : public detail::within::use_relate
296 {};
297 
298 } // namespace dispatch
299 #endif // DOXYGEN_NO_DISPATCH
300 
301 
302 }} // namespace boost::geometry
303 
304 #include <boost/geometry/index/rtree.hpp>
305 
306 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_IMPLEMENTATION_HPP
307