ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/point_on_border.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.Dimension. (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_DETAIL_POINT_ON_BORDER_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_ON_BORDER_HPP
  16
  17
  18 #include <cstddef>
  19
  20 #include <boost/range.hpp>
  21
  22 #include <boost/geometry/core/tags.hpp>
  23 #include <boost/geometry/core/point_type.hpp>
  24 #include <boost/geometry/core/ring_type.hpp>
  25
  26 #include <boost/geometry/geometries/concepts/check.hpp>
  27
  28 #include <boost/geometry/algorithms/assign.hpp>
  29 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
  30 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  31
  32
  33 namespace boost { namespace geometry
  34 {
  35
  36
  37 #ifndef DOXYGEN_NO_DETAIL
  38 namespace detail { namespace point_on_border
  39 {
  40
  41
  42 template<typename Point>
  43 struct get_point
  44 {
  45     static inline bool apply(Point& destination, Point const& source, bool)
  46     {
  47         destination = source;
  48         return true;
  49     }
  50 };
  51
  52 template<typename Point, std::size_t Dimension, std::size_t DimensionCount>
  53 struct midpoint_helper
  54 {
  55     template <typename InputPoint>
  56     static inline bool apply(Point& p, InputPoint const& p1, InputPoint const& p2)
  57     {
  58         typename coordinate_type<Point>::type const two = 2;
  59         set<Dimension>(p,
  60                     (get<Dimension>(p1) + get<Dimension>(p2)) / two);
  61         return midpoint_helper<Point, Dimension + 1, DimensionCount>::apply(p, p1, p2);
  62     }
  63 };
  64
  65
  66 template <typename Point, std::size_t DimensionCount>
  67 struct midpoint_helper<Point, DimensionCount, DimensionCount>
  68 {
  69     template <typename InputPoint>
  70     static inline bool apply(Point& , InputPoint const& , InputPoint const& )
  71     {
  72         return true;
  73     }
  74 };
  75
  76
  77 template<typename Point, typename Range>
  78 struct point_on_range
  79 {
  80     static inline bool apply(Point& point, Range const& range, bool midpoint)
  81     {
  82         const std::size_t n = boost::size(range);
  83         if (midpoint && n > 1)
  84         {
  85             typedef typename boost::range_iterator
  86                 <
  87                     Range const
  88                 >::type iterator;
  89
  90             iterator it = boost::begin(range);
  91             iterator prev = it++;
  92             while (it != boost::end(range)
  93                 && detail::equals::equals_point_point(*it, *prev))
  94             {
  95                 prev = it++;
  96             }
  97             if (it != boost::end(range))
  98             {
  99                 return midpoint_helper
 100                     <
 101                         Point,
 102                         0, dimension<Point>::value
 103                     >::apply(point, *prev, *it);
 104             }
 105         }
 106
 107         if (n > 0)
 108         {
 109             geometry::detail::conversion::convert_point_to_point(*boost::begin(range), point);
 110             return true;
 111         }
 112         return false;
 113     }
 114 };
 115
 116
 117 template<typename Point, typename Polygon>
 118 struct point_on_polygon
 119 {
 120     static inline bool apply(Point& point, Polygon const& polygon, bool midpoint)
 121     {
 122         return point_on_range
 123             <
 124                 Point,
 125                 typename ring_type<Polygon>::type
 126             >::apply(point, exterior_ring(polygon), midpoint);
 127     }
 128 };
 129
 130
 131 template<typename Point, typename Box>
 132 struct point_on_box
 133 {
 134     static inline bool apply(Point& point, Box const& box, bool midpoint)
 135     {
 136         if (midpoint)
 137         {
 138             Point p1, p2;
 139             detail::assign::assign_box_2d_corner<min_corner, min_corner>(box, p1);
 140             detail::assign::assign_box_2d_corner<max_corner, min_corner>(box, p2);
 141             midpoint_helper
 142                 <
 143                     Point,
 144                     0, dimension<Point>::value
 145                 >::apply(point, p1, p2);
 146         }
 147         else
 148         {
 149             detail::assign::assign_box_2d_corner<min_corner, min_corner>(box, point);
 150         }
 151
 152         return true;
 153     }
 154 };
 155
 156
 157 template
 158 <
 159     typename Point,
 160     typename MultiGeometry,
 161     typename Policy
 162 >
 163 struct point_on_multi
 164 {
 165     static inline bool apply(Point& point, MultiGeometry const& multi, bool midpoint)
 166     {
 167         // Take a point on the first multi-geometry
 168         // (i.e. the first that is not empty)
 169         for (typename boost::range_iterator
 170                 <
 171                     MultiGeometry const
 172                 >::type it = boost::begin(multi);
 173             it != boost::end(multi);
 174             ++it)
 175         {
 176             if (Policy::apply(point, *it, midpoint))
 177             {
 178                 return true;
 179             }
 180         }
 181         return false;
 182     }
 183 };
 184
 185
 186 }} // namespace detail::point_on_border
 187 #endif // DOXYGEN_NO_DETAIL
 188
 189
 190 #ifndef DOXYGEN_NO_DISPATCH
 191 namespace dispatch
 192 {
 193
 194
 195 template
 196 <
 197     typename GeometryTag,
 198     typename Point,
 199     typename Geometry
 200
 201 >
 202 struct point_on_border
 203 {};
 204
 205
 206 template<typename Point>
 207 struct point_on_border<point_tag, Point, Point>
 208     : detail::point_on_border::get_point<Point>
 209 {};
 210
 211
 212 template<typename Point, typename Linestring>
 213 struct point_on_border<linestring_tag, Point, Linestring>
 214     : detail::point_on_border::point_on_range<Point, Linestring>
 215 {};
 216
 217
 218 template<typename Point, typename Ring>
 219 struct point_on_border<ring_tag, Point, Ring>
 220     : detail::point_on_border::point_on_range<Point, Ring>
 221 {};
 222
 223
 224 template<typename Point, typename Polygon>
 225 struct point_on_border<polygon_tag, Point, Polygon>
 226     : detail::point_on_border::point_on_polygon<Point, Polygon>
 227 {};
 228
 229
 230 template<typename Point, typename Box>
 231 struct point_on_border<box_tag, Point, Box>
 232     : detail::point_on_border::point_on_box<Point, Box>
 233 {};
 234
 235
 236 template<typename Point, typename Multi>
 237 struct point_on_border<multi_polygon_tag, Point, Multi>
 238     : detail::point_on_border::point_on_multi
 239         <
 240             Point,
 241             Multi,
 242             detail::point_on_border::point_on_polygon
 243                 <
 244                     Point,
 245                     typename boost::range_value<Multi>::type
 246                 >
 247         >
 248 {};
 249
 250
 251 template<typename Point, typename Multi>
 252 struct point_on_border<multi_linestring_tag, Point, Multi>
 253     : detail::point_on_border::point_on_multi
 254         <
 255             Point,
 256             Multi,
 257             detail::point_on_border::point_on_range
 258                 <
 259                     Point,
 260                     typename boost::range_value<Multi>::type
 261                 >
 262         >
 263 {};
 264
 265
 266 } // namespace dispatch
 267 #endif // DOXYGEN_NO_DISPATCH
 268
 269
 270 /*!
 271 \brief Take point on a border
 272 \ingroup overlay
 273 \tparam Geometry geometry type. This also defines the type of the output point
 274 \param point to assign
 275 \param geometry geometry to take point from
 276 \param midpoint boolean flag, true if the point should not be a vertex, but some point
 277     in between of two vertices
 278 \return TRUE if successful, else false.
 279     It is only false if polygon/line have no points
 280 \note for a polygon, it is always a point on the exterior ring
 281 \note for take_midpoint, it is not taken from two consecutive duplicate vertices,
 282     (unless there are no other).
 283  */
 284 template <typename Point, typename Geometry>
 285 inline bool point_on_border(Point& point,
 286             Geometry const& geometry,
 287             bool midpoint = false)
 288 {
 289     concepts::check<Point>();
 290     concepts::check<Geometry const>();
 291
 292     return dispatch::point_on_border
 293             <
 294                 typename tag<Geometry>::type,
 295                 Point,
 296                 Geometry
 297             >::apply(point, geometry, midpoint);
 298 }
 299
 300
 301 }} // namespace boost::geometry
 302
 303
 304 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_ON_BORDER_HPP