1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // This file was modified by Oracle on 2013, 2014, 2015.
9 // Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
14 // Use, modification and distribution is subject to the Boost Software License,
15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
16 // http://www.boost.org/LICENSE_1_0.txt)
18 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
20 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
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>
30 #include <boost/geometry/core/assert.hpp>
32 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
33 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
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/within.hpp>
39 #include <boost/geometry/strategies/covered_by.hpp>
41 #include <boost/geometry/util/range.hpp>
42 #include <boost/geometry/views/detail/normalized_view.hpp>
44 namespace boost { namespace geometry {
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail { namespace within {
49 // TODO: is this needed?
50 inline int check_result_type(int result)
56 inline T check_result_type(T result)
58 BOOST_GEOMETRY_ASSERT(false);
62 template <typename Point, typename Range, typename Strategy> inline
63 int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
65 boost::ignore_unused(strategy);
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);
72 for ( iterator_type previous = it++ ; it != end ; ++previous, ++it )
74 if ( ! strategy.apply(point, *previous, *it, state) )
80 return check_result_type(strategy.result(state));
83 template <typename Geometry, typename Point, typename Range>
84 inline int point_in_range(Point const& point, Range const& range)
86 typedef typename point_type<Point>::type point_type1;
87 typedef typename point_type<Geometry>::type point_type2;
89 typedef typename strategy::within::services::default_strategy
91 typename tag<Point>::type,
92 typename tag<Geometry>::type,
93 typename tag<Point>::type,
94 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
97 typename cs_tag<point_type1>::type, spherical_tag
101 typename cs_tag<point_type2>::type, spherical_tag
105 >::type strategy_type;
107 typedef typename strategy::covered_by::services::default_strategy
109 typename tag<Point>::type,
110 typename tag<Geometry>::type,
111 typename tag<Point>::type,
112 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
115 typename cs_tag<point_type1>::type, spherical_tag
119 typename cs_tag<point_type2>::type, spherical_tag
123 >::type strategy_type2;
125 static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
126 BOOST_MPL_ASSERT_MSG((same_strategies),
127 DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
128 (strategy_type, strategy_type2));
130 return point_in_range(point, range, strategy_type());
133 }} // namespace detail::within
135 namespace detail_dispatch { namespace within {
137 // checks the relation between a point P and geometry G
138 // returns 1 if P is in the interior of G
139 // returns 0 if P is on the boundry of G
140 // returns -1 if P is in the exterior of G
142 template <typename Geometry,
143 typename Tag = typename geometry::tag<Geometry>::type>
144 struct point_in_geometry
145 : not_implemented<Tag>
148 template <typename Point2>
149 struct point_in_geometry<Point2, point_tag>
151 template <typename Point1, typename Strategy> static inline
152 int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
154 boost::ignore_unused(strategy);
155 return strategy.apply(point1, point2) ? 1 : -1;
159 template <typename Segment>
160 struct point_in_geometry<Segment, segment_tag>
162 template <typename Point, typename Strategy> static inline
163 int apply(Point const& point, Segment const& segment, Strategy const& strategy)
165 boost::ignore_unused(strategy);
167 typedef typename geometry::point_type<Segment>::type point_type;
169 // TODO: don't copy points
170 detail::assign_point_from_index<0>(segment, p0);
171 detail::assign_point_from_index<1>(segment, p1);
173 typename Strategy::state_type state;
174 strategy.apply(point, p0, p1, state);
175 int r = detail::within::check_result_type(strategy.result(state));
178 return -1; // exterior
180 // if the point is equal to the one of the terminal points
181 if ( detail::equals::equals_point_point(point, p0)
182 || detail::equals::equals_point_point(point, p1) )
183 return 0; // boundary
185 return 1; // interior
190 template <typename Linestring>
191 struct point_in_geometry<Linestring, linestring_tag>
193 template <typename Point, typename Strategy> static inline
194 int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
196 std::size_t count = boost::size(linestring);
199 if ( detail::within::point_in_range(point, linestring, strategy) != 0 )
200 return -1; // exterior
202 // if the linestring doesn't have a boundary
203 if (detail::equals::equals_point_point(range::front(linestring), range::back(linestring)))
204 return 1; // interior
205 // else if the point is equal to the one of the terminal points
206 else if (detail::equals::equals_point_point(point, range::front(linestring))
207 || detail::equals::equals_point_point(point, range::back(linestring)))
208 return 0; // boundary
210 return 1; // interior
212 // TODO: for now degenerated linestrings are ignored
213 // throw an exception here?
214 /*else if ( count == 1 )
216 if ( detail::equals::equals_point_point(point, range::front(linestring)) )
220 return -1; // exterior
224 template <typename Ring>
225 struct point_in_geometry<Ring, ring_tag>
227 template <typename Point, typename Strategy> static inline
228 int apply(Point const& point, Ring const& ring, Strategy const& strategy)
230 if ( boost::size(ring) < core_detail::closure::minimum_ring_size
232 geometry::closure<Ring>::value
238 detail::normalized_view<Ring const> view(ring);
239 return detail::within::point_in_range(point, view, strategy);
243 // Polygon: in exterior ring, and if so, not within interior ring(s)
244 template <typename Polygon>
245 struct point_in_geometry<Polygon, polygon_tag>
247 template <typename Point, typename Strategy>
248 static inline int apply(Point const& point, Polygon const& polygon,
249 Strategy const& strategy)
251 int const code = point_in_geometry
253 typename ring_type<Polygon>::type
254 >::apply(point, exterior_ring(polygon), strategy);
258 typename interior_return_type<Polygon const>::type
259 rings = interior_rings(polygon);
261 for (typename detail::interior_iterator<Polygon const>::type
262 it = boost::begin(rings);
263 it != boost::end(rings);
266 int const interior_code = point_in_geometry
268 typename ring_type<Polygon>::type
269 >::apply(point, *it, strategy);
271 if (interior_code != -1)
273 // If 0, return 0 (touch)
274 // If 1 (inside hole) return -1 (outside polygon)
275 // If -1 (outside hole) check other holes if any
276 return -interior_code;
284 template <typename Geometry>
285 struct point_in_geometry<Geometry, multi_point_tag>
287 template <typename Point, typename Strategy> static inline
288 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
290 typedef typename boost::range_value<Geometry>::type point_type;
291 typedef typename boost::range_const_iterator<Geometry>::type iterator;
292 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
294 int pip = point_in_geometry<point_type>::apply(point, *it, strategy);
296 //BOOST_GEOMETRY_ASSERT(pip != 0);
297 if ( pip > 0 ) // inside
301 return -1; // outside
305 template <typename Geometry>
306 struct point_in_geometry<Geometry, multi_linestring_tag>
308 template <typename Point, typename Strategy> static inline
309 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
311 int pip = -1; // outside
313 typedef typename boost::range_value<Geometry>::type linestring_type;
314 typedef typename boost::range_value<linestring_type>::type point_type;
315 typedef typename boost::range_iterator<Geometry const>::type iterator;
316 iterator it = boost::begin(geometry);
317 for ( ; it != boost::end(geometry) ; ++it )
319 pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);
321 // inside or on the boundary
333 // TODO: the following isn't needed for covered_by()
335 unsigned boundaries = pip == 0 ? 1 : 0;
337 for ( ; it != boost::end(geometry) ; ++it )
339 if ( boost::size(*it) < 2 )
342 point_type const& front = range::front(*it);
343 point_type const& back = range::back(*it);
345 // is closed_ring - no boundary
346 if ( detail::equals::equals_point_point(front, back) )
349 // is point on boundary
350 if ( detail::equals::equals_point_point(point, front)
351 || detail::equals::equals_point_point(point, back) )
357 // if the number of boundaries is odd, the point is on the boundary
358 return boundaries % 2 ? 0 : 1;
362 template <typename Geometry>
363 struct point_in_geometry<Geometry, multi_polygon_tag>
365 template <typename Point, typename Strategy> static inline
366 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
368 // For invalid multipolygons
369 //int res = -1; // outside
371 typedef typename boost::range_value<Geometry>::type polygon_type;
372 typedef typename boost::range_const_iterator<Geometry>::type iterator;
373 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
375 int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);
377 // inside or on the boundary
381 // For invalid multi-polygons
382 //if ( 1 == pip ) // inside polygon
384 //else if ( res < pip ) // point must be inside at least one polygon
388 return -1; // for valid multipolygons
389 //return res; // for invalid multipolygons
393 }} // namespace detail_dispatch::within
395 namespace detail { namespace within {
397 // 1 - in the interior
398 // 0 - in the boundry
399 // -1 - in the exterior
400 template <typename Point, typename Geometry, typename Strategy>
401 inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
403 concepts::within::check
405 typename tag<Point>::type,
406 typename tag<Geometry>::type,
407 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
411 return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
414 template <typename Point, typename Geometry>
415 inline int point_in_geometry(Point const& point, Geometry const& geometry)
417 typedef typename point_type<Point>::type point_type1;
418 typedef typename point_type<Geometry>::type point_type2;
420 typedef typename strategy::within::services::default_strategy
422 typename tag<Point>::type,
423 typename tag<Geometry>::type,
424 typename tag<Point>::type,
425 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
428 typename cs_tag<point_type1>::type, spherical_tag
432 typename cs_tag<point_type2>::type, spherical_tag
436 >::type strategy_type;
438 typedef typename strategy::covered_by::services::default_strategy
440 typename tag<Point>::type,
441 typename tag<Geometry>::type,
442 typename tag<Point>::type,
443 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
446 typename cs_tag<point_type1>::type, spherical_tag
450 typename cs_tag<point_type2>::type, spherical_tag
454 >::type strategy_type2;
456 static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
457 BOOST_MPL_ASSERT_MSG((same_strategies),
458 DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
459 (strategy_type, strategy_type2));
461 return point_in_geometry(point, geometry, strategy_type());
464 }} // namespace detail::within
465 #endif // DOXYGEN_NO_DETAIL
467 }} // namespace boost::geometry
469 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP