diff options
| author | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:33:54 +0900 |
|---|---|---|
| committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:36:09 +0900 |
| commit | d9ec475d945d3035377a0d89ed42e382d8988891 (patch) | |
| tree | 34aff2cee4b209906243ab5499d61f3edee2982f /boost/geometry | |
| parent | 71d216b90256936a9638f325af9bc69d720e75de (diff) | |
| download | boost-d9ec475d945d3035377a0d89ed42e382d8988891.tar.gz boost-d9ec475d945d3035377a0d89ed42e382d8988891.tar.bz2 boost-d9ec475d945d3035377a0d89ed42e382d8988891.zip | |
Imported Upstream version 1.60.0
Change-Id: Ie709530d6d5841088ceaba025cbe175a4ef43050
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry')
67 files changed, 1702 insertions, 309 deletions
diff --git a/boost/geometry/algorithms/centroid.hpp b/boost/geometry/algorithms/centroid.hpp index 1b99ab2ef3..8ef017a3f1 100644 --- a/boost/geometry/algorithms/centroid.hpp +++ b/boost/geometry/algorithms/centroid.hpp @@ -220,19 +220,22 @@ struct centroid_range_state iterator_type it = boost::begin(view); iterator_type end = boost::end(view); - typename PointTransformer::result_type - previous_pt = transformer.apply(*it); - - for ( ++it ; it != end ; ++it) + if (it != end) { typename PointTransformer::result_type - pt = transformer.apply(*it); + previous_pt = transformer.apply(*it); - strategy.apply(static_cast<point_type const&>(previous_pt), - static_cast<point_type const&>(pt), - state); - - previous_pt = pt; + for ( ++it ; it != end ; ++it) + { + typename PointTransformer::result_type + pt = transformer.apply(*it); + + strategy.apply(static_cast<point_type const&>(previous_pt), + static_cast<point_type const&>(pt), + state); + + previous_pt = pt; + } } } }; diff --git a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp index b25bcc7fb5..606726f338 100644 --- a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp @@ -31,6 +31,7 @@ #include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp> #include <boost/geometry/algorithms/detail/buffer/parallel_continue.hpp> +#include <boost/geometry/algorithms/assign.hpp> #include <boost/geometry/algorithms/num_interior_rings.hpp> #include <boost/geometry/algorithms/simplify.hpp> @@ -135,6 +136,7 @@ struct buffer_range RobustPolicy const& ) { output_point_type intersection_point; + geometry::assign_zero(intersection_point); strategy::buffer::join_selector join = get_join_type(penultimate_input, previous_input, input); @@ -392,7 +394,7 @@ inline void buffer_point(Point const& point, Collection& collection, point_strategy.apply(point, distance_strategy, range_out); collection.add_piece(strategy::buffer::buffered_point, range_out, false); collection.set_piece_center(point); - collection.finish_ring(); + collection.finish_ring(strategy::buffer::result_normal); } @@ -680,7 +682,7 @@ struct buffer_inserter<linestring_tag, Linestring, Polygon> distance, side_strategy, join_strategy, end_strategy, robust_policy, first_p1); } - collection.finish_ring(); + collection.finish_ring(code); } if (code == strategy::buffer::result_no_output && n >= 1) { @@ -740,12 +742,7 @@ private: join_strategy, end_strategy, point_strategy, robust_policy); - if (code == strategy::buffer::result_error_numerical) - { - collection.abort_ring(); - return; - } - collection.finish_ring(is_interior); + collection.finish_ring(code, is_interior); } } @@ -805,14 +802,8 @@ public: join_strategy, end_strategy, point_strategy, robust_policy); - if (code == strategy::buffer::result_error_numerical) - { - collection.abort_ring(); - } - else - { - collection.finish_ring(false, geometry::num_interior_rings(polygon) > 0u); - } + collection.finish_ring(code, false, + geometry::num_interior_rings(polygon) > 0u); } apply_interior_rings(interior_rings(polygon), diff --git a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp index 545d89cb9b..b580cf5b9b 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp @@ -860,8 +860,15 @@ struct buffered_piece_collection m_robust_policy); } - inline void finish_ring(bool is_interior = false, bool has_interiors = false) + inline void finish_ring(strategy::buffer::result_code code, + bool is_interior = false, bool has_interiors = false) { + if (code == strategy::buffer::result_error_numerical) + { + abort_ring(); + return; + } + if (m_first_piece_index == -1) { return; @@ -1188,7 +1195,7 @@ struct buffered_piece_collection typename cs_tag<Ring>::type >::type side_strategy_type; - enrich_intersection_points<false, false>(m_turns, + enrich_intersection_points<false, false, overlay_union>(m_turns, detail::overlay::operation_union, offsetted_rings, offsetted_rings, m_robust_policy, side_strategy_type()); diff --git a/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp b/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp index 19c91544ac..29a618b923 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp @@ -96,36 +96,36 @@ namespace traits template <typename Ring> -struct tag<detail::buffer::buffered_ring<Ring> > +struct tag<geometry::detail::buffer::buffered_ring<Ring> > { typedef ring_tag type; }; template <typename Ring> -struct point_order<detail::buffer::buffered_ring<Ring> > +struct point_order<geometry::detail::buffer::buffered_ring<Ring> > { static const order_selector value = geometry::point_order<Ring>::value; }; template <typename Ring> -struct closure<detail::buffer::buffered_ring<Ring> > +struct closure<geometry::detail::buffer::buffered_ring<Ring> > { static const closure_selector value = geometry::closure<Ring>::value; }; template <typename Ring> -struct point_type<detail::buffer::buffered_ring_collection<Ring> > +struct point_type<geometry::detail::buffer::buffered_ring_collection<Ring> > { typedef typename geometry::point_type<Ring>::type type; }; template <typename Ring> -struct tag<detail::buffer::buffered_ring_collection<Ring> > +struct tag<geometry::detail::buffer::buffered_ring_collection<Ring> > { - typedef detail::buffer::buffered_ring_collection_tag type; + typedef geometry::detail::buffer::buffered_ring_collection_tag type; }; diff --git a/boost/geometry/algorithms/detail/disjoint/box_box.hpp b/boost/geometry/algorithms/detail/disjoint/box_box.hpp index 84671f257e..6074af982b 100644 --- a/boost/geometry/algorithms/detail/disjoint/box_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/box_box.hpp @@ -1,12 +1,12 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. -// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013-2014. -// Modifications copyright (c) 2013-2014, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013-2015. +// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -36,7 +36,6 @@ namespace boost { namespace geometry namespace detail { namespace disjoint { - template < typename Box1, typename Box2, diff --git a/boost/geometry/algorithms/detail/disjoint/point_box.hpp b/boost/geometry/algorithms/detail/disjoint/point_box.hpp index 12213db056..73b7b70990 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_box.hpp @@ -1,12 +1,12 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. -// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland -// This file was modified by Oracle on 2013-2014. -// Modifications copyright (c) 2013-2014, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013-2015. +// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -29,7 +29,6 @@ #include <boost/geometry/algorithms/dispatch/disjoint.hpp> - namespace boost { namespace geometry { diff --git a/boost/geometry/algorithms/detail/distance/segment_to_box.hpp b/boost/geometry/algorithms/detail/distance/segment_to_box.hpp index 783699ee0a..fa95152476 100644 --- a/boost/geometry/algorithms/detail/distance/segment_to_box.hpp +++ b/boost/geometry/algorithms/detail/distance/segment_to_box.hpp @@ -562,11 +562,12 @@ private: // assert that the segment has non-negative slope BOOST_GEOMETRY_ASSERT( ( math::equals(geometry::get<0>(p0), geometry::get<0>(p1)) - && geometry::get<1>(p0) < geometry::get<1>(p1)) - || - ( geometry::get<0>(p0) < geometry::get<0>(p1) - && geometry::get<1>(p0) <= geometry::get<1>(p1) ) - ); + && geometry::get<1>(p0) < geometry::get<1>(p1)) + || + ( geometry::get<0>(p0) < geometry::get<0>(p1) + && geometry::get<1>(p0) <= geometry::get<1>(p1) ) + || geometry::has_nan_coordinate(p0) + || geometry::has_nan_coordinate(p1)); ReturnType result(0); @@ -617,8 +618,10 @@ private: typedef compare_less_equal<ReturnType, false> greater_equal; // assert that the segment has negative slope - BOOST_GEOMETRY_ASSERT( geometry::get<0>(p0) < geometry::get<0>(p1) - && geometry::get<1>(p0) > geometry::get<1>(p1) ); + BOOST_GEOMETRY_ASSERT( ( geometry::get<0>(p0) < geometry::get<0>(p1) + && geometry::get<1>(p0) > geometry::get<1>(p1) ) + || geometry::has_nan_coordinate(p0) + || geometry::has_nan_coordinate(p1) ); ReturnType result(0); @@ -665,7 +668,9 @@ public: PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) { - BOOST_GEOMETRY_ASSERT( geometry::less<SegmentPoint>()(p0, p1) ); + BOOST_GEOMETRY_ASSERT( geometry::less<SegmentPoint>()(p0, p1) + || geometry::has_nan_coordinate(p0) + || geometry::has_nan_coordinate(p1) ); if (geometry::get<0>(p0) < geometry::get<0>(p1) && geometry::get<1>(p0) > geometry::get<1>(p1)) diff --git a/boost/geometry/algorithms/detail/expand_by_epsilon.hpp b/boost/geometry/algorithms/detail/expand_by_epsilon.hpp new file mode 100644 index 0000000000..7af08ee371 --- /dev/null +++ b/boost/geometry/algorithms/detail/expand_by_epsilon.hpp @@ -0,0 +1,113 @@ +// Boost.Geometry + +// Copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Distributed under 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_ALGORITHMS_DETAIL_EXPAND_EXPAND_BY_EPSILON_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_EXPAND_BY_EPSILON_HPP + +#include <cstddef> +#include <algorithm> + +#include <boost/type_traits/is_floating_point.hpp> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_type.hpp> + +#include <boost/geometry/util/math.hpp> + +#include <boost/geometry/views/detail/indexed_point_view.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace expand +{ + +template +< + typename Point, + template <typename> class PlusOrMinus, + std::size_t I = 0, + std::size_t D = dimension<Point>::value, + bool Enable = boost::is_floating_point + < + typename coordinate_type<Point>::type + >::value +> +struct corner_by_epsilon +{ + static inline void apply(Point & point) + { + typedef typename coordinate_type<Point>::type coord_type; + coord_type const coord = get<I>(point); + coord_type const eps = math::scaled_epsilon(coord); + + set<I>(point, PlusOrMinus<coord_type>()(coord, eps)); + + corner_by_epsilon<Point, PlusOrMinus, I+1>::apply(point); + } +}; + +template +< + typename Point, + template <typename> class PlusOrMinus, + std::size_t I, + std::size_t D +> +struct corner_by_epsilon<Point, PlusOrMinus, I, D, false> +{ + static inline void apply(Point const&) {} +}; + +template +< + typename Point, + template <typename> class PlusOrMinus, + std::size_t D, + bool Enable +> +struct corner_by_epsilon<Point, PlusOrMinus, D, D, Enable> +{ + static inline void apply(Point const&) {} +}; + +template +< + typename Point, + template <typename> class PlusOrMinus, + std::size_t D +> +struct corner_by_epsilon<Point, PlusOrMinus, D, D, false> +{ + static inline void apply(Point const&) {} +}; + +} // namespace expand + +template <typename Box> +inline void expand_by_epsilon(Box & box) +{ + typedef detail::indexed_point_view<Box, min_corner> min_type; + min_type min_point(box); + expand::corner_by_epsilon<min_type, std::minus>::apply(min_point); + + typedef detail::indexed_point_view<Box, max_corner> max_type; + max_type max_point(box); + expand::corner_by_epsilon<max_type, std::plus>::apply(max_point); +} + +} // namespace detail +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_EXPAND_BY_EPSILON_HPP diff --git a/boost/geometry/algorithms/detail/is_simple/areal.hpp b/boost/geometry/algorithms/detail/is_simple/areal.hpp index 623632c44e..a2322e4831 100644 --- a/boost/geometry/algorithms/detail/is_simple/areal.hpp +++ b/boost/geometry/algorithms/detail/is_simple/areal.hpp @@ -40,11 +40,11 @@ struct is_simple_ring static inline bool apply(Ring const& ring) { simplicity_failure_policy policy; - return - !detail::is_valid::has_duplicates - < - Ring, geometry::closure<Ring>::value - >::apply(ring, policy); + return ! boost::empty(ring) + && ! detail::is_valid::has_duplicates + < + Ring, geometry::closure<Ring>::value + >::apply(ring, policy); } }; @@ -128,7 +128,7 @@ struct is_simple<MultiPolygon, multi_polygon_tag> < typename boost::range_value<MultiPolygon>::type >, - false // do not allow empty multi-polygon + true // allow empty multi-polygon >::apply(boost::begin(multipolygon), boost::end(multipolygon)); } }; diff --git a/boost/geometry/algorithms/detail/is_simple/linear.hpp b/boost/geometry/algorithms/detail/is_simple/linear.hpp index 0f77a49498..16d7b3a803 100644 --- a/boost/geometry/algorithms/detail/is_simple/linear.hpp +++ b/boost/geometry/algorithms/detail/is_simple/linear.hpp @@ -235,7 +235,8 @@ struct is_simple_linestring static inline bool apply(Linestring const& linestring) { simplicity_failure_policy policy; - return ! detail::is_valid::has_duplicates + return ! boost::empty(linestring) + && ! detail::is_valid::has_duplicates < Linestring, closed >::apply(linestring, policy) @@ -263,7 +264,7 @@ struct is_simple_multilinestring typename boost::range_value<MultiLinestring>::type, false // do not compute self-intersections >, - false // do not allow empty multilinestring + true // allow empty multilinestring >::apply(boost::begin(multilinestring), boost::end(multilinestring)) ) diff --git a/boost/geometry/algorithms/detail/is_simple/multipoint.hpp b/boost/geometry/algorithms/detail/is_simple/multipoint.hpp index 71c9e6ba90..f9f43d1cdb 100644 --- a/boost/geometry/algorithms/detail/is_simple/multipoint.hpp +++ b/boost/geometry/algorithms/detail/is_simple/multipoint.hpp @@ -40,9 +40,9 @@ struct is_simple_multipoint { static inline bool apply(MultiPoint const& multipoint) { - if ( boost::size(multipoint) == 0 ) + if (boost::empty(multipoint)) { - return false; + return true; } MultiPoint mp(multipoint); diff --git a/boost/geometry/algorithms/detail/is_valid/box.hpp b/boost/geometry/algorithms/detail/is_valid/box.hpp index e7a67252ba..863ce625fe 100644 --- a/boost/geometry/algorithms/detail/is_valid/box.hpp +++ b/boost/geometry/algorithms/detail/is_valid/box.hpp @@ -20,6 +20,7 @@ #include <boost/geometry/core/coordinate_dimension.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp> #include <boost/geometry/algorithms/dispatch/is_valid.hpp> @@ -66,6 +67,20 @@ struct has_valid_corners<Box, 0> } }; + +template <typename Box> +struct is_valid_box +{ + template <typename VisitPolicy> + static inline bool apply(Box const& box, VisitPolicy& visitor) + { + return + ! has_invalid_coordinate<Box>::apply(box, visitor) + && + has_valid_corners<Box, dimension<Box>::value>::apply(box, visitor); + } +}; + }} // namespace detail::is_valid #endif // DOXYGEN_NO_DETAIL @@ -85,7 +100,7 @@ namespace dispatch // Reference (for polygon validity): OGC 06-103r4 (6.1.11.1) template <typename Box> struct is_valid<Box, box_tag> - : detail::is_valid::has_valid_corners<Box, dimension<Box>::value> + : detail::is_valid::is_valid_box<Box> {}; diff --git a/boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp b/boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp new file mode 100644 index 0000000000..6e6823d62f --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp @@ -0,0 +1,151 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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_ALGORITHMS_DETAIL_IS_VALID_HAS_INVALID_COORDINATE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_INVALID_COORDINATE_HPP + +#include <cstddef> + +#include <boost/type_traits/is_floating_point.hpp> + +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/util/has_non_finite_coordinate.hpp> + +#include <boost/geometry/iterators/point_iterator.hpp> +#include <boost/geometry/views/detail/indexed_point_view.hpp> +#include <boost/geometry/algorithms/detail/check_iterator_range.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + +struct always_valid +{ + template <typename Geometry, typename VisitPolicy> + static inline bool apply(Geometry const&, VisitPolicy& visitor) + { + return ! visitor.template apply<no_failure>(); + } +}; + +struct point_has_invalid_coordinate +{ + template <typename Point, typename VisitPolicy> + static inline bool apply(Point const& point, VisitPolicy& visitor) + { + boost::ignore_unused(visitor); + + return + geometry::has_non_finite_coordinate(point) + ? + (! visitor.template apply<failure_invalid_coordinate>()) + : + (! visitor.template apply<no_failure>()); + } + + template <typename Point> + static inline bool apply(Point const& point) + { + return geometry::has_non_finite_coordinate(point); + } +}; + +struct indexed_has_invalid_coordinate +{ + template <typename Geometry, typename VisitPolicy> + static inline bool apply(Geometry const& geometry, VisitPolicy& visitor) + { + geometry::detail::indexed_point_view<Geometry const, 0> p0(geometry); + geometry::detail::indexed_point_view<Geometry const, 1> p1(geometry); + + return point_has_invalid_coordinate::apply(p0, visitor) + || point_has_invalid_coordinate::apply(p1, visitor); + } +}; + + +struct range_has_invalid_coordinate +{ + struct point_has_valid_coordinates + { + template <typename Point> + static inline bool apply(Point const& point) + { + return ! point_has_invalid_coordinate::apply(point); + } + }; + + template <typename Geometry, typename VisitPolicy> + static inline bool apply(Geometry const& geometry, VisitPolicy& visitor) + { + boost::ignore_unused(visitor); + + bool const has_valid_coordinates = detail::check_iterator_range + < + point_has_valid_coordinates, + true // do not consider an empty range as problematic + >::apply(geometry::points_begin(geometry), + geometry::points_end(geometry)); + + return has_valid_coordinates + ? + (! visitor.template apply<no_failure>()) + : + (! visitor.template apply<failure_invalid_coordinate>()); + } +}; + + +template +< + typename Geometry, + typename Tag = typename tag<Geometry>::type, + bool HasFloatingPointCoordinates = boost::is_floating_point + < + typename coordinate_type<Geometry>::type + >::value +> +struct has_invalid_coordinate + : range_has_invalid_coordinate +{}; + +template <typename Geometry, typename Tag> +struct has_invalid_coordinate<Geometry, Tag, false> + : always_valid +{}; + +template <typename Point> +struct has_invalid_coordinate<Point, point_tag, true> + : point_has_invalid_coordinate +{}; + +template <typename Segment> +struct has_invalid_coordinate<Segment, segment_tag, true> + : indexed_has_invalid_coordinate +{}; + +template <typename Box> +struct has_invalid_coordinate<Box, box_tag, true> + : indexed_has_invalid_coordinate +{}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_INVALID_COORDINATE_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/linear.hpp b/boost/geometry/algorithms/detail/is_valid/linear.hpp index e30064faf0..a49e077237 100644 --- a/boost/geometry/algorithms/detail/is_valid/linear.hpp +++ b/boost/geometry/algorithms/detail/is_valid/linear.hpp @@ -25,6 +25,7 @@ #include <boost/geometry/algorithms/equals.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp> #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp> #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp> @@ -46,6 +47,11 @@ struct is_valid_linestring static inline bool apply(Linestring const& linestring, VisitPolicy& visitor) { + if (has_invalid_coordinate<Linestring>::apply(linestring, visitor)) + { + return false; + } + if (boost::size(linestring) < 2) { return visitor.template apply<failure_few_points>(); diff --git a/boost/geometry/algorithms/detail/is_valid/pointlike.hpp b/boost/geometry/algorithms/detail/is_valid/pointlike.hpp index e51ab74643..51035f7a73 100644 --- a/boost/geometry/algorithms/detail/is_valid/pointlike.hpp +++ b/boost/geometry/algorithms/detail/is_valid/pointlike.hpp @@ -17,6 +17,7 @@ #include <boost/geometry/core/tags.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp> #include <boost/geometry/algorithms/dispatch/is_valid.hpp> #include <boost/geometry/util/condition.hpp> @@ -36,10 +37,13 @@ template <typename Point> struct is_valid<Point, point_tag> { template <typename VisitPolicy> - static inline bool apply(Point const&, VisitPolicy& visitor) + static inline bool apply(Point const& point, VisitPolicy& visitor) { boost::ignore_unused(visitor); - return visitor.template apply<no_failure>(); + return ! detail::is_valid::has_invalid_coordinate + < + Point + >::apply(point, visitor); } }; @@ -63,7 +67,10 @@ struct is_valid<MultiPoint, multi_point_tag, AllowEmptyMultiGeometries> { // we allow empty multi-geometries, so an empty multipoint // is considered valid - return visitor.template apply<no_failure>(); + return ! detail::is_valid::has_invalid_coordinate + < + MultiPoint + >::apply(multipoint, visitor); } else { diff --git a/boost/geometry/algorithms/detail/is_valid/polygon.hpp b/boost/geometry/algorithms/detail/is_valid/polygon.hpp index 6e87273aa1..bbe8e8fc39 100644 --- a/boost/geometry/algorithms/detail/is_valid/polygon.hpp +++ b/boost/geometry/algorithms/detail/is_valid/polygon.hpp @@ -11,6 +11,9 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP #include <cstddef> +#ifdef BOOST_GEOMETRY_TEST_DEBUG +#include <iostream> +#endif // BOOST_GEOMETRY_TEST_DEBUG #include <algorithm> #include <deque> @@ -327,7 +330,9 @@ protected: g.add_edge(v2, vip); } +#ifdef BOOST_GEOMETRY_TEST_DEBUG debug_print_complement_graph(std::cout, g); +#endif // BOOST_GEOMETRY_TEST_DEBUG if (g.has_cycles()) { diff --git a/boost/geometry/algorithms/detail/is_valid/ring.hpp b/boost/geometry/algorithms/detail/is_valid/ring.hpp index c35e843418..925c03a472 100644 --- a/boost/geometry/algorithms/detail/is_valid/ring.hpp +++ b/boost/geometry/algorithms/detail/is_valid/ring.hpp @@ -30,8 +30,9 @@ #include <boost/geometry/algorithms/intersects.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp> -#include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp> #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp> #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp> #include <boost/geometry/strategies/area.hpp> @@ -153,17 +154,23 @@ struct is_valid_ring static inline bool apply(Ring const& ring, VisitPolicy& visitor) { // return invalid if any of the following condition holds: - // (a) the ring's size is below the minimal one - // (b) the ring consists of at most two distinct points - // (c) the ring is not topologically closed - // (d) the ring has spikes - // (e) the ring has duplicate points (if AllowDuplicates is false) - // (f) the boundary of the ring has self-intersections - // (g) the order of the points is inconsistent with the defined order + // (a) the ring's point coordinates are not invalid (e.g., NaN) + // (b) the ring's size is below the minimal one + // (c) the ring consists of at most two distinct points + // (d) the ring is not topologically closed + // (e) the ring has spikes + // (f) the ring has duplicate points (if AllowDuplicates is false) + // (g) the boundary of the ring has self-intersections + // (h) the order of the points is inconsistent with the defined order // // Note: no need to check if the area is zero. If this is the // case, then the ring must have at least two spikes, which is - // checked by condition (c). + // checked by condition (d). + + if (has_invalid_coordinate<Ring>::apply(ring, visitor)) + { + return false; + } closure_selector const closure = geometry::closure<Ring>::value; typedef typename closeable_view<Ring const, closure>::type view_type; diff --git a/boost/geometry/algorithms/detail/is_valid/segment.hpp b/boost/geometry/algorithms/detail/is_valid/segment.hpp index a93d2bfe9e..f92f73381f 100644 --- a/boost/geometry/algorithms/detail/is_valid/segment.hpp +++ b/boost/geometry/algorithms/detail/is_valid/segment.hpp @@ -19,7 +19,7 @@ #include <boost/geometry/algorithms/assign.hpp> #include <boost/geometry/algorithms/equals.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> - +#include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp> #include <boost/geometry/algorithms/dispatch/is_valid.hpp> @@ -53,7 +53,14 @@ struct is_valid<Segment, segment_tag> detail::assign_point_from_index<0>(segment, p[0]); detail::assign_point_from_index<1>(segment, p[1]); - if(! geometry::equals(p[0], p[1])) + if (detail::is_valid::has_invalid_coordinate + < + Segment + >::apply(segment, visitor)) + { + return false; + } + else if (! geometry::equals(p[0], p[1])) { return visitor.template apply<no_failure>(); } diff --git a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp index b1a25c9f5e..8cb37d6954 100644 --- a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp +++ b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp @@ -51,14 +51,14 @@ class liang_barsky private: typedef model::referring_segment<Point> segment_type; - template <typename T> - inline bool check_edge(T const& p, T const& q, T& t1, T& t2) const + template <typename CoordinateType, typename CalcType> + inline bool check_edge(CoordinateType const& p, CoordinateType const& q, CalcType& t1, CalcType& t2) const { bool visible = true; if(p < 0) { - T const r = q / p; + CalcType const r = static_cast<CalcType>(q) / p; if (r > t2) visible = false; else if (r > t1) @@ -66,7 +66,7 @@ private: } else if(p > 0) { - T const r = q / p; + CalcType const r = static_cast<CalcType>(q) / p; if (r < t1) visible = false; else if (r < t2) @@ -86,9 +86,10 @@ public: inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const { typedef typename select_coordinate_type<Box, Point>::type coordinate_type; + typedef typename select_most_precise<coordinate_type, double>::type calc_type; - coordinate_type t1 = 0; - coordinate_type t2 = 1; + calc_type t1 = 0; + calc_type t2 = 1; coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s); coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s); diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 3f81c4dca9..bc84286241 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -26,7 +26,9 @@ #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> +#include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp> #include <boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/policies/robustness/robust_type.hpp> #include <boost/geometry/strategies/side.hpp> #ifdef BOOST_GEOMETRY_DEBUG_ENRICH @@ -466,6 +468,7 @@ inline void create_map(TurnPoints const& turn_points, MappedVector& mapped_vecto template < bool Reverse1, bool Reverse2, + overlay_type OverlayType, typename TurnPoints, typename Geometry1, typename Geometry2, typename RobustPolicy, @@ -490,10 +493,9 @@ inline void enrich_intersection_points(TurnPoints& turn_points, std::vector<indexed_turn_operation> > mapped_vector_type; - // DISCARD ALL UU - // #76 is the reason that this is necessary... - // With uu, at all points there is the risk that rings are being traversed twice or more. - // Without uu, all rings having only uu will be untouched and gathered by assemble + // Iterate through turns and discard uu + // and check if there are possible colocations + bool check_colocations = false; for (typename boost::range_iterator<TurnPoints>::type it = boost::begin(turn_points); it != boost::end(turn_points); @@ -501,14 +503,34 @@ inline void enrich_intersection_points(TurnPoints& turn_points, { if (it->both(detail::overlay::operation_union)) { + // Discard (necessary for a.o. #76). With uu, at all points there + // is the risk that rings are being traversed twice or more. + // Without uu, all rings having only uu will be untouched + // and gathered by assemble it->discarded = true; + check_colocations = true; } - if (it->both(detail::overlay::operation_none)) + else if (it->combination(detail::overlay::operation_union, + detail::overlay::operation_blocked)) + { + check_colocations = true; + } + else if (OverlayType == overlay_difference + && it->both(detail::overlay::operation_intersection)) + { + // For difference operation (u/u -> i/i) + check_colocations = true; + } + else if (it->both(detail::overlay::operation_none)) { it->discarded = true; } } + if (check_colocations) + { + detail::overlay::handle_colocations<OverlayType>(turn_points); + } // Create a map of vectors of indexed operation-types to be able // to sort intersection points PER RING diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp index b2c3836712..b9e48cdbfc 100644 --- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2015, Oracle and/or its affiliates. // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -22,6 +22,7 @@ #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> #include <boost/geometry/algorithms/detail/overlay/follow.hpp> +#include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -35,24 +36,6 @@ namespace boost { namespace geometry { -#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) -class inconsistent_turns_exception : public geometry::exception -{ -public: - - inline inconsistent_turns_exception() {} - - virtual ~inconsistent_turns_exception() throw() - {} - - virtual char const* what() const throw() - { - return "Boost.Geometry Inconsistent Turns exception"; - } -}; -#endif - - #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace overlay { diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 717f0b47a9..ac36c530bf 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -585,8 +585,8 @@ struct collinear : public base_turn_handler typename SidePolicy > static inline void apply( - Point1 const& , Point1 const& , Point1 const& , - Point2 const& , Point2 const& , Point2 const& , + Point1 const& , Point1 const& pj, Point1 const& pk, + Point2 const& , Point2 const& qj, Point2 const& qk, TurnInfo& ti, IntersectionInfo const& info, DirInfo const& dir_info, @@ -623,8 +623,30 @@ struct collinear : public base_turn_handler { ui_else_iu(product == 1, ti); } + + // Calculate remaining distance. If it continues collinearly it is + // measured until the end of the next segment + ti.operations[0].remaining_distance + = side_p == 0 + ? distance_measure(ti.point, pk) + : distance_measure(ti.point, pj); + ti.operations[1].remaining_distance + = side_q == 0 + ? distance_measure(ti.point, qk) + : distance_measure(ti.point, qj); } + template <typename Point1, typename Point2> + static inline typename geometry::coordinate_type<Point1>::type + distance_measure(Point1 const& a, Point2 const& b) + { + // TODO: use comparable distance for point-point instead - but that + // causes currently cycling include problems + typedef typename geometry::coordinate_type<Point1>::type ctype; + ctype const dx = get<0>(a) - get<0>(b); + ctype const dy = get<1>(b) - get<1>(b); + return dx * dx + dy * dy; + } }; template diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp index e4f8de42e1..ee0a93ae7e 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -23,9 +23,9 @@ namespace detail { namespace overlay { enum turn_position { position_middle, position_front, position_back }; -template <typename SegmentRatio> +template <typename Point, typename SegmentRatio> struct turn_operation_linear - : public turn_operation<SegmentRatio> + : public turn_operation<Point, SegmentRatio> { turn_operation_linear() : position(position_middle) diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index 098c7b5642..b2b97c0337 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -802,19 +802,19 @@ template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type> struct turn_operation_type { - typedef overlay::turn_operation<SegmentRatio> type; + typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type; }; template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag> { - typedef overlay::turn_operation_linear<SegmentRatio> type; + typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; }; template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag> { - typedef overlay::turn_operation_linear<SegmentRatio> type; + typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; }; }} // namespace detail::get_turns diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp new file mode 100644 index 0000000000..6f332ddff2 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -0,0 +1,278 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015 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 +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP + +#include <cstddef> +#include <algorithm> +#include <map> +#include <vector> + +#include <boost/range.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/algorithms/detail/ring_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> + +#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) +# include <iostream> +# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> +# include <boost/geometry/io/wkt/wkt.hpp> +# define BOOST_GEOMETRY_DEBUG_IDENTIFIER +#endif + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +struct turn_operation_index +{ + turn_operation_index(signed_size_type ti = -1, + signed_size_type oi = -1) + : turn_index(ti) + , op_index(oi) + {} + + signed_size_type turn_index; + signed_size_type op_index; // basically only 0,1 +}; + + +template <typename TurnPoints> +struct less_by_fraction_and_type +{ + inline less_by_fraction_and_type(TurnPoints const& turn_points) + : m_turns(turn_points) + { + } + + inline bool operator()(turn_operation_index const& left, + turn_operation_index const& right) const + { + typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + turn_type const& left_turn = m_turns[left.turn_index]; + turn_type const& right_turn = m_turns[right.turn_index]; + turn_operation_type const& left_op + = left_turn.operations[left.op_index]; + + turn_operation_type const& right_op + = right_turn.operations[right.op_index]; + + if (! (left_op.fraction == right_op.fraction)) + { + return left_op.fraction < right_op.fraction; + } + + turn_operation_type const& left_other_op + = left_turn.operations[1 - left.op_index]; + + turn_operation_type const& right_other_op + = right_turn.operations[1 - right.op_index]; + + // Fraction is the same, now sort on ring id, first outer ring, + // then interior rings + return left_other_op.seg_id < right_other_op.seg_id; + } + +private: + TurnPoints const& m_turns; +}; + +template <overlay_type OverlayType, typename TurnPoints, typename OperationVector> +inline void handle_colocation_cluster(TurnPoints& turn_points, + segment_identifier const& current_ring_seg_id, + OperationVector const& vec) +{ + typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + std::vector<turn_operation_index>::const_iterator vit = vec.begin(); + + turn_type cluster_turn = turn_points[vit->turn_index]; + turn_operation_type cluster_op + = cluster_turn.operations[vit->op_index]; + segment_identifier cluster_other_id + = cluster_turn.operations[1 - vit->op_index].seg_id; + bool const discard_colocated + = cluster_turn.both(operation_union) + || cluster_turn.combination(operation_blocked, operation_union); + + for (++vit; vit != vec.end(); ++vit) + { + turn_operation_index const& toi = *vit; + turn_type& turn = turn_points[toi.turn_index]; + turn_operation_type const& op = turn.operations[toi.op_index]; + segment_identifier const& other_id + = turn.operations[1 - toi.op_index].seg_id; + + if (cluster_op.fraction == op.fraction) + { + // Two turns of current ring with same source are colocated, + // one is from exterior ring, one from interior ring + bool const colocated_ext_int + = cluster_other_id.multi_index == other_id.multi_index + && cluster_other_id.ring_index == -1 + && other_id.ring_index >= 0; + + // Turn of current interior ring with other interior ring + bool const touch_int_int + = current_ring_seg_id.ring_index >= 0 + && other_id.ring_index >= 0; + + if (discard_colocated && colocated_ext_int) + { + // If the two turns on this same segment are a + // colocation with two different segments on the + // other geometry, of the same polygon but with + // the outer (u/u or u/x) and the inner ring (non u/u), + // that turn with inner ring should be discarded + turn.discarded = true; + turn.colocated = true; + } + else if (cluster_turn.colocated + && touch_int_int + && turn.both(operation_intersection)) + { + // Two holes touch each other at a point where the + // exterior ring also touches + turn.discarded = true; + turn.colocated = true; + } + else if (OverlayType == overlay_difference + && turn.both(operation_intersection) + && colocated_ext_int) + { + // For difference (polygon inside out) we need to + // discard i/i instead, in case of colocations + turn.discarded = true; + turn.colocated = true; + } + } + else + { + // Not on same fraction on this segment + // assign for next potential cluster + cluster_turn = turn; + cluster_op = op; + cluster_other_id = other_id; + } + + } +} + + +// Checks colocated turns and flags combinations of uu/other, possibly a +// combination of a ring touching another geometry's interior ring which is +// tangential to the exterior ring + +// This function can be extended to replace handle_tangencies: at each +// colocation incoming and outgoing vectors should be inspected + +template <overlay_type OverlayType, typename TurnPoints> +inline void handle_colocations(TurnPoints& turn_points) +{ + typedef std::map + < + segment_identifier, + std::vector<turn_operation_index> + > map_type; + + // Create and fill map on segment-identifier Map is sorted on seg_id, + // meaning it is sorted on ring_identifier too. This means that exterior + // rings are handled first. If there is a colocation on the exterior ring, + // that information can be used for the interior ring too + map_type map; + + int index = 0; + for (typename boost::range_iterator<TurnPoints>::type + it = boost::begin(turn_points); + it != boost::end(turn_points); + ++it, ++index) + { + map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0)); + map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1)); + } + + // Check if there are multiple turns on one or more segments, + // if not then nothing is to be done + bool colocations = 0; + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); + ++it) + { + if (it->second.size() > 1u) + { + colocations = true; + break; + } + } + + if (! colocations) + { + return; + } + + // Sort all vectors, per same segment + less_by_fraction_and_type<TurnPoints> less(turn_points); + for (typename map_type::iterator it = map.begin(); + it != map.end(); ++it) + { + std::sort(it->second.begin(), it->second.end(), less); + } + + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); ++it) + { + if (it->second.size() > 1) + { + handle_colocation_cluster<OverlayType>(turn_points, + it->first, it->second); + } + } + +#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) + std::cout << "*** Colocations " << map.size() << std::endl; + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); ++it) + { + std::cout << it->first << std::endl; + for (std::vector<turn_operation_index>::const_iterator vit + = it->second.begin(); vit != it->second.end(); ++vit) + { + turn_operation_index const& toi = *vit; + std::cout << geometry::wkt(turn_points[toi.turn_index].point) + << std::boolalpha + << " discarded=" << turn_points[toi.turn_index].discarded + << " colocated=" << turn_points[toi.turn_index].colocated + << " " << operation_char(turn_points[toi.turn_index].operations[0].operation) + << " " << turn_points[toi.turn_index].operations[0].seg_id + << " " << turn_points[toi.turn_index].operations[0].fraction + << " // " << operation_char(turn_points[toi.turn_index].operations[1].operation) + << " " << turn_points[toi.turn_index].operations[1].seg_id + << " " << turn_points[toi.turn_index].operations[1].fraction + << std::endl; + } + } +#endif // DEBUG + +} + + +}} // namespace detail::overlay +#endif //DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp new file mode 100644 index 0000000000..1486f94fbd --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp @@ -0,0 +1,38 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP + +#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) +#include <boost/geometry/core/exception.hpp> + +namespace boost { namespace geometry +{ + +class inconsistent_turns_exception : public geometry::exception +{ +public: + + inline inconsistent_turns_exception() {} + + virtual ~inconsistent_turns_exception() throw() + {} + + virtual char const* what() const throw() + { + return "Boost.Geometry Inconsistent Turns exception"; + } +}; + +}} // boost::geometry + +#endif // BOOST_GEOMETRY_OVERLAY_NO_THROW + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP diff --git a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp index dd041b0d7d..c62b7d2834 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp @@ -1,6 +1,11 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -39,19 +44,26 @@ struct intersection_box_box { typedef typename coordinate_type<BoxOut>::type ct; - ct min1 = get<min_corner, Dimension>(box1); - ct min2 = get<min_corner, Dimension>(box2); ct max1 = get<max_corner, Dimension>(box1); + ct min2 = get<min_corner, Dimension>(box2); + + if (max1 < min2) + { + return false; + } + ct max2 = get<max_corner, Dimension>(box2); + ct min1 = get<min_corner, Dimension>(box1); - if (max1 < min2 || max2 < min1) + if (max2 < min1) { return false; } + // Set dimensions of output coordinate set<min_corner, Dimension>(box_out, min1 < min2 ? min2 : min1); set<max_corner, Dimension>(box_out, max1 > max2 ? max2 : max1); - + return intersection_box_box<Dimension + 1, DimensionCount> ::apply(box1, box2, robust_policy, box_out, strategy); } diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index af0731f5a9..59c8f6f1ff 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -41,6 +41,7 @@ #include <boost/geometry/views/segment_view.hpp> #include <boost/geometry/views/detail/boundary_view.hpp> +#include <boost/geometry/algorithms/detail/check_iterator_range.hpp> #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp> @@ -175,21 +176,115 @@ template struct intersection_of_linestring_with_areal { #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) - template <typename Turn, typename Operation> - static inline void debug_follow(Turn const& turn, Operation op, - int index) + template <typename Turn, typename Operation> + static inline void debug_follow(Turn const& turn, Operation op, + int index) + { + std::cout << index + << " at " << op.seg_id + << " meth: " << method_char(turn.method) + << " op: " << operation_char(op.operation) + << " vis: " << visited_char(op.visited) + << " of: " << operation_char(turn.operations[0].operation) + << operation_char(turn.operations[1].operation) + << " " << geometry::wkt(turn.point) + << std::endl; + } + + template <typename Turn> + static inline void debug_turn(Turn const& t, bool non_crossing) + { + std::cout << "checking turn @" + << geometry::wkt(t.point) + << "; " << method_char(t.method) + << ":" << operation_char(t.operations[0].operation) + << "/" << operation_char(t.operations[1].operation) + << "; non-crossing? " + << std::boolalpha << non_crossing << std::noboolalpha + << std::endl; + } +#endif + + class is_crossing_turn + { + // return true is the operation is intersection or blocked + template <std::size_t Index, typename Turn> + static inline bool has_op_i_or_b(Turn const& t) { - std::cout << index - << " at " << op.seg_id - << " meth: " << method_char(turn.method) - << " op: " << operation_char(op.operation) - << " vis: " << visited_char(op.visited) - << " of: " << operation_char(turn.operations[0].operation) - << operation_char(turn.operations[1].operation) - << " " << geometry::wkt(turn.point) - << std::endl; + return + t.operations[Index].operation == overlay::operation_intersection + || + t.operations[Index].operation == overlay::operation_blocked; } + + template <typename Turn> + static inline bool has_method_crosses(Turn const& t) + { + return t.method == overlay::method_crosses; + } + + template <typename Turn> + static inline bool is_cc(Turn const& t) + { + return + (t.method == overlay::method_touch_interior + || + t.method == overlay::method_equal + || + t.method == overlay::method_collinear) + && + t.operations[0].operation == t.operations[1].operation + && + t.operations[0].operation == overlay::operation_continue + ; + } + + template <typename Turn> + static inline bool has_i_or_b_ops(Turn const& t) + { + return + (t.method == overlay::method_touch + || + t.method == overlay::method_touch_interior + || + t.method == overlay::method_collinear) + && + t.operations[1].operation != t.operations[0].operation + && + (has_op_i_or_b<0>(t) || has_op_i_or_b<1>(t)); + } + + public: + template <typename Turn> + static inline bool apply(Turn const& t) + { + bool const is_crossing + = has_method_crosses(t) || is_cc(t) || has_i_or_b_ops(t); +#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) + debug_turn(t, ! is_crossing); #endif + return is_crossing; + } + }; + + struct is_non_crossing_turn + { + template <typename Turn> + static inline bool apply(Turn const& t) + { + return ! is_crossing_turn::apply(t); + } + }; + + template <typename Turns> + static inline bool no_crossing_turns_or_empty(Turns const& turns) + { + return detail::check_iterator_range + < + is_non_crossing_turn, + true // allow an empty turns range + >::apply(boost::begin(turns), boost::end(turns)); + } template < @@ -212,7 +307,8 @@ struct intersection_of_linestring_with_areal LineStringOut, LineString, Areal, - OverlayType + OverlayType, + false // do not remove spikes for linear geometries > follower; typedef typename point_type<LineStringOut>::type point_type; @@ -231,7 +327,7 @@ struct intersection_of_linestring_with_areal detail::overlay::assign_null_policy >(linestring, areal, robust_policy, turns, policy); - if (turns.empty()) + if (no_crossing_turns_or_empty(turns)) { // No intersection points, it is either completely // inside (interior + borders) diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index baf9d4777d..6eb0b8864c 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -78,6 +78,11 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, && ! turn_info.both(operation_intersection) ; + if (! both_uu && turn_info.colocated) + { + skip = true; + } + for (typename boost::range_iterator<container_type const>::type op_it = boost::begin(turn_info.operations); op_it != boost::end(turn_info.operations); @@ -105,7 +110,7 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, template < - typename GeometryOut, overlay_type Direction, bool ReverseOut, + typename GeometryOut, overlay_type OverlayType, bool ReverseOut, typename Geometry1, typename Geometry2, typename OutputIterator > @@ -129,8 +134,8 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, // Union: return either of them // Intersection: return nothing // Difference: return first of them - if (Direction == overlay_intersection - || (Direction == overlay_difference && geometry::is_empty(geometry1))) + if (OverlayType == overlay_intersection + || (OverlayType == overlay_difference && geometry::is_empty(geometry1))) { return out; } @@ -143,7 +148,7 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, std::map<ring_identifier, ring_turn_info> empty; std::map<ring_identifier, properties> all_of_one_of_them; - select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them); + select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them); ring_container_type rings; assign_parents(geometry1, geometry2, rings, all_of_one_of_them); return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out); @@ -155,7 +160,7 @@ template typename Geometry1, typename Geometry2, bool Reverse1, bool Reverse2, bool ReverseOut, typename GeometryOut, - overlay_type Direction + overlay_type OverlayType > struct overlay { @@ -178,7 +183,7 @@ struct overlay { return return_if_one_input_is_empty < - GeometryOut, Direction, ReverseOut + GeometryOut, OverlayType, ReverseOut >(geometry1, geometry2, out); } @@ -211,8 +216,8 @@ std::cout << "get turns" << std::endl; std::cout << "enrich" << std::endl; #endif typename Strategy::side_strategy_type side_strategy; - geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points, - Direction == overlay_union + geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turn_points, + OverlayType == overlay_union ? geometry::detail::overlay::operation_union : geometry::detail::overlay::operation_intersection, geometry1, geometry2, @@ -229,7 +234,7 @@ std::cout << "traverse" << std::endl; traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply ( geometry1, geometry2, - Direction == overlay_union + OverlayType == overlay_union ? geometry::detail::overlay::operation_union : geometry::detail::overlay::operation_intersection, robust_policy, @@ -246,7 +251,7 @@ std::cout << "traverse" << std::endl; // Select all rings which are NOT touched by any intersection point std::map<ring_identifier, properties> selected_ring_properties; - select_rings<Direction>(geometry1, geometry2, turn_info_per_ring, + select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring, selected_ring_properties); // Add rings created during traversal diff --git a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp index 6ee32c17c0..8cabfb0d8d 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp @@ -25,7 +25,7 @@ namespace detail { namespace overlay template <typename Point, typename SegmentRatio> -struct traversal_turn_operation : public turn_operation<SegmentRatio> +struct traversal_turn_operation : public turn_operation<Point, SegmentRatio> { enrichment_info<Point> enriched; visit_info visited; diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index 803a164711..45e15d13d0 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -174,7 +174,17 @@ inline bool select_next_ip(operation_type operation, { return false; } + bool has_tp = false; + + typedef typename std::iterator_traits + < + Iterator + >::value_type operation_type; + + typename operation_type::comparable_distance_type + max_remaining_distance = 0; + selected = boost::end(turn.operations); for (Iterator it = boost::begin(turn.operations); it != boost::end(turn.operations); @@ -206,10 +216,24 @@ inline bool select_next_ip(operation_type operation, ) ) { + if (it->operation == operation_continue) + { + max_remaining_distance = it->remaining_distance; + } selected = it; debug_traverse(turn, *it, " Candidate"); has_tp = true; } + + if (it->operation == operation_continue && has_tp) + { + if (it->remaining_distance > max_remaining_distance) + { + max_remaining_distance = it->remaining_distance; + selected = it; + debug_traverse(turn, *it, " Candidate override"); + } + } } if (has_tp) diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index 26669a4b1f..1ac77d5796 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -12,6 +12,7 @@ #include <boost/array.hpp> +#include <boost/geometry/core/coordinate_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> namespace boost { namespace geometry @@ -54,15 +55,19 @@ enum method_type The class is to be included in the turn_info class, either direct or a derived or similar class with more (e.g. enrichment) information. */ -template <typename SegmentRatio> +template <typename Point, typename SegmentRatio> struct turn_operation { operation_type operation; segment_identifier seg_id; SegmentRatio fraction; + typedef typename coordinate_type<Point>::type comparable_distance_type; + comparable_distance_type remaining_distance; + inline turn_operation() : operation(operation_none) + , remaining_distance(0) {} }; @@ -80,7 +85,7 @@ template < typename Point, typename SegmentRatio, - typename Operation = turn_operation<SegmentRatio>, + typename Operation = turn_operation<Point, SegmentRatio>, typename Container = boost::array<Operation, 2> > struct turn_info @@ -93,6 +98,7 @@ struct turn_info method_type method; bool discarded; bool selectable_start; // Can be used as starting-turn in traverse + bool colocated; Container operations; @@ -101,6 +107,7 @@ struct turn_info : method(method_none) , discarded(false) , selectable_start(true) + , colocated(false) {} inline bool both(operation_type type) const diff --git a/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp b/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp index 9db1ef8e0c..399c8fbefc 100644 --- a/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp +++ b/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp @@ -1,9 +1,14 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2013 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2013 Mateusz Loskot, London, UK. -// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -12,8 +17,6 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP -#include <boost/geometry/arithmetic/arithmetic.hpp> -#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> #include <boost/geometry/algorithms/detail/recalculate.hpp> #include <boost/geometry/policies/robustness/robust_point_type.hpp> #include <boost/geometry/strategies/side.hpp> @@ -28,6 +31,17 @@ namespace boost { namespace geometry namespace detail { +template <std::size_t Index, typename Point1, typename Point2> +inline int sign_of_difference(Point1 const& point1, Point2 const& point2) +{ + return + math::equals(geometry::get<Index>(point1), geometry::get<Index>(point2)) + ? + 0 + : + (geometry::get<Index>(point1) > geometry::get<Index>(point2) ? 1 : -1); +} + // Checks if a point ("last_point") causes a spike w.r.t. // the specified two other points (segment_a, segment_b) // @@ -35,7 +49,9 @@ namespace detail // a lp b // // Above, lp generates a spike w.r.t. segment(a,b) -// So specify last point first, then (a,b) (this is unordered, so unintuitive) +// So specify last point first, then (a,b) +// The segment's orientation does matter: if lp is to the right of b +// no spike is reported template <typename Point1, typename Point2, typename Point3> static inline bool point_is_spike_or_equal(Point1 const& last_point, Point2 const& segment_a, @@ -46,29 +62,21 @@ static inline bool point_is_spike_or_equal(Point1 const& last_point, typename cs_tag<Point1>::type >::type side_strategy; - typedef Point1 vector_type; - int const side = side_strategy::apply(last_point, segment_a, segment_b); if (side == 0) { // Last point is collinear w.r.t previous segment. // Check if it is equal - vector_type diff1; - conversion::convert_point_to_point(last_point, diff1); - geometry::subtract_point(diff1, segment_b); - int const sgn_x1 = math::sign(geometry::get<0>(diff1)); - int const sgn_y1 = math::sign(geometry::get<1>(diff1)); + int const sgn_x1 = sign_of_difference<0>(last_point, segment_b); + int const sgn_y1 = sign_of_difference<1>(last_point, segment_b); if (sgn_x1 == 0 && sgn_y1 == 0) { return true; } // Check if it moves forward - vector_type diff2; - conversion::convert_point_to_point(segment_b, diff2); - geometry::subtract_point(diff2, segment_a); - int const sgn_x2 = math::sign(geometry::get<0>(diff2)); - int const sgn_y2 = math::sign(geometry::get<1>(diff2)); + int const sgn_x2 = sign_of_difference<0>(segment_b, segment_a); + int const sgn_y2 = sign_of_difference<1>(segment_b, segment_a); return sgn_x1 != sgn_x2 || sgn_y1 != sgn_y2; } diff --git a/boost/geometry/algorithms/detail/relate/areal_areal.hpp b/boost/geometry/algorithms/detail/relate/areal_areal.hpp index cc9c1b67ca..a74954326b 100644 --- a/boost/geometry/algorithms/detail/relate/areal_areal.hpp +++ b/boost/geometry/algorithms/detail/relate/areal_areal.hpp @@ -338,7 +338,7 @@ struct areal_areal template <std::size_t OpId, typename Turn> inline void per_turn(Turn const& turn) { - static const std::size_t other_op_id = (OpId + 1) % 2; + //static const std::size_t other_op_id = (OpId + 1) % 2; static const bool transpose_result = OpId != 0; overlay::operation_type const op = turn.operations[OpId].operation; @@ -357,11 +357,14 @@ struct areal_areal else if ( op == overlay::operation_intersection ) { // ignore i/i - if ( turn.operations[other_op_id].operation != overlay::operation_intersection ) + /*if ( turn.operations[other_op_id].operation != overlay::operation_intersection ) { - update<interior, interior, '2', transpose_result>(m_result); + // not correct e.g. for G1 touching G2 in a point where a hole is touching the exterior ring + // in this case 2 turns i/... and u/u will be generated for this IP + //update<interior, interior, '2', transpose_result>(m_result); + //update<boundary, interior, '1', transpose_result>(m_result); - } + }*/ update<boundary, boundary, '0', transpose_result>(m_result); } @@ -473,8 +476,11 @@ struct areal_areal // ignore i/i if ( it->operations[other_op_id].operation != overlay::operation_intersection ) { - // already set in interrupt policy + // this was set in the interrupt policy but it was wrong + // also here it's wrong since it may be a fake entry point //update<interior, interior, '2', transpose_result>(result); + + // already set in interrupt policy //update<boundary, boundary, '0', transpose_result>(result); m_enter_detected = true; } @@ -523,6 +529,7 @@ struct areal_areal template <typename Result> static inline void update_enter(Result & result) { + update<interior, interior, '2', transpose_result>(result); update<boundary, interior, '1', transpose_result>(result); update<exterior, interior, '2', transpose_result>(result); } @@ -574,6 +581,7 @@ struct areal_areal , m_flags(0) { // check which relations must be analysed + // NOTE: 1 and 4 could probably be connected if ( ! may_update<interior, interior, '2', transpose_result>(m_result) ) { @@ -662,21 +670,12 @@ struct areal_areal if ( it->operations[0].operation == overlay::operation_intersection && it->operations[1].operation == overlay::operation_intersection ) { - // ignore exterior ring - if ( it->operations[OpId].seg_id.ring_index >= 0 ) - { - found_ii = true; - } + found_ii = true; } else if ( it->operations[0].operation == overlay::operation_union && it->operations[1].operation == overlay::operation_union ) { - // ignore if u/u is for holes - //if ( it->operations[OpId].seg_id.ring_index >= 0 - // && it->operations[other_id].seg_id.ring_index >= 0 ) - { - found_uu = true; - } + found_uu = true; } else // ignore { @@ -687,8 +686,11 @@ struct areal_areal // only i/i was generated for this ring if ( found_ii ) { - //update<interior, interior, '0', transpose_result>(m_result); - //update<boundary, boundary, '0', transpose_result>(m_result); + update<interior, interior, '2', transpose_result>(m_result); + m_flags |= 1; + + //update<boundary, boundary, '0', transpose_result>(m_result); + update<boundary, interior, '1', transpose_result>(m_result); update<exterior, interior, '2', transpose_result>(m_result); m_flags |= 4; diff --git a/boost/geometry/algorithms/detail/relate/boundary_checker.hpp b/boost/geometry/algorithms/detail/relate/boundary_checker.hpp index 9de1bacb7d..1a9a5a8fd7 100644 --- a/boost/geometry/algorithms/detail/relate/boundary_checker.hpp +++ b/boost/geometry/algorithms/detail/relate/boundary_checker.hpp @@ -17,6 +17,8 @@ #include <boost/geometry/algorithms/detail/equals/point_point.hpp> +#include <boost/geometry/util/has_nan_coordinate.hpp> + namespace boost { namespace geometry { @@ -90,19 +92,43 @@ public: for ( multi_iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++ it ) { + typename boost::range_reference<Geometry const>::type + ls = *it; + // empty or point - no boundary - if ( boost::size(*it) < 2 ) + if (boost::size(ls) < 2) + { continue; + } - // linear ring or point - no boundary - if ( equals::equals_point_point(range::front(*it), range::back(*it)) ) - continue; + typedef typename boost::range_reference + < + typename boost::range_value<Geometry const>::type const + >::type point_reference; + + point_reference front_pt = range::front(ls); + point_reference back_pt = range::back(ls); - boundary_points.push_back(range::front(*it)); - boundary_points.push_back(range::back(*it)); + // linear ring or point - no boundary + if (! equals::equals_point_point(front_pt, back_pt)) + { + // do not add points containing NaN coordinates + // because they cannot be reasonably compared, e.g. with MSVC + // an assertion failure is reported in std::equal_range() + if (! geometry::has_nan_coordinate(front_pt)) + { + boundary_points.push_back(front_pt); + } + if (! geometry::has_nan_coordinate(back_pt)) + { + boundary_points.push_back(back_pt); + } + } } - std::sort(boundary_points.begin(), boundary_points.end(), geometry::less<point_type>()); + std::sort(boundary_points.begin(), + boundary_points.end(), + geometry::less<point_type>()); is_filled = true; } diff --git a/boost/geometry/algorithms/detail/relate/topology_check.hpp b/boost/geometry/algorithms/detail/relate/topology_check.hpp index 98b857a488..caa8a3c22d 100644 --- a/boost/geometry/algorithms/detail/relate/topology_check.hpp +++ b/boost/geometry/algorithms/detail/relate/topology_check.hpp @@ -16,6 +16,8 @@ #include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/policies/compare.hpp> +#include <boost/geometry/util/has_nan_coordinate.hpp> + namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DETAIL @@ -106,20 +108,42 @@ struct topology_check<MultiLinestring, multi_linestring_tag> typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator; for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it ) { - std::size_t count = boost::size(*it); + typename boost::range_reference<MultiLinestring const>::type + ls = *it; + + std::size_t count = boost::size(ls); - if ( count > 0 ) + if (count > 0) { has_interior = true; } - if ( count > 1 ) + if (count > 1) { + typedef typename boost::range_reference + < + typename boost::range_value<MultiLinestring const>::type const + >::type point_reference; + + point_reference front_pt = range::front(ls); + point_reference back_pt = range::back(ls); + // don't store boundaries of linear rings, this doesn't change anything - if ( ! equals::equals_point_point(range::front(*it), range::back(*it)) ) + if (! equals::equals_point_point(front_pt, back_pt)) { - endpoints.push_back(range::front(*it)); - endpoints.push_back(range::back(*it)); + // do not add points containing NaN coordinates + // because they cannot be reasonably compared, e.g. with MSVC + // an assertion failure is reported in std::equal_range() + // NOTE: currently ignoring_counter calling std::equal_range() + // is not used anywhere in the code, still it's safer this way + if (! geometry::has_nan_coordinate(front_pt)) + { + endpoints.push_back(front_pt); + } + if (! geometry::has_nan_coordinate(back_pt)) + { + endpoints.push_back(back_pt); + } } } } diff --git a/boost/geometry/algorithms/detail/relate/turns.hpp b/boost/geometry/algorithms/detail/relate/turns.hpp index d54948e1f5..09d74dec3a 100644 --- a/boost/geometry/algorithms/detail/relate/turns.hpp +++ b/boost/geometry/algorithms/detail/relate/turns.hpp @@ -128,8 +128,8 @@ struct get_turns template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0> struct op_to_int { - template <typename SegmentRatio> - inline int operator()(detail::overlay::turn_operation<SegmentRatio> const& op) const + template <typename Operation> + inline int operator()(Operation const& op) const { switch(op.operation) { diff --git a/boost/geometry/algorithms/detail/sections/section_functions.hpp b/boost/geometry/algorithms/detail/sections/section_functions.hpp index ba1cf931b2..7bc5c08046 100644 --- a/boost/geometry/algorithms/detail/sections/section_functions.hpp +++ b/boost/geometry/algorithms/detail/sections/section_functions.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // 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) diff --git a/boost/geometry/algorithms/detail/sections/sectionalize.hpp b/boost/geometry/algorithms/detail/sections/sectionalize.hpp index 1ced394353..6443965e95 100644 --- a/boost/geometry/algorithms/detail/sections/sectionalize.hpp +++ b/boost/geometry/algorithms/detail/sections/sectionalize.hpp @@ -52,6 +52,8 @@ #include <boost/geometry/views/reversible_view.hpp> #include <boost/geometry/geometries/segment.hpp> +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> + namespace boost { namespace geometry { @@ -599,19 +601,18 @@ inline void enlarge_sections(Sections& sections) // Reason: turns might, rarely, be missed otherwise (case: "buffer_mp1") // Drawback: not really, range is now completely inside the section. Section is a tiny bit too large, // which might cause (a small number) of more comparisons - // TODO: make dimension-agnostic + + // NOTE: above is old comment to the not used code expanding the Boxes by relaxed_epsilon(10) + + // Enlarge sections by scaled epsilon, this should be consistent with math::equals(). + // Points and Segments are equal-compared WRT machine epsilon, but Boxes aren't + // Enlarging Boxes ensures that they correspond to the bound objects, + // Segments in this case, since Sections are collections of Segments. for (typename boost::range_iterator<Sections>::type it = boost::begin(sections); it != boost::end(sections); ++it) { - typedef typename boost::range_value<Sections>::type section_type; - typedef typename section_type::box_type box_type; - typedef typename geometry::coordinate_type<box_type>::type coordinate_type; - coordinate_type const reps = math::relaxed_epsilon(10.0); - geometry::set<0, 0>(it->bounding_box, geometry::get<0, 0>(it->bounding_box) - reps); - geometry::set<0, 1>(it->bounding_box, geometry::get<0, 1>(it->bounding_box) - reps); - geometry::set<1, 0>(it->bounding_box, geometry::get<1, 0>(it->bounding_box) + reps); - geometry::set<1, 1>(it->bounding_box, geometry::get<1, 1>(it->bounding_box) + reps); + detail::expand_by_epsilon(it->bounding_box); } } @@ -802,6 +803,8 @@ inline void sectionalize(Geometry const& geometry, Reverse, DimensionVector >::apply(geometry, robust_policy, sections, ring_id, max_count); + + detail::sectionalize::enlarge_sections(sections); } diff --git a/boost/geometry/algorithms/overlaps.hpp b/boost/geometry/algorithms/overlaps.hpp index 96310d6cb5..9b5abdb2a0 100644 --- a/boost/geometry/algorithms/overlaps.hpp +++ b/boost/geometry/algorithms/overlaps.hpp @@ -1,11 +1,13 @@ // 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) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015. +// Modifications copyright (c) 2014-2015 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. @@ -14,8 +16,6 @@ // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP #define BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP @@ -31,6 +31,7 @@ #include <boost/geometry/algorithms/relate.hpp> #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp> + namespace boost { namespace geometry { @@ -83,6 +84,7 @@ struct box_box_loop { one_in_two = false; } + // Same other way round if (min2 < min1 || max2 > max1) { diff --git a/boost/geometry/algorithms/touches.hpp b/boost/geometry/algorithms/touches.hpp index d6f0df3c74..570c54797f 100644 --- a/boost/geometry/algorithms/touches.hpp +++ b/boost/geometry/algorithms/touches.hpp @@ -1,12 +1,14 @@ // 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) 2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013, 2014. -// Modifications copyright (c) 2013, 2014, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015, 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. @@ -15,8 +17,6 @@ // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #ifndef BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP #define BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP @@ -40,6 +40,7 @@ #include <boost/geometry/algorithms/relate.hpp> #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp> + namespace boost { namespace geometry { @@ -70,12 +71,12 @@ struct box_box_loop // TODO assert or exception? //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2); - if ( max1 < min2 || max2 < min1 ) + if (max1 < min2 || max2 < min1) { return false; } - if ( max1 == min2 || max2 == min1 ) + if (max1 == min2 || max2 == min1) { touch = true; } @@ -385,6 +386,16 @@ struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, true> template <typename Areal1, typename Areal2, typename Tag1, typename Tag2> struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false> + : detail::relate::relate_impl + < + detail::de9im::static_mask_touches_type, + Areal1, + Areal2 + > +{}; + +template <typename Areal1, typename Areal2> +struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false> : detail::touches::areal_areal<Areal1, Areal2> {}; diff --git a/boost/geometry/algorithms/validity_failure_type.hpp b/boost/geometry/algorithms/validity_failure_type.hpp index 42de99c585..3fbf8027b4 100644 --- a/boost/geometry/algorithms/validity_failure_type.hpp +++ b/boost/geometry/algorithms/validity_failure_type.hpp @@ -78,7 +78,10 @@ enum validity_failure_type /// The top-right corner of the box is lexicographically smaller /// than its bottom-left corner /// (applies to boxes only) - failure_wrong_corner_order = 50 // for boxes + failure_wrong_corner_order = 50, // for boxes + /// The geometry has at least one point with an invalid coordinate + /// (for example, the coordinate is a NaN) + failure_invalid_coordinate = 60 }; diff --git a/boost/geometry/arithmetic/determinant.hpp b/boost/geometry/arithmetic/determinant.hpp index 14edea7182..a8e46ca9a0 100644 --- a/boost/geometry/arithmetic/determinant.hpp +++ b/boost/geometry/arithmetic/determinant.hpp @@ -18,6 +18,8 @@ #include <boost/geometry/geometries/concepts/point_concept.hpp> #include <boost/geometry/util/select_coordinate_type.hpp> +#include <boost/numeric/conversion/cast.hpp> + namespace boost { namespace geometry { diff --git a/boost/geometry/core/exception.hpp b/boost/geometry/core/exception.hpp index 6868ca775a..21abbd577b 100644 --- a/boost/geometry/core/exception.hpp +++ b/boost/geometry/core/exception.hpp @@ -32,6 +32,7 @@ namespace boost { namespace geometry */ class exception : public std::exception { +public: virtual char const* what() const throw() { return "Boost.Geometry exception"; diff --git a/boost/geometry/index/detail/is_bounding_geometry.hpp b/boost/geometry/index/detail/is_bounding_geometry.hpp new file mode 100644 index 0000000000..d14204af71 --- /dev/null +++ b/boost/geometry/index/detail/is_bounding_geometry.hpp @@ -0,0 +1,35 @@ +// Boost.Geometry Index +// +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. +// +// 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_INDEX_DETAIL_IS_BOUNDING_GEOMETRY_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_IS_BOUNDING_GEOMETRY_HPP + +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> + +namespace boost { namespace geometry { namespace index { namespace detail { + +template +< + typename Geometry, + typename Tag = typename geometry::tag<Geometry>::type +> +struct is_bounding_geometry +{ + static const bool value = false; +}; + +template <typename Box> +struct is_bounding_geometry<Box, box_tag> +{ + static const bool value = true; +}; + +}}}} // namespave boost::geometry::index::detail + +#endif // BOOST_GEOMETRY_INDEX_DETAIL_IS_BOUNDING_GEOMETRY_HPP diff --git a/boost/geometry/index/detail/is_indexable.hpp b/boost/geometry/index/detail/is_indexable.hpp new file mode 100644 index 0000000000..1e86463a37 --- /dev/null +++ b/boost/geometry/index/detail/is_indexable.hpp @@ -0,0 +1,47 @@ +// Boost.Geometry Index +// +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. +// +// 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_INDEX_DETAIL_IS_INDEXABLE_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_IS_INDEXABLE_HPP + +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> + +namespace boost { namespace geometry { namespace index { namespace detail { + +template +< + typename Geometry, + typename Tag = typename geometry::tag<Geometry>::type +> +struct is_indexable +{ + static const bool value = false; +}; + +template <typename Point> +struct is_indexable<Point, geometry::point_tag> +{ + static const bool value = true; +}; + +template <typename Box> +struct is_indexable<Box, geometry::box_tag> +{ + static const bool value = true; +}; + +template <typename Segment> +struct is_indexable<Segment, geometry::segment_tag> +{ + static const bool value = true; +}; + +}}}} // namespave boost::geometry::index::detail + +#endif // BOOST_GEOMETRY_INDEX_DETAIL_IS_INDEXABLE_HPP diff --git a/boost/geometry/index/detail/rtree/node/node.hpp b/boost/geometry/index/detail/rtree/node/node.hpp index b04744c85a..2b270319f6 100644 --- a/boost/geometry/index/detail/rtree/node/node.hpp +++ b/boost/geometry/index/detail/rtree/node/node.hpp @@ -34,6 +34,7 @@ #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> #include <boost/geometry/index/detail/algorithms/bounds.hpp> +#include <boost/geometry/index/detail/is_bounding_geometry.hpp> namespace boost { namespace geometry { namespace index { @@ -45,8 +46,16 @@ template <typename Box, typename FwdIter, typename Translator> inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr) { Box result; + + // Only here to suppress 'uninitialized local variable used' warning + // until the suggestion below is not implemented + geometry::assign_inverse(result); - BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required"); + //BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required"); + // NOTE: this is not elegant temporary solution, + // reference to box could be passed as parameter and bool returned + if ( first == last ) + return result; detail::bounds(element_indexable(*first, tr), result); ++first; @@ -57,6 +66,35 @@ inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr) return result; } +// Enlarge bounds of a leaf node WRT epsilon if needed. +// It's because Points and Segments are compared WRT machine epsilon. +// This ensures that leafs bounds correspond to the stored elements. +// NOTE: this is done only if the Indexable is not a Box +// in the future don't do it also for NSphere +template <typename Box, typename FwdIter, typename Translator> +inline Box values_box(FwdIter first, FwdIter last, Translator const& tr) +{ + typedef typename std::iterator_traits<FwdIter>::value_type element_type; + BOOST_MPL_ASSERT_MSG((is_leaf_element<element_type>::value), + SHOULD_BE_CALLED_ONLY_FOR_LEAF_ELEMENTS, + (element_type)); + + Box result = elements_box<Box>(first, last, tr); + +#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON + if (BOOST_GEOMETRY_CONDITION(( + ! is_bounding_geometry + < + typename indexable_type<Translator>::type + >::value))) + { + geometry::detail::expand_by_epsilon(result); + } +#endif + + return result; +} + // destroys subtree if the element is internal node's element template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> struct destroy_element diff --git a/boost/geometry/index/detail/rtree/node/node_elements.hpp b/boost/geometry/index/detail/rtree/node/node_elements.hpp index e3bfb701f8..0e5848987e 100644 --- a/boost/geometry/index/detail/rtree/node/node_elements.hpp +++ b/boost/geometry/index/detail/rtree/node/node_elements.hpp @@ -2,7 +2,7 @@ // // R-tree node elements access // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -12,6 +12,7 @@ #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_ELEMENTS_HPP #include <boost/container/vector.hpp> +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> #include <boost/geometry/index/detail/varray.hpp> #include <boost/geometry/index/detail/rtree/node/pairs.hpp> @@ -36,6 +37,20 @@ struct element_indexable_type< typedef First type; }; +// is leaf element + +template <typename Element> +struct is_leaf_element +{ + static const bool value = true; +}; + +template <typename First, typename Pointer> +struct is_leaf_element< rtree::ptr_pair<First, Pointer> > +{ + static const bool value = false; +}; + // element's indexable getter template <typename Element, typename Translator> diff --git a/boost/geometry/index/detail/rtree/pack_create.hpp b/boost/geometry/index/detail/rtree/pack_create.hpp index ce07d293db..e56ce076d2 100644 --- a/boost/geometry/index/detail/rtree/pack_create.hpp +++ b/boost/geometry/index/detail/rtree/pack_create.hpp @@ -14,6 +14,8 @@ #include <boost/geometry/algorithms/expand.hpp> #include <boost/geometry/index/detail/algorithms/bounds.hpp> +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> + namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace pack_utils { @@ -214,6 +216,11 @@ private: } } + void expand_by_epsilon() + { + geometry::detail::expand_by_epsilon(m_box); + } + BoxType const& get() const { BOOST_GEOMETRY_INDEX_ASSERT(m_initialized, "uninitialized envelope accessed"); @@ -264,6 +271,23 @@ private: rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C) } +#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON + // Enlarge bounds of a leaf node. + // It's because Points and Segments are compared WRT machine epsilon + // This ensures that leafs bounds correspond to the stored elements + // NOTE: this is done only if the Indexable is a different kind of Geometry + // than the bounds (only Box for now). Spatial predicates are checked + // the same way for Geometry of the same kind. + if ( BOOST_GEOMETRY_CONDITION(( + ! index::detail::is_bounding_geometry + < + typename indexable_type<Translator>::type + >::value )) ) + { + elements_box.expand_by_epsilon(); + } +#endif + auto_remover.release(); return internal_element(elements_box.get(), n); } diff --git a/boost/geometry/index/detail/rtree/rstar/insert.hpp b/boost/geometry/index/detail/rtree/rstar/insert.hpp index ce92140872..127290194f 100644 --- a/boost/geometry/index/detail/rtree/rstar/insert.hpp +++ b/boost/geometry/index/detail/rtree/rstar/insert.hpp @@ -2,7 +2,7 @@ // // R-tree R*-tree insert algorithm implementation // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -231,16 +231,28 @@ struct level_insert_base } template <typename Node> - inline void recalculate_aabb_if_necessary(Node &n) const + inline void recalculate_aabb_if_necessary(Node const& n) const { if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() ) { // calulate node's new box - base::m_traverse_data.current_element().first = - elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); + recalculate_aabb(n); } } + template <typename Node> + inline void recalculate_aabb(Node const& n) const + { + base::m_traverse_data.current_element().first = + elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); + } + + inline void recalculate_aabb(leaf const& n) const + { + base::m_traverse_data.current_element().first = + values_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator); + } + size_type result_relative_level; result_elements_type result_elements; }; diff --git a/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp b/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp index d2caa36707..8e0560379b 100644 --- a/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp +++ b/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp @@ -2,7 +2,7 @@ // // R-tree boxes validating visitor implementation // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -60,13 +60,7 @@ public: m_box = box_bckup; m_is_root = is_root_bckup; - Box box_exp; - geometry::convert(elements.front().first, box_exp); - for( typename elements_type::const_iterator it = elements.begin() + 1; - it != elements.end() ; ++it) - { - geometry::expand(box_exp, it->first); - } + Box box_exp = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr); if ( m_exact_match ) result = m_is_root || geometry::equals(box_exp, m_box); @@ -88,15 +82,7 @@ public: return; } - Box box_exp; - geometry::convert( - index::detail::return_ref_or_bounds(m_tr(elements.front())), - box_exp); - for(typename elements_type::const_iterator it = elements.begin() + 1; - it != elements.end() ; ++it) - { - geometry::expand(box_exp, m_tr(*it)); - } + Box box_exp = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr); if ( m_exact_match ) result = geometry::equals(box_exp, m_box); diff --git a/boost/geometry/index/detail/rtree/visitors/children_box.hpp b/boost/geometry/index/detail/rtree/visitors/children_box.hpp index 93726063b4..6c1bafd3de 100644 --- a/boost/geometry/index/detail/rtree/visitors/children_box.hpp +++ b/boost/geometry/index/detail/rtree/visitors/children_box.hpp @@ -2,7 +2,7 @@ // // R-tree node children box calculating visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -40,7 +40,7 @@ public: typedef typename rtree::elements_type<leaf>::type elements_type; elements_type const& elements = rtree::elements(n); - m_result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr); + m_result = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr); } private: diff --git a/boost/geometry/index/detail/rtree/visitors/insert.hpp b/boost/geometry/index/detail/rtree/visitors/insert.hpp index e697c065e1..87d5bbbcca 100644 --- a/boost/geometry/index/detail/rtree/visitors/insert.hpp +++ b/boost/geometry/index/detail/rtree/visitors/insert.hpp @@ -11,6 +11,11 @@ #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_INSERT_HPP +#include <boost/type_traits/is_same.hpp> + +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> +#include <boost/geometry/util/condition.hpp> + #include <boost/geometry/index/detail/algorithms/content.hpp> namespace boost { namespace geometry { namespace index { @@ -262,6 +267,29 @@ protected: BOOST_GEOMETRY_INDEX_ASSERT(0 != m_root_node, "there is no root node"); // TODO // assert - check if Box is correct + + // When a value is inserted, during the tree traversal bounds of nodes + // on a path from the root to a leaf must be expanded. So prepare + // a bounding object at the beginning to not do it later for each node. + // NOTE: This is actually only needed because conditionally the bounding + // object may be expanded below. Otherwise the indexable could be + // directly used instead + index::detail::bounds(rtree::element_indexable(m_element, m_translator), m_element_bounds); + +#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON + // Enlarge it in case if it's not bounding geometry type. + // It's because Points and Segments are compared WRT machine epsilon + // This ensures that leafs bounds correspond to the stored elements + if (BOOST_GEOMETRY_CONDITION(( + boost::is_same<Element, Value>::value + && ! index::detail::is_bounding_geometry + < + typename indexable_type<Translator>::type + >::value )) ) + { + geometry::detail::expand_by_epsilon(m_element_bounds); + } +#endif } template <typename Visitor> @@ -274,7 +302,8 @@ protected: // expand the node to contain value geometry::expand( rtree::elements(n)[choosen_node_index].first, - rtree::element_indexable(m_element, m_translator)); + m_element_bounds + /*rtree::element_indexable(m_element, m_translator)*/); // next traversing step traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc) @@ -342,6 +371,22 @@ protected: // for exception safety subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators); +#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON + // Enlarge bounds of a leaf node. + // It's because Points and Segments are compared WRT machine epsilon + // This ensures that leafs' bounds correspond to the stored elements. + if (BOOST_GEOMETRY_CONDITION(( + boost::is_same<Node, leaf>::value + && ! index::detail::is_bounding_geometry + < + typename indexable_type<Translator>::type + >::value ))) + { + geometry::detail::expand_by_epsilon(n_box); + geometry::detail::expand_by_epsilon(additional_nodes[0].first); + } +#endif + // node is not the root - just add the new node if ( !m_traverse_data.current_is_root() ) { @@ -383,6 +428,7 @@ protected: // TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation Element const& m_element; + Box m_element_bounds; parameters_type const& m_parameters; Translator const& m_translator; size_type const m_relative_level; diff --git a/boost/geometry/index/detail/rtree/visitors/remove.hpp b/boost/geometry/index/detail/rtree/visitors/remove.hpp index 494d5a019e..6326f87db6 100644 --- a/boost/geometry/index/detail/rtree/visitors/remove.hpp +++ b/boost/geometry/index/detail/rtree/visitors/remove.hpp @@ -97,6 +97,9 @@ public: size_type relative_level = m_leafs_level - m_current_level; // move node to the container - store node's relative level as well and return new underflow state + // NOTE: if the min elements number is 1, then after an underflow + // here the child elements count is 0, so it's not required to store this node, + // it could just be destroyed m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy) } @@ -120,10 +123,16 @@ public: reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc) // shorten the tree - if ( rtree::elements(n).size() == 1 ) + // NOTE: if the min elements number is 1, then after underflow + // here the number of elements may be equal to 0 + // this can occur only for the last removed element + if ( rtree::elements(n).size() <= 1 ) { node_pointer root_to_destroy = m_root_node; - m_root_node = rtree::elements(n)[0].second; + if ( rtree::elements(n).size() == 0 ) + m_root_node = 0; + else + m_root_node = rtree::elements(n)[0].second; --m_leafs_level; rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, root_to_destroy); @@ -161,7 +170,7 @@ public: if ( 0 != m_parent ) { rtree::elements(*m_parent)[m_current_child_index].first - = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator); + = rtree::values_box<Box>(elements.begin(), elements.end(), m_translator); } } } diff --git a/boost/geometry/index/indexable.hpp b/boost/geometry/index/indexable.hpp index 391b544f37..feaae557af 100644 --- a/boost/geometry/index/indexable.hpp +++ b/boost/geometry/index/indexable.hpp @@ -1,6 +1,6 @@ // Boost.Geometry Index // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -11,30 +11,9 @@ #include <boost/mpl/assert.hpp> -namespace boost { namespace geometry { namespace index { namespace detail { - -template <typename Geometry, typename GeometryTag> -struct is_indexable_impl { static const bool value = false; }; - -template <typename Point> -struct is_indexable_impl<Point, geometry::point_tag> { static const bool value = true; }; - -template <typename Box> -struct is_indexable_impl<Box, geometry::box_tag> { static const bool value = true; }; +#include <boost/geometry/index/detail/is_indexable.hpp> -template <typename Segment> -struct is_indexable_impl<Segment, geometry::segment_tag> { static const bool value = true; }; - -template <typename Indexable> -struct is_indexable -{ - static const bool value = - is_indexable_impl - < - Indexable, - typename geometry::tag<Indexable>::type - >::value; -}; +namespace boost { namespace geometry { namespace index { namespace detail { /*! \brief The function object extracting Indexable from Value. diff --git a/boost/geometry/index/rtree.hpp b/boost/geometry/index/rtree.hpp index 84c4da8a2a..ea7fc74ed3 100644 --- a/boost/geometry/index/rtree.hpp +++ b/boost/geometry/index/rtree.hpp @@ -627,6 +627,9 @@ public: template <typename ConvertibleOrRange> inline void insert(ConvertibleOrRange const& conv_or_rng) { + if ( !m_members.root ) + this->raw_create(); + typedef boost::mpl::bool_ < boost::is_convertible<ConvertibleOrRange, value_type>::value @@ -657,6 +660,9 @@ public: */ inline size_type remove(value_type const& value) { + if ( !m_members.root ) + return 0; + return this->raw_remove(value); } @@ -687,6 +693,10 @@ public: inline size_type remove(Iterator first, Iterator last) { size_type result = 0; + + if ( !m_members.root ) + return result; + for ( ; first != last ; ++first ) result += this->raw_remove(*first); return result; @@ -716,6 +726,9 @@ public: template <typename ConvertibleOrRange> inline size_type remove(ConvertibleOrRange const& conv_or_rng) { + if ( !m_members.root ) + return 0; + typedef boost::mpl::bool_ < boost::is_convertible<ConvertibleOrRange, value_type>::value @@ -1279,6 +1292,9 @@ public: template <typename ValueOrIndexable> size_type count(ValueOrIndexable const& vori) const { + if ( !m_members.root ) + return 0; + // the input should be convertible to Value or Indexable type enum { as_val = 0, as_ind, dont_know }; @@ -1570,9 +1586,6 @@ private: inline void insert_dispatch(ValueConvertible const& val_conv, boost::mpl::bool_<true> const& /*is_convertible*/) { - if ( !m_members.root ) - this->raw_create(); - this->raw_insert(val_conv); } @@ -1592,9 +1605,6 @@ private: PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE, (Range)); - if ( !m_members.root ) - this->raw_create(); - typedef typename boost::range_const_iterator<Range>::type It; for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it ) this->raw_insert(*it); @@ -1664,6 +1674,8 @@ private: template <typename Predicates, typename OutIter> size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const { + BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist"); + static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value; detail::rtree::visitors::distance_query< value_type, @@ -1690,8 +1702,7 @@ private: template <typename ValueOrIndexable> size_type raw_count(ValueOrIndexable const& vori) const { - if ( !m_members.root ) - return 0; + BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist"); detail::rtree::visitors::count < diff --git a/boost/geometry/policies/is_valid/failing_reason_policy.hpp b/boost/geometry/policies/is_valid/failing_reason_policy.hpp index d1918adbda..bb28091d98 100644 --- a/boost/geometry/policies/is_valid/failing_reason_policy.hpp +++ b/boost/geometry/policies/is_valid/failing_reason_policy.hpp @@ -54,6 +54,8 @@ inline char const* validity_failure_type_message(validity_failure_type failure) return "Geometry has duplicate (consecutive) points"; case failure_wrong_corner_order: return "Box has corners in wrong order"; + case failure_invalid_coordinate: + return "Geometry has point(s) with invalid coordinate(s)"; default: // to avoid -Wreturn-type warning return ""; } diff --git a/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp b/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp index 99e7d9b50f..053723e4cc 100644 --- a/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp +++ b/boost/geometry/strategies/agnostic/simplify_douglas_peucker.hpp @@ -308,7 +308,7 @@ public : namespace traits { template <typename P> -struct point_type<strategy::simplify::detail::douglas_peucker_point<P> > +struct point_type<geometry::strategy::simplify::detail::douglas_peucker_point<P> > { typedef P type; }; diff --git a/boost/geometry/strategies/cartesian/box_in_box.hpp b/boost/geometry/strategies/cartesian/box_in_box.hpp index 9889658a13..56aef9e4df 100644 --- a/boost/geometry/strategies/cartesian/box_in_box.hpp +++ b/boost/geometry/strategies/cartesian/box_in_box.hpp @@ -1,9 +1,14 @@ // 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) 2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, 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. @@ -32,10 +37,10 @@ namespace within struct box_within_range { template <typename BoxContainedValue, typename BoxContainingValue> - static inline bool apply(BoxContainedValue const& bed_min - , BoxContainedValue const& bed_max - , BoxContainingValue const& bing_min - , BoxContainingValue const& bing_max) + static inline bool apply(BoxContainedValue const& bed_min, + BoxContainedValue const& bed_max, + BoxContainingValue const& bing_min, + BoxContainingValue const& bing_max) { return bing_min <= bed_min && bed_max <= bing_max // contained in containing && bed_min < bed_max; // interiors overlap @@ -46,10 +51,10 @@ struct box_within_range struct box_covered_by_range { template <typename BoxContainedValue, typename BoxContainingValue> - static inline bool apply(BoxContainedValue const& bed_min - , BoxContainedValue const& bed_max - , BoxContainingValue const& bing_min - , BoxContainingValue const& bing_max) + static inline bool apply(BoxContainedValue const& bed_min, + BoxContainedValue const& bed_max, + BoxContainingValue const& bing_min, + BoxContainingValue const& bing_max) { return bed_min >= bing_min && bed_max <= bing_max; } diff --git a/boost/geometry/strategies/cartesian/point_in_box.hpp b/boost/geometry/strategies/cartesian/point_in_box.hpp index 79f094113d..bd2303cbc4 100644 --- a/boost/geometry/strategies/cartesian/point_in_box.hpp +++ b/boost/geometry/strategies/cartesian/point_in_box.hpp @@ -1,8 +1,13 @@ // 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) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, 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. diff --git a/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp b/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp index 14c5bd4eda..59be3645f5 100644 --- a/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp +++ b/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp @@ -161,7 +161,7 @@ public: } } - // Otherwise determine which αμονγ the two medirian segments of the + // Otherwise determine which among the two medirian segments of the // box the point is closest to, and compute the distance of // the point to this closest segment diff --git a/boost/geometry/strategies/transform/inverse_transformer.hpp b/boost/geometry/strategies/transform/inverse_transformer.hpp index 685cf874b8..e64a46e4a8 100644 --- a/boost/geometry/strategies/transform/inverse_transformer.hpp +++ b/boost/geometry/strategies/transform/inverse_transformer.hpp @@ -16,6 +16,9 @@ // Remove the ublas checking, otherwise the inverse might fail // (while nothing seems to be wrong) +#ifdef BOOST_UBLAS_TYPE_CHECK +#undef BOOST_UBLAS_TYPE_CHECK +#endif #define BOOST_UBLAS_TYPE_CHECK 0 #include <boost/numeric/ublas/lu.hpp> diff --git a/boost/geometry/strategies/transform/matrix_transformers.hpp b/boost/geometry/strategies/transform/matrix_transformers.hpp index 699b91b3aa..d891263a7d 100644 --- a/boost/geometry/strategies/transform/matrix_transformers.hpp +++ b/boost/geometry/strategies/transform/matrix_transformers.hpp @@ -24,6 +24,9 @@ // Remove the ublas checking, otherwise the inverse might fail // (while nothing seems to be wrong) +#ifdef BOOST_UBLAS_TYPE_CHECK +#undef BOOST_UBLAS_TYPE_CHECK +#endif #define BOOST_UBLAS_TYPE_CHECK 0 #include <boost/numeric/conversion/cast.hpp> diff --git a/boost/geometry/util/has_infinite_coordinate.hpp b/boost/geometry/util/has_infinite_coordinate.hpp new file mode 100644 index 0000000000..3f1d11a3b0 --- /dev/null +++ b/boost/geometry/util/has_infinite_coordinate.hpp @@ -0,0 +1,55 @@ +// Boost.Geometry + +// Copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// 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_UTIL_HAS_INFINITE_COORDINATE_HPP +#define BOOST_GEOMETRY_UTIL_HAS_INFINITE_COORDINATE_HPP + +#include <boost/type_traits/is_floating_point.hpp> + +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/util/has_nan_coordinate.hpp> +#include <boost/math/special_functions/fpclassify.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail +{ + +struct isinf +{ + template <typename T> + static inline bool apply(T const& t) + { + return boost::math::isinf(t); + } +}; + +} // namespace detail +#endif // DOXYGEN_NO_DETAIL + +template <typename Point> +bool has_infinite_coordinate(Point const& point) +{ + return detail::has_coordinate_with_property + < + Point, + detail::isinf, + boost::is_floating_point + < + typename coordinate_type<Point>::type + >::value + >::apply(point); +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_UTIL_HAS_INFINITE_COORDINATE_HPP diff --git a/boost/geometry/util/has_nan_coordinate.hpp b/boost/geometry/util/has_nan_coordinate.hpp new file mode 100644 index 0000000000..93d7c7f035 --- /dev/null +++ b/boost/geometry/util/has_nan_coordinate.hpp @@ -0,0 +1,99 @@ +// Boost.Geometry + +// Copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// 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_UTIL_HAS_NAN_COORDINATE_HPP +#define BOOST_GEOMETRY_UTIL_HAS_NAN_COORDINATE_HPP + +#include <cstddef> + +#include <boost/type_traits/is_floating_point.hpp> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_type.hpp> + +#include <boost/math/special_functions/fpclassify.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail +{ + +struct isnan +{ + template <typename T> + static inline bool apply(T const& t) + { + return boost::math::isnan(t); + } +}; + +template +< + typename Point, + typename Predicate, + bool Enable, + std::size_t I = 0, + std::size_t N = geometry::dimension<Point>::value +> +struct has_coordinate_with_property +{ + static bool apply(Point const& point) + { + return Predicate::apply(geometry::get<I>(point)) + || has_coordinate_with_property + < + Point, Predicate, Enable, I+1, N + >::apply(point); + } +}; + +template <typename Point, typename Predicate, std::size_t I, std::size_t N> +struct has_coordinate_with_property<Point, Predicate, false, I, N> +{ + static inline bool apply(Point const&) + { + return false; + } +}; + +template <typename Point, typename Predicate, std::size_t N> +struct has_coordinate_with_property<Point, Predicate, true, N, N> +{ + static bool apply(Point const& ) + { + return false; + } +}; + +} // namespace detail +#endif // DOXYGEN_NO_DETAIL + +template <typename Point> +bool has_nan_coordinate(Point const& point) +{ + return detail::has_coordinate_with_property + < + Point, + detail::isnan, + boost::is_floating_point + < + typename coordinate_type<Point>::type + >::value + >::apply(point); +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_UTIL_HAS_NAN_COORDINATE_HPP diff --git a/boost/geometry/util/has_non_finite_coordinate.hpp b/boost/geometry/util/has_non_finite_coordinate.hpp new file mode 100644 index 0000000000..50075641ed --- /dev/null +++ b/boost/geometry/util/has_non_finite_coordinate.hpp @@ -0,0 +1,55 @@ +// Boost.Geometry + +// Copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// 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_UTIL_HAS_NON_FINITE_COORDINATE_HPP +#define BOOST_GEOMETRY_UTIL_HAS_NON_FINITE_COORDINATE_HPP + +#include <boost/type_traits/is_floating_point.hpp> + +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/util/has_nan_coordinate.hpp> +#include <boost/math/special_functions/fpclassify.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail +{ + +struct is_not_finite +{ + template <typename T> + static inline bool apply(T const& t) + { + return ! boost::math::isfinite(t); + } +}; + +} // namespace detail +#endif // DOXYGEN_NO_DETAIL + +template <typename Point> +bool has_non_finite_coordinate(Point const& point) +{ + return detail::has_coordinate_with_property + < + Point, + detail::is_not_finite, + boost::is_floating_point + < + typename coordinate_type<Point>::type + >::value + >::apply(point); +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_UTIL_HAS_NON_FINITE_COORDINATE_HPP diff --git a/boost/geometry/util/math.hpp b/boost/geometry/util/math.hpp index d84b11f480..c193c8f3f1 100644 --- a/boost/geometry/util/math.hpp +++ b/boost/geometry/util/math.hpp @@ -201,11 +201,36 @@ struct smaller<Type, true> { static inline bool apply(Type const& a, Type const& b) { - if (equals<Type, true>::apply(a, b, equals_default_policy())) + if (!(a < b)) // a >= b { return false; } - return a < b; + + return ! equals<Type, true>::apply(b, a, equals_default_policy()); + } +}; + +template <typename Type, + bool IsFloatingPoint = boost::is_floating_point<Type>::value> +struct smaller_or_equals +{ + static inline bool apply(Type const& a, Type const& b) + { + return a <= b; + } +}; + +template <typename Type> +struct smaller_or_equals<Type, true> +{ + static inline bool apply(Type const& a, Type const& b) + { + if (a <= b) + { + return true; + } + + return equals<Type, true>::apply(a, b, equals_default_policy()); } }; @@ -407,6 +432,30 @@ struct relaxed_epsilon } }; +// This must be consistent with math::equals. +// By default math::equals() scales the error by epsilon using the greater of +// compared values but here is only one value, though it should work the same way. +// (a-a) <= max(a, a) * EPS -> 0 <= a*EPS +// (a+da-a) <= max(a+da, a) * EPS -> da <= (a+da)*EPS +template <typename T, bool IsFloat = boost::is_floating_point<T>::value> +struct scaled_epsilon +{ + static inline T apply(T const& val) + { + return (std::max)(abs<T>::apply(val), T(1)) + * std::numeric_limits<T>::epsilon(); + } +}; + +template <typename T> +struct scaled_epsilon<T, false> +{ + static inline T apply(T const&) + { + return T(0); + } +}; + // ItoF ItoI FtoF template <typename Result, typename Source, bool ResultIsInteger = std::numeric_limits<Result>::is_integer, @@ -460,6 +509,12 @@ inline T relaxed_epsilon(T const& factor) return detail::relaxed_epsilon<T>::apply(factor); } +template <typename T> +inline T scaled_epsilon(T const& value) +{ + return detail::scaled_epsilon<T>::apply(value); +} + // Maybe replace this by boost equals or boost ublas numeric equals or so @@ -512,6 +567,24 @@ inline bool larger(T1 const& a, T2 const& b) >::apply(b, a); } +template <typename T1, typename T2> +inline bool smaller_or_equals(T1 const& a, T2 const& b) +{ + return detail::smaller_or_equals + < + typename select_most_precise<T1, T2>::type + >::apply(a, b); +} + +template <typename T1, typename T2> +inline bool larger_or_equals(T1 const& a, T2 const& b) +{ + return detail::smaller_or_equals + < + typename select_most_precise<T1, T2>::type + >::apply(b, a); +} + template <typename T> inline T d2r() |