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