detail/algorithms/path_intersection.hpp

0001 // Boost.Geometry Index
0002 //
0003 // n-dimensional box-linestring intersection
0004 //
0005 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2020-2023.
0008 // Modifications copyright (c) 2020-2023, Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
0018
0019
0020 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
0021 #include <boost/geometry/algorithms/detail/distance/interface.hpp>
0022
0023 #include <boost/geometry/core/static_assert.hpp>
0024
0025 #include <boost/geometry/index/detail/algorithms/segment_intersection.hpp>
0026
0027 #include <boost/geometry/strategies/default_distance_result.hpp>
0028 #include <boost/geometry/strategies/default_length_result.hpp>
0029
0030 #include <boost/range/begin.hpp>
0031 #include <boost/range/end.hpp>
0032 #include <boost/range/size.hpp>
0033 #include <boost/range/value_type.hpp>
0034
0035 namespace boost { namespace geometry { namespace index { namespace detail {
0036
0037 namespace dispatch {
0038
0039 template <typename Indexable, typename Geometry, typename IndexableTag, typename GeometryTag>
0040 struct path_intersection
0041 {
0042     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0043         "Not implemented for this Geometry or Indexable.",
0044         Indexable, Geometry, IndexableTag, GeometryTag);
0045 };
0046
0047 // TODO: FP type must be used as a relative distance type!
0048 // and default_distance_result can be some user-defined int type
0049 // BUT! This code is experimental and probably won't be released at all
0050 // since more flexible user-defined-nearest predicate should be added instead
0051
0052 template <typename Indexable, typename Segment>
0053 struct path_intersection<Indexable, Segment, box_tag, segment_tag>
0054 {
0055     typedef typename default_distance_result<typename point_type<Segment>::type>::type comparable_distance_type;
0056
0057     static inline bool apply(Indexable const& b, Segment const& segment, comparable_distance_type & comparable_distance)
0058     {
0059         typedef typename point_type<Segment>::type point_type;
0060         point_type p1, p2;
0061         geometry::detail::assign_point_from_index<0>(segment, p1);
0062         geometry::detail::assign_point_from_index<1>(segment, p2);
0063         return index::detail::segment_intersection(b, p1, p2, comparable_distance);
0064     }
0065 };
0066
0067 template <typename Indexable, typename Linestring>
0068 struct path_intersection<Indexable, Linestring, box_tag, linestring_tag>
0069 {
0070     typedef typename default_length_result<Linestring>::type comparable_distance_type;
0071
0072     static inline bool apply(Indexable const& b, Linestring const& path, comparable_distance_type & comparable_distance)
0073     {
0074         typedef typename ::boost::range_value<Linestring>::type point_type;
0075         typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;
0076         typedef typename ::boost::range_size<Linestring>::type size_type;
0077
0078         const size_type count = ::boost::size(path);
0079
0080         if ( count == 2 )
0081         {
0082             return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
0083         }
0084         else if ( 2 < count )
0085         {
0086             const_iterator it0 = ::boost::begin(path);
0087             const_iterator it1 = ::boost::begin(path) + 1;
0088             const_iterator last = ::boost::end(path);
0089
0090             comparable_distance = 0;
0091
0092             for ( ; it1 != last ; ++it0, ++it1 )
0093             {
0094                 typename default_distance_result<point_type, point_type>::type
0095                     dist = geometry::distance(*it0, *it1);
0096
0097                 comparable_distance_type rel_dist;
0098                 if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
0099                 {
0100                     comparable_distance += dist * rel_dist;
0101                     return true;
0102                 }
0103                 else
0104                     comparable_distance += dist;
0105             }
0106         }
0107
0108         return false;
0109     }
0110 };
0111
0112 } // namespace dispatch
0113
0114 template <typename Indexable, typename SegmentOrLinestring>
0115 struct default_path_intersection_distance_type
0116 {
0117     typedef typename dispatch::path_intersection<
0118         Indexable, SegmentOrLinestring,
0119         typename tag<Indexable>::type,
0120         typename tag<SegmentOrLinestring>::type
0121     >::comparable_distance_type type;
0122 };
0123
0124 template <typename Indexable, typename SegmentOrLinestring> inline
0125 bool path_intersection(Indexable const& b,
0126                        SegmentOrLinestring const& path,
0127                        typename default_path_intersection_distance_type<Indexable, SegmentOrLinestring>::type & comparable_distance)
0128 {
0129     // TODO check Indexable and Linestring concepts
0130
0131     return dispatch::path_intersection<
0132             Indexable, SegmentOrLinestring,
0133             typename tag<Indexable>::type,
0134             typename tag<SegmentOrLinestring>::type
0135         >::apply(b, path, comparable_distance);
0136 }
0137
0138 }}}} // namespace boost::geometry::index::detail
0139
0140 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP