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 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
7
8 // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018, 2019.
9 // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates.
10
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
15
16 // Use, modification and distribution is subject to the Boost Software License,
17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
18 // http://www.boost.org/LICENSE_1_0.txt)
19
20 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
22
23
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/mpl/assert.hpp>
26 #include <boost/range.hpp>
27 #include <boost/type_traits/is_same.hpp>
28 #include <boost/type_traits/remove_reference.hpp>
29
30 #include <boost/geometry/core/assert.hpp>
31
32 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
33 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
34
35 #include <boost/geometry/geometries/concepts/check.hpp>
36 #include <boost/geometry/strategies/concepts/within_concept.hpp>
37 #include <boost/geometry/strategies/default_strategy.hpp>
38 #include <boost/geometry/strategies/relate.hpp>
39
40 #include <boost/geometry/util/range.hpp>
41 #include <boost/geometry/views/detail/normalized_view.hpp>
42
43 namespace boost { namespace geometry {
44
45 #ifndef DOXYGEN_NO_DETAIL
46 namespace detail { namespace within {
47
48 template <typename Point1, typename Point2, typename Strategy>
equals_point_point(Point1 const & p1,Point2 const & p2,Strategy const & strategy)49 inline bool equals_point_point(Point1 const& p1, Point2 const& p2, Strategy const& strategy)
50 {
51 return equals::equals_point_point(p1, p2, strategy.get_equals_point_point_strategy());
52 }
53
54 // TODO: is this needed?
check_result_type(int result)55 inline int check_result_type(int result)
56 {
57 return result;
58 }
59
60 template <typename T>
check_result_type(T result)61 inline T check_result_type(T result)
62 {
63 BOOST_GEOMETRY_ASSERT(false);
64 return result;
65 }
66
67 template <typename Point, typename Range, typename Strategy> inline
point_in_range(Point const & point,Range const & range,Strategy const & strategy)68 int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
69 {
70 boost::ignore_unused(strategy);
71
72 typedef typename boost::range_iterator<Range const>::type iterator_type;
73 typename Strategy::state_type state;
74 iterator_type it = boost::begin(range);
75 iterator_type end = boost::end(range);
76
77 for ( iterator_type previous = it++ ; it != end ; ++previous, ++it )
78 {
79 if ( ! strategy.apply(point, *previous, *it, state) )
80 {
81 break;
82 }
83 }
84
85 return check_result_type(strategy.result(state));
86 }
87
88 template <typename Geometry, typename Point, typename Range>
point_in_range(Point const & point,Range const & range)89 inline int point_in_range(Point const& point, Range const& range)
90 {
91 typedef typename strategy::point_in_geometry::services::default_strategy
92 <
93 Point, Geometry
94 >::type strategy_type;
95
96 return point_in_range(point, range, strategy_type());
97 }
98
99 }} // namespace detail::within
100
101 namespace detail_dispatch { namespace within {
102
103 // checks the relation between a point P and geometry G
104 // returns 1 if P is in the interior of G
105 // returns 0 if P is on the boundry of G
106 // returns -1 if P is in the exterior of G
107
108 template <typename Geometry,
109 typename Tag = typename geometry::tag<Geometry>::type>
110 struct point_in_geometry
111 : not_implemented<Tag>
112 {};
113
114 template <typename Point2>
115 struct point_in_geometry<Point2, point_tag>
116 {
117 template <typename Point1, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry118 int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
119 {
120 boost::ignore_unused(strategy);
121 return strategy.apply(point1, point2) ? 1 : -1;
122 }
123 };
124
125 template <typename Segment>
126 struct point_in_geometry<Segment, segment_tag>
127 {
128 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry129 int apply(Point const& point, Segment const& segment, Strategy const& strategy)
130 {
131 boost::ignore_unused(strategy);
132
133 typedef typename geometry::point_type<Segment>::type point_type;
134 point_type p0, p1;
135 // TODO: don't copy points
136 detail::assign_point_from_index<0>(segment, p0);
137 detail::assign_point_from_index<1>(segment, p1);
138
139 typename Strategy::state_type state;
140 strategy.apply(point, p0, p1, state);
141 int r = detail::within::check_result_type(strategy.result(state));
142
143 if ( r != 0 )
144 return -1; // exterior
145
146 // if the point is equal to the one of the terminal points
147 if ( detail::within::equals_point_point(point, p0, strategy)
148 || detail::within::equals_point_point(point, p1, strategy) )
149 return 0; // boundary
150 else
151 return 1; // interior
152 }
153 };
154
155
156 template <typename Linestring>
157 struct point_in_geometry<Linestring, linestring_tag>
158 {
159 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry160 int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
161 {
162 std::size_t count = boost::size(linestring);
163 if ( count > 1 )
164 {
165 if ( detail::within::point_in_range(point, linestring, strategy) != 0 )
166 return -1; // exterior
167
168 // if the linestring doesn't have a boundary
169 if (detail::within::equals_point_point(range::front(linestring), range::back(linestring), strategy))
170 return 1; // interior
171 // else if the point is equal to the one of the terminal points
172 else if (detail::within::equals_point_point(point, range::front(linestring), strategy)
173 || detail::within::equals_point_point(point, range::back(linestring), strategy))
174 return 0; // boundary
175 else
176 return 1; // interior
177 }
178 // TODO: for now degenerated linestrings are ignored
179 // throw an exception here?
180 /*else if ( count == 1 )
181 {
182 if ( detail::equals::equals_point_point(point, range::front(linestring)) )
183 return 1;
184 }*/
185
186 return -1; // exterior
187 }
188 };
189
190 template <typename Ring>
191 struct point_in_geometry<Ring, ring_tag>
192 {
193 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry194 int apply(Point const& point, Ring const& ring, Strategy const& strategy)
195 {
196 if ( boost::size(ring) < core_detail::closure::minimum_ring_size
197 <
198 geometry::closure<Ring>::value
199 >::value )
200 {
201 return -1;
202 }
203
204 detail::normalized_view<Ring const> view(ring);
205 return detail::within::point_in_range(point, view, strategy);
206 }
207 };
208
209 // Polygon: in exterior ring, and if so, not within interior ring(s)
210 template <typename Polygon>
211 struct point_in_geometry<Polygon, polygon_tag>
212 {
213 template <typename Point, typename Strategy>
applyboost::geometry::detail_dispatch::within::point_in_geometry214 static inline int apply(Point const& point, Polygon const& polygon,
215 Strategy const& strategy)
216 {
217 int const code = point_in_geometry
218 <
219 typename ring_type<Polygon>::type
220 >::apply(point, exterior_ring(polygon), strategy);
221
222 if (code == 1)
223 {
224 typename interior_return_type<Polygon const>::type
225 rings = interior_rings(polygon);
226
227 for (typename detail::interior_iterator<Polygon const>::type
228 it = boost::begin(rings);
229 it != boost::end(rings);
230 ++it)
231 {
232 int const interior_code = point_in_geometry
233 <
234 typename ring_type<Polygon>::type
235 >::apply(point, *it, strategy);
236
237 if (interior_code != -1)
238 {
239 // If 0, return 0 (touch)
240 // If 1 (inside hole) return -1 (outside polygon)
241 // If -1 (outside hole) check other holes if any
242 return -interior_code;
243 }
244 }
245 }
246 return code;
247 }
248 };
249
250 template <typename Geometry>
251 struct point_in_geometry<Geometry, multi_point_tag>
252 {
253 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry254 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
255 {
256 typedef typename boost::range_value<Geometry>::type point_type;
257 typedef typename boost::range_const_iterator<Geometry>::type iterator;
258 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
259 {
260 int pip = point_in_geometry<point_type>::apply(point, *it, strategy);
261
262 //BOOST_GEOMETRY_ASSERT(pip != 0);
263 if ( pip > 0 ) // inside
264 return 1;
265 }
266
267 return -1; // outside
268 }
269 };
270
271 template <typename Geometry>
272 struct point_in_geometry<Geometry, multi_linestring_tag>
273 {
274 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry275 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
276 {
277 int pip = -1; // outside
278
279 typedef typename boost::range_value<Geometry>::type linestring_type;
280 typedef typename boost::range_value<linestring_type>::type point_type;
281 typedef typename boost::range_iterator<Geometry const>::type iterator;
282 iterator it = boost::begin(geometry);
283 for ( ; it != boost::end(geometry) ; ++it )
284 {
285 pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);
286
287 // inside or on the boundary
288 if ( pip >= 0 )
289 {
290 ++it;
291 break;
292 }
293 }
294
295 // outside
296 if ( pip < 0 )
297 return -1;
298
299 // TODO: the following isn't needed for covered_by()
300
301 unsigned boundaries = pip == 0 ? 1 : 0;
302
303 for ( ; it != boost::end(geometry) ; ++it )
304 {
305 if ( boost::size(*it) < 2 )
306 continue;
307
308 point_type const& front = range::front(*it);
309 point_type const& back = range::back(*it);
310
311 // is closed_ring - no boundary
312 if ( detail::within::equals_point_point(front, back, strategy) )
313 continue;
314
315 // is point on boundary
316 if ( detail::within::equals_point_point(point, front, strategy)
317 || detail::within::equals_point_point(point, back, strategy) )
318 {
319 ++boundaries;
320 }
321 }
322
323 // if the number of boundaries is odd, the point is on the boundary
324 return boundaries % 2 ? 0 : 1;
325 }
326 };
327
328 template <typename Geometry>
329 struct point_in_geometry<Geometry, multi_polygon_tag>
330 {
331 template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry332 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
333 {
334 // For invalid multipolygons
335 //int res = -1; // outside
336
337 typedef typename boost::range_value<Geometry>::type polygon_type;
338 typedef typename boost::range_const_iterator<Geometry>::type iterator;
339 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
340 {
341 int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);
342
343 // inside or on the boundary
344 if ( pip >= 0 )
345 return pip;
346
347 // For invalid multi-polygons
348 //if ( 1 == pip ) // inside polygon
349 // return 1;
350 //else if ( res < pip ) // point must be inside at least one polygon
351 // res = pip;
352 }
353
354 return -1; // for valid multipolygons
355 //return res; // for invalid multipolygons
356 }
357 };
358
359 }} // namespace detail_dispatch::within
360
361 namespace detail { namespace within {
362
363 // 1 - in the interior
364 // 0 - in the boundry
365 // -1 - in the exterior
366 template <typename Point, typename Geometry, typename Strategy>
point_in_geometry(Point const & point,Geometry const & geometry,Strategy const & strategy)367 inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
368 {
369 concepts::within::check<Point, Geometry, Strategy>();
370
371 return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
372 }
373
374 template <typename Point, typename Geometry>
point_in_geometry(Point const & point,Geometry const & geometry)375 inline int point_in_geometry(Point const& point, Geometry const& geometry)
376 {
377 typedef typename strategy::point_in_geometry::services::default_strategy
378 <
379 Point, Geometry
380 >::type strategy_type;
381
382 return point_in_geometry(point, geometry, strategy_type());
383 }
384
385 template <typename Point, typename Geometry, typename Strategy>
within_point_geometry(Point const & point,Geometry const & geometry,Strategy const & strategy)386 inline bool within_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
387 {
388 return point_in_geometry(point, geometry, strategy) > 0;
389 }
390
391 template <typename Point, typename Geometry>
within_point_geometry(Point const & point,Geometry const & geometry)392 inline bool within_point_geometry(Point const& point, Geometry const& geometry)
393 {
394 return point_in_geometry(point, geometry) > 0;
395 }
396
397 template <typename Point, typename Geometry, typename Strategy>
covered_by_point_geometry(Point const & point,Geometry const & geometry,Strategy const & strategy)398 inline bool covered_by_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
399 {
400 return point_in_geometry(point, geometry, strategy) >= 0;
401 }
402
403 template <typename Point, typename Geometry>
covered_by_point_geometry(Point const & point,Geometry const & geometry)404 inline bool covered_by_point_geometry(Point const& point, Geometry const& geometry)
405 {
406 return point_in_geometry(point, geometry) >= 0;
407 }
408
409 }} // namespace detail::within
410 #endif // DOXYGEN_NO_DETAIL
411
412 }} // namespace boost::geometry
413
414 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
415