diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp | 41 |
1 files changed, 19 insertions, 22 deletions
diff --git a/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp b/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp index 618afe5fba..11f1c689a5 100644 --- a/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp +++ b/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2012-2019 Barend Gehrels, Amsterdam, the Netherlands. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -10,7 +10,6 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP -#include <boost/geometry/arithmetic/determinant.hpp> #include <boost/geometry/util/math.hpp> #include <boost/geometry/strategies/buffer.hpp> #include <boost/geometry/algorithms/detail/buffer/parallel_continue.hpp> @@ -35,14 +34,19 @@ struct line_line_intersection static inline strategy::buffer::join_selector apply(Point const& pi, Point const& pj, Point const& qi, Point const& qj, Point& ip) { - // See http://mathworld.wolfram.com/Line-LineIntersection.html - typedef typename coordinate_type<Point>::type coordinate_type; + typedef typename coordinate_type<Point>::type ct; - coordinate_type const denominator - = determinant<coordinate_type>(get<0>(pi) - get<0>(pj), - get<1>(pi) - get<1>(pj), - get<0>(qi) - get<0>(qj), - get<1>(qi) - get<1>(qj)); + // Construct lines in general form (ax + by + c = 0), + // (will be replaced by a general_form structure in a next PR) + ct const pa = get<1>(pi) - get<1>(pj); + ct const pb = get<0>(pj) - get<0>(pi); + ct const pc = -pa * get<0>(pi) - pb * get<1>(pi); + + ct const qa = get<1>(qi) - get<1>(qj); + ct const qb = get<0>(qj) - get<0>(qi); + ct const qc = -qa * get<0>(qi) - qb * get<1>(qi); + + ct const denominator = pb * qa - pa * qb; // Even if the corner was checked before (so it is convex now), that // was done on the original geometry. This function runs on the buffered @@ -51,27 +55,20 @@ struct line_line_intersection // to check it again. // For round joins, it will not be used at all. - // For miter joints, there is a miter limit + // For miter joins, there is a miter limit // If segments are parallel/collinear we must be distinguish two cases: // they continue each other, or they form a spike - if (math::equals(denominator, coordinate_type())) + ct const zero = ct(); + if (math::equals(denominator, zero)) { - return parallel_continue(get<0>(qj) - get<0>(qi), - get<1>(qj) - get<1>(qi), - get<0>(pj) - get<0>(pi), - get<1>(pj) - get<1>(pi)) + return parallel_continue(qb, -qa, pb, -pa) ? strategy::buffer::join_continue : strategy::buffer::join_spike ; } - coordinate_type d1 = determinant<coordinate_type>(get<0>(pi), get<1>(pi), get<0>(pj), get<1>(pj)); - coordinate_type d2 = determinant<coordinate_type>(get<0>(qi), get<1>(qi), get<0>(qj), get<1>(qj)); - - double const multiplier = 1.0 / denominator; - - set<0>(ip, determinant<coordinate_type>(d1, get<0>(pi) - get<0>(pj), d2, get<0>(qi) - get<0>(qj)) * multiplier); - set<1>(ip, determinant<coordinate_type>(d1, get<1>(pi) - get<1>(pj), d2, get<1>(qi) - get<1>(qj)) * multiplier); + set<0>(ip, (pc * qb - pb * qc) / denominator); + set<1>(ip, (pa * qc - pc * qa) / denominator); return strategy::buffer::join_convex; } |