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

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