boost/geometry/algorithms/within.hpp

   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 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
   8 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP
  16
  17
  18 #include <cstddef>
  19
  20 #include <boost/range.hpp>
  21 #include <boost/typeof/typeof.hpp>
  22
  23 #include <boost/geometry/algorithms/make.hpp>
  24 #include <boost/geometry/algorithms/not_implemented.hpp>
  25
  26 #include <boost/geometry/core/access.hpp>
  27 #include <boost/geometry/core/closure.hpp>
  28 #include <boost/geometry/core/cs.hpp>
  29 #include <boost/geometry/core/exterior_ring.hpp>
  30 #include <boost/geometry/core/interior_rings.hpp>
  31 #include <boost/geometry/core/point_order.hpp>
  32 #include <boost/geometry/core/ring_type.hpp>
  33 #include <boost/geometry/core/interior_rings.hpp>
  34 #include <boost/geometry/core/tags.hpp>
  35
  36 #include <boost/geometry/geometries/concepts/check.hpp>
  37 #include <boost/geometry/strategies/within.hpp>
  38 #include <boost/geometry/strategies/concepts/within_concept.hpp>
  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
  45 namespace boost { namespace geometry
  46 {
  47
  48 #ifndef DOXYGEN_NO_DETAIL
  49 namespace detail { namespace within
  50 {
  51
  52
  53 template
  54 <
  55     typename Point,
  56     typename Ring,
  57     iterate_direction Direction,
  58     closure_selector Closure,
  59     typename Strategy
  60 >
  61 struct point_in_ring
  62 {
  63     BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategyPolygonal<Strategy>) );
  64
  65     static inline int apply(Point const& point, Ring const& ring,
  66             Strategy const& strategy)
  67     {
  68         if (boost::size(ring)
  69                 < core_detail::closure::minimum_ring_size<Closure>::value)
  70         {
  71             return -1;
  72         }
  73
  74         typedef typename reversible_view<Ring const, Direction>::type rev_view_type;
  75         typedef typename closeable_view
  76             <
  77                 rev_view_type const, Closure
  78             >::type cl_view_type;
  79         typedef typename boost::range_iterator<cl_view_type const>::type iterator_type;
  80
  81         rev_view_type rev_view(ring);
  82         cl_view_type view(rev_view);
  83         typename Strategy::state_type state;
  84         iterator_type it = boost::begin(view);
  85         iterator_type end = boost::end(view);
  86
  87         bool stop = false;
  88         for (iterator_type previous = it++;
  89             it != end && ! stop;
  90             ++previous, ++it)
  91         {
  92             if (! strategy.apply(point, *previous, *it, state))
  93             {
  94                 stop = true;
  95             }
  96         }
  97
  98         return strategy.result(state);
  99     }
 100 };
 101
 102
 103 // Polygon: in exterior ring, and if so, not within interior ring(s)
 104 template
 105 <
 106     typename Point,
 107     typename Polygon,
 108     iterate_direction Direction,
 109     closure_selector Closure,
 110     typename Strategy
 111 >
 112 struct point_in_polygon
 113 {
 114     BOOST_CONCEPT_ASSERT( (geometry::concept::WithinStrategyPolygonal<Strategy>) );
 115
 116     static inline int apply(Point const& point, Polygon const& poly,
 117             Strategy const& strategy)
 118     {
 119         int const code = point_in_ring
 120             <
 121                 Point,
 122                 typename ring_type<Polygon>::type,
 123                 Direction,
 124                 Closure,
 125                 Strategy
 126             >::apply(point, exterior_ring(poly), strategy);
 127
 128         if (code == 1)
 129         {
 130             typename interior_return_type<Polygon const>::type rings
 131                         = interior_rings(poly);
 132             for (BOOST_AUTO_TPL(it, boost::begin(rings));
 133                 it != boost::end(rings);
 134                 ++it)
 135             {
 136                 int const interior_code = point_in_ring
 137                     <
 138                         Point,
 139                         typename ring_type<Polygon>::type,
 140                         Direction,
 141                         Closure,
 142                         Strategy
 143                     >::apply(point, *it, strategy);
 144
 145                 if (interior_code != -1)
 146                 {
 147                     // If 0, return 0 (touch)
 148                     // If 1 (inside hole) return -1 (outside polygon)
 149                     // If -1 (outside hole) check other holes if any
 150                     return -interior_code;
 151                 }
 152             }
 153         }
 154         return code;
 155     }
 156 };
 157
 158 }} // namespace detail::within
 159 #endif // DOXYGEN_NO_DETAIL
 160
 161
 162 #ifndef DOXYGEN_NO_DISPATCH
 163 namespace dispatch
 164 {
 165
 166 template
 167 <
 168     typename Geometry1,
 169     typename Geometry2,
 170     typename Tag1 = typename tag<Geometry1>::type,
 171     typename Tag2 = typename tag<Geometry2>::type
 172 >
 173 struct within: not_implemented<Tag1, Tag2>
 174 {};
 175
 176
 177 template <typename Point, typename Box>
 178 struct within<Point, Box, point_tag, box_tag>
 179 {
 180     template <typename Strategy>
 181     static inline bool apply(Point const& point, Box const& box, Strategy const& strategy)
 182     {
 183         return strategy.apply(point, box);
 184     }
 185 };
 186
 187 template <typename Box1, typename Box2>
 188 struct within<Box1, Box2, box_tag, box_tag>
 189 {
 190     template <typename Strategy>
 191     static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
 192     {
 193         assert_dimension_equal<Box1, Box2>();
 194         return strategy.apply(box1, box2);
 195     }
 196 };
 197
 198
 199
 200 template <typename Point, typename Ring>
 201 struct within<Point, Ring, point_tag, ring_tag>
 202 {
 203     template <typename Strategy>
 204     static inline bool apply(Point const& point, Ring const& ring, Strategy const& strategy)
 205     {
 206         return detail::within::point_in_ring
 207             <
 208                 Point,
 209                 Ring,
 210                 order_as_direction<geometry::point_order<Ring>::value>::value,
 211                 geometry::closure<Ring>::value,
 212                 Strategy
 213             >::apply(point, ring, strategy) == 1;
 214     }
 215 };
 216
 217 template <typename Point, typename Polygon>
 218 struct within<Point, Polygon, point_tag, polygon_tag>
 219 {
 220     template <typename Strategy>
 221     static inline bool apply(Point const& point, Polygon const& polygon, Strategy const& strategy)
 222     {
 223         return detail::within::point_in_polygon
 224             <
 225                 Point,
 226                 Polygon,
 227                 order_as_direction<geometry::point_order<Polygon>::value>::value,
 228                 geometry::closure<Polygon>::value,
 229                 Strategy
 230             >::apply(point, polygon, strategy) == 1;
 231     }
 232 };
 233
 234 } // namespace dispatch
 235 #endif // DOXYGEN_NO_DISPATCH
 236
 237
 238 /*!
 239 \brief \brief_check12{is completely inside}
 240 \ingroup within
 241 \details \details_check12{within, is completely inside}.
 242 \tparam Geometry1 \tparam_geometry
 243 \tparam Geometry2 \tparam_geometry
 244 \param geometry1 \param_geometry which might be within the second geometry
 245 \param geometry2 \param_geometry which might contain the first geometry
 246 \return true if geometry1 is completely contained within geometry2,
 247     else false
 248 \note The default strategy is used for within detection
 249
 250
 251 \qbk{[include reference/algorithms/within.qbk]}
 252
 253 \qbk{
 254 [heading Example]
 255 [within]
 256 [within_output]
 257 }
 258  */
 259 template<typename Geometry1, typename Geometry2>
 260 inline bool within(Geometry1 const& geometry1, Geometry2 const& geometry2)
 261 {
 262     concept::check<Geometry1 const>();
 263     concept::check<Geometry2 const>();
 264     assert_dimension_equal<Geometry1, Geometry2>();
 265
 266     typedef typename point_type<Geometry1>::type point_type1;
 267     typedef typename point_type<Geometry2>::type point_type2;
 268
 269     typedef typename strategy::within::services::default_strategy
 270         <
 271             typename tag<Geometry1>::type,
 272             typename tag<Geometry2>::type,
 273             typename tag<Geometry1>::type,
 274             typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
 275             typename tag_cast
 276                 <
 277                     typename cs_tag<point_type1>::type, spherical_tag
 278                 >::type,
 279             typename tag_cast
 280                 <
 281                     typename cs_tag<point_type2>::type, spherical_tag
 282                 >::type,
 283             Geometry1,
 284             Geometry2
 285         >::type strategy_type;
 286
 287     return dispatch::within
 288         <
 289             Geometry1,
 290             Geometry2
 291         >::apply(geometry1, geometry2, strategy_type());
 292 }
 293
 294 /*!
 295 \brief \brief_check12{is completely inside} \brief_strategy
 296 \ingroup within
 297 \details \details_check12{within, is completely inside}, \brief_strategy. \details_strategy_reasons
 298 \tparam Geometry1 \tparam_geometry
 299 \tparam Geometry2 \tparam_geometry
 300 \param geometry1 \param_geometry which might be within the second geometry
 301 \param geometry2 \param_geometry which might contain the first geometry
 302 \param strategy strategy to be used
 303 \return true if geometry1 is completely contained within geometry2,
 304     else false
 305
 306 \qbk{distinguish,with strategy}
 307 \qbk{[include reference/algorithms/within.qbk]}
 308 \qbk{
 309 [heading Available Strategies]
 310 \* [link geometry.reference.strategies.strategy_within_winding Winding (coordinate system agnostic)]
 311 \* [link geometry.reference.strategies.strategy_within_franklin Franklin (cartesian)]
 312 \* [link geometry.reference.strategies.strategy_within_crossings_multiply Crossings Multiply (cartesian)]
 313
 314 [heading Example]
 315 [within_strategy]
 316 [within_strategy_output]
 317
 318 }
 319 */
 320 template<typename Geometry1, typename Geometry2, typename Strategy>
 321 inline bool within(Geometry1 const& geometry1, Geometry2 const& geometry2,
 322         Strategy const& strategy)
 323 {
 324     concept::within::check
 325         <
 326             typename tag<Geometry1>::type,
 327             typename tag<Geometry2>::type,
 328             typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
 329             Strategy
 330         >();
 331     concept::check<Geometry1 const>();
 332     concept::check<Geometry2 const>();
 333     assert_dimension_equal<Geometry1, Geometry2>();
 334
 335     return dispatch::within
 336         <
 337             Geometry1,
 338             Geometry2
 339         >::apply(geometry1, geometry2, strategy);
 340 }
 341
 342 }} // namespace boost::geometry
 343
 344 #endif // BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP