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