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> applyboost::geometry::detail::buffer::line_line_intersection35 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 89