ceph/src/boost/boost/geometry/algorithms/detail/relate/boundary_checker.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_BOUNDARY_CHECKER_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
  13
  14 #include <boost/geometry/util/range.hpp>
  15 #include <boost/geometry/algorithms/num_points.hpp>
  16 #include <boost/geometry/algorithms/detail/sub_range.hpp>
  17
  18 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  19
  20 #include <boost/geometry/util/has_nan_coordinate.hpp>
  21
  22 namespace boost { namespace geometry
  23 {
  24
  25 #ifndef DOXYGEN_NO_DETAIL
  26 namespace detail { namespace relate {
  27
  28 enum boundary_query { boundary_front, boundary_back, boundary_any };
  29
  30 template <typename Geometry,
  31           typename Tag = typename geometry::tag<Geometry>::type>
  32 class boundary_checker {};
  33
  34 template <typename Geometry>
  35 class boundary_checker<Geometry, linestring_tag>
  36 {
  37     typedef typename point_type<Geometry>::type point_type;
  38
  39 public:
  40     boundary_checker(Geometry const& g)
  41         : has_boundary( boost::size(g) >= 2
  42                      && !detail::equals::equals_point_point(range::front(g), range::back(g)) )
  43         , geometry(g)
  44     {}
  45
  46     template <boundary_query BoundaryQuery>
  47     bool is_endpoint_boundary(point_type const& pt) const
  48     {
  49         boost::ignore_unused_variable_warning(pt);
  50 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
  51         // may give false positives for INT
  52         BOOST_GEOMETRY_ASSERT( (BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
  53                    && detail::equals::equals_point_point(pt, range::front(geometry))
  54                    || (BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
  55                    && detail::equals::equals_point_point(pt, range::back(geometry)) );
  56 #endif
  57         return has_boundary;
  58     }
  59
  60 private:
  61     bool has_boundary;
  62     Geometry const& geometry;
  63 };
  64
  65 template <typename Geometry>
  66 class boundary_checker<Geometry, multi_linestring_tag>
  67 {
  68     typedef typename point_type<Geometry>::type point_type;
  69
  70 public:
  71     boundary_checker(Geometry const& g)
  72         : is_filled(false), geometry(g)
  73     {}
  74
  75     // First call O(NlogN)
  76     // Each next call O(logN)
  77     template <boundary_query BoundaryQuery>
  78     bool is_endpoint_boundary(point_type const& pt) const
  79     {
  80         typedef typename boost::range_size<Geometry>::type size_type;
  81         size_type multi_count = boost::size(geometry);
  82
  83         if ( multi_count < 1 )
  84             return false;
  85
  86         if ( ! is_filled )
  87         {
  88             //boundary_points.clear();
  89             boundary_points.reserve(multi_count * 2);
  90
  91             typedef typename boost::range_iterator<Geometry const>::type multi_iterator;
  92             for ( multi_iterator it = boost::begin(geometry) ;
  93                   it != boost::end(geometry) ; ++ it )
  94             {
  95                 typename boost::range_reference<Geometry const>::type
  96                     ls = *it;
  97
  98                 // empty or point - no boundary
  99                 if (boost::size(ls) < 2)
 100                 {
 101                     continue;
 102                 }
 103
 104                 typedef typename boost::range_reference
 105                     <
 106                         typename boost::range_value<Geometry const>::type const
 107                     >::type point_reference;
 108
 109                 point_reference front_pt = range::front(ls);
 110                 point_reference back_pt = range::back(ls);
 111
 112                 // linear ring or point - no boundary
 113                 if (! equals::equals_point_point(front_pt, back_pt))
 114                 {
 115                     // do not add points containing NaN coordinates
 116                     // because they cannot be reasonably compared, e.g. with MSVC
 117                     // an assertion failure is reported in std::equal_range()
 118                     if (! geometry::has_nan_coordinate(front_pt))
 119                     {
 120                         boundary_points.push_back(front_pt);
 121                     }
 122                     if (! geometry::has_nan_coordinate(back_pt))
 123                     {
 124                         boundary_points.push_back(back_pt);
 125                     }
 126                 }
 127             }
 128
 129             std::sort(boundary_points.begin(),
 130                       boundary_points.end(),
 131                       geometry::less<point_type>());
 132
 133             is_filled = true;
 134         }
 135
 136         std::size_t equal_points_count
 137             = boost::size(
 138                 std::equal_range(boundary_points.begin(),
 139                                  boundary_points.end(),
 140                                  pt,
 141                                  geometry::less<point_type>())
 142             );
 143
 144         return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0
 145     }
 146
 147 private:
 148     mutable bool is_filled;
 149     // TODO: store references/pointers instead of points?
 150     mutable std::vector<point_type> boundary_points;
 151
 152     Geometry const& geometry;
 153 };
 154
 155 }} // namespace detail::relate
 156 #endif // DOXYGEN_NO_DETAIL
 157
 158 }} // namespace boost::geometry
 159
 160 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP