diff options
Diffstat (limited to 'boost/geometry/strategies/cartesian')
| -rw-r--r-- | boost/geometry/strategies/cartesian/area.hpp | 146 | ||||
| -rw-r--r-- | boost/geometry/strategies/cartesian/area_surveyor.hpp | 131 | ||||
| -rw-r--r-- | boost/geometry/strategies/cartesian/centroid_average.hpp | 4 | ||||
| -rw-r--r-- | boost/geometry/strategies/cartesian/densify.hpp | 133 | ||||
| -rw-r--r-- | boost/geometry/strategies/cartesian/intersection.hpp | 47 |
5 files changed, 329 insertions, 132 deletions
diff --git a/boost/geometry/strategies/cartesian/area.hpp b/boost/geometry/strategies/cartesian/area.hpp new file mode 100644 index 0000000000..27708424c2 --- /dev/null +++ b/boost/geometry/strategies/cartesian/area.hpp @@ -0,0 +1,146 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2012 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2016, 2017. +// Modifications copyright (c) 2016-2017, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, 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 +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_AREA_HPP +#define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_AREA_HPP + + +#include <boost/mpl/if.hpp> + +//#include <boost/geometry/arithmetic/determinant.hpp> +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/strategies/area.hpp> +#include <boost/geometry/util/select_most_precise.hpp> + + +namespace boost { namespace geometry +{ + +namespace strategy { namespace area +{ + +/*! +\brief Cartesian area calculation +\ingroup strategies +\details Calculates cartesian area using the trapezoidal rule +\tparam CalculationType \tparam_calculation + +\qbk{ +[heading See also] +[link geometry.reference.algorithms.area.area_2_with_strategy area (with strategy)] +} + +*/ +template +< + typename CalculationType = void +> +class cartesian +{ +public : + template <typename Geometry> + struct result_type + : strategy::area::detail::result_type + < + Geometry, + CalculationType + > + {}; + + template <typename Geometry> + class state + { + friend class cartesian; + + typedef typename result_type<Geometry>::type return_type; + + public: + inline state() + : sum(0) + { + // Strategy supports only 2D areas + assert_dimension<Geometry, 2>(); + } + + private: + inline return_type area() const + { + return_type const two = 2; + return sum / two; + } + + return_type sum; + }; + + template <typename PointOfSegment, typename Geometry> + static inline void apply(PointOfSegment const& p1, + PointOfSegment const& p2, + state<Geometry>& st) + { + typedef typename state<Geometry>::return_type return_type; + + // Below formulas are equivalent, however the two lower ones + // suffer less from accuracy loss for great values of coordinates. + // See: https://svn.boost.org/trac/boost/ticket/11928 + + // SUM += x2 * y1 - x1 * y2; + // state.sum += detail::determinant<return_type>(p2, p1); + + // SUM += (x2 - x1) * (y2 + y1) + //state.sum += (return_type(get<0>(p2)) - return_type(get<0>(p1))) + // * (return_type(get<1>(p2)) + return_type(get<1>(p1))); + + // SUM += (x1 + x2) * (y1 - y2) + st.sum += (return_type(get<0>(p1)) + return_type(get<0>(p2))) + * (return_type(get<1>(p1)) - return_type(get<1>(p2))); + } + + template <typename Geometry> + static inline typename result_type<Geometry>::type + result(state<Geometry>& st) + { + return st.area(); + } + +}; + +#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS + +namespace services +{ + template <> + struct default_strategy<cartesian_tag> + { + typedef strategy::area::cartesian<> type; + }; + +} // namespace services + +#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS + + +}} // namespace strategy::area + + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_AREA_HPP diff --git a/boost/geometry/strategies/cartesian/area_surveyor.hpp b/boost/geometry/strategies/cartesian/area_surveyor.hpp index b3f19b1b1e..91df31745a 100644 --- a/boost/geometry/strategies/cartesian/area_surveyor.hpp +++ b/boost/geometry/strategies/cartesian/area_surveyor.hpp @@ -3,6 +3,7 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2016, 2017. // Modifications copyright (c) 2016-2017, Oracle and/or its affiliates. @@ -20,133 +21,9 @@ #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_AREA_SURVEYOR_HPP -#include <boost/mpl/if.hpp> - -//#include <boost/geometry/arithmetic/determinant.hpp> -#include <boost/geometry/core/coordinate_type.hpp> -#include <boost/geometry/core/coordinate_dimension.hpp> -#include <boost/geometry/strategies/area.hpp> -#include <boost/geometry/util/select_most_precise.hpp> - - -namespace boost { namespace geometry -{ - -namespace strategy { namespace area -{ - -/*! -\brief Area calculation for cartesian points -\ingroup strategies -\details Calculates area using the Surveyor's formula, a well-known - triangulation algorithm -\tparam PointOfSegment \tparam_segment_point -\tparam CalculationType \tparam_calculation - -\qbk{ -[heading See also] -[link geometry.reference.algorithms.area.area_2_with_strategy area (with strategy)] -} - -*/ -template -< - typename PointOfSegment, - typename CalculationType = void -> -class surveyor -{ -public : - // If user specified a calculation type, use that type, - // whatever it is and whatever the point-type is. - // Else, use the pointtype, but at least double - typedef typename - boost::mpl::if_c - < - boost::is_void<CalculationType>::type::value, - typename select_most_precise - < - typename coordinate_type<PointOfSegment>::type, - double - >::type, - CalculationType - >::type return_type; - - -private : - - class summation - { - friend class surveyor; - - return_type sum; - public : - - inline summation() : sum(return_type()) - { - // Strategy supports only 2D areas - assert_dimension<PointOfSegment, 2>(); - } - inline return_type area() const - { - return_type result = sum; - return_type const two = 2; - result /= two; - return result; - } - }; - -public : - typedef summation state_type; - typedef PointOfSegment segment_point_type; - - static inline void apply(PointOfSegment const& p1, - PointOfSegment const& p2, - summation& state) - { - // Below formulas are equivalent, however the two lower ones - // suffer less from accuracy loss for great values of coordinates. - // See: https://svn.boost.org/trac/boost/ticket/11928 - - // SUM += x2 * y1 - x1 * y2; - // state.sum += detail::determinant<return_type>(p2, p1); - - // SUM += (x2 - x1) * (y2 + y1) - //state.sum += (return_type(get<0>(p2)) - return_type(get<0>(p1))) - // * (return_type(get<1>(p2)) + return_type(get<1>(p1))); - - // SUM += (x1 + x2) * (y1 - y2) - state.sum += (return_type(get<0>(p1)) + return_type(get<0>(p2))) - * (return_type(get<1>(p1)) - return_type(get<1>(p2))); - } - - static inline return_type result(summation const& state) - { - return state.area(); - } - -}; - -#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS - -namespace services -{ - template <typename Point> - struct default_strategy<cartesian_tag, Point> - { - typedef strategy::area::surveyor<Point> type; - }; - -} // namespace services - -#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS - - -}} // namespace strategy::area - - - -}} // namespace boost::geometry +// keep this file for now, for backward compatibility +// functionality-wise, make it equivalent to boost/geometry/strategies/cartesian/area.hpp +#include <boost/geometry/strategies/cartesian/area.hpp> #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_AREA_SURVEYOR_HPP diff --git a/boost/geometry/strategies/cartesian/centroid_average.hpp b/boost/geometry/strategies/cartesian/centroid_average.hpp index c12f6e2024..32f551cf95 100644 --- a/boost/geometry/strategies/cartesian/centroid_average.hpp +++ b/boost/geometry/strategies/cartesian/centroid_average.hpp @@ -3,6 +3,7 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2015. // Modifications copyright (c) 2015 Oracle and/or its affiliates. @@ -23,6 +24,7 @@ #include <cstddef> #include <boost/geometry/algorithms/assign.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> #include <boost/geometry/arithmetic/arithmetic.hpp> #include <boost/geometry/core/coordinate_type.hpp> #include <boost/geometry/core/point_type.hpp> @@ -53,7 +55,7 @@ private : class sum { friend class average; - std::size_t count; + signed_size_type count; PointCentroid centroid; public : diff --git a/boost/geometry/strategies/cartesian/densify.hpp b/boost/geometry/strategies/cartesian/densify.hpp new file mode 100644 index 0000000000..23651637b9 --- /dev/null +++ b/boost/geometry/strategies/cartesian/densify.hpp @@ -0,0 +1,133 @@ +// Boost.Geometry + +// Copyright (c) 2017-2018, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DENSIFY_HPP +#define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DENSIFY_HPP + + +#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> +#include <boost/geometry/arithmetic/arithmetic.hpp> +#include <boost/geometry/arithmetic/dot_product.hpp> +#include <boost/geometry/core/assert.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/strategies/densify.hpp> +#include <boost/geometry/util/math.hpp> +#include <boost/geometry/util/select_most_precise.hpp> + + +namespace boost { namespace geometry +{ + +namespace strategy { namespace densify +{ + + +/*! +\brief Densification of cartesian segment. +\ingroup strategies +\tparam CalculationType \tparam_calculation + +\qbk{ +[heading See also] +[link geometry.reference.algorithms.densify.densify_4_with_strategy densify (with strategy)] +} + */ +template +< + typename CalculationType = void +> +class cartesian +{ +public: + template <typename Point, typename AssignPolicy, typename T> + static inline void apply(Point const& p0, Point const& p1, AssignPolicy & policy, T const& length_threshold) + { + typedef typename AssignPolicy::point_type out_point_t; + typedef typename select_most_precise + < + typename coordinate_type<Point>::type, + typename coordinate_type<out_point_t>::type, + CalculationType + >::type calc_t; + + typedef model::point<calc_t, geometry::dimension<Point>::value, cs::cartesian> calc_point_t; + + calc_point_t cp0, cp1; + geometry::detail::conversion::convert_point_to_point(p0, cp0); + geometry::detail::conversion::convert_point_to_point(p1, cp1); + + // dir01 = xy1 - xy0 + calc_point_t dir01 = cp1; + geometry::subtract_point(dir01, cp0); + calc_t const dot01 = geometry::dot_product(dir01, dir01); + calc_t const len = math::sqrt(dot01); + + BOOST_GEOMETRY_ASSERT(length_threshold > T(0)); + + signed_size_type n = signed_size_type(len / length_threshold); + if (n <= 0) + { + return; + } + + // NOTE: Normalization will not work for integral coordinates + // normalize + //geometry::divide_value(dir01, len); + + calc_t step = len / (n + 1); + + calc_t d = step; + for (signed_size_type i = 0 ; i < n ; ++i, d += step) + { + // pd = xy0 + d * dir01 + calc_point_t pd = dir01; + + // without normalization + geometry::multiply_value(pd, calc_t(i + 1)); + geometry::divide_value(pd, calc_t(n + 1)); + // with normalization + //geometry::multiply_value(pd, d); + + geometry::add_point(pd, cp0); + + // NOTE: Only needed if types calc_point_t and out_point_t are different + // otherwise pd could simply be passed into policy + out_point_t p; + assert_dimension_equal<calc_point_t, out_point_t>(); + geometry::detail::conversion::convert_point_to_point(pd, p); + + policy.apply(p); + } + } +}; + + +#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS +namespace services +{ + +template <> +struct default_strategy<cartesian_tag> +{ + typedef strategy::densify::cartesian<> type; +}; + + +} // namespace services +#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS + + +}} // namespace strategy::densify + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DENSIFY_HPP diff --git a/boost/geometry/strategies/cartesian/intersection.hpp b/boost/geometry/strategies/cartesian/intersection.hpp index 233bb50b64..10fd73ba54 100644 --- a/boost/geometry/strategies/cartesian/intersection.hpp +++ b/boost/geometry/strategies/cartesian/intersection.hpp @@ -1,7 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2014, 2016, 2017. // Modifications copyright (c) 2014-2017, Oracle and/or its affiliates. @@ -33,7 +33,7 @@ #include <boost/geometry/util/promote_integral.hpp> #include <boost/geometry/util/select_calculation_type.hpp> -#include <boost/geometry/strategies/cartesian/area_surveyor.hpp> +#include <boost/geometry/strategies/cartesian/area.hpp> #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp> #include <boost/geometry/strategies/cartesian/envelope_segment.hpp> #include <boost/geometry/strategies/cartesian/point_in_poly_winding.hpp> @@ -103,9 +103,8 @@ struct cartesian_segments template <typename Geometry> struct area_strategy { - typedef area::surveyor + typedef area::cartesian < - typename point_type<Geometry>::type, CalculationType > type; }; @@ -144,6 +143,7 @@ struct cartesian_segments template <typename CoordinateType, typename SegmentRatio> struct segment_intersection_info { + private : typedef typename select_most_precise < CoordinateType, double @@ -198,6 +198,45 @@ struct cartesian_segments >(numerator * dy_promoted / denominator)); } + public : + template <typename Point, typename Segment1, typename Segment2> + void calculate(Point& point, Segment1 const& a, Segment2 const& b) const + { + bool use_a = true; + + // Prefer one segment if one is on or near an endpoint + bool const a_near_end = robust_ra.near_end(); + bool const b_near_end = robust_rb.near_end(); + if (a_near_end && ! b_near_end) + { + use_a = true; + } + else if (b_near_end && ! a_near_end) + { + use_a = false; + } + else + { + // Prefer shorter segment + promoted_type const len_a = comparable_length_a(); + promoted_type const len_b = comparable_length_b(); + if (len_b < len_a) + { + use_a = false; + } + // else use_a is true but was already assigned like that + } + + if (use_a) + { + assign_a(point, a, b); + } + else + { + assign_b(point, a, b); + } + } + CoordinateType dx_a, dy_a; CoordinateType dx_b, dy_b; SegmentRatio robust_ra; |