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

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