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 // 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_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
  13
  14
  15 #include <boost/geometry/index/detail/algorithms/segment_intersection.hpp>
  16
  17 #include <boost/geometry/strategies/default_length_result.hpp>
  18
  19
  20 namespace boost { namespace geometry { namespace index { namespace detail {
  21
  22 namespace dispatch {
  23
  24 template <typename Indexable, typename Geometry, typename IndexableTag, typename GeometryTag>
  25 struct path_intersection
  26 {
  27     BOOST_MPL_ASSERT_MSG((false), NOT_IMPLEMENTED_FOR_THIS_GEOMETRY_OR_INDEXABLE, (path_intersection));
  28 };
  29
  30 // TODO: FP type must be used as a relative distance type!
  31 // and default_distance_result can be some user-defined int type
  32 // BUT! This code is experimental and probably won't be released at all
  33 // since more flexible user-defined-nearest predicate should be added instead
  34
  35 template <typename Indexable, typename Segment>
  36 struct path_intersection<Indexable, Segment, box_tag, segment_tag>
  37 {
  38     typedef typename default_distance_result<typename point_type<Segment>::type>::type comparable_distance_type;
  39
  40     static inline bool apply(Indexable const& b, Segment const& segment, comparable_distance_type & comparable_distance)
  41     {
  42         typedef typename point_type<Segment>::type point_type;
  43         point_type p1, p2;
  44         geometry::detail::assign_point_from_index<0>(segment, p1);
  45         geometry::detail::assign_point_from_index<1>(segment, p2);
  46         return index::detail::segment_intersection(b, p1, p2, comparable_distance);
  47     }
  48 };
  49
  50 template <typename Indexable, typename Linestring>
  51 struct path_intersection<Indexable, Linestring, box_tag, linestring_tag>
  52 {
  53     typedef typename default_length_result<Linestring>::type comparable_distance_type;
  54
  55     static inline bool apply(Indexable const& b, Linestring const& path, comparable_distance_type & comparable_distance)
  56     {
  57         typedef typename ::boost::range_value<Linestring>::type point_type;
  58         typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;
  59         typedef typename ::boost::range_size<Linestring>::type size_type;
  60
  61         const size_type count = ::boost::size(path);
  62
  63         if ( count == 2 )
  64         {
  65             return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
  66         }
  67         else if ( 2 < count )
  68         {
  69             const_iterator it0 = ::boost::begin(path);
  70             const_iterator it1 = ::boost::begin(path) + 1;
  71             const_iterator last = ::boost::end(path);
  72
  73             comparable_distance = 0;
  74
  75             for ( ; it1 != last ; ++it0, ++it1 )
  76             {
  77                 typename default_distance_result<point_type, point_type>::type
  78                     dist = geometry::distance(*it0, *it1);
  79
  80                 comparable_distance_type rel_dist;
  81                 if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
  82                 {
  83                     comparable_distance += dist * rel_dist;
  84                     return true;
  85                 }
  86                 else
  87                     comparable_distance += dist;
  88             }
  89         }
  90
  91         return false;
  92     }
  93 };
  94
  95 } // namespace dispatch
  96
  97 template <typename Indexable, typename SegmentOrLinestring>
  98 struct default_path_intersection_distance_type
  99 {
 100     typedef typename dispatch::path_intersection<
 101         Indexable, SegmentOrLinestring,
 102         typename tag<Indexable>::type,
 103         typename tag<SegmentOrLinestring>::type
 104     >::comparable_distance_type type;
 105 };
 106
 107 template <typename Indexable, typename SegmentOrLinestring> inline
 108 bool path_intersection(Indexable const& b,
 109                        SegmentOrLinestring const& path,
 110                        typename default_path_intersection_distance_type<Indexable, SegmentOrLinestring>::type & comparable_distance)
 111 {
 112     // TODO check Indexable and Linestring concepts
 113
 114     return dispatch::path_intersection<
 115             Indexable, SegmentOrLinestring,
 116             typename tag<Indexable>::type,
 117             typename tag<SegmentOrLinestring>::type
 118         >::apply(b, path, comparable_distance);
 119 }
 120
 121 }}}} // namespace boost::geometry::index::detail
 122
 123 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP