ceph/src/boost/libs/geometry/include/boost/geometry/policies/relate/intersection_points.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2016.
   6 // Modifications copyright (c) 2016 Oracle and/or its affiliates.
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Use, modification and distribution is subject to the Boost Software License,
  10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  11 // http://www.boost.org/LICENSE_1_0.txt)
  12
  13 #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
  14 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
  15
  16
  17 #include <algorithm>
  18 #include <string>
  19
  20 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
  21 #include <boost/geometry/core/access.hpp>
  22 #include <boost/geometry/core/assert.hpp>
  23 #include <boost/geometry/strategies/side_info.hpp>
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28 namespace policies { namespace relate
  29 {
  30
  31
  32 /*!
  33 \brief Policy calculating the intersection points themselves
  34  */
  35 template
  36 <
  37     typename ReturnType
  38 >
  39 struct segments_intersection_points
  40 {
  41     typedef ReturnType return_type;
  42
  43     template
  44     <
  45         typename Segment1,
  46         typename Segment2,
  47         typename SegmentIntersectionInfo
  48     >
  49     static inline return_type segments_crosses(side_info const&,
  50                     SegmentIntersectionInfo const& sinfo,
  51                     Segment1 const& s1, Segment2 const& s2)
  52     {
  53         return_type result;
  54         result.count = 1;
  55
  56         bool use_a = true;
  57
  58         // Prefer one segment if one is on or near an endpoint
  59         bool const a_near_end = sinfo.robust_ra.near_end();
  60         bool const b_near_end = sinfo.robust_rb.near_end();
  61         if (a_near_end && ! b_near_end)
  62         {
  63             use_a = true;
  64         }
  65         else if (b_near_end && ! a_near_end)
  66         {
  67             use_a = false;
  68         }
  69         else
  70         {
  71             // Prefer shorter segment
  72             typedef typename SegmentIntersectionInfo::promoted_type ptype;
  73             ptype const len_a = sinfo.comparable_length_a();
  74             ptype const len_b = sinfo.comparable_length_b();
  75             if (len_b < len_a)
  76             {
  77                 use_a = false;
  78             }
  79             // else use_a is true but was already assigned like that
  80         }
  81
  82         if (use_a)
  83         {
  84             sinfo.assign_a(result.intersections[0], s1, s2);
  85         }
  86         else
  87         {
  88             sinfo.assign_b(result.intersections[0], s1, s2);
  89         }
  90
  91         result.fractions[0].assign(sinfo);
  92
  93         return result;
  94     }
  95
  96     template <typename Segment1, typename Segment2, typename Ratio>
  97     static inline return_type segments_collinear(
  98         Segment1 const& a, Segment2 const& b, bool /*opposite*/,
  99         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
 100         Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b,
 101         Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a)
 102     {
 103         return_type result;
 104         unsigned int index = 0, count_a = 0, count_b = 0;
 105         Ratio on_a[2];
 106
 107         // The conditions "index < 2" are necessary for non-robust handling,
 108         // if index would be 2 this indicate an (currently uncatched) error
 109
 110         // IMPORTANT: the order of conditions is different as in direction.hpp
 111         if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment()
 112             && index < 2)
 113         {
 114             //     a1--------->a2
 115             // b1----->b2
 116             //
 117             // ra1 (relative to b) is between 0/1:
 118             // -> First point of A is intersection point
 119             detail::assign_point_from_index<0>(a, result.intersections[index]);
 120             result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b);
 121             on_a[index] = Ratio::zero();
 122             index++;
 123             count_a++;
 124         }
 125         if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment()
 126             && index < 2)
 127         {
 128             // We take the first intersection point of B
 129             // a1--------->a2
 130             //         b1----->b2
 131             // But only if it is not located on A
 132             // a1--------->a2
 133             // b1----->b2      rb_from_wrt_a == 0/1 -> a already taken
 134
 135             detail::assign_point_from_index<0>(b, result.intersections[index]);
 136             result.fractions[index].assign(rb_from_wrt_a, Ratio::zero());
 137             on_a[index] = rb_from_wrt_a;
 138             index++;
 139             count_b++;
 140         }
 141
 142         if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment()
 143             && index < 2)
 144         {
 145             // Similarly, second IP (here a2)
 146             // a1--------->a2
 147             //         b1----->b2
 148             detail::assign_point_from_index<1>(a, result.intersections[index]);
 149             result.fractions[index].assign(Ratio::one(), ra_to_wrt_b);
 150             on_a[index] = Ratio::one();
 151             index++;
 152             count_a++;
 153         }
 154         if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment()
 155             && index < 2)
 156         {
 157             detail::assign_point_from_index<1>(b, result.intersections[index]);
 158             result.fractions[index].assign(rb_to_wrt_a, Ratio::one());
 159             on_a[index] = rb_to_wrt_a;
 160             index++;
 161             count_b++;
 162         }
 163
 164         // TEMPORARY
 165         // If both are from b, and b is reversed w.r.t. a, we swap IP's
 166         // to align them w.r.t. a
 167         // get_turn_info still relies on some order (in some collinear cases)
 168         if (index == 2 && on_a[1] < on_a[0])
 169         {
 170             std::swap(result.fractions[0], result.fractions[1]);
 171             std::swap(result.intersections[0], result.intersections[1]);
 172         }
 173
 174         result.count = index;
 175
 176         return result;
 177     }
 178
 179     static inline return_type disjoint()
 180     {
 181         return return_type();
 182     }
 183     static inline return_type error(std::string const&)
 184     {
 185         return return_type();
 186     }
 187
 188     // Both degenerate
 189     template <typename Segment>
 190     static inline return_type degenerate(Segment const& segment, bool)
 191     {
 192         return_type result;
 193         result.count = 1;
 194         set<0>(result.intersections[0], get<0, 0>(segment));
 195         set<1>(result.intersections[0], get<0, 1>(segment));
 196         return result;
 197     }
 198
 199     // One degenerate
 200     template <typename Segment, typename Ratio>
 201     static inline return_type one_degenerate(Segment const& degenerate_segment,
 202             Ratio const& ratio, bool a_degenerate)
 203     {
 204         return_type result;
 205         result.count = 1;
 206         set<0>(result.intersections[0], get<0, 0>(degenerate_segment));
 207         set<1>(result.intersections[0], get<0, 1>(degenerate_segment));
 208         if (a_degenerate)
 209         {
 210             // IP lies on ratio w.r.t. segment b
 211             result.fractions[0].assign(Ratio::zero(), ratio);
 212         }
 213         else
 214         {
 215             result.fractions[0].assign(ratio, Ratio::zero());
 216         }
 217         return result;
 218     }
 219 };
 220
 221
 222 }} // namespace policies::relate
 223
 224 }} // namespace boost::geometry
 225
 226 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP