boost/geometry/algorithms/envelope.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_ENVELOPE_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_ENVELOPE_HPP
  16
  17 #include <vector>
  18
  19 #include <boost/numeric/conversion/cast.hpp>
  20 #include <boost/range.hpp>
  21 #include <boost/variant/static_visitor.hpp>
  22 #include <boost/variant/apply_visitor.hpp>
  23 #include <boost/variant/variant_fwd.hpp>
  24
  25 #include <boost/geometry/algorithms/assign.hpp>
  26 #include <boost/geometry/algorithms/expand.hpp>
  27 #include <boost/geometry/algorithms/not_implemented.hpp>
  28 #include <boost/geometry/core/cs.hpp>
  29 #include <boost/geometry/core/exterior_ring.hpp>
  30 #include <boost/geometry/core/point_type.hpp>
  31 #include <boost/geometry/core/tags.hpp>
  32
  33 #include <boost/geometry/geometries/concepts/check.hpp>
  34
  35
  36 namespace boost { namespace geometry
  37 {
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace envelope
  41 {
  42
  43
  44 /// Calculate envelope of an 2D or 3D segment
  45 struct envelope_expand_one
  46 {
  47     template<typename Geometry, typename Box>
  48     static inline void apply(Geometry const& geometry, Box& mbr)
  49     {
  50         assign_inverse(mbr);
  51         geometry::expand(mbr, geometry);
  52     }
  53 };
  54
  55
  56 /// Iterate through range (also used in multi*)
  57 template<typename Range, typename Box>
  58 inline void envelope_range_additional(Range const& range, Box& mbr)
  59 {
  60     typedef typename boost::range_iterator<Range const>::type iterator_type;
  61
  62     for (iterator_type it = boost::begin(range);
  63         it != boost::end(range);
  64         ++it)
  65     {
  66         geometry::expand(mbr, *it);
  67     }
  68 }
  69
  70
  71
  72 /// Generic range dispatching struct
  73 struct envelope_range
  74 {
  75     /// Calculate envelope of range using a strategy
  76     template <typename Range, typename Box>
  77     static inline void apply(Range const& range, Box& mbr)
  78     {
  79         assign_inverse(mbr);
  80         envelope_range_additional(range, mbr);
  81     }
  82 };
  83
  84
  85 struct envelope_multi_linestring
  86 {
  87     template<typename MultiLinestring, typename Box>
  88     static inline void apply(MultiLinestring const& mp, Box& mbr)
  89     {
  90         assign_inverse(mbr);
  91         for (typename boost::range_iterator<MultiLinestring const>::type
  92                 it = mp.begin();
  93             it != mp.end();
  94             ++it)
  95         {
  96             envelope_range_additional(*it, mbr);
  97         }
  98     }
  99 };
 100
 101
 102 // version for multi_polygon: outer ring's of all polygons
 103 struct envelope_multi_polygon
 104 {
 105     template<typename MultiPolygon, typename Box>
 106     static inline void apply(MultiPolygon const& mp, Box& mbr)
 107     {
 108         assign_inverse(mbr);
 109         for (typename boost::range_const_iterator<MultiPolygon>::type
 110                 it = mp.begin();
 111             it != mp.end();
 112             ++it)
 113         {
 114             envelope_range_additional(exterior_ring(*it), mbr);
 115         }
 116     }
 117 };
 118
 119
 120 }} // namespace detail::envelope
 121 #endif // DOXYGEN_NO_DETAIL
 122
 123 #ifndef DOXYGEN_NO_DISPATCH
 124 namespace dispatch
 125 {
 126
 127
 128 template
 129 <
 130     typename Geometry,
 131     typename Tag = typename tag<Geometry>::type
 132 >
 133 struct envelope: not_implemented<Tag>
 134 {};
 135
 136
 137 template <typename Point>
 138 struct envelope<Point, point_tag>
 139     : detail::envelope::envelope_expand_one
 140 {};
 141
 142
 143 template <typename Box>
 144 struct envelope<Box, box_tag>
 145     : detail::envelope::envelope_expand_one
 146 {};
 147
 148
 149 template <typename Segment>
 150 struct envelope<Segment, segment_tag>
 151     : detail::envelope::envelope_expand_one
 152 {};
 153
 154
 155 template <typename Linestring>
 156 struct envelope<Linestring, linestring_tag>
 157     : detail::envelope::envelope_range
 158 {};
 159
 160
 161 template <typename Ring>
 162 struct envelope<Ring, ring_tag>
 163     : detail::envelope::envelope_range
 164 {};
 165
 166
 167 template <typename Polygon>
 168 struct envelope<Polygon, polygon_tag>
 169     : detail::envelope::envelope_range
 170 {
 171     template <typename Box>
 172     static inline void apply(Polygon const& poly, Box& mbr)
 173     {
 174         // For polygon, inspecting outer ring is sufficient
 175         detail::envelope::envelope_range::apply(exterior_ring(poly), mbr);
 176     }
 177
 178 };
 179
 180
 181 template <typename Multi>
 182 struct envelope<Multi, multi_point_tag>
 183     : detail::envelope::envelope_range
 184 {};
 185
 186
 187 template <typename Multi>
 188 struct envelope<Multi, multi_linestring_tag>
 189     : detail::envelope::envelope_multi_linestring
 190 {};
 191
 192
 193 template <typename Multi>
 194 struct envelope<Multi, multi_polygon_tag>
 195     : detail::envelope::envelope_multi_polygon
 196 {};
 197
 198
 199 } // namespace dispatch
 200 #endif
 201
 202
 203 namespace resolve_variant {
 204
 205 template <typename Geometry>
 206 struct envelope
 207 {
 208     template <typename Box>
 209     static inline void apply(Geometry const& geometry, Box& box)
 210     {
 211         concept::check<Geometry const>();
 212         concept::check<Box>();
 213
 214         dispatch::envelope<Geometry>::apply(geometry, box);
 215     }
 216 };
 217
 218 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 219 struct envelope<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 220 {
 221     template <typename Box>
 222     struct visitor: boost::static_visitor<void>
 223     {
 224         Box& m_box;
 225
 226         visitor(Box& box): m_box(box) {}
 227
 228         template <typename Geometry>
 229         void operator()(Geometry const& geometry) const
 230         {
 231             envelope<Geometry>::apply(geometry, m_box);
 232         }
 233     };
 234
 235     template <typename Box>
 236     static inline void
 237     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 238           Box& box)
 239     {
 240         boost::apply_visitor(visitor<Box>(box), geometry);
 241     }
 242 };
 243
 244 } // namespace resolve_variant
 245
 246
 247 /*!
 248 \brief \brief_calc{envelope}
 249 \ingroup envelope
 250 \details \details_calc{envelope,\det_envelope}.
 251 \tparam Geometry \tparam_geometry
 252 \tparam Box \tparam_box
 253 \param geometry \param_geometry
 254 \param mbr \param_box \param_set{envelope}
 255
 256 \qbk{[include reference/algorithms/envelope.qbk]}
 257 \qbk{
 258 [heading Example]
 259 [envelope] [envelope_output]
 260 }
 261 */
 262 template<typename Geometry, typename Box>
 263 inline void envelope(Geometry const& geometry, Box& mbr)
 264 {
 265     resolve_variant::envelope<Geometry>::apply(geometry, mbr);
 266 }
 267
 268
 269 /*!
 270 \brief \brief_calc{envelope}
 271 \ingroup envelope
 272 \details \details_calc{return_envelope,\det_envelope}. \details_return{envelope}
 273 \tparam Box \tparam_box
 274 \tparam Geometry \tparam_geometry
 275 \param geometry \param_geometry
 276 \return \return_calc{envelope}
 277
 278 \qbk{[include reference/algorithms/envelope.qbk]}
 279 \qbk{
 280 [heading Example]
 281 [return_envelope] [return_envelope_output]
 282 }
 283 */
 284 template<typename Box, typename Geometry>
 285 inline Box return_envelope(Geometry const& geometry)
 286 {
 287     Box mbr;
 288     resolve_variant::envelope<Geometry>::apply(geometry, mbr);
 289     return mbr;
 290 }
 291
 292 }} // namespace boost::geometry
 293
 294 #endif // BOOST_GEOMETRY_ALGORITHMS_ENVELOPE_HPP