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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014, Oracle and/or its affiliates.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
  13
  14 #include <boost/geometry/util/range.hpp>
  15
  16 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  17 #include <boost/geometry/policies/compare.hpp>
  18
  19 #include <boost/geometry/util/has_nan_coordinate.hpp>
  20
  21 namespace boost { namespace geometry {
  22
  23 #ifndef DOXYGEN_NO_DETAIL
  24 namespace detail { namespace relate {
  25
  26 // TODO: change the name for e.g. something with the word "exterior"
  27
  28 template <typename Geometry,
  29           typename Tag = typename geometry::tag<Geometry>::type>
  30 struct topology_check
  31     : not_implemented<Tag>
  32 {};
  33
  34 //template <typename Point>
  35 //struct topology_check<Point, point_tag>
  36 //{
  37 //    static const char interior = '0';
  38 //    static const char boundary = 'F';
  39 //
  40 //    static const bool has_interior = true;
  41 //    static const bool has_boundary = false;
  42 //
  43 //    topology_check(Point const&) {}
  44 //    template <typename IgnoreBoundaryPoint>
  45 //    topology_check(Point const&, IgnoreBoundaryPoint const&) {}
  46 //};
  47
  48 template <typename Linestring>
  49 struct topology_check<Linestring, linestring_tag>
  50 {
  51     static const char interior = '1';
  52     static const char boundary = '0';
  53
  54     bool has_interior;
  55     bool has_boundary;
  56
  57     topology_check(Linestring const& ls)
  58     {
  59         init(ls, 0); /*dummy param*/
  60     }
  61
  62     template <typename IgnoreBoundaryPoint>
  63     topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp)
  64     {
  65         init(ls, ibp); /*dummy param, won't be used*/
  66     }
  67
  68     // Even if some point is on the boundary, if the Linestring has the boundary,
  69     // there will be second boundary point different than IgnoreBoundaryPoint
  70     template <typename IgnoreBoundaryPoint>
  71     void init(Linestring const& ls, IgnoreBoundaryPoint const&)
  72     {
  73         std::size_t count = boost::size(ls);
  74         has_interior = count > 0;
  75         // NOTE: Linestring with all points equal is treated as 1d linear ring
  76         has_boundary = count > 1
  77                     && ! detail::equals::equals_point_point(range::front(ls), range::back(ls));
  78     }
  79 };
  80
  81 template <typename MultiLinestring>
  82 struct topology_check<MultiLinestring, multi_linestring_tag>
  83 {
  84     static const char interior = '1';
  85     static const char boundary = '0';
  86
  87     bool has_interior;
  88     bool has_boundary;
  89
  90     topology_check(MultiLinestring const& mls)
  91     {
  92         init(mls, not_ignoring_counter());
  93     }
  94
  95     template <typename IgnoreBoundaryPoint>
  96     topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp)
  97     {
  98         init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp));
  99     }
 100
 101     template <typename OddCounter>
 102     void init(MultiLinestring const& mls, OddCounter const& odd_counter)
 103     {
 104         typedef typename geometry::point_type<MultiLinestring>::type point_type;
 105         std::vector<point_type> endpoints;
 106         endpoints.reserve(boost::size(mls) * 2);
 107
 108         typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator;
 109         for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it )
 110         {
 111             typename boost::range_reference<MultiLinestring const>::type
 112                 ls = *it;
 113
 114             std::size_t count = boost::size(ls);
 115
 116             if (count > 0)
 117             {
 118                 has_interior = true;
 119             }
 120
 121             if (count > 1)
 122             {
 123                 typedef typename boost::range_reference
 124                     <
 125                         typename boost::range_value<MultiLinestring const>::type const
 126                     >::type point_reference;
 127
 128                 point_reference front_pt = range::front(ls);
 129                 point_reference back_pt = range::back(ls);
 130
 131                 // don't store boundaries of linear rings, this doesn't change anything
 132                 if (! equals::equals_point_point(front_pt, back_pt))
 133                 {
 134                     // do not add points containing NaN coordinates
 135                     // because they cannot be reasonably compared, e.g. with MSVC
 136                     // an assertion failure is reported in std::equal_range()
 137                     // NOTE: currently ignoring_counter calling std::equal_range()
 138                     //   is not used anywhere in the code, still it's safer this way
 139                     if (! geometry::has_nan_coordinate(front_pt))
 140                     {
 141                         endpoints.push_back(front_pt);
 142                     }
 143                     if (! geometry::has_nan_coordinate(back_pt))
 144                     {
 145                         endpoints.push_back(back_pt);
 146                     }
 147                 }
 148             }
 149         }
 150
 151         has_boundary = false;
 152
 153         if ( !endpoints.empty() )
 154         {
 155             std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>());
 156             has_boundary = odd_counter(endpoints.begin(), endpoints.end());
 157         }
 158     }
 159
 160     struct not_ignoring_counter
 161     {
 162         template <typename It>
 163         bool operator()(It first, It last) const
 164         {
 165             return find_odd_count(first, last);
 166         }
 167     };
 168
 169     template <typename Point>
 170     struct ignoring_counter
 171     {
 172         ignoring_counter(Point const& pt) : m_pt(pt) {}
 173
 174         template <typename It>
 175         bool operator()(It first, It last) const
 176         {
 177             typedef typename std::iterator_traits<It>::value_type point_type;
 178
 179             std::pair<It, It> ignore_range
 180                               = std::equal_range(first, last, m_pt,
 181                                                  geometry::less<point_type>());
 182
 183             if ( find_odd_count(first, ignore_range.first) )
 184                 return true;
 185
 186             return find_odd_count(ignore_range.second, last);
 187         }
 188
 189         Point const& m_pt;
 190     };
 191
 192     template <typename It>
 193     static inline bool find_odd_count(It first, It last)
 194     {
 195         if ( first == last )
 196             return false;
 197
 198         std::size_t count = 1;
 199         It prev = first;
 200         ++first;
 201         for ( ; first != last ; ++first, ++prev )
 202         {
 203             // the end of the equal points subrange
 204             if ( ! equals::equals_point_point(*first, *prev) )
 205             {
 206                 if ( count % 2 != 0 )
 207                     return true;
 208
 209                 count = 1;
 210             }
 211             else
 212             {
 213                 ++count;
 214             }
 215         }
 216
 217         return count % 2 != 0;
 218     }
 219 };
 220
 221 template <typename Ring>
 222 struct topology_check<Ring, ring_tag>
 223 {
 224     static const char interior = '2';
 225     static const char boundary = '1';
 226     static const bool has_interior = true;
 227     static const bool has_boundary = true;
 228
 229     topology_check(Ring const&) {}
 230     template <typename P>
 231     topology_check(Ring const&, P const&) {}
 232 };
 233
 234 template <typename Polygon>
 235 struct topology_check<Polygon, polygon_tag>
 236 {
 237     static const char interior = '2';
 238     static const char boundary = '1';
 239     static const bool has_interior = true;
 240     static const bool has_boundary = true;
 241
 242     topology_check(Polygon const&) {}
 243     template <typename P>
 244     topology_check(Polygon const&, P const&) {}
 245 };
 246
 247 template <typename MultiPolygon>
 248 struct topology_check<MultiPolygon, multi_polygon_tag>
 249 {
 250     static const char interior = '2';
 251     static const char boundary = '1';
 252     static const bool has_interior = true;
 253     static const bool has_boundary = true;
 254
 255     topology_check(MultiPolygon const&) {}
 256     template <typename P>
 257     topology_check(MultiPolygon const&, P const&) {}
 258 };
 259
 260 }} // namespace detail::relate
 261 #endif // DOXYGEN_NO_DETAIL
 262
 263 }} // namespace boost::geometry
 264
 265 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP