ceph/src/boost/boost/geometry/index/detail/algorithms/path_intersection.hpp

   1 // Boost.Geometry Index
   2 //
   3 // n-dimensional box-linestring intersection
   4 //
   5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // This file was modified by Oracle on 2020.
   8 // Modifications copyright (c) 2020 Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10 //
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
  17
  18
  19 #include <boost/geometry/core/static_assert.hpp>
  20
  21 #include <boost/geometry/index/detail/algorithms/segment_intersection.hpp>
  22
  23 #include <boost/geometry/strategies/default_length_result.hpp>
  24
  25
  26 namespace boost { namespace geometry { namespace index { namespace detail {
  27
  28 namespace dispatch {
  29
  30 template <typename Indexable, typename Geometry, typename IndexableTag, typename GeometryTag>
  31 struct path_intersection
  32 {
  33     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
  34         "Not implemented for this Geometry or Indexable.",
  35         Indexable, Geometry, IndexableTag, GeometryTag);
  36 };
  37
  38 // TODO: FP type must be used as a relative distance type!
  39 // and default_distance_result can be some user-defined int type
  40 // BUT! This code is experimental and probably won't be released at all
  41 // since more flexible user-defined-nearest predicate should be added instead
  42
  43 template <typename Indexable, typename Segment>
  44 struct path_intersection<Indexable, Segment, box_tag, segment_tag>
  45 {
  46     typedef typename default_distance_result<typename point_type<Segment>::type>::type comparable_distance_type;
  47
  48     static inline bool apply(Indexable const& b, Segment const& segment, comparable_distance_type & comparable_distance)
  49     {
  50         typedef typename point_type<Segment>::type point_type;
  51         point_type p1, p2;
  52         geometry::detail::assign_point_from_index<0>(segment, p1);
  53         geometry::detail::assign_point_from_index<1>(segment, p2);
  54         return index::detail::segment_intersection(b, p1, p2, comparable_distance);
  55     }
  56 };
  57
  58 template <typename Indexable, typename Linestring>
  59 struct path_intersection<Indexable, Linestring, box_tag, linestring_tag>
  60 {
  61     typedef typename default_length_result<Linestring>::type comparable_distance_type;
  62
  63     static inline bool apply(Indexable const& b, Linestring const& path, comparable_distance_type & comparable_distance)
  64     {
  65         typedef typename ::boost::range_value<Linestring>::type point_type;
  66         typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;
  67         typedef typename ::boost::range_size<Linestring>::type size_type;
  68
  69         const size_type count = ::boost::size(path);
  70
  71         if ( count == 2 )
  72         {
  73             return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
  74         }
  75         else if ( 2 < count )
  76         {
  77             const_iterator it0 = ::boost::begin(path);
  78             const_iterator it1 = ::boost::begin(path) + 1;
  79             const_iterator last = ::boost::end(path);
  80
  81             comparable_distance = 0;
  82
  83             for ( ; it1 != last ; ++it0, ++it1 )
  84             {
  85                 typename default_distance_result<point_type, point_type>::type
  86                     dist = geometry::distance(*it0, *it1);
  87
  88                 comparable_distance_type rel_dist;
  89                 if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
  90                 {
  91                     comparable_distance += dist * rel_dist;
  92                     return true;
  93                 }
  94                 else
  95                     comparable_distance += dist;
  96             }
  97         }
  98
  99         return false;
 100     }
 101 };
 102
 103 } // namespace dispatch
 104
 105 template <typename Indexable, typename SegmentOrLinestring>
 106 struct default_path_intersection_distance_type
 107 {
 108     typedef typename dispatch::path_intersection<
 109         Indexable, SegmentOrLinestring,
 110         typename tag<Indexable>::type,
 111         typename tag<SegmentOrLinestring>::type
 112     >::comparable_distance_type type;
 113 };
 114
 115 template <typename Indexable, typename SegmentOrLinestring> inline
 116 bool path_intersection(Indexable const& b,
 117                        SegmentOrLinestring const& path,
 118                        typename default_path_intersection_distance_type<Indexable, SegmentOrLinestring>::type & comparable_distance)
 119 {
 120     // TODO check Indexable and Linestring concepts
 121
 122     return dispatch::path_intersection<
 123             Indexable, SegmentOrLinestring,
 124             typename tag<Indexable>::type,
 125             typename tag<SegmentOrLinestring>::type
 126         >::apply(b, path, comparable_distance);
 127 }
 128
 129 }}}} // namespace boost::geometry::index::detail
 130
 131 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP