ceph/src/boost/boost/geometry/algorithms/detail/relate/topology_check.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
  13
  14
  15 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  16
  17 #include <boost/geometry/policies/compare.hpp>
  18
  19 #include <boost/geometry/util/has_nan_coordinate.hpp>
  20 #include <boost/geometry/util/range.hpp>
  21
  22
  23 namespace boost { namespace geometry {
  24
  25 #ifndef DOXYGEN_NO_DETAIL
  26 namespace detail { namespace relate {
  27
  28 // TODO: change the name for e.g. something with the word "exterior"
  29
  30 template <typename Geometry,
  31           typename Tag = typename geometry::tag<Geometry>::type>
  32 struct topology_check
  33     : not_implemented<Tag>
  34 {};
  35
  36 //template <typename Point>
  37 //struct topology_check<Point, point_tag>
  38 //{
  39 //    static const char interior = '0';
  40 //    static const char boundary = 'F';
  41 //
  42 //    static const bool has_interior = true;
  43 //    static const bool has_boundary = false;
  44 //
  45 //    topology_check(Point const&) {}
  46 //    template <typename IgnoreBoundaryPoint>
  47 //    topology_check(Point const&, IgnoreBoundaryPoint const&) {}
  48 //};
  49
  50 template <typename Linestring>
  51 struct topology_check<Linestring, linestring_tag>
  52 {
  53     static const char interior = '1';
  54     static const char boundary = '0';
  55
  56     topology_check(Linestring const& ls)
  57         : m_ls(ls)
  58         , m_is_initialized(false)
  59     {}
  60
  61     bool has_interior() const
  62     {
  63         init();
  64         return m_has_interior;
  65     }
  66
  67     bool has_boundary() const
  68     {
  69         init();
  70         return m_has_boundary;
  71     }
  72
  73     /*template <typename Point>
  74     bool check_boundary_point(Point const& point) const
  75     {
  76         init();
  77         return m_has_boundary
  78             && ( equals::equals_point_point(point, range::front(m_ls))
  79               || equals::equals_point_point(point, range::back(m_ls)) );
  80     }*/
  81
  82     template <typename Visitor>
  83     void for_each_boundary_point(Visitor & visitor) const
  84     {
  85         init();
  86         if (m_has_boundary)
  87         {
  88             if (visitor.apply(range::front(m_ls)))
  89                 visitor.apply(range::back(m_ls));
  90         }
  91     }
  92
  93 private:
  94     void init() const
  95     {
  96         if (m_is_initialized)
  97             return;
  98
  99         std::size_t count = boost::size(m_ls);
 100         m_has_interior = count > 0;
 101         // NOTE: Linestring with all points equal is treated as 1d linear ring
 102         m_has_boundary = count > 1
 103                 && ! detail::equals::equals_point_point(range::front(m_ls), range::back(m_ls));
 104
 105         m_is_initialized = true;
 106     }
 107
 108     Linestring const& m_ls;
 109     mutable bool m_is_initialized;
 110
 111     mutable bool m_has_interior;
 112     mutable bool m_has_boundary;
 113 };
 114
 115 template <typename MultiLinestring>
 116 struct topology_check<MultiLinestring, multi_linestring_tag>
 117 {
 118     static const char interior = '1';
 119     static const char boundary = '0';
 120
 121     topology_check(MultiLinestring const& mls)
 122         : m_mls(mls)
 123         , m_is_initialized(false)
 124     {}
 125
 126     bool has_interior() const
 127     {
 128         init();
 129         return m_has_interior;
 130     }
 131
 132     bool has_boundary() const
 133     {
 134         init();
 135         return m_has_boundary;
 136     }
 137
 138     template <typename Point>
 139     bool check_boundary_point(Point const& point) const
 140     {
 141         init();
 142
 143         if (! m_has_boundary)
 144             return false;
 145
 146         std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point);
 147
 148         return count % 2 != 0; // odd count -> boundary
 149     }
 150
 151     template <typename Visitor>
 152     void for_each_boundary_point(Visitor & visitor) const
 153     {
 154         init();
 155         if (m_has_boundary)
 156         {
 157             for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor);
 158         }
 159     }
 160
 161 private:
 162     void init() const
 163     {
 164         if (m_is_initialized)
 165             return;
 166
 167         m_endpoints.reserve(boost::size(m_mls) * 2);
 168
 169         m_has_interior = false;
 170
 171         typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator;
 172         for ( ls_iterator it = boost::begin(m_mls) ; it != boost::end(m_mls) ; ++it )
 173         {
 174             typename boost::range_reference<MultiLinestring const>::type
 175                 ls = *it;
 176
 177             std::size_t count = boost::size(ls);
 178
 179             if (count > 0)
 180             {
 181                 m_has_interior = true;
 182             }
 183
 184             if (count > 1)
 185             {
 186                 typedef typename boost::range_reference
 187                     <
 188                         typename boost::range_value<MultiLinestring const>::type const
 189                     >::type point_reference;
 190
 191                 point_reference front_pt = range::front(ls);
 192                 point_reference back_pt = range::back(ls);
 193
 194                 // don't store boundaries of linear rings, this doesn't change anything
 195                 if (! equals::equals_point_point(front_pt, back_pt))
 196                 {
 197                     // do not add points containing NaN coordinates
 198                     // because they cannot be reasonably compared, e.g. with MSVC
 199                     // an assertion failure is reported in std::equal_range()
 200                     // NOTE: currently ignoring_counter calling std::equal_range()
 201                     //   is not used anywhere in the code, still it's safer this way
 202                     if (! geometry::has_nan_coordinate(front_pt))
 203                     {
 204                         m_endpoints.push_back(front_pt);
 205                     }
 206                     if (! geometry::has_nan_coordinate(back_pt))
 207                     {
 208                         m_endpoints.push_back(back_pt);
 209                     }
 210                 }
 211             }
 212         }
 213
 214         m_has_boundary = false;
 215
 216         if (! m_endpoints.empty() )
 217         {
 218             std::sort(m_endpoints.begin(), m_endpoints.end(), geometry::less<>());
 219             m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end());
 220         }
 221
 222         m_is_initialized = true;
 223     }
 224
 225     template <typename It, typename Point>
 226     static inline std::size_t count_equal(It first, It last, Point const& point)
 227     {
 228         std::pair<It, It> rng = std::equal_range(first, last, point, geometry::less<>());
 229         return (std::size_t)std::distance(rng.first, rng.second);
 230     }
 231
 232     template <typename It>
 233     static inline bool find_odd_count(It first, It last)
 234     {
 235         interrupting_visitor visitor;
 236         for_each_boundary_point(first, last, visitor);
 237         return visitor.found;
 238     }
 239
 240     struct interrupting_visitor
 241     {
 242         bool found;
 243         interrupting_visitor() : found(false) {}
 244         template <typename Point>
 245         bool apply(Point const&)
 246         {
 247             found = true;
 248             return false;
 249         }
 250     };
 251
 252     template <typename It, typename Visitor>
 253     static void for_each_boundary_point(It first, It last, Visitor& visitor)
 254     {
 255         if ( first == last )
 256             return;
 257
 258         std::size_t count = 1;
 259         It prev = first;
 260         ++first;
 261         for ( ; first != last ; ++first, ++prev )
 262         {
 263             // the end of the equal points subrange
 264             if ( ! equals::equals_point_point(*first, *prev) )
 265             {
 266                 // odd count -> boundary
 267                 if ( count % 2 != 0 )
 268                 {
 269                     if (! visitor.apply(*prev))
 270                     {
 271                         return;
 272                     }
 273                 }
 274
 275                 count = 1;
 276             }
 277             else
 278             {
 279                 ++count;
 280             }
 281         }
 282
 283         // odd count -> boundary
 284         if ( count % 2 != 0 )
 285         {
 286             visitor.apply(*prev);
 287         }
 288     }
 289
 290 private:
 291     MultiLinestring const& m_mls;
 292     mutable bool m_is_initialized;
 293
 294     mutable bool m_has_interior;
 295     mutable bool m_has_boundary;
 296
 297     typedef typename geometry::point_type<MultiLinestring>::type point_type;
 298     mutable std::vector<point_type> m_endpoints;
 299 };
 300
 301 template <typename Ring>
 302 struct topology_check<Ring, ring_tag>
 303 {
 304     static const char interior = '2';
 305     static const char boundary = '1';
 306
 307     topology_check(Ring const&) {}
 308
 309     static bool has_interior() { return true; }
 310     static bool has_boundary() { return true; }
 311 };
 312
 313 template <typename Polygon>
 314 struct topology_check<Polygon, polygon_tag>
 315 {
 316     static const char interior = '2';
 317     static const char boundary = '1';
 318
 319     topology_check(Polygon const&) {}
 320
 321     static bool has_interior() { return true; }
 322     static bool has_boundary() { return true; }
 323 };
 324
 325 template <typename MultiPolygon>
 326 struct topology_check<MultiPolygon, multi_polygon_tag>
 327 {
 328     static const char interior = '2';
 329     static const char boundary = '1';
 330
 331     topology_check(MultiPolygon const&) {}
 332
 333     static bool has_interior() { return true; }
 334     static bool has_boundary() { return true; }
 335     template <typename Point>
 336     static bool check_boundary_point(Point const& ) { return true; }
 337 };
 338
 339 }} // namespace detail::relate
 340 #endif // DOXYGEN_NO_DETAIL
 341
 342 }} // namespace boost::geometry
 343
 344 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP