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.
9 // Modifications copyright (c) 2013-2017, 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 
49 // TODO: is this needed?
check_result_type(int result)50 inline int check_result_type(int result)
51 {
52     return result;
53 }
54 
55 template <typename T>
check_result_type(T result)56 inline T check_result_type(T result)
57 {
58     BOOST_GEOMETRY_ASSERT(false);
59     return result;
60 }
61 
62 template <typename Point, typename Range, typename Strategy> inline
point_in_range(Point const & point,Range const & range,Strategy const & strategy)63 int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
64 {
65     boost::ignore_unused(strategy);
66 
67     typedef typename boost::range_iterator<Range const>::type iterator_type;
68     typename Strategy::state_type state;
69     iterator_type it = boost::begin(range);
70     iterator_type end = boost::end(range);
71 
72     for ( iterator_type previous = it++ ; it != end ; ++previous, ++it )
73     {
74         if ( ! strategy.apply(point, *previous, *it, state) )
75         {
76             break;
77         }
78     }
79 
80     return check_result_type(strategy.result(state));
81 }
82 
83 template <typename Geometry, typename Point, typename Range>
point_in_range(Point const & point,Range const & range)84 inline int point_in_range(Point const& point, Range const& range)
85 {
86     typedef typename strategy::point_in_geometry::services::default_strategy
87         <
88             Point, Geometry
89         >::type strategy_type;
90 
91     return point_in_range(point, range, strategy_type());
92 }
93 
94 }} // namespace detail::within
95 
96 namespace detail_dispatch { namespace within {
97 
98 // checks the relation between a point P and geometry G
99 // returns 1 if P is in the interior of G
100 // returns 0 if P is on the boundry of G
101 // returns -1 if P is in the exterior of G
102 
103 template <typename Geometry,
104           typename Tag = typename geometry::tag<Geometry>::type>
105 struct point_in_geometry
106     : not_implemented<Tag>
107 {};
108 
109 template <typename Point2>
110 struct point_in_geometry<Point2, point_tag>
111 {
112     template <typename Point1, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry113     int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
114     {
115         boost::ignore_unused(strategy);
116         return strategy.apply(point1, point2) ? 1 : -1;
117     }
118 };
119 
120 template <typename Segment>
121 struct point_in_geometry<Segment, segment_tag>
122 {
123     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry124     int apply(Point const& point, Segment const& segment, Strategy const& strategy)
125     {
126         boost::ignore_unused(strategy);
127 
128         typedef typename geometry::point_type<Segment>::type point_type;
129         point_type p0, p1;
130 // TODO: don't copy points
131         detail::assign_point_from_index<0>(segment, p0);
132         detail::assign_point_from_index<1>(segment, p1);
133 
134         typename Strategy::state_type state;
135         strategy.apply(point, p0, p1, state);
136         int r = detail::within::check_result_type(strategy.result(state));
137 
138         if ( r != 0 )
139             return -1; // exterior
140 
141         // if the point is equal to the one of the terminal points
142         if ( detail::equals::equals_point_point(point, p0)
143           || detail::equals::equals_point_point(point, p1) )
144             return 0; // boundary
145         else
146             return 1; // interior
147     }
148 };
149 
150 
151 template <typename Linestring>
152 struct point_in_geometry<Linestring, linestring_tag>
153 {
154     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry155     int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
156     {
157         std::size_t count = boost::size(linestring);
158         if ( count > 1 )
159         {
160             if ( detail::within::point_in_range(point, linestring, strategy) != 0 )
161                 return -1; // exterior
162 
163             // if the linestring doesn't have a boundary
164             if (detail::equals::equals_point_point(range::front(linestring), range::back(linestring)))
165                 return 1; // interior
166             // else if the point is equal to the one of the terminal points
167             else if (detail::equals::equals_point_point(point, range::front(linestring))
168                 || detail::equals::equals_point_point(point, range::back(linestring)))
169                 return 0; // boundary
170             else
171                 return 1; // interior
172         }
173 // TODO: for now degenerated linestrings are ignored
174 //       throw an exception here?
175         /*else if ( count == 1 )
176         {
177             if ( detail::equals::equals_point_point(point, range::front(linestring)) )
178                 return 1;
179         }*/
180 
181         return -1; // exterior
182     }
183 };
184 
185 template <typename Ring>
186 struct point_in_geometry<Ring, ring_tag>
187 {
188     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry189     int apply(Point const& point, Ring const& ring, Strategy const& strategy)
190     {
191         if ( boost::size(ring) < core_detail::closure::minimum_ring_size
192                                     <
193                                         geometry::closure<Ring>::value
194                                     >::value )
195         {
196             return -1;
197         }
198 
199         detail::normalized_view<Ring const> view(ring);
200         return detail::within::point_in_range(point, view, strategy);
201     }
202 };
203 
204 // Polygon: in exterior ring, and if so, not within interior ring(s)
205 template <typename Polygon>
206 struct point_in_geometry<Polygon, polygon_tag>
207 {
208     template <typename Point, typename Strategy>
applyboost::geometry::detail_dispatch::within::point_in_geometry209     static inline int apply(Point const& point, Polygon const& polygon,
210                             Strategy const& strategy)
211     {
212         int const code = point_in_geometry
213             <
214                 typename ring_type<Polygon>::type
215             >::apply(point, exterior_ring(polygon), strategy);
216 
217         if (code == 1)
218         {
219             typename interior_return_type<Polygon const>::type
220                 rings = interior_rings(polygon);
221 
222             for (typename detail::interior_iterator<Polygon const>::type
223                  it = boost::begin(rings);
224                  it != boost::end(rings);
225                  ++it)
226             {
227                 int const interior_code = point_in_geometry
228                     <
229                         typename ring_type<Polygon>::type
230                     >::apply(point, *it, strategy);
231 
232                 if (interior_code != -1)
233                 {
234                     // If 0, return 0 (touch)
235                     // If 1 (inside hole) return -1 (outside polygon)
236                     // If -1 (outside hole) check other holes if any
237                     return -interior_code;
238                 }
239             }
240         }
241         return code;
242     }
243 };
244 
245 template <typename Geometry>
246 struct point_in_geometry<Geometry, multi_point_tag>
247 {
248     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry249     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
250     {
251         typedef typename boost::range_value<Geometry>::type point_type;
252         typedef typename boost::range_const_iterator<Geometry>::type iterator;
253         for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
254         {
255             int pip = point_in_geometry<point_type>::apply(point, *it, strategy);
256 
257             //BOOST_GEOMETRY_ASSERT(pip != 0);
258             if ( pip > 0 ) // inside
259                 return 1;
260         }
261 
262         return -1; // outside
263     }
264 };
265 
266 template <typename Geometry>
267 struct point_in_geometry<Geometry, multi_linestring_tag>
268 {
269     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry270     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
271     {
272         int pip = -1; // outside
273 
274         typedef typename boost::range_value<Geometry>::type linestring_type;
275         typedef typename boost::range_value<linestring_type>::type point_type;
276         typedef typename boost::range_iterator<Geometry const>::type iterator;
277         iterator it = boost::begin(geometry);
278         for ( ; it != boost::end(geometry) ; ++it )
279         {
280             pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);
281 
282             // inside or on the boundary
283             if ( pip >= 0 )
284             {
285                 ++it;
286                 break;
287             }
288         }
289 
290         // outside
291         if ( pip < 0 )
292             return -1;
293 
294         // TODO: the following isn't needed for covered_by()
295 
296         unsigned boundaries = pip == 0 ? 1 : 0;
297 
298         for ( ; it != boost::end(geometry) ; ++it )
299         {
300             if ( boost::size(*it) < 2 )
301                 continue;
302 
303             point_type const& front = range::front(*it);
304             point_type const& back = range::back(*it);
305 
306             // is closed_ring - no boundary
307             if ( detail::equals::equals_point_point(front, back) )
308                 continue;
309 
310             // is point on boundary
311             if ( detail::equals::equals_point_point(point, front)
312               || detail::equals::equals_point_point(point, back) )
313             {
314                 ++boundaries;
315             }
316         }
317 
318         // if the number of boundaries is odd, the point is on the boundary
319         return boundaries % 2 ? 0 : 1;
320     }
321 };
322 
323 template <typename Geometry>
324 struct point_in_geometry<Geometry, multi_polygon_tag>
325 {
326     template <typename Point, typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::point_in_geometry327     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
328     {
329         // For invalid multipolygons
330         //int res = -1; // outside
331 
332         typedef typename boost::range_value<Geometry>::type polygon_type;
333         typedef typename boost::range_const_iterator<Geometry>::type iterator;
334         for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
335         {
336             int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);
337 
338             // inside or on the boundary
339             if ( pip >= 0 )
340                 return pip;
341 
342             // For invalid multi-polygons
343             //if ( 1 == pip ) // inside polygon
344             //    return 1;
345             //else if ( res < pip ) // point must be inside at least one polygon
346             //    res = pip;
347         }
348 
349         return -1; // for valid multipolygons
350         //return res; // for invalid multipolygons
351     }
352 };
353 
354 }} // namespace detail_dispatch::within
355 
356 namespace detail { namespace within {
357 
358 // 1 - in the interior
359 // 0 - in the boundry
360 // -1 - in the exterior
361 template <typename Point, typename Geometry, typename Strategy>
point_in_geometry(Point const & point,Geometry const & geometry,Strategy const & strategy)362 inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
363 {
364     concepts::within::check
365         <
366             typename tag<Point>::type,
367             typename tag<Geometry>::type,
368             typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
369             Strategy
370         >();
371 
372     return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
373 }
374 
375 template <typename Point, typename Geometry>
point_in_geometry(Point const & point,Geometry const & geometry)376 inline int point_in_geometry(Point const& point, Geometry const& geometry)
377 {
378     typedef typename strategy::point_in_geometry::services::default_strategy
379         <
380             Point, Geometry
381         >::type strategy_type;
382 
383     return point_in_geometry(point, geometry, strategy_type());
384 }
385 
386 }} // namespace detail::within
387 #endif // DOXYGEN_NO_DETAIL
388 
389 }} // namespace boost::geometry
390 
391 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
392