ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP
  11
  12
  13 #include <boost/geometry/arithmetic/determinant.hpp>
  14 #include <boost/geometry/util/math.hpp>
  15 #include <boost/geometry/strategies/buffer.hpp>
  16 #include <boost/geometry/algorithms/detail/buffer/parallel_continue.hpp>
  17
  18 namespace boost { namespace geometry
  19 {
  20
  21
  22 #ifndef DOXYGEN_NO_DETAIL
  23 namespace detail { namespace buffer
  24 {
  25
  26
  27 // TODO: once change this to proper strategy
  28 // It is different from current segment intersection because these are not segments but lines
  29 // If we have the Line concept, we can create a strategy
  30 // Assumes a convex corner
  31 struct line_line_intersection
  32 {
  33
  34     template <typename Point>
  35     static inline strategy::buffer::join_selector apply(Point const& pi, Point const& pj,
  36         Point const& qi, Point const& qj, Point& ip)
  37     {
  38         // See http://mathworld.wolfram.com/Line-LineIntersection.html
  39         typedef typename coordinate_type<Point>::type coordinate_type;
  40
  41         coordinate_type const denominator
  42             = determinant<coordinate_type>(get<0>(pi) - get<0>(pj),
  43                 get<1>(pi) - get<1>(pj),
  44                 get<0>(qi) - get<0>(qj),
  45                 get<1>(qi) - get<1>(qj));
  46
  47         // Even if the corner was checked before (so it is convex now), that
  48         // was done on the original geometry. This function runs on the buffered
  49         // geometries, where sides are generated and might be slightly off. In
  50         // Floating Point, that slightly might just exceed the limit and we have
  51         // to check it again.
  52
  53         // For round joins, it will not be used at all.
  54         // For miter joints, there is a miter limit
  55         // If segments are parallel/collinear we must be distinguish two cases:
  56         // they continue each other, or they form a spike
  57         if (math::equals(denominator, coordinate_type()))
  58         {
  59             return parallel_continue(get<0>(qj) - get<0>(qi),
  60                                 get<1>(qj) - get<1>(qi),
  61                                 get<0>(pj) - get<0>(pi),
  62                                 get<1>(pj) - get<1>(pi))
  63                 ? strategy::buffer::join_continue
  64                 : strategy::buffer::join_spike
  65                 ;
  66         }
  67
  68         coordinate_type d1 = determinant<coordinate_type>(get<0>(pi), get<1>(pi), get<0>(pj), get<1>(pj));
  69         coordinate_type d2 = determinant<coordinate_type>(get<0>(qi), get<1>(qi), get<0>(qj), get<1>(qj));
  70
  71         double const multiplier = 1.0 / denominator;
  72
  73         set<0>(ip, determinant<coordinate_type>(d1, get<0>(pi) - get<0>(pj), d2, get<0>(qi) - get<0>(qj)) * multiplier);
  74         set<1>(ip, determinant<coordinate_type>(d1, get<1>(pi) - get<1>(pj), d2, get<1>(qi) - get<1>(qj)) * multiplier);
  75
  76         return strategy::buffer::join_convex;
  77     }
  78 };
  79
  80
  81 }} // namespace detail::buffer
  82 #endif // DOXYGEN_NO_DETAIL
  83
  84
  85 }} // namespace boost::geometry
  86
  87
  88 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP