diff options
Diffstat (limited to 'boost/geometry/algorithms')
56 files changed, 2292 insertions, 878 deletions
diff --git a/boost/geometry/algorithms/correct.hpp b/boost/geometry/algorithms/correct.hpp index a572d921d5..07e012fafa 100644 --- a/boost/geometry/algorithms/correct.hpp +++ b/boost/geometry/algorithms/correct.hpp @@ -32,6 +32,7 @@ #include <boost/variant/static_visitor.hpp> #include <boost/variant/variant_fwd.hpp> +#include <boost/geometry/algorithms/correct_closure.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> #include <boost/geometry/core/closure.hpp> @@ -45,7 +46,6 @@ #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/algorithms/area.hpp> -#include <boost/geometry/algorithms/disjoint.hpp> #include <boost/geometry/algorithms/detail/multi_modify.hpp> #include <boost/geometry/util/order_as_direction.hpp> @@ -140,23 +140,9 @@ struct correct_ring template <typename Strategy> static inline void apply(Ring& r, Strategy const& strategy) { - // Check close-ness - if (boost::size(r) > 2) - { - // check if closed, if not, close it - bool const disjoint = geometry::disjoint(*boost::begin(r), *(boost::end(r) - 1)); - closure_selector const s = geometry::closure<Ring>::value; - - if (disjoint && (s == closed)) - { - geometry::append(r, *boost::begin(r)); - } - if (! disjoint && s != closed) - { - // Open it by removing last point - geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1); - } - } + // Correct closure if necessary + detail::correct_closure::close_or_open_ring<Ring>::apply(r); + // Check area typedef typename Strategy::return_type area_result_type; Predicate<area_result_type> predicate; diff --git a/boost/geometry/algorithms/correct_closure.hpp b/boost/geometry/algorithms/correct_closure.hpp new file mode 100644 index 0000000000..323107f23a --- /dev/null +++ b/boost/geometry/algorithms/correct_closure.hpp @@ -0,0 +1,235 @@ +// Boost.Geometry + +// Copyright (c) 2017 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_CORRECT_CLOSURE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_CORRECT_CLOSURE_HPP + +#include <cstddef> + +#include <boost/range.hpp> + +#include <boost/variant/apply_visitor.hpp> +#include <boost/variant/static_visitor.hpp> +#include <boost/variant/variant_fwd.hpp> + +#include <boost/geometry/algorithms/detail/interior_iterator.hpp> + +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/interior_rings.hpp> +#include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/geometries/concepts/check.hpp> + +#include <boost/geometry/algorithms/disjoint.hpp> +#include <boost/geometry/algorithms/detail/multi_modify.hpp> + +namespace boost { namespace geometry +{ + +// Silence warning C4127: conditional expression is constant +#if defined(_MSC_VER) +#pragma warning(push) +#pragma warning(disable : 4127) +#endif + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace correct_closure +{ + +template <typename Geometry> +struct nop +{ + static inline void apply(Geometry& ) + {} +}; + + +// Close a ring, if not closed, or open it +template <typename Ring> +struct close_or_open_ring +{ + static inline void apply(Ring& r) + { + if (boost::size(r) <= 2) + { + return; + } + + bool const disjoint = geometry::disjoint(*boost::begin(r), + *(boost::end(r) - 1)); + closure_selector const s = geometry::closure<Ring>::value; + + if (disjoint && s == closed) + { + // Close it by adding first point + geometry::append(r, *boost::begin(r)); + } + else if (! disjoint && s != closed) + { + // Open it by removing last point + geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1); + } + } +}; + +// Close/open exterior ring and all its interior rings +template <typename Polygon> +struct close_or_open_polygon +{ + typedef typename ring_type<Polygon>::type ring_type; + + static inline void apply(Polygon& poly) + { + close_or_open_ring<ring_type>::apply(exterior_ring(poly)); + + typename interior_return_type<Polygon>::type + rings = interior_rings(poly); + + for (typename detail::interior_iterator<Polygon>::type + it = boost::begin(rings); it != boost::end(rings); ++it) + { + close_or_open_ring<ring_type>::apply(*it); + } + } +}; + +}} // namespace detail::correct_closure +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct correct_closure: not_implemented<Tag> +{}; + +template <typename Point> +struct correct_closure<Point, point_tag> + : detail::correct_closure::nop<Point> +{}; + +template <typename LineString> +struct correct_closure<LineString, linestring_tag> + : detail::correct_closure::nop<LineString> +{}; + +template <typename Segment> +struct correct_closure<Segment, segment_tag> + : detail::correct_closure::nop<Segment> +{}; + + +template <typename Box> +struct correct_closure<Box, box_tag> + : detail::correct_closure::nop<Box> +{}; + +template <typename Ring> +struct correct_closure<Ring, ring_tag> + : detail::correct_closure::close_or_open_ring<Ring> +{}; + +template <typename Polygon> +struct correct_closure<Polygon, polygon_tag> + : detail::correct_closure::close_or_open_polygon<Polygon> +{}; + + +template <typename MultiPoint> +struct correct_closure<MultiPoint, multi_point_tag> + : detail::correct_closure::nop<MultiPoint> +{}; + + +template <typename MultiLineString> +struct correct_closure<MultiLineString, multi_linestring_tag> + : detail::correct_closure::nop<MultiLineString> +{}; + + +template <typename Geometry> +struct correct_closure<Geometry, multi_polygon_tag> + : detail::multi_modify + < + Geometry, + detail::correct_closure::close_or_open_polygon + < + typename boost::range_value<Geometry>::type + > + > +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +namespace resolve_variant +{ + +template <typename Geometry> +struct correct_closure +{ + static inline void apply(Geometry& geometry) + { + concepts::check<Geometry const>(); + dispatch::correct_closure<Geometry>::apply(geometry); + } +}; + +template <BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct correct_closure<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + struct visitor: boost::static_visitor<void> + { + template <typename Geometry> + void operator()(Geometry& geometry) const + { + correct_closure<Geometry>::apply(geometry); + } + }; + + static inline void + apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry) + { + visitor vis; + boost::apply_visitor(vis, geometry); + } +}; + +} // namespace resolve_variant + + +/*! +\brief Closes or opens a geometry, according to its type +\details Corrects a geometry w.r.t. closure points to all rings which do not + have a closing point and are typed as they should have one, the first point + is appended. +\ingroup correct_closure +\tparam Geometry \tparam_geometry +\param geometry \param_geometry which will be corrected if necessary +*/ +template <typename Geometry> +inline void correct_closure(Geometry& geometry) +{ + resolve_variant::correct_closure<Geometry>::apply(geometry); +} + + +#if defined(_MSC_VER) +#pragma warning(pop) +#endif + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_CLOSURE_HPP diff --git a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp index a149f1dd46..990081a86c 100644 --- a/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp @@ -243,6 +243,7 @@ struct buffer_range EndStrategy const& end_strategy, RobustPolicy const& robust_policy, Strategy const& strategy, // side strategy + bool linear, output_point_type& first_p1, output_point_type& first_p2, output_point_type& last_p1, @@ -274,6 +275,10 @@ struct buffer_range * pup: penultimate_point */ + bool const mark_flat + = linear + && end_strategy.get_piece_type() == geometry::strategy::buffer::buffered_flat_end; + geometry::strategy::buffer::result_code result = geometry::strategy::buffer::result_no_output; bool first = true; @@ -318,6 +323,11 @@ struct buffer_range collection.add_side_piece(*prev, *it, generated_side, first); + if (first && mark_flat) + { + collection.mark_flat_start(); + } + penultimate_point = *prev; ultimate_point = *it; last_p1 = generated_side.front(); @@ -331,6 +341,12 @@ struct buffer_range first_p2 = generated_side.back(); } } + + if (mark_flat) + { + collection.mark_flat_end(); + } + return result; } }; @@ -396,7 +412,7 @@ inline void buffer_point(Point const& point, Collection& collection, DistanceStrategy const& distance_strategy, PointStrategy const& point_strategy) { - collection.start_new_ring(); + collection.start_new_ring(false); std::vector<OutputPointType> range_out; point_strategy.apply(point, distance_strategy, range_out); collection.add_piece(geometry::strategy::buffer::buffered_point, range_out, false); @@ -499,7 +515,7 @@ struct buffer_inserter_ring side, distance_strategy, side_strategy, join_strategy, end_strategy, robust_policy, strategy, - first_p1, first_p2, last_p1, last_p2); + false, first_p1, first_p2, last_p1, last_p2); // Generate closing join if (result == geometry::strategy::buffer::result_normal) @@ -611,7 +627,7 @@ struct buffer_inserter<ring_tag, RingInput, RingOutput> RobustPolicy const& robust_policy, Strategy const& strategy) // side strategy { - collection.start_new_ring(); + collection.start_new_ring(distance.negative()); geometry::strategy::buffer::result_code const code = buffer_inserter_ring<RingInput, RingOutput>::apply(ring, collection, distance, @@ -689,7 +705,7 @@ struct buffer_inserter<linestring_tag, Linestring, Polygon> begin, end, side, distance_strategy, side_strategy, join_strategy, end_strategy, robust_policy, strategy, - first_p1, first_p2, last_p1, last_p2); + true, first_p1, first_p2, last_p1, last_p2); if (result == geometry::strategy::buffer::result_normal) { @@ -729,7 +745,7 @@ struct buffer_inserter<linestring_tag, Linestring, Polygon> std::size_t n = boost::size(simplified); if (n > 1) { - collection.start_new_ring(); + collection.start_new_ring(false); output_point_type first_p1; code = iterate(collection, boost::begin(simplified), boost::end(simplified), @@ -803,7 +819,13 @@ private: { for (Iterator it = begin; it != end; ++it) { - collection.start_new_ring(); + // For exterior rings, it deflates if distance is negative. + // For interior rings, it is vice versa + bool const deflate = is_interior + ? ! distance.negative() + : distance.negative(); + + collection.start_new_ring(deflate); geometry::strategy::buffer::result_code const code = policy::apply(*it, collection, distance, side_strategy, join_strategy, end_strategy, point_strategy, @@ -865,7 +887,7 @@ public: Strategy const& strategy) // side strategy { { - collection.start_new_ring(); + collection.start_new_ring(distance.negative()); geometry::strategy::buffer::result_code const code = policy::apply(exterior_ring(polygon), collection, @@ -956,11 +978,6 @@ inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator typename tag_cast<typename tag<GeometryInput>::type, areal_tag>::type, areal_tag >::type::value; - bool const linear = boost::is_same - < - typename tag_cast<typename tag<GeometryInput>::type, linear_tag>::type, - linear_tag - >::type::value; dispatch::buffer_inserter < @@ -977,7 +994,7 @@ inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator robust_policy, intersection_strategy.get_side_strategy()); collection.get_turns(); - collection.classify_turns(linear); + collection.classify_turns(); if (BOOST_GEOMETRY_CONDITION(areal)) { collection.check_remaining_points(distance_strategy); diff --git a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp index c0d906fe62..bc9c1ca7fb 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp @@ -46,6 +46,7 @@ #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> +#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp> #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -216,7 +217,10 @@ struct buffered_piece_collection // 2: half, not part of offsetted rings - part of robust ring std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end #endif + bool is_flat_start; + bool is_flat_end; + bool is_deflated; bool is_convex; bool is_monotonic_increasing[2]; // 0=x, 1=y bool is_monotonic_decreasing[2]; // 0=x, 1=y @@ -244,6 +248,9 @@ struct buffered_piece_collection , right_index(-1) , last_segment_index(-1) , offsetted_count(-1) + , is_flat_start(false) + , is_flat_end(false) + , is_deflated(false) , is_convex(false) , robust_min_comparable_radius(0) , robust_max_comparable_radius(0) @@ -295,6 +302,8 @@ struct buffered_piece_collection piece_vector_type m_pieces; turn_vector_type m_turns; signed_size_type m_first_piece_index; + bool m_deflate; + bool m_has_deflated; buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index std::vector<robust_original> robust_originals; // robust representation of the original(s) @@ -333,6 +342,8 @@ struct buffered_piece_collection buffered_piece_collection(IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy) : m_first_piece_index(-1) + , m_deflate(false) + , m_has_deflated(false) , m_intersection_strategy(intersection_strategy) , m_side_strategy(intersection_strategy.get_side_strategy()) , m_area_strategy(intersection_strategy.template get_area_strategy<point_type>()) @@ -498,7 +509,7 @@ struct buffered_piece_collection } } - inline void classify_turns(bool linear) + inline void classify_turns() { for (typename boost::range_iterator<turn_vector_type>::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) @@ -507,7 +518,7 @@ struct buffered_piece_collection { it->location = inside_buffer; } - if (it->count_on_original_boundary > 0 && ! linear) + if (it->count_on_original_boundary > 0) { it->location = inside_buffer; } @@ -524,6 +535,90 @@ struct buffered_piece_collection } } + struct deflate_properties + { + bool has_inflated; + std::size_t count; + + inline deflate_properties() + : has_inflated(false) + , count(0u) + {} + }; + + inline void discard_turns_for_deflate() + { + // Deflate cases should have at least 3 points PER deflated original + // to form a correct triangle + + // But if there are intersections between a deflated ring and another + // ring, it is all accepted + + // In deflate most turns are i/u by nature, but u/u is also possible + + std::map<signed_size_type, deflate_properties> properties; + + for (typename boost::range_iterator<turn_vector_type const>::type it = + boost::begin(m_turns); it != boost::end(m_turns); ++it) + { + const buffer_turn_info_type& turn = *it; + if (turn.location == location_ok) + { + const buffer_turn_operation_type& op0 = turn.operations[0]; + const buffer_turn_operation_type& op1 = turn.operations[1]; + + if (! m_pieces[op0.seg_id.piece_index].is_deflated + || ! m_pieces[op1.seg_id.piece_index].is_deflated) + { + properties[op0.seg_id.multi_index].has_inflated = true; + properties[op1.seg_id.multi_index].has_inflated = true; + continue; + } + + // It is deflated, update counts + for (int i = 0; i < 2; i++) + { + const buffer_turn_operation_type& op = turn.operations[i]; + if (op.operation == detail::overlay::operation_union + || op.operation == detail::overlay::operation_continue) + { + properties[op.seg_id.multi_index].count++; + } + } + } + } + + for (typename boost::range_iterator<turn_vector_type>::type it = + boost::begin(m_turns); it != boost::end(m_turns); ++it) + { + buffer_turn_info_type& turn = *it; + + if (turn.location == location_ok) + { + const buffer_turn_operation_type& op0 = turn.operations[0]; + const buffer_turn_operation_type& op1 = turn.operations[1]; + signed_size_type const multi0 = op0.seg_id.multi_index; + signed_size_type const multi1 = op1.seg_id.multi_index; + + if (multi0 == multi1) + { + const deflate_properties& prop = properties[multi0]; + if (! prop.has_inflated && prop.count < 3) + { + // Property is not inflated + // Not enough points, this might be caused by <float> where + // detection turn-in-original failed because of numeric errors + turn.location = location_discard; + } + } + else + { + // Two different (possibly deflated) rings + } + } + } + } + template <typename DistanceStrategy> inline void check_remaining_points(DistanceStrategy const& distance_strategy) { @@ -549,7 +644,7 @@ struct buffered_piece_collection { if (deflate && turn.count_in_original <= 0) { - // For deflate: it is not in original, discard + // For deflate/negative buffers: it is not in original, discard turn.location = location_discard; } else if (! deflate && turn.count_in_original > 0) @@ -559,6 +654,12 @@ struct buffered_piece_collection } } } + + if (m_has_deflated) + { + // Either strategy was negative, or there were interior rings + discard_turns_for_deflate(); + } } inline bool assert_indices_in_robust_rings() const @@ -827,7 +928,7 @@ struct buffered_piece_collection } } - inline void start_new_ring() + inline void start_new_ring(bool deflate) { signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size()); current_segment_id.source_index = 0; @@ -839,6 +940,13 @@ struct buffered_piece_collection current_robust_ring.clear(); m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces)); + m_deflate = deflate; + if (deflate) + { + // Pieces contain either deflated exterior rings, or inflated + // interior rings which are effectively deflated too + m_has_deflated = true; + } } inline void abort_ring() @@ -973,12 +1081,12 @@ struct buffered_piece_collection piece pc; pc.type = type; pc.index = static_cast<signed_size_type>(boost::size(m_pieces)); + pc.is_deflated = m_deflate; current_segment_id.piece_index = pc.index; pc.first_seg_id = current_segment_id; - // Assign left/right (for first/last piece per ring they will be re-assigned later) pc.left_index = pc.index - 1; pc.right_index = pc.index + 1; @@ -1232,6 +1340,24 @@ struct buffered_piece_collection } } + inline void mark_flat_start() + { + if (! m_pieces.empty()) + { + piece& back = m_pieces.back(); + back.is_flat_start = true; + } + } + + inline void mark_flat_end() + { + if (! m_pieces.empty()) + { + piece& back = m_pieces.back(); + back.is_flat_end = true; + } + } + //------------------------------------------------------------------------- inline void enrich() @@ -1369,12 +1495,14 @@ struct buffered_piece_collection overlay_buffer, backtrack_for_buffer > traverser; + std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring; traversed_rings.clear(); buffer_overlay_visitor visitor; traverser::apply(offsetted_rings, offsetted_rings, m_intersection_strategy, m_robust_policy, m_turns, traversed_rings, + turn_info_per_ring, m_clusters, visitor); } @@ -1442,8 +1570,12 @@ struct buffered_piece_collection } } - detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, m_intersection_strategy, true); - return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out); + // Assign parents, checking orientation but NOT discarding double + // negative rings (negative child with negative parent) + detail::overlay::assign_parents(offsetted_rings, traversed_rings, + selected, m_intersection_strategy, true, false); + return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out, + m_area_strategy); } }; diff --git a/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp b/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp index d23a3b3fd6..29e49f9dae 100644 --- a/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp +++ b/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp @@ -311,7 +311,11 @@ class analyse_turn_wrt_piece template <typename Point, typename Turn> static inline analyse_result check_helper_segment(Point const& s1, Point const& s2, Turn const& turn, +#if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) + bool , // is on original, to be reused +#else bool is_original, +#endif Point const& offsetted) { boost::ignore_unused(offsetted); @@ -340,11 +344,9 @@ class analyse_turn_wrt_piece if (geometry::covered_by(turn.robust_point, box)) { - // Points on helper-segments are considered as within - // Points on original boundary are processed differently - return is_original - ? analyse_on_original_boundary - : analyse_within; + // Points on helper-segments (and not on its corners) + // are considered as within + return analyse_within; } // It is collinear but not on the segment. Because these @@ -424,6 +426,13 @@ class analyse_turn_wrt_piece { points[i] = piece.robust_ring[piece.offsetted_count + i]; } + + // 3--offsetted outline--0 + // | | + // left | | right + // | | + // 2===>==original===>===1 + } else if (helper_count == 3) { @@ -447,9 +456,15 @@ class analyse_turn_wrt_piece { return analyse_on_offsetted; } - if (comparator(point, points[1]) || comparator(point, points[2])) + if (comparator(point, points[1])) + { + // On original, right corner + return piece.is_flat_end ? analyse_continue : analyse_on_original_boundary; + } + if (comparator(point, points[2])) { - return analyse_on_original_boundary; + // On original, left corner + return piece.is_flat_start ? analyse_continue : analyse_on_original_boundary; } // Right side of the piece diff --git a/boost/geometry/algorithms/detail/direction_code.hpp b/boost/geometry/algorithms/detail/direction_code.hpp index c5c5221109..3a7d3d8789 100644 --- a/boost/geometry/algorithms/detail/direction_code.hpp +++ b/boost/geometry/algorithms/detail/direction_code.hpp @@ -114,7 +114,9 @@ struct direction_code_impl<Point, spherical_equatorial_tag> typedef typename geometry::select_coordinate_type <Point1, Point2>::type calc_t; typedef math::detail::constants_on_spheroid<coord1_t, units_t> constants1; typedef math::detail::constants_on_spheroid<coord2_t, units_t> constants2; - typedef math::detail::constants_on_spheroid<calc_t, units_t> constants; + static coord1_t const pi_half1 = constants1::max_latitude(); + static coord2_t const pi_half2 = constants2::max_latitude(); + static calc_t const c0 = 0; coord1_t const a0 = geometry::get<0>(segment_a); coord1_t const a1 = geometry::get<1>(segment_a); @@ -122,11 +124,6 @@ struct direction_code_impl<Point, spherical_equatorial_tag> coord1_t const b1 = geometry::get<1>(segment_b); coord2_t const p0 = geometry::get<0>(p); coord2_t const p1 = geometry::get<1>(p); - coord1_t const pi_half1 = constants1::max_latitude(); - coord2_t const pi_half2 = constants2::max_latitude(); - calc_t const pi = constants::half_period(); - calc_t const pi_half = constants::max_latitude(); - calc_t const c0 = 0; if ( (math::equals(b0, a0) && math::equals(b1, a1)) || (math::equals(b0, p0) && math::equals(b1, p1)) ) @@ -147,12 +144,12 @@ struct direction_code_impl<Point, spherical_equatorial_tag> // NOTE: as opposed to the implementation for cartesian CS // here point b is the origin - calc_t const dlon1 = math::longitude_distance_signed<units_t>(b0, a0); - calc_t const dlon2 = math::longitude_distance_signed<units_t>(b0, p0); + calc_t const dlon1 = math::longitude_distance_signed<units_t, calc_t>(b0, a0); + calc_t const dlon2 = math::longitude_distance_signed<units_t, calc_t>(b0, p0); bool is_antilon1 = false, is_antilon2 = false; - calc_t const dlat1 = latitude_distance_signed(b1, a1, dlon1, pi, is_antilon1); - calc_t const dlat2 = latitude_distance_signed(b1, p1, dlon2, pi, is_antilon2); + calc_t const dlat1 = latitude_distance_signed<units_t, calc_t>(b1, a1, dlon1, is_antilon1); + calc_t const dlat2 = latitude_distance_signed<units_t, calc_t>(b1, p1, dlon2, is_antilon2); calc_t mx = is_a_pole || is_b_pole || is_p_pole ? c0 : @@ -176,10 +173,12 @@ struct direction_code_impl<Point, spherical_equatorial_tag> return s1 == s2 ? -1 : 1; } - template <typename T> - static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, T const& pi, bool & is_antilon) + template <typename Units, typename T> + static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, bool & is_antilon) { - T const c0 = 0; + typedef math::detail::constants_on_spheroid<T, Units> constants; + static T const pi = constants::half_period(); + static T const c0 = 0; T res = lat2 - lat1; diff --git a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp index f8d3e3c593..d7aa9089e3 100644 --- a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp @@ -36,10 +36,11 @@ #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/algorithms/dispatch/disjoint.hpp> +#include <boost/geometry/policies/compare.hpp> + namespace boost { namespace geometry { @@ -56,10 +57,10 @@ class multipoint_multipoint private: template <typename Iterator> class unary_disjoint_predicate - : detail::relate::less + : geometry::less<> { private: - typedef detail::relate::less base_type; + typedef geometry::less<> base_type; public: unary_disjoint_predicate(Iterator first, Iterator last) @@ -90,7 +91,7 @@ public: std::vector<point1_type> points1(boost::begin(multipoint1), boost::end(multipoint1)); - std::sort(points1.begin(), points1.end(), detail::relate::less()); + std::sort(points1.begin(), points1.end(), geometry::less<>()); typedef unary_disjoint_predicate < diff --git a/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp index ab5de3d9b2..9596799cb2 100644 --- a/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp +++ b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp @@ -391,7 +391,7 @@ struct distance template <typename Point, typename Polygon, typename Strategy> struct distance < - Point, Polygon, Strategy, point_tag, polygon_tag, + Point, Polygon, Strategy, point_tag, polygon_tag, strategy_tag_distance_point_segment, false > : detail::distance::point_to_polygon < diff --git a/boost/geometry/algorithms/detail/envelope/box.hpp b/boost/geometry/algorithms/detail/envelope/box.hpp index 795f51392e..33b43da255 100644 --- a/boost/geometry/algorithms/detail/envelope/box.hpp +++ b/boost/geometry/algorithms/detail/envelope/box.hpp @@ -4,11 +4,12 @@ // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2015, 2016. -// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2016, 2017. +// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -146,13 +147,19 @@ namespace dispatch { -template <typename Box, typename CS_Tag> -struct envelope<Box, box_tag, CS_Tag> +template <typename Box> +struct envelope<Box, box_tag, cartesian_tag> : detail::envelope::envelope_box {}; template <typename Box> +struct envelope<Box, box_tag, spherical_polar_tag> + : detail::envelope::envelope_box_on_spheroid +{}; + + +template <typename Box> struct envelope<Box, box_tag, spherical_equatorial_tag> : detail::envelope::envelope_box_on_spheroid {}; diff --git a/boost/geometry/algorithms/detail/envelope/multipoint.hpp b/boost/geometry/algorithms/detail/envelope/multipoint.hpp index efee4701c9..eef7563796 100644 --- a/boost/geometry/algorithms/detail/envelope/multipoint.hpp +++ b/boost/geometry/algorithms/detail/envelope/multipoint.hpp @@ -1,9 +1,10 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2015-2016, Oracle and/or its affiliates. +// Copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -336,8 +337,6 @@ public: { detail::expand::point_loop < - strategy::compare::default_strategy, - strategy::compare::default_strategy, 2, dimension<Box>::value >::apply(mbr, *it, strategy); } diff --git a/boost/geometry/algorithms/detail/envelope/point.hpp b/boost/geometry/algorithms/detail/envelope/point.hpp index ee0559bf5f..86e73f3aa3 100644 --- a/boost/geometry/algorithms/detail/envelope/point.hpp +++ b/boost/geometry/algorithms/detail/envelope/point.hpp @@ -4,11 +4,12 @@ // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2015, 2016. +// This file was modified by Oracle on 2015, 2016, 2017. // Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -102,13 +103,19 @@ namespace dispatch { -template <typename Point, typename CS_Tag> -struct envelope<Point, point_tag, CS_Tag> +template <typename Point> +struct envelope<Point, point_tag, cartesian_tag> : detail::envelope::envelope_one_point<0, dimension<Point>::value> {}; template <typename Point> +struct envelope<Point, point_tag, spherical_polar_tag> + : detail::envelope::envelope_point_on_spheroid +{}; + + +template <typename Point> struct envelope<Point, point_tag, spherical_equatorial_tag> : detail::envelope::envelope_point_on_spheroid {}; diff --git a/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp index f61fc422de..9b9e2f85d3 100644 --- a/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp +++ b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp @@ -1,9 +1,10 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2015-2016, Oracle and/or its affiliates. +// Copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -194,8 +195,6 @@ struct envelope_range_of_boxes_by_expansion { detail::expand::indexed_loop < - strategy::compare::default_strategy, - strategy::compare::default_strategy, min_corner, Dimension, DimensionCount @@ -203,8 +202,6 @@ struct envelope_range_of_boxes_by_expansion detail::expand::indexed_loop < - strategy::compare::default_strategy, - strategy::compare::default_strategy, max_corner, Dimension, DimensionCount @@ -243,9 +240,15 @@ struct envelope_range_of_boxes RangeOfBoxes const >::type iterator_type; + static const bool is_equatorial = ! boost::is_same + < + typename cs_tag<box_type>::type, + spherical_polar_tag + >::value; + typedef math::detail::constants_on_spheroid < - coordinate_type, units_type + coordinate_type, units_type, is_equatorial > constants; typedef longitude_interval<coordinate_type> interval_type; diff --git a/boost/geometry/algorithms/detail/envelope/segment.hpp b/boost/geometry/algorithms/detail/envelope/segment.hpp index 7e37194968..97f2fc84a8 100644 --- a/boost/geometry/algorithms/detail/envelope/segment.hpp +++ b/boost/geometry/algorithms/detail/envelope/segment.hpp @@ -80,6 +80,35 @@ struct envelope_segment_call_vertex_latitude<CalculationType, geographic_tag> } }; +template <typename Units, typename CS_Tag> +struct envelope_segment_convert_polar +{ + template <typename T> + static inline void pre(T & , T & ) {} + + template <typename T> + static inline void post(T & , T & ) {} +}; + +template <typename Units> +struct envelope_segment_convert_polar<Units, spherical_polar_tag> +{ + template <typename T> + static inline void pre(T & lat1, T & lat2) + { + lat1 = math::latitude_convert_ep<Units>(lat1); + lat2 = math::latitude_convert_ep<Units>(lat2); + } + + template <typename T> + static inline void post(T & lat1, T & lat2) + { + lat1 = math::latitude_convert_ep<Units>(lat1); + lat2 = math::latitude_convert_ep<Units>(lat2); + std::swap(lat1, lat2); + } +}; + template <typename CS_Tag> class envelope_segment_impl { @@ -171,7 +200,7 @@ private: lat1 = lat_min; } } - else if (mid_lat > 0) + else { // update using max latitude CalculationType const lat_max_rad = p_max; @@ -266,29 +295,29 @@ private: Box, box_coordinate_type, Units >::type helper_box_type; - helper_box_type radian_mbr; + helper_box_type helper_mbr; geometry::set < min_corner, 0 - >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon1)); + >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon1)); geometry::set < min_corner, 1 - >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat1)); + >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat1)); geometry::set < max_corner, 0 - >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon2)); + >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon2)); geometry::set < max_corner, 1 - >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat2)); + >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat2)); - transform_units(radian_mbr, mbr); + transform_units(helper_mbr, mbr); } @@ -347,7 +376,14 @@ public: Box& mbr, Strategy const& strategy) { + typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar; + + convert_polar::pre(lat1, lat2); + apply<Units>(lon1, lat1, lon2, lat2, strategy); + + convert_polar::post(lat1, lat2); + create_box<Units>(lon1, lat1, lon2, lat2, mbr); } @@ -366,7 +402,14 @@ public: Strategy const& strategy, CalculationType alp1) { + typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar; + + convert_polar::pre(lat1, lat2); + apply<Units>(lon1, lat1, lon2, lat2, strategy, alp1); + + convert_polar::post(lat1, lat2); + create_box<Units>(lon1, lat1, lon2, lat2, mbr); } }; @@ -383,8 +426,6 @@ struct envelope_one_segment envelope_one_point<Dimension, DimensionCount>::apply(p1, mbr, strategy); detail::expand::point_loop < - strategy::compare::default_strategy, - strategy::compare::default_strategy, Dimension, DimensionCount >::apply(mbr, p2, strategy); @@ -409,13 +450,14 @@ struct envelope_segment envelope_one_segment<2, DimensionCount>::apply(p1, p2, mbr, strategy); } - template <typename Segment, typename Box> - static inline void apply(Segment const& segment, Box& mbr) + template <typename Segment, typename Box, typename Strategy> + static inline void apply(Segment const& segment, Box& mbr, + Strategy const& strategy) { typename point_type<Segment>::type p[2]; detail::assign_point_from_index<0>(segment, p[0]); detail::assign_point_from_index<1>(segment, p[1]); - apply(p[0], p[1], mbr); + apply(p[0], p[1], mbr, strategy); } }; diff --git a/boost/geometry/algorithms/detail/expand/box.hpp b/boost/geometry/algorithms/detail/expand/box.hpp index 3edb23f5ae..485f4d25e6 100644 --- a/boost/geometry/algorithms/detail/expand/box.hpp +++ b/boost/geometry/algorithms/detail/expand/box.hpp @@ -5,11 +5,12 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France. -// This file was modified by Oracle on 2015, 2016. -// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2016, 2017. +// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -73,48 +74,54 @@ namespace dispatch template < typename BoxOut, typename BoxIn, - typename StrategyLess, typename StrategyGreater, typename CSTagOut, typename CSTag > struct expand < BoxOut, BoxIn, - StrategyLess, StrategyGreater, box_tag, box_tag, CSTagOut, CSTag - > : detail::expand::expand_indexed - < - 0, dimension<BoxIn>::value, StrategyLess, StrategyGreater - > + > { - BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value), - COORDINATE_SYSTEMS_MUST_BE_THE_SAME, + BOOST_MPL_ASSERT_MSG((false), + NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS, (types<CSTagOut, CSTag>())); }; -template -< - typename BoxOut, typename BoxIn, - typename StrategyLess, typename StrategyGreater -> +template <typename BoxOut, typename BoxIn> +struct expand + < + BoxOut, BoxIn, + box_tag, box_tag, + cartesian_tag, cartesian_tag + > : detail::expand::expand_indexed + < + 0, dimension<BoxIn>::value + > +{}; + +template <typename BoxOut, typename BoxIn> struct expand < BoxOut, BoxIn, - StrategyLess, StrategyGreater, box_tag, box_tag, spherical_equatorial_tag, spherical_equatorial_tag > : detail::expand::box_on_spheroid {}; -template -< - typename BoxOut, typename BoxIn, - typename StrategyLess, typename StrategyGreater -> +template <typename BoxOut, typename BoxIn> +struct expand + < + BoxOut, BoxIn, + box_tag, box_tag, + spherical_polar_tag, spherical_polar_tag + > : detail::expand::box_on_spheroid +{}; + +template <typename BoxOut, typename BoxIn> struct expand < BoxOut, BoxIn, - StrategyLess, StrategyGreater, box_tag, box_tag, geographic_tag, geographic_tag > : detail::expand::box_on_spheroid diff --git a/boost/geometry/algorithms/detail/expand/indexed.hpp b/boost/geometry/algorithms/detail/expand/indexed.hpp index 28cf0e2e4f..fe7ee4f781 100644 --- a/boost/geometry/algorithms/detail/expand/indexed.hpp +++ b/boost/geometry/algorithms/detail/expand/indexed.hpp @@ -5,11 +5,12 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France. -// This file was modified by Oracle on 2015, 2016. -// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2016, 2017. +// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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. @@ -22,15 +23,13 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_INDEXED_HPP #include <cstddef> +#include <functional> #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/util/select_coordinate_type.hpp> -#include <boost/geometry/strategies/compare.hpp> -#include <boost/geometry/policies/compare.hpp> - #include <boost/geometry/algorithms/dispatch/expand.hpp> @@ -44,7 +43,6 @@ namespace detail { namespace expand template < - typename StrategyLess, typename StrategyGreater, std::size_t Index, std::size_t Dimension, std::size_t DimensionCount > @@ -53,27 +51,17 @@ struct indexed_loop template <typename Box, typename Geometry, typename Strategy> static inline void apply(Box& box, Geometry const& source, Strategy const& strategy) { - typedef typename strategy::compare::detail::select_strategy - < - StrategyLess, 1, Box, Dimension - >::type less_type; - - typedef typename strategy::compare::detail::select_strategy - < - StrategyGreater, -1, Box, Dimension - >::type greater_type; - typedef typename select_coordinate_type < Box, Geometry >::type coordinate_type; - less_type less; - greater_type greater; - coordinate_type const coord = get<Index, Dimension>(source); + std::less<coordinate_type> less; + std::greater<coordinate_type> greater; + if (less(coord, get<min_corner, Dimension>(box))) { set<min_corner, Dimension>(box, coord); @@ -86,21 +74,15 @@ struct indexed_loop indexed_loop < - StrategyLess, StrategyGreater, Index, Dimension + 1, DimensionCount >::apply(box, source, strategy); } }; -template -< - typename StrategyLess, typename StrategyGreater, - std::size_t Index, std::size_t DimensionCount -> +template <std::size_t Index, std::size_t DimensionCount> struct indexed_loop < - StrategyLess, StrategyGreater, Index, DimensionCount, DimensionCount > { @@ -111,11 +93,7 @@ struct indexed_loop // Changes a box such that the other box is also contained by the box -template -< - std::size_t Dimension, std::size_t DimensionCount, - typename StrategyLess, typename StrategyGreater -> +template <std::size_t Dimension, std::size_t DimensionCount> struct expand_indexed { template <typename Box, typename Geometry, typename Strategy> @@ -125,13 +103,11 @@ struct expand_indexed { indexed_loop < - StrategyLess, StrategyGreater, 0, Dimension, DimensionCount >::apply(box, geometry, strategy); indexed_loop < - StrategyLess, StrategyGreater, 1, Dimension, DimensionCount >::apply(box, geometry, strategy); } diff --git a/boost/geometry/algorithms/detail/expand/point.hpp b/boost/geometry/algorithms/detail/expand/point.hpp index f0cbd1db02..2d8b0feff6 100644 --- a/boost/geometry/algorithms/detail/expand/point.hpp +++ b/boost/geometry/algorithms/detail/expand/point.hpp @@ -5,11 +5,12 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France. -// This file was modified by Oracle on 2015, 2016. -// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2016, 2017. +// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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. @@ -23,6 +24,7 @@ #include <cstddef> #include <algorithm> +#include <functional> #include <boost/mpl/assert.hpp> #include <boost/type_traits/is_same.hpp> @@ -36,9 +38,6 @@ #include <boost/geometry/util/math.hpp> #include <boost/geometry/util/select_coordinate_type.hpp> -#include <boost/geometry/strategies/compare.hpp> -#include <boost/geometry/policies/compare.hpp> - #include <boost/geometry/algorithms/detail/normalize.hpp> #include <boost/geometry/algorithms/detail/envelope/transform_units.hpp> @@ -53,33 +52,19 @@ namespace detail { namespace expand { -template -< - typename StrategyLess, typename StrategyGreater, - std::size_t Dimension, std::size_t DimensionCount -> +template <std::size_t Dimension, std::size_t DimensionCount> struct point_loop { template <typename Box, typename Point, typename Strategy> static inline void apply(Box& box, Point const& source, Strategy const& strategy) { - typedef typename strategy::compare::detail::select_strategy - < - StrategyLess, 1, Point, Dimension - >::type less_type; - - typedef typename strategy::compare::detail::select_strategy - < - StrategyGreater, -1, Point, Dimension - >::type greater_type; - typedef typename select_coordinate_type < Point, Box >::type coordinate_type; - less_type less; - greater_type greater; + std::less<coordinate_type> less; + std::greater<coordinate_type> greater; coordinate_type const coord = get<Dimension>(source); @@ -93,37 +78,21 @@ struct point_loop set<max_corner, Dimension>(box, coord); } - point_loop - < - StrategyLess, StrategyGreater, Dimension + 1, DimensionCount - >::apply(box, source, strategy); + point_loop<Dimension + 1, DimensionCount>::apply(box, source, strategy); } }; -template -< - typename StrategyLess, - typename StrategyGreater, - std::size_t DimensionCount -> -struct point_loop - < - StrategyLess, StrategyGreater, DimensionCount, DimensionCount - > +template <std::size_t DimensionCount> +struct point_loop<DimensionCount, DimensionCount> { template <typename Box, typename Point, typename Strategy> static inline void apply(Box&, Point const&, Strategy const&) {} }; -// implementation for the spherical equatorial and geographic coordinate systems -template -< - typename StrategyLess, - typename StrategyGreater, - std::size_t DimensionCount -> +// implementation for the spherical and geographic coordinate systems +template <std::size_t DimensionCount, bool IsEquatorial = true> struct point_loop_on_spheroid { template <typename Box, typename Point, typename Strategy> @@ -133,11 +102,12 @@ struct point_loop_on_spheroid { typedef typename point_type<Box>::type box_point_type; typedef typename coordinate_type<Box>::type box_coordinate_type; + typedef typename coordinate_system<Box>::type::units units_type; typedef math::detail::constants_on_spheroid < box_coordinate_type, - typename coordinate_system<Box>::type::units + units_type > constants; // normalize input point and input box @@ -157,7 +127,7 @@ struct point_loop_on_spheroid b_lon_max = geometry::get<max_corner, 0>(box), b_lat_max = geometry::get<max_corner, 1>(box); - if (math::equals(math::abs(p_lat), constants::max_latitude())) + if (math::is_latitude_pole<units_type, IsEquatorial>(p_lat)) { // the point of expansion is the either the north or the // south pole; the only important coordinate here is the @@ -169,7 +139,7 @@ struct point_loop_on_spheroid } if (math::equals(b_lat_min, b_lat_max) - && math::equals(math::abs(b_lat_min), constants::max_latitude())) + && math::is_latitude_pole<units_type, IsEquatorial>(b_lat_min)) { // the box degenerates to either the north or the south pole; // the only important coordinate here is the pole's latitude, @@ -228,7 +198,7 @@ struct point_loop_on_spheroid point_loop < - StrategyLess, StrategyGreater, 2, DimensionCount + 2, DimensionCount >::apply(box, point, strategy); } }; @@ -246,56 +216,70 @@ namespace dispatch template < typename BoxOut, typename Point, - typename StrategyLess, typename StrategyGreater, typename CSTagOut, typename CSTag > struct expand < BoxOut, Point, - StrategyLess, StrategyGreater, box_tag, point_tag, CSTagOut, CSTag - > : detail::expand::point_loop - < - StrategyLess, StrategyGreater, 0, dimension<Point>::value - > + > { - BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value), - COORDINATE_SYSTEMS_MUST_BE_THE_SAME, + BOOST_MPL_ASSERT_MSG((false), + NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS, (types<CSTagOut, CSTag>())); }; -template -< - typename BoxOut, typename Point, - typename StrategyLess, typename StrategyGreater -> + +template <typename BoxOut, typename Point> +struct expand + < + BoxOut, Point, + box_tag, point_tag, + cartesian_tag, cartesian_tag + > : detail::expand::point_loop + < + 0, dimension<Point>::value + > +{}; + +template <typename BoxOut, typename Point> struct expand < BoxOut, Point, - StrategyLess, StrategyGreater, box_tag, point_tag, spherical_equatorial_tag, spherical_equatorial_tag > : detail::expand::point_loop_on_spheroid < - StrategyLess, StrategyGreater, dimension<Point>::value + dimension<Point>::value + > +{}; + +template <typename BoxOut, typename Point> +struct expand + < + BoxOut, Point, + box_tag, point_tag, + spherical_polar_tag, spherical_polar_tag + > : detail::expand::point_loop_on_spheroid + < + dimension<Point>::value, + false > {}; template < - typename BoxOut, typename Point, - typename StrategyLess, typename StrategyGreater + typename BoxOut, typename Point > struct expand < BoxOut, Point, - StrategyLess, StrategyGreater, box_tag, point_tag, geographic_tag, geographic_tag > : detail::expand::point_loop_on_spheroid < - StrategyLess, StrategyGreater, dimension<Point>::value + dimension<Point>::value > {}; diff --git a/boost/geometry/algorithms/detail/expand/segment.hpp b/boost/geometry/algorithms/detail/expand/segment.hpp index 0570e944d4..dddd3d2c7a 100644 --- a/boost/geometry/algorithms/detail/expand/segment.hpp +++ b/boost/geometry/algorithms/detail/expand/segment.hpp @@ -5,11 +5,12 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France. -// This file was modified by Oracle on 2015, 2016. -// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2016, 2017. +// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// 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 @@ -77,48 +78,57 @@ namespace dispatch template < typename Box, typename Segment, - typename StrategyLess, typename StrategyGreater, typename CSTagOut, typename CSTag > struct expand < Box, Segment, - StrategyLess, StrategyGreater, box_tag, segment_tag, CSTagOut, CSTag - > : detail::expand::expand_indexed - < - 0, dimension<Segment>::value, StrategyLess, StrategyGreater - > + > { - BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value), - COORDINATE_SYSTEMS_MUST_BE_THE_SAME, + BOOST_MPL_ASSERT_MSG((false), + NOT_IMPLEMENTED_FOR_THESE_COORDINATE_SYSTEMS, (types<CSTagOut, CSTag>())); }; template < - typename Box, typename Segment, - typename StrategyLess, typename StrategyGreater + typename Box, typename Segment > struct expand < Box, Segment, - StrategyLess, StrategyGreater, + box_tag, segment_tag, + cartesian_tag, cartesian_tag + > : detail::expand::expand_indexed + < + 0, dimension<Segment>::value + > +{}; + +template <typename Box, typename Segment> +struct expand + < + Box, Segment, + box_tag, segment_tag, + spherical_polar_tag, spherical_polar_tag + > : detail::expand::segment +{}; + +template <typename Box, typename Segment> +struct expand + < + Box, Segment, box_tag, segment_tag, spherical_equatorial_tag, spherical_equatorial_tag > : detail::expand::segment {}; -template -< - typename Box, typename Segment, - typename StrategyLess, typename StrategyGreater -> +template <typename Box, typename Segment> struct expand < Box, Segment, - StrategyLess, StrategyGreater, box_tag, segment_tag, geographic_tag, geographic_tag > : detail::expand::segment diff --git a/boost/geometry/algorithms/detail/has_self_intersections.hpp b/boost/geometry/algorithms/detail/has_self_intersections.hpp index c34bb217a6..1289d946a5 100644 --- a/boost/geometry/algorithms/detail/has_self_intersections.hpp +++ b/boost/geometry/algorithms/detail/has_self_intersections.hpp @@ -81,7 +81,11 @@ inline bool has_self_intersections(Geometry const& geometry, std::deque<turn_info> turns; detail::disjoint::disjoint_interrupt_policy policy; - detail::self_get_turn_points::self_turns<false, detail::overlay::assign_null_policy>(geometry, strategy, robust_policy, turns, policy); + detail::self_get_turn_points::self_turns + < + false, + detail::overlay::assign_null_policy + >(geometry, strategy, robust_policy, turns, policy, 0, false); #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS bool first = true; diff --git a/boost/geometry/algorithms/detail/intersection/multi.hpp b/boost/geometry/algorithms/detail/intersection/multi.hpp index 88b49b0167..92ce89bb2d 100644 --- a/boost/geometry/algorithms/detail/intersection/multi.hpp +++ b/boost/geometry/algorithms/detail/intersection/multi.hpp @@ -237,7 +237,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, multi_linestring_tag, multi_linestring_tag, point_tag, - false, false, false + linear_tag, linear_tag, pointlike_tag > : detail::intersection::intersection_multi_linestring_multi_linestring_point < GeometryOut @@ -259,7 +259,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, linestring_tag, multi_linestring_tag, point_tag, - false, false, false + linear_tag, linear_tag, pointlike_tag > : detail::intersection::intersection_linestring_multi_linestring_point < GeometryOut @@ -281,7 +281,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, multi_linestring_tag, box_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::clip_multi_linestring < GeometryOut @@ -303,7 +303,7 @@ struct intersection_insert OverlayType, ReverseLinestring, ReverseMultiPolygon, ReverseOut, linestring_tag, multi_polygon_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_linestring_with_areal < ReverseMultiPolygon, @@ -329,7 +329,7 @@ struct intersection_insert OverlayType, ReversePolygon, ReverseMultiLinestring, ReverseOut, polygon_tag, multi_linestring_tag, linestring_tag, - true, false, false + areal_tag, linear_tag, linear_tag > : detail::intersection::intersection_of_areal_with_multi_linestring < ReversePolygon, @@ -353,7 +353,7 @@ struct intersection_insert OverlayType, ReverseMultiLinestring, ReverseRing, ReverseOut, multi_linestring_tag, ring_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_multi_linestring_with_areal < ReverseRing, @@ -376,7 +376,7 @@ struct intersection_insert OverlayType, ReverseMultiLinestring, ReverseRing, ReverseOut, multi_linestring_tag, polygon_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_multi_linestring_with_areal < ReverseRing, @@ -401,7 +401,7 @@ struct intersection_insert OverlayType, ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut, multi_linestring_tag, multi_polygon_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_multi_linestring_with_areal < ReverseMultiPolygon, diff --git a/boost/geometry/algorithms/detail/intersects/implementation.hpp b/boost/geometry/algorithms/detail/intersects/implementation.hpp index 2379168e83..f9b5402d0c 100644 --- a/boost/geometry/algorithms/detail/intersects/implementation.hpp +++ b/boost/geometry/algorithms/detail/intersects/implementation.hpp @@ -72,10 +72,11 @@ struct self_intersects rescale_policy_type robust_policy; detail::disjoint::disjoint_interrupt_policy policy; + // TODO: skip_adjacent should be set to false detail::self_get_turn_points::get_turns < false, turn_policy - >::apply(geometry, strategy, robust_policy, turns, policy, 0); + >::apply(geometry, strategy, robust_policy, turns, policy, 0, true); return policy.has_intersections; } }; diff --git a/boost/geometry/algorithms/detail/is_simple/linear.hpp b/boost/geometry/algorithms/detail/is_simple/linear.hpp index 5acf56c5b1..e36049a961 100644 --- a/boost/geometry/algorithms/detail/is_simple/linear.hpp +++ b/boost/geometry/algorithms/detail/is_simple/linear.hpp @@ -217,6 +217,7 @@ inline bool has_self_intersections(Linear const& linear, Strategy const& strateg is_acceptable_turn<Linear> > interrupt_policy(predicate); + // TODO: skip_adjacent should be set to false detail::self_get_turn_points::get_turns < false, turn_policy @@ -224,7 +225,7 @@ inline bool has_self_intersections(Linear const& linear, Strategy const& strateg strategy, detail::no_rescale_policy(), turns, - interrupt_policy, 0); + interrupt_policy, 0, true); detail::is_valid::debug_print_turns(turns.begin(), turns.end()); debug_print_boundary_points(linear); diff --git a/boost/geometry/algorithms/detail/normalize.hpp b/boost/geometry/algorithms/detail/normalize.hpp index 913fe324b7..7a761d42bb 100644 --- a/boost/geometry/algorithms/detail/normalize.hpp +++ b/boost/geometry/algorithms/detail/normalize.hpp @@ -1,8 +1,9 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2015, Oracle and/or its affiliates. +// Copyright (c) 2015-2017, 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 @@ -120,7 +121,7 @@ struct assign_loop<1, DimensionCount> }; -template <typename PointIn, typename PointOut> +template <typename PointIn, typename PointOut, bool IsEquatorial = true> struct normalize_point { static inline void apply(PointIn const& point_in, PointOut& point_out) @@ -133,6 +134,7 @@ struct normalize_point math::normalize_spheroidal_coordinates < typename coordinate_system<PointIn>::type::units, + IsEquatorial, in_coordinate_type >(longitude, latitude); @@ -144,7 +146,7 @@ struct normalize_point }; -template <typename BoxIn, typename BoxOut> +template <typename BoxIn, typename BoxOut, bool IsEquatorial = true> class normalize_box { template <typename UnitsIn, typename UnitsOut, typename CoordinateInType> @@ -193,6 +195,7 @@ public: math::normalize_spheroidal_box_coordinates < typename coordinate_system<BoxIn>::type::units, + IsEquatorial, in_coordinate_type >(lon_min, lat_min, lon_max, lat_max); @@ -237,6 +240,15 @@ struct normalize template <typename PointIn, typename PointOut> struct normalize < + PointIn, PointOut, point_tag, point_tag, + spherical_polar_tag, spherical_polar_tag + > : detail::normalization::normalize_point<PointIn, PointOut, false> +{}; + + +template <typename PointIn, typename PointOut> +struct normalize + < PointIn, PointOut, point_tag, point_tag, geographic_tag, geographic_tag > : detail::normalization::normalize_point<PointIn, PointOut> {}; @@ -254,6 +266,15 @@ struct normalize template <typename BoxIn, typename BoxOut> struct normalize < + BoxIn, BoxOut, box_tag, box_tag, + spherical_polar_tag, spherical_polar_tag + > : detail::normalization::normalize_box<BoxIn, BoxOut, false> +{}; + + +template <typename BoxIn, typename BoxOut> +struct normalize + < BoxIn, BoxOut, box_tag, box_tag, geographic_tag, geographic_tag > : detail::normalization::normalize_box<BoxIn, BoxOut> {}; diff --git a/boost/geometry/algorithms/detail/overlay/add_rings.hpp b/boost/geometry/algorithms/detail/overlay/add_rings.hpp index fcb240941f..f64eb0b069 100644 --- a/boost/geometry/algorithms/detail/overlay/add_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/add_rings.hpp @@ -62,6 +62,13 @@ inline void convert_and_add(GeometryOut& result, } } +enum add_rings_error_handling +{ + add_rings_ignore_unordered, + add_rings_add_unordered, + add_rings_throw_if_reversed +}; + template < typename GeometryOut, @@ -69,16 +76,18 @@ template typename Geometry1, typename Geometry2, typename RingCollection, - typename OutputIterator + typename OutputIterator, + typename AreaStrategy > inline OutputIterator add_rings(SelectionMap const& map, Geometry1 const& geometry1, Geometry2 const& geometry2, RingCollection const& collection, - OutputIterator out) + OutputIterator out, + AreaStrategy const& area_strategy, + add_rings_error_handling error_handling = add_rings_ignore_unordered) { typedef typename SelectionMap::const_iterator iterator; - typedef typename SelectionMap::mapped_type property_type; - typedef typename property_type::area_type area_type; + typedef typename AreaStrategy::return_type area_type; area_type const zero = 0; std::size_t const min_num_points = core_detail::closure::minimum_ring_size @@ -122,10 +131,22 @@ inline OutputIterator add_rings(SelectionMap const& map, // Only add rings if they satisfy minimal requirements. // This cannot be done earlier (during traversal), not // everything is figured out yet (sum of positive/negative rings) - if (geometry::num_points(result) >= min_num_points - && math::larger(geometry::area(result), zero)) + if (geometry::num_points(result) >= min_num_points) { - *out++ = result; + area_type const area = geometry::area(result, area_strategy); + // Ignore if area is 0 + if (! math::equals(area, zero)) + { + if (error_handling == add_rings_add_unordered + || area > zero) + { + *out++ = result; + } + else if (error_handling == add_rings_throw_if_reversed) + { + BOOST_THROW_EXCEPTION(invalid_output_exception()); + } + } } } } @@ -139,15 +160,17 @@ template typename SelectionMap, typename Geometry, typename RingCollection, - typename OutputIterator + typename OutputIterator, + typename AreaStrategy > inline OutputIterator add_rings(SelectionMap const& map, Geometry const& geometry, RingCollection const& collection, - OutputIterator out) + OutputIterator out, + AreaStrategy const& area_strategy) { Geometry empty; - return add_rings<GeometryOut>(map, geometry, empty, collection, out); + return add_rings<GeometryOut>(map, geometry, empty, collection, out, area_strategy); } diff --git a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp index 106ecaad07..3f2aea1b1d 100644 --- a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp +++ b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp @@ -25,7 +25,7 @@ struct ring_with_direction ring_identifier ring_id; direction_type direction; - std::size_t turn_index; + signed_size_type turn_index; int operation_index; operation_type operation; signed_size_type region_id; @@ -50,8 +50,12 @@ struct ring_with_direction struct rank_with_rings { + // Define a set having a ring, with its direction (from/to). Each ring + // arrive at / leaves a cluster only once. TODO: this is not true for + // invalid ring. The rank needs to be considered too. + typedef std::set<ring_with_direction> container_type; std::size_t rank; - std::set<ring_with_direction> rings; + container_type rings; rank_with_rings() : rank(0) @@ -60,7 +64,7 @@ struct rank_with_rings inline bool all_equal(direction_type dir_type) const { - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { if (it->direction != dir_type) @@ -83,7 +87,7 @@ struct rank_with_rings inline bool has_only(operation_type op) const { - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; @@ -100,7 +104,7 @@ struct rank_with_rings { bool has1 = false; bool has2 = false; - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; @@ -114,7 +118,7 @@ struct rank_with_rings inline bool is_isolated() const { - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; @@ -128,8 +132,8 @@ struct rank_with_rings inline bool has_unique_region_id() const { - int region_id = -1; - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + signed_size_type region_id = -1; + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; @@ -145,10 +149,10 @@ struct rank_with_rings return true; } - inline int region_id() const + inline signed_size_type region_id() const { - int region_id = -1; - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + signed_size_type region_id = -1; + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; @@ -170,7 +174,7 @@ struct rank_with_rings typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; - for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + for (container_type::const_iterator it = rings.begin(); it != rings.end(); ++it) { const ring_with_direction& rwd = *it; diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 78160f5204..c8ce651007 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -224,7 +224,8 @@ inline void assign_parents(Geometry1 const& geometry1, RingCollection const& collection, RingMap& ring_map, Strategy const& strategy, - bool check_for_orientation = false) + bool check_for_orientation = false, + bool discard_double_negative = false) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; @@ -334,28 +335,38 @@ inline void assign_parents(Geometry1 const& geometry1, for (map_iterator_type it = boost::begin(ring_map); it != boost::end(ring_map); ++it) { - if (geometry::math::equals(it->second.get_area(), 0)) + ring_info_type& info = it->second; + if (geometry::math::equals(info.get_area(), 0)) { - it->second.discarded = true; + info.discarded = true; } - else if (it->second.parent.source_index >= 0 - && math::larger(it->second.get_area(), 0)) + else if (info.parent.source_index >= 0) { - const ring_info_type& parent = ring_map[it->second.parent]; + const ring_info_type& parent = ring_map[info.parent]; + bool const pos = math::larger(info.get_area(), 0); + bool const parent_pos = math::larger(parent.area, 0); - if (math::larger(parent.area, 0)) + bool const double_neg = discard_double_negative && ! pos && ! parent_pos; + + if ((pos && parent_pos) || double_neg) { // Discard positive inner ring with positive parent - it->second.discarded = true; + // Also, for some cases (dissolve), negative inner ring + // with negative parent shouild be discarded + info.discarded = true; + } + + if (pos || info.discarded) + { + // Remove parent ID from any positive or discarded inner rings + info.parent.source_index = -1; } - // Remove parent ID from any positive inner ring - it->second.parent.source_index = -1; } - else if (it->second.parent.source_index < 0 - && math::smaller(it->second.get_area(), 0)) + else if (info.parent.source_index < 0 + && math::smaller(info.get_area(), 0)) { // Reverse negative ring without parent - it->second.reversed = true; + info.reversed = true; } } } @@ -372,7 +383,7 @@ inline void assign_parents(Geometry1 const& geometry1, } -// Version for one geometry (called by buffer) +// Version for one geometry (called by buffer/dissolve) template < typename Geometry, @@ -384,13 +395,15 @@ inline void assign_parents(Geometry const& geometry, RingCollection const& collection, RingMap& ring_map, Strategy const& strategy, - bool check_for_orientation) + bool check_for_orientation, + bool discard_double_negative) { // Call it with an empty geometry as second geometry (source_id == 1) // (ring_map should be empty for source_id==1) Geometry empty; - assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation); + assign_parents(geometry, empty, collection, ring_map, strategy, + check_for_orientation, discard_double_negative); } diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 47225328df..e25445651a 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -118,7 +118,7 @@ inline void enrich_assign(Operations& operations, Turns& turns) // Cluster behaviour: next should point after cluster, unless // their seg_ids are not the same - while (turn.cluster_id != -1 + while (turn.is_clustered() && it->turn_index != next->turn_index && turn.cluster_id == turns[next->turn_index].cluster_id && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id) @@ -245,10 +245,6 @@ inline void calculate_remaining_distance(Turns& turns) ++it) { turn_type& turn = *it; - if (! turn.both(detail::overlay::operation_continue)) - { - continue; - } op_type& op0 = turn.operations[0]; op_type& op1 = turn.operations[1]; @@ -261,7 +257,7 @@ inline void calculate_remaining_distance(Turns& turns) int const to_index0 = op0.enriched.get_next_turn_index(); int const to_index1 = op1.enriched.get_next_turn_index(); - if (to_index1 >= 0 + if (to_index0 >= 0 && to_index1 >= 0 && to_index0 != to_index1) { @@ -359,12 +355,11 @@ inline void enrich_intersection_points(Turns& turns, } if (detail::overlay::is_self_turn<OverlayType>(turn) - && turn.cluster_id < 0 + && ! turn.is_clustered() && ! turn.both(target_operation)) { // Only keep self-uu-turns or self-ii-turns turn.discarded = true; - turn.cluster_id = -1; continue; } @@ -379,12 +374,12 @@ inline void enrich_intersection_points(Turns& turns, < OverlayType, target_operation - >::apply(turns, geometry1, geometry2); + >::apply(turns, clusters, geometry1, geometry2); detail::overlay::discard_open_turns < OverlayType, target_operation - >::apply(turns, geometry1, geometry2); + >::apply(turns, clusters, geometry1, geometry2); // Create a map of vectors of indexed operation-types to be able // to sort intersection points PER RING @@ -421,6 +416,9 @@ inline void enrich_intersection_points(Turns& turns, detail::overlay::enrich_assign(mit->second, turns); } + // Check some specific type of self-turns (after getting enriched info) + detail::overlay::discard_self_turns_which_loop<OverlayType>(turns); + if (has_colocations) { // First gather cluster properties (using even clusters with diff --git a/boost/geometry/algorithms/detail/overlay/follow.hpp b/boost/geometry/algorithms/detail/overlay/follow.hpp index 589e12cc2b..4a5993ea31 100644 --- a/boost/geometry/algorithms/detail/overlay/follow.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow.hpp @@ -26,6 +26,7 @@ #include <boost/geometry/algorithms/covered_by.hpp> #include <boost/geometry/algorithms/clear.hpp> +#include <boost/geometry/algorithms/detail/relate/turns.hpp> namespace boost { namespace geometry @@ -343,6 +344,7 @@ template class follow { +#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR template <typename Turn> struct sort_on_segment { @@ -389,7 +391,7 @@ class follow } }; - +#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR public : @@ -433,7 +435,15 @@ public : // Sort intersection points on segments-along-linestring, and distance // (like in enrich is done for poly/poly) + // sort turns by Linear seg_id, then by fraction, then + // for same ring id: x, u, i, c + // for different ring id: c, i, u, x +#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>()); +#else + typedef relate::turns::less<0, relate::turns::less_op_linear_areal_single<0> > turn_less; + std::sort(boost::begin(turns), boost::end(turns), turn_less()); +#endif LineStringOut current_piece; geometry::segment_identifier current_segment_id(0, -1, -1, -1); diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index f88dfe8422..fd1e49ca24 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -144,7 +144,7 @@ class get_turns_in_sections template <typename Geometry, typename Section> - static inline bool neighbouring(Section const& section, + static inline bool adjacent(Section const& section, signed_size_type index1, signed_size_type index2) { // About n-2: @@ -152,7 +152,7 @@ class get_turns_in_sections // -> 0-3 are adjacent, don't check on intersections) // Also tested for open polygons, and/or duplicates // About first condition: will be optimized by compiler (static) - // It checks if it is areal (box,ring,(multi)polygon + // It checks if it is areal (box, ring, (multi)polygon) signed_size_type const n = static_cast<signed_size_type>(section.range_count); boost::ignore_unused_variable_warning(n); @@ -180,7 +180,7 @@ public : static inline bool apply( int source_id1, Geometry1 const& geometry1, Section1 const& sec1, int source_id2, Geometry2 const& geometry2, Section2 const& sec2, - bool skip_larger, + bool skip_larger, bool skip_adjacent, IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy, Turns& turns, @@ -214,11 +214,6 @@ public : signed_size_type index1 = sec1.begin_index; signed_size_type ndi1 = sec1.non_duplicate_index; - bool const same_source = - source_id1 == source_id2 - && sec1.ring_id.multi_index == sec2.ring_id.multi_index - && sec1.ring_id.ring_index == sec2.ring_id.ring_index; - range1_iterator prev1, it1, end1; get_start_point_iterator(sec1, view1, prev1, it1, end1, @@ -254,22 +249,32 @@ public : it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy); ++prev2, ++it2, ++index2, ++next2, ++ndi2) { - bool skip = same_source; - if (skip) + bool skip = false; + + if (source_id1 == source_id2 + && sec1.ring_id.multi_index == sec2.ring_id.multi_index + && sec1.ring_id.ring_index == sec2.ring_id.ring_index) { - // If sources are the same (possibly self-intersecting): - // skip if it is a neighbouring segment. - // (including first-last segment - // and two segments with one or more degenerate/duplicate - // (zero-length) segments in between) - - // Also skip if index1 < index2 to avoid getting all - // intersections twice (only do this on same source!) - - skip = (skip_larger && index1 >= index2) - || ndi2 == ndi1 + 1 - || neighbouring<Geometry1>(sec1, index1, index2) - ; + // Sources and rings are the same + + if (skip_larger && index1 >= index2) + { + // Skip to avoid getting all intersections twice + skip = true; + } + else if (skip_adjacent) + { + // In some cases (dissolve, has_self_intersections) + // neighbouring segments should be checked + // (for example to detect spikes properly) + + // skip if it is a neighbouring segment. + // (including, for areas, first-last segment + // and two segments with one or more degenerate/duplicate + // (zero-length) segments in between) + skip = ndi2 == ndi1 + 1 + || adjacent<Geometry1>(sec1, index1, index2); + } } if (! skip) @@ -431,7 +436,7 @@ struct section_visitor TurnPolicy >::apply(m_source_id1, m_geometry1, sec1, m_source_id2, m_geometry2, sec2, - false, + false, false, m_intersection_strategy, m_rescale_policy, m_turns, m_interrupt_policy); diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp index f3311b34e9..c634fc450f 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -24,6 +24,7 @@ #include <boost/geometry/core/point_order.hpp> #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> +#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -181,6 +182,7 @@ inline signed_size_type add_turn_to_cluster(Turn const& turn, if (cid0 == -1 && cid1 == -1) { + // Because of this, first cluster ID will be 1 ++cluster_id; add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id); add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id); @@ -314,7 +316,7 @@ inline void assign_cluster_to_turns(Turns& turns, if (it != cluster_per_segment.end()) { #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) - if (turn.cluster_id != -1 + if (turn.is_clustered() && turn.cluster_id != it->second) { std::cout << " CONFLICT " << std::endl; @@ -503,6 +505,7 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) template < + overlay_type OverlayType, typename Turns, typename Clusters > @@ -517,38 +520,65 @@ inline void set_colocation(Turns& turns, Clusters const& clusters) cluster_info const& cinfo = cit->second; std::set<signed_size_type> const& ids = cinfo.turn_indices; - bool has_ii = false; - bool has_uu = false; + bool both_target = false; for (set_iterator it = ids.begin(); it != ids.end(); ++it) { turn_type const& turn = turns[*it]; - if (turn.both(operation_intersection)) - { - has_ii = true; - } - if (turn.both(operation_union) || turn.combination(operation_union, operation_blocked)) + if (turn.both(operation_from_overlay<OverlayType>::value)) { - has_uu = true; + both_target = true; + break; } } - if (has_ii || has_uu) + + if (both_target) { for (set_iterator it = ids.begin(); it != ids.end(); ++it) { turn_type& turn = turns[*it]; - if (has_ii) - { - turn.colocated_ii = true; - } - if (has_uu) + + if (both_target) { - turn.colocated_uu = true; + turn.has_colocated_both = true; } } } } } +template +< + typename Turns, + typename Clusters +> +inline void check_colocation(bool& has_blocked, + int cluster_id, Turns const& turns, Clusters const& clusters) +{ + typedef typename boost::range_value<Turns>::type turn_type; + + has_blocked = false; + + typename Clusters::const_iterator mit = clusters.find(cluster_id); + if (mit == clusters.end()) + { + return; + } + + cluster_info const& cinfo = mit->second; + + for (std::set<signed_size_type>::const_iterator it + = cinfo.turn_indices.begin(); + it != cinfo.turn_indices.end(); ++it) + { + turn_type const& turn = turns[*it]; + if (turn.any_blocked()) + { + has_blocked = true; + } + } +} + + // 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 @@ -627,6 +657,10 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters, > cluster_per_segment_type; cluster_per_segment_type cluster_per_segment; + + // Assign to zero, because of pre-increment later the cluster_id + // effectively starts with 1 + // (and can later be negated to use uniquely with turn_index) signed_size_type cluster_id = 0; for (typename map_type::const_iterator it = map.begin(); @@ -640,7 +674,9 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters, } assign_cluster_to_turns(turns, clusters, cluster_per_segment); - set_colocation(turns, clusters); + // Get colocated information here and not later, to keep information + // on turns which are discarded afterwards + set_colocation<OverlayType>(turns, clusters); discard_interior_exterior_turns < do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1, @@ -758,14 +794,21 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, cinfo.open_count = sbs.open_count(for_operation); - // Unset the startable flag for all 'closed' zones + bool const set_startable + = OverlayType != overlay_dissolve_union + && OverlayType != overlay_dissolve_intersection; + + // Unset the startable flag for all 'closed' zones. This does not + // apply for self-turns, because those counts are not from both + // polygons for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { const typename sbs_type::rp& ranked = sbs.m_ranked_points[i]; turn_type& turn = turns[ranked.turn_index]; turn_operation_type& op = turn.operations[ranked.operation_index]; - if (for_operation == operation_union && cinfo.open_count == 0) + if (set_startable + && for_operation == operation_union && cinfo.open_count == 0) { op.enriched.startable = false; } @@ -780,6 +823,18 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, op.enriched.rank = ranked.rank; op.enriched.zone = ranked.zone; + if (! set_startable) + { + continue; + } + + if (OverlayType != overlay_difference + && is_self_turn<OverlayType>(turn)) + { + // Difference needs the self-turns, TODO: investigate + continue; + } + if ((for_operation == operation_union && ranked.count_left != 0) || (for_operation == operation_intersection diff --git a/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp index 39c55db759..9c4a3094e0 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp @@ -11,6 +11,7 @@ #include <boost/range.hpp> +#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/within.hpp> @@ -24,9 +25,9 @@ namespace detail { namespace overlay struct discard_turns { - template <typename Turns, typename Geometry0, typename Geometry1> + template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> static inline - void apply(Turns& , Geometry0 const& , Geometry1 const& ) + void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& ) {} }; @@ -38,9 +39,9 @@ template <> struct discard_closed_turns<overlay_union, operation_union> { - template <typename Turns, typename Geometry0, typename Geometry1> + template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> static inline - void apply(Turns& turns, + void apply(Turns& turns, Clusters const& clusters, Geometry0 const& geometry0, Geometry1 const& geometry1) { typedef typename boost::range_value<Turns>::type turn_type; @@ -52,9 +53,7 @@ struct discard_closed_turns<overlay_union, operation_union> { turn_type& turn = *it; - if (turn.cluster_id >= 0 - || turn.discarded - || ! is_self_turn<overlay_union>(turn)) + if (turn.discarded || ! is_self_turn<overlay_union>(turn)) { continue; } @@ -75,11 +74,106 @@ struct discard_closed_turns<overlay_union, operation_union> struct discard_self_intersection_turns { - template <typename Turns, typename Geometry0, typename Geometry1> +private : + + template <typename Turns, typename Clusters> + static inline + bool any_blocked(signed_size_type cluster_id, + const Turns& turns, Clusters const& clusters) + { + typename Clusters::const_iterator cit = clusters.find(cluster_id); + if (cit == clusters.end()) + { + return false; + } + cluster_info const& cinfo = cit->second; + for (std::set<signed_size_type>::const_iterator it + = cinfo.turn_indices.begin(); + it != cinfo.turn_indices.end(); ++it) + { + typename boost::range_value<Turns>::type const& turn = turns[*it]; + if (turn.any_blocked()) + { + return true; + } + } + return false; + } + + template <typename Turns, typename Clusters> + static inline + bool is_self_cluster(signed_size_type cluster_id, + const Turns& turns, Clusters const& clusters) + { + typename Clusters::const_iterator cit = clusters.find(cluster_id); + if (cit == clusters.end()) + { + return false; + } + + cluster_info const& cinfo = cit->second; + for (std::set<signed_size_type>::const_iterator it + = cinfo.turn_indices.begin(); + it != cinfo.turn_indices.end(); ++it) + { + if (! is_self_turn<overlay_intersection>(turns[*it])) + { + return false; + } + } + + return true; + } + + template <typename Turn, typename Geometry0, typename Geometry1> + static inline + bool within(Turn const& turn, Geometry0 const& geometry0, + Geometry1 const& geometry1) + { + return turn.operations[0].seg_id.source_index == 0 + ? geometry::within(turn.point, geometry1) + : geometry::within(turn.point, geometry0); + } + + template <typename Turns, typename Clusters, + typename Geometry0, typename Geometry1> + static inline + void discard_clusters(Turns& turns, Clusters const& clusters, + Geometry0 const& geometry0, Geometry1 const& geometry1) + { + for (typename Clusters::const_iterator cit = clusters.begin(); + cit != clusters.end(); ++cit) + { + signed_size_type cluster_id = cit->first; + + // If there are only self-turns in the cluster, the cluster should + // be located within the other geometry, for intersection + if (is_self_cluster(cluster_id, turns, clusters)) + { + cluster_info const& cinfo = cit->second; + if (! within(turns[*cinfo.turn_indices.begin()], geometry0, geometry1)) + { + // Discard all turns in cluster + for (std::set<signed_size_type>::const_iterator sit = cinfo.turn_indices.begin(); + sit != cinfo.turn_indices.end(); ++sit) + { + turns[*sit].discarded = true; + } + } + } + } + } + +public : + + template <typename Turns, typename Clusters, + typename Geometry0, typename Geometry1> static inline - void apply(Turns& turns, + void apply(Turns& turns, Clusters const& clusters, Geometry0 const& geometry0, Geometry1 const& geometry1) { + discard_clusters(turns, clusters, geometry0, geometry1); + typedef typename boost::range_value<Turns>::type turn_type; for (typename boost::range_iterator<Turns>::type @@ -89,9 +183,7 @@ struct discard_self_intersection_turns { turn_type& turn = *it; - if (turn.cluster_id >= 0 - || turn.discarded - || ! is_self_turn<overlay_intersection>(turn)) + if (turn.discarded || ! is_self_turn<overlay_intersection>(turn)) { continue; } @@ -106,16 +198,22 @@ struct discard_self_intersection_turns continue; } - // It is a non co-located ii self-turn + if (turn.is_clustered() && turn.has_colocated_both) + { + // Don't delete a self-ii-turn colocated with another ii-turn + // (for example #case_recursive_boxes_70) + // But for some cases (#case_58_iet) they should be deleted, + // there are many self-turns there and also blocked turns there + if (! any_blocked(turn.cluster_id, turns, clusters)) + { + continue; + } + } + + // It is a ii self-turn // Check if it is within the other geometry // If not, it can be ignored - - bool const within = - turn.operations[0].seg_id.source_index == 0 - ? geometry::within(turn.point, geometry1) - : geometry::within(turn.point, geometry0); - - if (! within) + if (! within(turn, geometry0, geometry1)) { // It is not within another geometry, discard the turn turn.discarded = true; @@ -134,6 +232,61 @@ struct discard_open_turns<overlay_intersection, operation_intersection> // For difference, it should be done in a different way (TODO) + +template <overlay_type OverlayType, typename Turns> +inline void discard_self_turns_which_loop(Turns& turns) +{ + if (operation_from_overlay<OverlayType>::value == operation_union) + { + // For union, self-turn i/u traveling to itself are allowed to form + // holes. #case_recursive_boxes_37 + // TODO: this can be finetuned by inspecting the cluster too, + // and if there are non-self-turns the polygons on their sides can + // be checked + return; + } + + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type op_type; + + signed_size_type turn_index = 0; + for (typename boost::range_iterator<Turns>::type + it = boost::begin(turns); + it != boost::end(turns); + ++it, ++turn_index) + { + turn_type& turn = *it; + + if (! is_self_turn<OverlayType>(turn)) + { + continue; + } + if (! turn.combination(operation_intersection, operation_union)) + { + // ii may travel to itself + continue; + } + + for (int i = 0; i < 2; i++) + { + op_type& op = turn.operations[i]; + + if (op.enriched.startable + && op.operation == operation_intersection + && op.enriched.get_next_turn_index() == turn_index) + { + // Self-turn i/u, i part traveling to itself. Discard it. + // (alternatively it might be made unstartable - but the + // intersection-operation may not be traveled anyway, and the + // union-operation is not traveled at all in intersections + // #case_recursive_boxes_77 + turn.discarded = true; + } + } + } + +} + }} // namespace detail::overlay #endif //DOXYGEN_NO_DETAIL diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index 7106e7b480..60255cd953 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -208,6 +208,8 @@ struct intersection_of_linestring_with_areal } #endif +#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + class is_crossing_turn { // return true is the operation is intersection or blocked @@ -310,6 +312,91 @@ struct intersection_of_linestring_with_areal return 0; } +#else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + + template <typename Linestring, typename Areal, typename Strategy, typename Turns> + static inline bool simple_turns_analysis(Linestring const& linestring, + Areal const& areal, + Strategy const& strategy, + Turns const& turns, + int & inside_value) + { + using namespace overlay; + + bool found_continue = false; + bool found_intersection = false; + bool found_union = false; + bool found_front = false; + + for (typename Turns::const_iterator it = turns.begin(); + it != turns.end(); ++it) + { + method_type const method = it->method; + operation_type const op = it->operations[0].operation; + + if (method == method_crosses) + { + return false; + } + else if (op == operation_intersection) + { + found_intersection = true; + } + else if (op == operation_union) + { + found_union = true; + } + else if (op == operation_continue) + { + found_continue = true; + } + + if ((found_intersection || found_continue) && found_union) + { + return false; + } + + if (it->operations[0].position == position_front) + { + found_front = true; + } + } + + if (found_front) + { + if (found_intersection) + { + inside_value = 1; // inside + } + else if (found_union) + { + inside_value = -1; // outside + } + else // continue and blocked + { + inside_value = 0; + } + return true; + } + + // if needed analyse points of a linestring + // NOTE: range_in_geometry checks points of a linestring + // until a point inside/outside areal is found + // TODO: Could be replaced with point_in_geometry() because found_front is false + inside_value = range_in_geometry(linestring, areal, strategy); + + if ( (found_intersection && inside_value == -1) // going in from outside + || (found_continue && inside_value == -1) // going on boundary from outside + || (found_union && inside_value == 1) ) // going out from inside + { + return false; + } + + return true; + } + +#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + template < typename LineString, typename Areal, @@ -336,14 +423,30 @@ struct intersection_of_linestring_with_areal > follower; typedef typename point_type<LineStringOut>::type point_type; +#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR typedef detail::overlay::traversal_turn_info - < - point_type, - typename geometry::segment_ratio_type<point_type, RobustPolicy>::type - > turn_info; + < + point_type, + typename geometry::segment_ratio_type<point_type, RobustPolicy>::type + > turn_info; +#else + typedef detail::overlay::turn_info + < + point_type, + typename geometry::segment_ratio_type<point_type, RobustPolicy>::type, + detail::overlay::turn_operation_linear + < + point_type, + typename geometry::segment_ratio_type<point_type, RobustPolicy>::type + > + > turn_info; +#endif std::deque<turn_info> turns; detail::get_turns::no_interrupt_policy policy; + +#ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + geometry::get_turns < false, @@ -366,7 +469,7 @@ struct intersection_of_linestring_with_areal // until a point inside/outside areal is found inside_value = overlay::range_in_geometry(linestring, areal, strategy); } - // add point to the output if conditions are met + // add linestring to the output if conditions are met if (inside_value != 0 && follower::included(inside_value)) { LineStringOut copy; @@ -376,6 +479,47 @@ struct intersection_of_linestring_with_areal return out; } +#else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + + typedef detail::overlay::get_turn_info_linear_areal + < + detail::overlay::assign_null_policy + > turn_policy; + + dispatch::get_turns + < + typename geometry::tag<LineString>::type, + typename geometry::tag<Areal>::type, + LineString, + Areal, + false, + (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal), + turn_policy + >::apply(0, linestring, 1, areal, + strategy, robust_policy, + turns, policy); + + int inside_value = 0; + if (simple_turns_analysis(linestring, areal, strategy, turns, inside_value)) + { + // No crossing the boundary, it is either + // inside (interior + borders) + // or outside (exterior + borders) + // or on boundary + + // add linestring to the output if conditions are met + if (follower::included(inside_value)) + { + LineStringOut copy; + geometry::convert(linestring, copy); + *out++ = copy; + } + + return out; + } + +#endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR + #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) int index = 0; for(typename std::deque<turn_info>::const_iterator @@ -395,6 +539,135 @@ struct intersection_of_linestring_with_areal }; +template <typename Turns, typename OutputIterator> +inline OutputIterator intersection_output_turn_points(Turns const& turns, + OutputIterator out) +{ + for (typename Turns::const_iterator + it = turns.begin(); it != turns.end(); ++it) + { + *out++ = it->point; + } + + return out; +} + +template <typename PointOut> +struct intersection_areal_areal_point +{ + template + < + typename Geometry1, typename Geometry2, + typename RobustPolicy, + typename OutputIterator, + typename Strategy + > + static inline OutputIterator apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + RobustPolicy const& robust_policy, + OutputIterator out, + Strategy const& strategy) + { + typedef detail::overlay::turn_info + < + PointOut, + typename segment_ratio_type<PointOut, RobustPolicy>::type + > turn_info; + std::vector<turn_info> turns; + + detail::get_turns::no_interrupt_policy policy; + + geometry::get_turns + < + false, false, detail::overlay::assign_null_policy + >(geometry1, geometry2, strategy, robust_policy, turns, policy); + + return intersection_output_turn_points(turns, out); + } +}; + +template <typename PointOut> +struct intersection_linear_areal_point +{ + template + < + typename Geometry1, typename Geometry2, + typename RobustPolicy, + typename OutputIterator, + typename Strategy + > + static inline OutputIterator apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + RobustPolicy const& robust_policy, + OutputIterator out, + Strategy const& strategy) + { + typedef typename geometry::segment_ratio_type + < + PointOut, RobustPolicy + >::type segment_ratio_type; + + typedef detail::overlay::turn_info + < + PointOut, + segment_ratio_type, + detail::overlay::turn_operation_linear + < + PointOut, + segment_ratio_type + > + > turn_info; + + typedef detail::overlay::get_turn_info_linear_areal + < + detail::overlay::assign_null_policy + > turn_policy; + + std::vector<turn_info> turns; + + detail::get_turns::no_interrupt_policy interrupt_policy; + + dispatch::get_turns + < + typename geometry::tag<Geometry1>::type, + typename geometry::tag<Geometry2>::type, + Geometry1, + Geometry2, + false, + false, + turn_policy + >::apply(0, geometry1, 1, geometry2, + strategy, robust_policy, + turns, interrupt_policy); + + return intersection_output_turn_points(turns, out); + } +}; + +template <typename PointOut> +struct intersection_areal_linear_point +{ + template + < + typename Geometry1, typename Geometry2, + typename RobustPolicy, + typename OutputIterator, + typename Strategy + > + static inline OutputIterator apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + RobustPolicy const& robust_policy, + OutputIterator out, + Strategy const& strategy) + { + return intersection_linear_areal_point + < + PointOut + >::apply(geometry2, geometry1, robust_policy, out, strategy); + } +}; + + }} // namespace detail::intersection #endif // DOXYGEN_NO_DETAIL @@ -420,9 +693,9 @@ template typename TagIn2 = typename geometry::tag<Geometry2>::type, typename TagOut = typename geometry::tag<GeometryOut>::type, // metafunction finetuning helpers: - bool Areal1 = geometry::is_areal<Geometry1>::value, - bool Areal2 = geometry::is_areal<Geometry2>::value, - bool ArealOut = geometry::is_areal<GeometryOut>::value + typename CastedTagIn1 = typename geometry::tag_cast<TagIn1, areal_tag, linear_tag, pointlike_tag>::type, + typename CastedTagIn2 = typename geometry::tag_cast<TagIn2, areal_tag, linear_tag, pointlike_tag>::type, + typename CastedTagOut = typename geometry::tag_cast<TagOut, areal_tag, linear_tag, pointlike_tag>::type > struct intersection_insert { @@ -449,7 +722,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, TagIn1, TagIn2, TagOut, - true, true, true + areal_tag, areal_tag, areal_tag > : detail::overlay::overlay <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType> {}; @@ -471,7 +744,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, TagIn, box_tag, TagOut, - true, true, true + areal_tag, areal_tag, areal_tag > : detail::overlay::overlay <Geometry, Box, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType> {}; @@ -491,7 +764,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, segment_tag, segment_tag, point_tag, - false, false, false + linear_tag, linear_tag, pointlike_tag > : detail::intersection::intersection_segment_segment_point<GeometryOut> {}; @@ -510,7 +783,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, linestring_tag, linestring_tag, point_tag, - false, false, false + linear_tag, linear_tag, pointlike_tag > : detail::intersection::intersection_linestring_linestring_point<GeometryOut> {}; @@ -528,7 +801,7 @@ struct intersection_insert overlay_intersection, Reverse1, Reverse2, ReverseOut, linestring_tag, box_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > { template <typename RobustPolicy, typename OutputIterator, typename Strategy> @@ -559,7 +832,7 @@ struct intersection_insert OverlayType, ReverseLinestring, ReversePolygon, ReverseOut, linestring_tag, polygon_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_linestring_with_areal < ReversePolygon, @@ -583,7 +856,7 @@ struct intersection_insert OverlayType, ReverseLinestring, ReverseRing, ReverseOut, linestring_tag, ring_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > : detail::intersection::intersection_of_linestring_with_areal < ReverseRing, @@ -606,7 +879,7 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, segment_tag, box_tag, linestring_tag, - false, true, false + linear_tag, areal_tag, linear_tag > { template <typename RobustPolicy, typename OutputIterator, typename Strategy> @@ -630,8 +903,7 @@ template typename PointOut, overlay_type OverlayType, bool Reverse1, bool Reverse2, bool ReverseOut, - typename Tag1, typename Tag2, - bool Areal1, bool Areal2 + typename Tag1, typename Tag2 > struct intersection_insert < @@ -640,38 +912,59 @@ struct intersection_insert OverlayType, Reverse1, Reverse2, ReverseOut, Tag1, Tag2, point_tag, - Areal1, Areal2, false + areal_tag, areal_tag, pointlike_tag > -{ - template <typename RobustPolicy, typename OutputIterator, typename Strategy> - static inline OutputIterator apply(Geometry1 const& geometry1, - Geometry2 const& geometry2, - RobustPolicy const& robust_policy, - OutputIterator out, Strategy const& strategy) - { - - typedef detail::overlay::turn_info - < - PointOut, - typename segment_ratio_type<PointOut, RobustPolicy>::type - > turn_info; - std::vector<turn_info> turns; - - detail::get_turns::no_interrupt_policy policy; - geometry::get_turns - < - false, false, detail::overlay::assign_null_policy - >(geometry1, geometry2, strategy, robust_policy, turns, policy); - for (typename std::vector<turn_info>::const_iterator it - = turns.begin(); it != turns.end(); ++it) - { - *out++ = it->point; - } + : public detail::intersection::intersection_areal_areal_point + < + PointOut + > +{}; - return out; - } -}; +template +< + typename Geometry1, typename Geometry2, + typename PointOut, + overlay_type OverlayType, + bool Reverse1, bool Reverse2, bool ReverseOut, + typename Tag1, typename Tag2 +> +struct intersection_insert + < + Geometry1, Geometry2, + PointOut, + OverlayType, + Reverse1, Reverse2, ReverseOut, + Tag1, Tag2, point_tag, + linear_tag, areal_tag, pointlike_tag + > + : public detail::intersection::intersection_linear_areal_point + < + PointOut + > +{}; +template +< + typename Geometry1, typename Geometry2, + typename PointOut, + overlay_type OverlayType, + bool Reverse1, bool Reverse2, bool ReverseOut, + typename Tag1, typename Tag2 +> +struct intersection_insert + < + Geometry1, Geometry2, + PointOut, + OverlayType, + Reverse1, Reverse2, ReverseOut, + Tag1, Tag2, point_tag, + areal_tag, linear_tag, pointlike_tag + > + : public detail::intersection::intersection_areal_linear_point + < + PointOut + > +{}; template < @@ -713,7 +1006,7 @@ struct intersection_insert overlay_intersection, Reverse1, Reverse2, ReverseOut, Tag1, Tag2, linestring_tag, - true, true, false + areal_tag, areal_tag, linear_tag > { template @@ -739,47 +1032,20 @@ struct intersection_insert } }; -// dispatch for non-areal geometries -template -< - typename Geometry1, typename Geometry2, typename GeometryOut, - overlay_type OverlayType, - bool Reverse1, bool Reverse2, bool ReverseOut, - typename TagIn1, typename TagIn2 -> -struct intersection_insert - < - Geometry1, Geometry2, GeometryOut, - OverlayType, - Reverse1, Reverse2, ReverseOut, - TagIn1, TagIn2, linestring_tag, - false, false, false - > : intersection_insert - < - Geometry1, Geometry2, GeometryOut, - OverlayType, - Reverse1, Reverse2, ReverseOut, - typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type, - typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type, - linestring_tag, - false, false, false - > -{}; - - // dispatch for difference/intersection of linear geometries template < typename Linear1, typename Linear2, typename LineStringOut, overlay_type OverlayType, - bool Reverse1, bool Reverse2, bool ReverseOut + bool Reverse1, bool Reverse2, bool ReverseOut, + typename TagIn1, typename TagIn2 > struct intersection_insert < Linear1, Linear2, LineStringOut, OverlayType, Reverse1, Reverse2, ReverseOut, - linear_tag, linear_tag, linestring_tag, - false, false, false + TagIn1, TagIn2, linestring_tag, + linear_tag, linear_tag, linear_tag > : detail::overlay::linear_linear_linestring < Linear1, Linear2, LineStringOut, OverlayType @@ -800,7 +1066,7 @@ struct intersection_insert Point1, Point2, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, point_tag, point_tag, point_tag, - false, false, false + pointlike_tag, pointlike_tag, pointlike_tag > : detail::overlay::point_point_point < Point1, Point2, PointOut, OverlayType @@ -819,7 +1085,7 @@ struct intersection_insert MultiPoint, Point, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, multi_point_tag, point_tag, point_tag, - false, false, false + pointlike_tag, pointlike_tag, pointlike_tag > : detail::overlay::multipoint_point_point < MultiPoint, Point, PointOut, OverlayType @@ -838,7 +1104,7 @@ struct intersection_insert Point, MultiPoint, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, point_tag, multi_point_tag, point_tag, - false, false, false + pointlike_tag, pointlike_tag, pointlike_tag > : detail::overlay::point_multipoint_point < Point, MultiPoint, PointOut, OverlayType @@ -857,7 +1123,7 @@ struct intersection_insert MultiPoint1, MultiPoint2, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, multi_point_tag, multi_point_tag, point_tag, - false, false, false + pointlike_tag, pointlike_tag, pointlike_tag > : detail::overlay::multipoint_multipoint_point < MultiPoint1, MultiPoint2, PointOut, OverlayType @@ -878,7 +1144,7 @@ struct intersection_insert Point, Linear, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, point_tag, Tag, point_tag, - false, false, false + pointlike_tag, linear_tag, pointlike_tag > : detail_dispatch::overlay::pointlike_linear_point < Point, Linear, PointOut, OverlayType, @@ -899,7 +1165,7 @@ struct intersection_insert MultiPoint, Linear, PointOut, OverlayType, Reverse1, Reverse2, ReverseOut, multi_point_tag, Tag, point_tag, - false, false, false + pointlike_tag, linear_tag, pointlike_tag > : detail_dispatch::overlay::pointlike_linear_point < MultiPoint, Linear, PointOut, OverlayType, @@ -919,7 +1185,7 @@ struct intersection_insert Linestring, MultiPoint, PointOut, overlay_intersection, Reverse1, Reverse2, ReverseOut, linestring_tag, multi_point_tag, point_tag, - false, false, false + linear_tag, pointlike_tag, pointlike_tag > { template <typename RobustPolicy, typename OutputIterator, typename Strategy> diff --git a/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp index 9cb7a0fca9..9423a24b33 100644 --- a/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp +++ b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp @@ -41,7 +41,7 @@ struct is_self_turn_check<overlay_buffer> }; template <> -struct is_self_turn_check<overlay_dissolve> +struct is_self_turn_check<overlay_dissolve_union> { template <typename Turn> static inline bool apply(Turn const& turn) @@ -50,6 +50,15 @@ struct is_self_turn_check<overlay_dissolve> } }; +template <> +struct is_self_turn_check<overlay_dissolve_intersection> +{ + template <typename Turn> + static inline bool apply(Turn const& turn) + { + return false; + } +}; template <overlay_type OverlayType, typename Turn> bool is_self_turn(Turn const& turn) diff --git a/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp b/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp new file mode 100644 index 0000000000..87fdd00d58 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp @@ -0,0 +1,83 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2017-2017 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_NEEDS_SELF_TURNS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NEEDS_SELF_TURNS_HPP + +#include <boost/range.hpp> + +#include <boost/geometry/core/tags.hpp> +#include <boost/geometry/algorithms/num_interior_rings.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +template +< + typename Geometry, + typename Tag = typename tag<Geometry>::type +> +struct needs_self_turns +{ +}; + +template <typename Geometry> +struct needs_self_turns<Geometry, box_tag> +{ + static inline bool apply(Geometry const&) + { + return false; + } +}; + +template <typename Geometry> +struct needs_self_turns<Geometry, ring_tag> +{ + static inline bool apply(Geometry const&) + { + return false; + } +}; + +template <typename Geometry> +struct needs_self_turns<Geometry, polygon_tag> +{ + static inline bool apply(Geometry const& polygon) + { + return geometry::num_interior_rings(polygon) > 0; + } +}; + +template <typename Geometry> +struct needs_self_turns<Geometry, multi_polygon_tag> +{ + static inline bool apply(Geometry const& multi) + { + typedef typename boost::range_value<Geometry>::type polygon_type; + std::size_t const n = boost::size(multi); + return n > 1 || (n == 1 + && needs_self_turns<polygon_type> + ::apply(*boost::begin(multi))); + } +}; + + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NEEDS_SELF_TURNS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index 10829abd4f..f24cde8b8f 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -29,6 +29,7 @@ #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> +#include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> @@ -99,89 +100,88 @@ template inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters) { typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; typedef typename turn_type::container_type container_type; static const operation_type target_operation = operation_from_overlay<OverlayType>::value; static const operation_type opposite_operation - = target_operation == operation_union ? operation_intersection : operation_union; + = target_operation == operation_union + ? operation_intersection + : operation_union; - signed_size_type turn_index = 0; for (typename boost::range_iterator<Turns const>::type it = boost::begin(turns); it != boost::end(turns); - ++it, turn_index++) + ++it) { - typename boost::range_value<Turns>::type const& turn = *it; - - bool const colocated_target = target_operation == operation_union - ? turn.colocated_uu : turn.colocated_ii; - bool const colocated_opp = target_operation == operation_union - ? turn.colocated_ii : turn.colocated_uu; - bool const both_opposite = turn.both(opposite_operation); - - bool const traversed - = turn.operations[0].visited.finalized() - || turn.operations[0].visited.rejected() - || turn.operations[1].visited.finalized() - || turn.operations[1].visited.rejected() - || turn.both(operation_blocked) - || turn.combination(opposite_operation, operation_blocked); - - bool is_closed = false; - if (turn.cluster_id >= 0 && target_operation == operation_union) - { - typename Clusters::const_iterator mit = clusters.find(turn.cluster_id); - BOOST_ASSERT(mit != clusters.end()); + turn_type const& turn = *it; - cluster_info const& cinfo = mit->second; - is_closed = cinfo.open_count == 0; - } + bool cluster_checked = false; + bool has_blocked = false; for (typename boost::range_iterator<container_type const>::type op_it = boost::begin(turn.operations); op_it != boost::end(turn.operations); ++op_it) { + turn_operation_type const& op = *op_it; ring_identifier const ring_id ( - op_it->seg_id.source_index, - op_it->seg_id.multi_index, - op_it->seg_id.ring_index + op.seg_id.source_index, + op.seg_id.multi_index, + op.seg_id.ring_index ); - if (traversed || is_closed || ! op_it->enriched.startable) + if (! is_self_turn<OverlayType>(turn) + && ( + (target_operation == operation_union + && op.enriched.count_left > 0) + || (target_operation == operation_intersection + && op.enriched.count_right <= 2))) { - turn_info_map[ring_id].has_traversed_turn = true; + // Avoid including untraversed rings which have polygons on + // their left side (union) or not two on their right side (int) + // This can only be done for non-self-turns because of count + // information + turn_info_map[ring_id].has_blocked_turn = true; + continue; } - else if (both_opposite && colocated_target) - { - // For union: ii, colocated with a uu - // For example, two interior rings touch where two exterior rings also touch. - // The interior rings are not yet traversed, and should be taken from the input - - // For intersection: uu, colocated with an ii - // unless it is two interior inner rings colocated with a uu - // So don't set has_traversed_turn here + if (turn.any_blocked()) + { + turn_info_map[ring_id].has_blocked_turn = true; + } + if (turn_info_map[ring_id].has_traversed_turn + || turn_info_map[ring_id].has_blocked_turn) + { + continue; } - else if (both_opposite && ! is_self_turn<OverlayType>(turn)) + + // Check information in colocated turns + if (! cluster_checked && turn.is_clustered()) { - // For union, mark any ring with a ii turn as traversed - // For intersection, any uu - but not if it is a self-turn - turn_info_map[ring_id].has_traversed_turn = true; + check_colocation(has_blocked, turn.cluster_id, turns, clusters); + cluster_checked = true; } - else if (colocated_opp && ! colocated_target) + + // Block rings where any other turn is blocked, + // and (with exceptions): i for union and u for intersection + // Exceptions: don't block self-uu for intersection + // don't block self-ii for union + // don't block (for union) i/u if there is an self-ii too + if (has_blocked + || (op.operation == opposite_operation + && ! turn.has_colocated_both + && ! (turn.both(opposite_operation) + && is_self_turn<OverlayType>(turn)))) { - // For union, a turn colocated with ii and NOT with uu/ux - // For intersection v.v. - turn_info_map[ring_id].has_traversed_turn = true; + turn_info_map[ring_id].has_blocked_turn = true; } } } } - template < typename GeometryOut, overlay_type OverlayType, bool ReverseOut, @@ -234,7 +234,8 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy); ring_container_type rings; assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy); - return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out); + return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out, + strategy.template get_area_strategy<point_type1>()); } @@ -306,9 +307,13 @@ std::cout << "get turns" << std::endl; visitor.visit_turns(1, turns); #ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS + if (needs_self_turns<Geometry1>::apply(geometry1)) { self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1, strategy, robust_policy, turns, policy, 0); + } + if (needs_self_turns<Geometry2>::apply(geometry2)) + { self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2, strategy, robust_policy, turns, policy, 1); } @@ -320,6 +325,7 @@ std::cout << "enrich" << std::endl; #endif typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy(); cluster_type clusters; + std::map<ring_identifier, ring_turn_info> turn_info_per_ring; geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, clusters, geometry1, geometry2, @@ -343,11 +349,12 @@ std::cout << "traverse" << std::endl; strategy, robust_policy, turns, rings, + turn_info_per_ring, clusters, visitor ); + visitor.visit_turns(3, turns); - std::map<ring_identifier, ring_turn_info> turn_info_per_ring; get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters); typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type; @@ -364,9 +371,8 @@ std::cout << "traverse" << std::endl; selected_ring_properties, strategy); // Add rings created during traversal + area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>(); { - area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>(); - ring_identifier id(2, 0, -1); for (typename boost::range_iterator<ring_container_type>::type it = boost::begin(rings); @@ -381,7 +387,24 @@ std::cout << "traverse" << std::endl; assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy); - return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out); + // NOTE: There is no need to check result area for union because + // as long as the polygons in the input are valid the resulting + // polygons should be valid as well. + // By default the area is checked (this is old behavior) however this + // can be changed with #define. This may be important in non-cartesian CSes. + // The result may be too big, so the area is negative. In this case either + // it can be returned or an exception can be thrown. + return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out, + area_strategy, + OverlayType == overlay_union ? +#if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION) + add_rings_throw_if_reversed +#elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID) + add_rings_add_unordered +#else + add_rings_ignore_unordered +#endif + : add_rings_ignore_unordered); } template <typename RobustPolicy, typename OutputIterator, typename Strategy> diff --git a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp index 0f60840973..f3ec9eaa64 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp @@ -21,7 +21,8 @@ enum overlay_type overlay_intersection, overlay_difference, overlay_buffer, - overlay_dissolve + overlay_dissolve_union, + overlay_dissolve_intersection }; #ifndef DOXYGEN_NO_DETAIL @@ -42,6 +43,17 @@ enum operation_type template <overlay_type OverlayType> struct operation_from_overlay { +}; + +template <> +struct operation_from_overlay<overlay_union> +{ + static const operation_type value = operation_union; +}; + +template <> +struct operation_from_overlay<overlay_buffer> +{ static const operation_type value = operation_union; }; @@ -57,6 +69,19 @@ struct operation_from_overlay<overlay_difference> static const operation_type value = operation_intersection; }; +template <> +struct operation_from_overlay<overlay_dissolve_union> +{ + static const operation_type value = operation_union; +}; + +template <> +struct operation_from_overlay<overlay_dissolve_intersection> +{ + static const operation_type value = operation_intersection; +}; + + }} // namespace detail::overlay #endif //DOXYGEN_NO_DETAIL diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp index 0a7c3bc469..6f8fdd32b8 100644 --- a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp @@ -32,7 +32,6 @@ #include <boost/geometry/algorithms/detail/not.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> #include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp index 438a377876..88aedecf86 100644 --- a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp +++ b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp @@ -1,12 +1,13 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014-2015, Oracle and/or its affiliates. +// Copyright (c) 2014-2017, 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 -// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle - #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP @@ -24,10 +25,11 @@ #include <boost/geometry/algorithms/convert.hpp> #include <boost/geometry/algorithms/not_implemented.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> +#include <boost/geometry/policies/compare.hpp> + namespace boost { namespace geometry { @@ -264,17 +266,20 @@ struct multipoint_multipoint_point >::apply(multipoint2, multipoint1, robust_policy, oit, strategy); } - std::vector<typename boost::range_value<MultiPoint2>::type> - points2(boost::begin(multipoint2), boost::end(multipoint2)); + typedef typename boost::range_value<MultiPoint2>::type point2_type; + + std::vector<point2_type> points2(boost::begin(multipoint2), + boost::end(multipoint2)); - std::sort(points2.begin(), points2.end(), detail::relate::less()); + geometry::less<> const less = geometry::less<>(); + std::sort(points2.begin(), points2.end(), less); for (typename boost::range_iterator<MultiPoint1 const>::type it1 = boost::begin(multipoint1); it1 != boost::end(multipoint1); ++it1) { bool found = std::binary_search(points2.begin(), points2.end(), - *it1, detail::relate::less()); + *it1, less); action_selector_pl_pl < diff --git a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp index 5447c8813e..14e84c9496 100644 --- a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp +++ b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp @@ -57,6 +57,7 @@ struct segment_identifier return source_index != other.source_index ? source_index < other.source_index : multi_index !=other.multi_index ? multi_index < other.multi_index : ring_index != other.ring_index ? ring_index < other.ring_index + : piece_index != other.piece_index ? piece_index < other.piece_index : segment_index < other.segment_index ; } @@ -66,6 +67,7 @@ struct segment_identifier return source_index == other.source_index && segment_index == other.segment_index && ring_index == other.ring_index + && piece_index == other.piece_index && multi_index == other.multi_index ; } @@ -79,6 +81,7 @@ struct segment_identifier ; if (seg_id.ring_index >= 0) os << ", r:" << seg_id.ring_index; if (seg_id.multi_index >= 0) os << ", m:" << seg_id.multi_index; + if (seg_id.piece_index >= 0) os << ", p:" << seg_id.piece_index; return os; } #endif diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp index 67a4f4bb75..262ba748ab 100644 --- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp @@ -41,10 +41,12 @@ namespace detail { namespace overlay struct ring_turn_info { bool has_traversed_turn; + bool has_blocked_turn; bool within_other; ring_turn_info() : has_traversed_turn(false) + , has_blocked_turn(false) , within_other(false) {} }; @@ -265,9 +267,9 @@ inline void update_ring_selection(Geometry1 const& geometry1, info = tcit->second; // Copy by value } - if (info.has_traversed_turn) + if (info.has_traversed_turn || info.has_blocked_turn) { - // This turn is traversed (or blocked), + // This turn is traversed or blocked, // don't include the original ring continue; } diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp index 5e9d8efa8e..a00606b087 100644 --- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp @@ -78,19 +78,22 @@ struct self_section_visitor Turns& m_turns; InterruptPolicy& m_interrupt_policy; std::size_t m_source_index; + bool m_skip_adjacent; inline self_section_visitor(Geometry const& g, IntersectionStrategy const& is, RobustPolicy const& rp, Turns& turns, InterruptPolicy& ip, - std::size_t source_index) + std::size_t source_index, + bool skip_adjacent) : m_geometry(g) , m_intersection_strategy(is) , m_rescale_policy(rp) , m_turns(turns) , m_interrupt_policy(ip) , m_source_index(source_index) + , m_skip_adjacent(skip_adjacent) {} template <typename Section> @@ -109,7 +112,7 @@ struct self_section_visitor TurnPolicy >::apply(m_source_index, m_geometry, sec1, m_source_index, m_geometry, sec2, - false, + false, m_skip_adjacent, m_intersection_strategy, m_rescale_policy, m_turns, m_interrupt_policy); @@ -132,7 +135,7 @@ struct get_turns RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - std::size_t source_index) + std::size_t source_index, bool skip_adjacent) { typedef model::box < @@ -143,9 +146,11 @@ struct get_turns >::type > box_type; - typedef geometry::sections<box_type, 1> sections_type; + // sectionalize in two dimensions to detect + // all potential spikes correctly + typedef geometry::sections<box_type, 2> sections_type; - typedef boost::mpl::vector_c<std::size_t, 0> dimensions; + typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions; sections_type sec; geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec, @@ -155,7 +160,7 @@ struct get_turns < Reverse, Geometry, Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy - > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index); + > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index, skip_adjacent); // false if interrupted geometry::partition @@ -224,7 +229,8 @@ struct self_get_turn_points RobustPolicy const& , Turns& , InterruptPolicy& , - std::size_t) + std::size_t /*source_index*/, + bool /*skip_adjacent*/) { return true; } @@ -286,7 +292,8 @@ inline void self_turns(Geometry const& geometry, RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - std::size_t source_index = 0) + std::size_t source_index = 0, + bool skip_adjacent = false) { concepts::check<Geometry const>(); @@ -298,7 +305,8 @@ inline void self_turns(Geometry const& geometry, typename tag<Geometry>::type, Geometry, turn_policy - >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, source_index); + >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, + source_index, skip_adjacent); } }} // namespace detail::self_get_turn_points @@ -331,7 +339,8 @@ inline void self_turns(Geometry const& geometry, RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - std::size_t source_index = 0) + std::size_t source_index = 0, + bool skip_adjacent = false) { concepts::check<Geometry const>(); @@ -344,7 +353,8 @@ inline void self_turns(Geometry const& geometry, < reverse, AssignPolicy - >(geometry, strategy, robust_policy, turns, interrupt_policy, source_index); + >(geometry, strategy, robust_policy, turns, interrupt_policy, + source_index, skip_adjacent); } diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp index 5ad2e41b12..fea5698ae1 100644 --- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp +++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp @@ -91,13 +91,20 @@ struct less_by_index template <typename T> inline bool operator()(const T& first, const T& second) const { + // Length might be considered too // First order by from/to if (first.direction != second.direction) { return first.direction < second.direction; } - // All the same, order by turn index (we might consider length too) - return first.turn_index < second.turn_index; + // Then by turn index + if (first.turn_index != second.turn_index) + { + return first.turn_index < second.turn_index; + } + // This can also be the same (for example in buffer), but seg_id is + // never the same + return first.seg_id < second.seg_id; } }; diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp index 69d62b788b..6a9b1def99 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -131,7 +131,8 @@ struct traversal { } - inline void finalize_visit_info() + template <typename TurnInfoMap> + inline void finalize_visit_info(TurnInfoMap& turn_info_map) { for (typename boost::range_iterator<Turns>::type it = boost::begin(m_turns); @@ -142,6 +143,32 @@ struct traversal for (int i = 0; i < 2; i++) { turn_operation_type& op = turn.operations[i]; + if (op.visited.visited() + || op.visited.started() + || op.visited.finished() ) + { + ring_identifier const ring_id + ( + op.seg_id.source_index, + op.seg_id.multi_index, + op.seg_id.ring_index + ); + turn_info_map[ring_id].has_traversed_turn = true; + + if (op.operation == operation_continue) + { + // Continue operations should mark the other operation + // as traversed too + turn_operation_type& other_op = turn.operations[1 - i]; + ring_identifier const other_ring_id + ( + other_op.seg_id.source_index, + other_op.seg_id.multi_index, + other_op.seg_id.ring_index + ); + turn_info_map[other_ring_id].has_traversed_turn = true; + } + } op.visited.finalize(); } } @@ -192,7 +219,7 @@ struct traversal { op.visited.set_visited(); } - if (turn.cluster_id >= 0) + if (turn.is_clustered()) { set_visited_in_cluster(turn.cluster_id, op.enriched.rank); } @@ -204,6 +231,16 @@ struct traversal return op.visited.visited(); } + template <signed_size_type segment_identifier::*Member> + inline bool select_source_generic(bool switch_source, + segment_identifier const& current, + segment_identifier const& previous) const + { + return switch_source + ? current.*Member != previous.*Member + : current.*Member == previous.*Member; + } + inline bool select_source(signed_size_type turn_index, segment_identifier const& candidate_seg_id, segment_identifier const& previous_seg_id) const @@ -211,22 +248,6 @@ struct traversal // For uu/ii, only switch sources if indicated turn_type const& turn = m_turns[turn_index]; - if (OverlayType == overlay_buffer) - { - // Buffer does not use source_index (always 0) - return turn.switch_source - ? candidate_seg_id.multi_index != previous_seg_id.multi_index - : candidate_seg_id.multi_index == previous_seg_id.multi_index; - } - - if (is_self_turn<OverlayType>(turn)) - { - // Also, if it is a self-turn, stay on same ring (multi/ring) - return turn.switch_source - ? candidate_seg_id.multi_index != previous_seg_id.multi_index - : candidate_seg_id.multi_index == previous_seg_id.multi_index; - } - #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) if (turn.switch_source) { @@ -237,9 +258,24 @@ struct traversal std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl; } #endif - return turn.switch_source - ? candidate_seg_id.source_index != previous_seg_id.source_index - : candidate_seg_id.source_index == previous_seg_id.source_index; + if (OverlayType == overlay_buffer + || OverlayType == overlay_dissolve_union) + { + // Buffer does not use source_index (always 0). + return select_source_generic<&segment_identifier::multi_index>( + turn.switch_source, candidate_seg_id, previous_seg_id); + } + + if (is_self_turn<OverlayType>(turn)) + { + // Also, if it is a self-turn, stay on same ring (multi/ring) + return select_source_generic<&segment_identifier::multi_index>( + turn.switch_source, candidate_seg_id, previous_seg_id); + } + + // Use source_index + return select_source_generic<&segment_identifier::source_index>( + turn.switch_source, candidate_seg_id, previous_seg_id); } inline bool traverse_possible(signed_size_type turn_index) const @@ -253,7 +289,7 @@ struct traversal // It is not a dead end if there is an operation to continue, or of // there is a cluster (assuming for now we can get out of the cluster) - return turn.cluster_id >= 0 + return turn.is_clustered() || turn.has(target_operation) || turn.has(operation_continue); } @@ -318,6 +354,7 @@ struct traversal if (op.operation == target_operation && ! op.visited.finished() + && ! op.visited.visited() && (! result || select_source(turn_index, op.seg_id, previous_seg_id))) { selected_op_index = i; @@ -380,13 +417,51 @@ struct traversal return true; } + inline int select_turn_in_cluster_union(std::size_t selected_rank, + typename sbs_type::rp const& ranked_point, + signed_size_type start_turn_index, int start_op_index) const + { + // Returns 0 if it not OK + // Returns 1 if it OK + // Returns 2 if it OK and start turn matches + // Returns 3 if it OK and start turn and start op both match + if (ranked_point.rank != selected_rank + || ranked_point.direction != sort_by_side::dir_to) + { + return 0; + } + + turn_type const& turn = m_turns[ranked_point.turn_index]; + turn_operation_type const& op = turn.operations[ranked_point.operation_index]; + + // Check finalized: TODO: this should be finetuned, it is not necessary + if (op.visited.finalized()) + { + return 0; + } + + if (OverlayType != overlay_dissolve_union + && (op.enriched.count_left != 0 || op.enriched.count_right == 0)) + { + // Check counts: in some cases interior rings might be generated with + // polygons on both sides. For dissolve it can be anything. + return 0; + } + + return ranked_point.turn_index == start_turn_index + && ranked_point.operation_index == start_op_index ? 3 + : ranked_point.turn_index == start_turn_index ? 2 + : 1 + ; + } + inline bool select_from_cluster_union(signed_size_type& turn_index, - int& op_index, sbs_type& sbs) const + int& op_index, sbs_type& sbs, + signed_size_type start_turn_index, int start_op_index) const { std::vector<sort_by_side::rank_with_rings> aggregation; sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_union); - sort_by_side::rank_with_rings const& incoming = aggregation.front(); // Take the first one outgoing for the incoming region @@ -402,62 +477,32 @@ struct traversal } } + int best_code = 0; + bool result = false; for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++) { typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; - if (ranked_point.rank == selected_rank - && ranked_point.direction == sort_by_side::dir_to) - { - turn_index = ranked_point.turn_index; - op_index = ranked_point.operation_index; - - turn_type const& turn = m_turns[turn_index]; - turn_operation_type const& op = turn.operations[op_index]; - - if (op.enriched.count_left == 0 - && op.enriched.count_right > 0 - && ! op.visited.finalized()) - { - // In some cases interior rings might be generated with polygons - // on both sides - - // TODO: this should be finetuned such that checking - // finalized is not necessary - return true; - } - } - } - return false; - } - - inline bool all_operations_of_type(sort_by_side::rank_with_rings const& rwr, - operation_type op_type, - sort_by_side::direction_type dir) const - { - typedef std::set<sort_by_side::ring_with_direction>::const_iterator sit_type; - for (sit_type it = rwr.rings.begin(); it != rwr.rings.end(); ++it) - { - sort_by_side::ring_with_direction const& rwd = *it; - if (rwd.direction != dir) + if (ranked_point.rank > selected_rank) { - return false; - } - turn_type const& turn = m_turns[rwd.turn_index]; - if (! turn.both(op_type)) - { - return false; + // Sorted on rank, so it makes no sense to continue + break; } - // Check if this is not yet taken - turn_operation_type const& op = turn.operations[rwd.operation_index]; - if (op.visited.finalized()) + int const code + = select_turn_in_cluster_union(selected_rank, ranked_point, + start_turn_index, start_op_index); + + if (code > best_code) { - return false; + // It is 1 or higher and matching better than previous + best_code = code; + turn_index = ranked_point.turn_index; + op_index = ranked_point.operation_index; + result = true; } - } - return true; + return result; } inline bool analyze_cluster_intersection(signed_size_type& turn_index, @@ -475,12 +520,14 @@ struct traversal || intersection_pattern_common_interior2(selected_rank, aggregation) || intersection_pattern_common_interior3(selected_rank, aggregation) || intersection_pattern_common_interior4(selected_rank, aggregation) + || intersection_pattern_common_interior5(selected_rank, aggregation) + || intersection_pattern_common_interior6(selected_rank, aggregation) ; if (! detected) { - int incoming_region_id = 0; - std::set<int> outgoing_region_ids; + signed_size_type incoming_region_id = 0; + std::set<signed_size_type> outgoing_region_ids; for (std::size_t i = 0; i < aggregation.size(); i++) { @@ -530,7 +577,7 @@ struct traversal { for (int i = 0; i < 2; i++) { - int const region_id = turn.operations[i].enriched.region_id; + signed_size_type const region_id = turn.operations[i].enriched.region_id; if (outgoing_region_ids.count(region_id) == 1) { selected_rank = 0; @@ -545,6 +592,9 @@ struct traversal if (selected_rank > 0) { + typename turn_operation_type::comparable_distance_type + min_remaining_distance = 0; + std::size_t selected_index = sbs.m_ranked_points.size(); for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { @@ -562,8 +612,13 @@ struct traversal continue; } - // Take the last turn from this rank - selected_index = i; + // Take turn with the smallest remaining distance + if (selected_index == sbs.m_ranked_points.size() + || ranked_op.remaining_distance < min_remaining_distance) + { + selected_index = i; + min_remaining_distance = ranked_op.remaining_distance; + } } } @@ -581,13 +636,13 @@ struct traversal inline bool select_turn_from_cluster(signed_size_type& turn_index, int& op_index, - signed_size_type start_turn_index, + signed_size_type start_turn_index, int start_op_index, segment_identifier const& previous_seg_id) const { bool const is_union = target_operation == operation_union; turn_type const& turn = m_turns[turn_index]; - BOOST_ASSERT(turn.cluster_id >= 0); + BOOST_ASSERT(turn.is_clustered()); typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id); BOOST_ASSERT(mit != m_clusters.end()); @@ -628,7 +683,8 @@ struct traversal if (is_union) { - result = select_from_cluster_union(turn_index, op_index, sbs); + result = select_from_cluster_union(turn_index, op_index, sbs, + start_turn_index, start_op_index); } else { @@ -669,11 +725,15 @@ struct traversal turn_operation_type const& start_op, int start_op_index) const { - if (OverlayType != overlay_buffer) + if (OverlayType != overlay_buffer + && OverlayType != overlay_dissolve_union + && OverlayType != overlay_dissolve_intersection) { return; } + const bool allow_uu = OverlayType != overlay_buffer; + // It travels to itself, can happen. If this is a buffer, it can // sometimes travel to itself in the following configuration: // @@ -696,7 +756,10 @@ struct traversal = start_turn.operations[1 - start_op_index]; bool const correct - = ! start_turn.both(operation_union) + = (allow_uu || ! start_turn.both(operation_union)) + && start_op.seg_id.source_index == other_op.seg_id.source_index + && start_op.seg_id.multi_index == other_op.seg_id.multi_index + && start_op.seg_id.ring_index == other_op.seg_id.ring_index && start_op.seg_id.segment_index == to_vertex_index; #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) @@ -770,7 +833,7 @@ struct traversal if (target_operation == operation_intersection) { bool const back_at_start_cluster - = current_turn.cluster_id >= 0 + = current_turn.is_clustered() && m_turns[start_turn_index].cluster_id == current_turn.cluster_id; if (turn_index == start_turn_index || back_at_start_cluster) @@ -781,7 +844,7 @@ struct traversal return true; } - if (current_turn.cluster_id < 0 + if (! current_turn.is_clustered() && current_turn.both(operation_intersection)) { if (analyze_ii_intersection(turn_index, op_index, @@ -792,10 +855,10 @@ struct traversal } } - if (current_turn.cluster_id >= 0) + if (current_turn.is_clustered()) { if (! select_turn_from_cluster(turn_index, op_index, - start_turn_index, previous_seg_id)) + start_turn_index, start_op_index, previous_seg_id)) { return false; } diff --git a/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp index 12279d762f..a8abea230e 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp @@ -32,8 +32,8 @@ inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggreg { sort_by_side::rank_with_rings const& curr = aggregation[i]; sort_by_side::rank_with_rings const& next = aggregation[i + 1]; - int const curr_id = curr.region_id(); - int const next_id = next.region_id(); + signed_size_type const curr_id = curr.region_id(); + signed_size_type const next_id = next.region_id(); bool const possible = curr.rings.size() == 2 @@ -249,7 +249,7 @@ inline bool intersection_pattern_common_interior4(std::size_t& selected_rank, //Rank 1 {13[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->15} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->15} //Rank 2 {13[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO} - // LEAVING (in two different directions, take last one) + // LEAVING (in two different directions, take penultimate one) //Rank 3 {10[1] (s:1, m:0) i T rgn: 1 ISO ->0} //Rank 4 {11[0] (s:0, m:0) i T rgn: 1 ISO ->12} @@ -292,12 +292,157 @@ inline bool intersection_pattern_common_interior4(std::size_t& selected_rank, // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy if (check_pairs(aggregation, incoming.region_id(), 1, n - 3)) { - selected_rank = n - 1; + selected_rank = n - 2; return true; } return false; } +inline bool intersection_pattern_common_interior5(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: isolated regions + + // See #case_recursive_boxes_65 + + // INCOMING: + // Rank 0 {19[0] (s:0, r:2, m:0) i F rgn: 4 ISO} + + // Rank 1 {19[1] (s:1, m:0) i T rgn: 1 ISO FIN ->18 (2.5)} + // Rank 2 {21[1] (s:1, m:2) i F rgn: 1 ISO} + // Rank 3 {21[1] (s:1, m:2) i T rgn: 1 ISO ->17 (2)} + // Rank 4 {19[1] (s:1, m:0) i F rgn: 1 ISO FIN} + + // LEAVING (take this one): + // Rank 5 {19[0] (s:0, r:2, m:0) i T rgn: 4 ISO ->22 (1)} + + std::size_t const n = aggregation.size(); + if (n < 3) + { + return false; + } + + sort_by_side::rank_with_rings const& incoming = aggregation.front(); + sort_by_side::rank_with_rings const& outgoing = aggregation.back(); + + bool const incoming_ok = + incoming.all_from() + && incoming.has_unique_region_id() + && incoming.is_isolated(); + + if (! incoming_ok) + { + return false; + } + + signed_size_type const incoming_region_id = incoming.region_id(); + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.has_unique_region_id() + && outgoing.is_isolated() + && outgoing.region_id() == incoming_region_id; + + if (! outgoing_ok) + { + return false; + } + + selected_rank = n - 1; + bool other_region = true; + + // Assumed is that other regions go (T) and come back (F) + for (std::size_t i = 1; i < n - 1; i++) + { + sort_by_side::rank_with_rings const& rwr = aggregation[i]; + if (! rwr.has_unique_region_id() || ! rwr.is_isolated()) + { + return false; + } + signed_size_type const region_id = rwr.region_id(); + if (other_region && region_id != incoming_region_id) + { + // OK + } + else if (other_region && region_id == incoming_region_id) + { + // OK, next phase (same region as incoming region) + selected_rank = i; + other_region = false; + } + else if (! other_region && region_id != incoming_region_id) + { + // After that the region is the same is incoming, it should + // stay like that + return false; + } + } + + return true; +} + +inline bool intersection_pattern_common_interior6(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: isolated regions in between + + // See #case_recursive_boxes_75 + + // Incoming: one region + // In between: several rings having isolated region, all the same + // Outging == incoming + + std::size_t const n = aggregation.size(); + if (n < 3) + { + return false; + } + + sort_by_side::rank_with_rings const& incoming = aggregation.front(); + sort_by_side::rank_with_rings const& outgoing = aggregation.back(); + sort_by_side::rank_with_rings const& first_isolated = aggregation[2]; + + bool const incoming_ok = + incoming.all_from() + && incoming.has_unique_region_id() + && ! incoming.is_isolated(); + + if (! incoming_ok) + { + return false; + } + + signed_size_type const incoming_region_id = incoming.region_id(); + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.has_unique_region_id() + && ! outgoing.is_isolated() + && outgoing.region_id() == incoming_region_id; + + if (! outgoing_ok) + { + return false; + } + + const signed_size_type isolated_region_id = first_isolated.region_id(); + + for (std::size_t i = 1; i < n - 1; i++) + { + sort_by_side::rank_with_rings const& rwr = aggregation[i]; + if (! rwr.has_unique_region_id() + || ! rwr.is_isolated() + || rwr.region_id() != isolated_region_id) + { + return false; + } + } + + selected_rank = n - 1; + + return true; +} + }} // namespace detail::overlay #endif // DOXYGEN_NO_DETAIL diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp index af643a822b..4df3f6e7ac 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp @@ -41,6 +41,7 @@ template typename Geometry1, typename Geometry2, typename Turns, + typename TurnInfoMap, typename Clusters, typename IntersectionStrategy, typename RobustPolicy, @@ -64,7 +65,8 @@ struct traversal_ring_creator = operation_from_overlay<OverlayType>::value; inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2, - Turns& turns, Clusters const& clusters, + Turns& turns, TurnInfoMap& turn_info_map, + Clusters const& clusters, IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy, Visitor& visitor) : m_trav(geometry1, geometry2, turns, clusters, @@ -73,6 +75,7 @@ struct traversal_ring_creator , m_geometry1(geometry1) , m_geometry2(geometry2) , m_turns(turns) + , m_turn_info_map(turn_info_map) , m_clusters(clusters) , m_intersection_strategy(intersection_strategy) , m_robust_policy(robust_policy) @@ -203,7 +206,7 @@ struct traversal_ring_creator return traverse_error_none; } - if (start_turn.cluster_id >= 0) + if (start_turn.is_clustered()) { turn_type const& turn = m_turns[current_turn_index]; if (turn.cluster_id == start_turn.cluster_id) @@ -286,7 +289,7 @@ struct traversal_ring_creator m_robust_policy); rings.push_back(ring); - m_trav.finalize_visit_info(); + m_trav.finalize_visit_info(m_turn_info_map); finalized_ring_size++; } } @@ -347,6 +350,7 @@ private: Geometry1 const& m_geometry1; Geometry2 const& m_geometry2; Turns& m_turns; + TurnInfoMap& m_turn_info_map; // contains turn-info information per ring Clusters const& m_clusters; IntersectionStrategy const& m_intersection_strategy; RobustPolicy const& m_robust_policy; diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp index 0b4f393ef4..72f9c4f12a 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp @@ -48,17 +48,24 @@ template > struct traversal_switch_detector { - enum isolation_type { isolation_unknown = -1, isolation_no = 0, isolation_yes = 1 }; + enum isolation_type + { + isolation_unknown = -1, + isolation_no = 0, + isolation_yes = 1, + isolation_multiple = 2 + }; typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; + typedef std::set<signed_size_type> set_type; // Per ring, first turns are collected (in turn_indices), and later // a region_id is assigned struct merged_ring_properties { signed_size_type region_id; - std::set<signed_size_type> turn_indices; + set_type turn_indices; merged_ring_properties() : region_id(-1) @@ -68,7 +75,8 @@ struct traversal_switch_detector struct connection_properties { std::size_t count; - std::set<signed_size_type> cluster_indices; + // Contains turn-index OR, if clustered, minus-cluster_id + set_type unique_turn_ids; connection_properties() : count(0) {} @@ -82,6 +90,7 @@ struct traversal_switch_detector { signed_size_type region_id; isolation_type isolated; + set_type unique_turn_ids; // Maps from connected region_id to their properties connection_map connected_region_counts; @@ -96,7 +105,7 @@ struct traversal_switch_detector typedef std::map<ring_identifier, merged_ring_properties > merge_map; typedef std::map<signed_size_type, region_properties> region_connection_map; - typedef std::set<signed_size_type>::const_iterator set_iterator; + typedef set_type::const_iterator set_iterator; inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2, Turns& turns, Clusters& clusters, @@ -110,111 +119,232 @@ struct traversal_switch_detector { } - isolation_type get_isolation(region_properties const& properties, - signed_size_type parent_region_id, - const std::set<signed_size_type>& visited) + bool inspect_difference(set_type& turn_id_difference, + set_type const& turn_ids, + set_type const& other_turn_ids) const { - if (properties.isolated != isolation_unknown) + // TODO: consider if std::set_difference can be used in the final version + int const turn_count = turn_ids.size(); + int const other_turn_count = other_turn_ids.size(); + + // First quick check on size (TODO: implement multiple-multiple connections) + if (turn_count - other_turn_count > 1) { - return properties.isolated; + return false; } - bool all_colocated = true; - int unique_cluster_id = -1; - for (typename connection_map::const_iterator it = properties.connected_region_counts.begin(); - all_colocated && it != properties.connected_region_counts.end(); ++it) + // Check if all turns are also present in the connection. + // The difference is returned + for (set_iterator it = turn_ids.begin(); it != turn_ids.end(); ++it) { - connection_properties const& cprop = it->second; - if (cprop.cluster_indices.size() != 1) - { - // Either no cluster (non colocated point), or more clusters - all_colocated = false; - } - int const cluster_id = *cprop.cluster_indices.begin(); - if (cluster_id == -1) + signed_size_type const& id = *it; + if (other_turn_ids.count(id) == 0) { - all_colocated = false; - } - else if (unique_cluster_id == -1) - { - unique_cluster_id = cluster_id; - } - else if (unique_cluster_id != cluster_id) - { - all_colocated = false; + turn_id_difference.insert(id); } } - if (all_colocated) + return true; + } + + bool one_connection_to_another_region(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | + // | / \| + // | | x + // | \__/| + // | | + // +----------------------+ + + if (region.connected_region_counts.size() == 1) { - return isolation_yes; + connection_properties const& cprop = region.connected_region_counts.begin()->second; + return cprop.count <= 1; } + return region.connected_region_counts.empty(); + } + // TODO: might be combined with previous + bool multiple_connections_to_one_region(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | + // | / \| + // | | x + // | \ /| + // | / \| + // | | x + // | \__/| + // | | + // +----------------------+ + + if (region.connected_region_counts.size() == 1) + { + connection_properties const& cprop = region.connected_region_counts.begin()->second; + return cprop.count > 1; + } + return false; + } - // It is isolated if there is only one connection, or if there are more connections but all - // of them are isolated themselves, or if there are more connections - // but they are all colocated - std::size_t non_isolation_count = 0; - bool child_not_isolated = false; - for (typename connection_map::const_iterator it = properties.connected_region_counts.begin(); - it != properties.connected_region_counts.end(); ++it) + bool one_connection_to_multiple_regions(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | __ + // | / \|/ | + // | | x | + // | \__/|\__| + // | | + // +----------------------+ + + bool first = true; + signed_size_type first_turn_id = 0; + for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); + it != region.connected_region_counts.end(); ++it) { - signed_size_type const region_id = it->first; connection_properties const& cprop = it->second; - if (region_id == parent_region_id) + if (cprop.count != 1) { - // Normal situation, skip its direct parent - continue; + return false; } - if (visited.count(region_id) > 0) + signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); + if (first) { - // Find one of its ancestors again, this is a ring. Not isolated. - return isolation_no; + first_turn_id = unique_turn_id; + first = false; } - if (cprop.count > 1) + else if (first_turn_id != unique_turn_id) { - return isolation_no; + return false; } + } + return true; + } - typename region_connection_map::iterator mit = m_connected_regions.find(region_id); + bool has_only_isolated_children(region_properties const& region) const + { + bool first_with_turn = true; + bool first_with_multiple = true; + signed_size_type first_turn_id = 0; + signed_size_type first_multiple_region_id = 0; + + for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); + it != region.connected_region_counts.end(); ++it) + { + signed_size_type const region_id = it->first; + connection_properties const& cprop = it->second; + + typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id); if (mit == m_connected_regions.end()) { // Should not occur - continue; + return false; } - std::set<signed_size_type> vis = visited; - vis.insert(parent_region_id); + region_properties const& connected_region = mit->second; + + bool const multiple = connected_region.isolated == isolation_multiple; - region_properties& prop = mit->second; - if (prop.isolated == isolation_unknown) + if (cprop.count != 1) { - isolation_type const iso = get_isolation(prop, properties.region_id, vis); - prop.isolated = iso; - if (iso == isolation_no) + if (! multiple) + { + return false; + } + + // It connects multiple times to an isolated region. + // This is allowed as long as it happens only once + if (first_with_multiple) + { + first_multiple_region_id = connected_region.region_id; + first_with_multiple = false; + } + else if (first_multiple_region_id != connected_region.region_id) + { + return false; + } + + // Turns in region should be either present in the connection, + // of form part of the connection with the other region + set_type diff; + if (! inspect_difference(diff, region.unique_turn_ids, + connected_region.unique_turn_ids)) { - child_not_isolated = true; + return false; + } + if (diff.size() > 1) + { + // For now: + return false; } } - if (prop.isolated == isolation_no) + + if (connected_region.isolated != isolation_yes && ! multiple) { - non_isolation_count++; + signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); + if (first_with_turn) + { + first_turn_id = unique_turn_id; + first_with_turn = false; + } + else if (first_turn_id != unique_turn_id) + { + return false; + } } } - - return child_not_isolated || non_isolation_count > 1 ? isolation_no : isolation_yes; + // If there is only one connection (with a 'parent'), and all other + // connections are itself isolated, it is isolated + return true; } void get_isolated_regions() { - for (typename region_connection_map::iterator it = m_connected_regions.begin(); + typedef typename region_connection_map::iterator it_type; + + // First time: check regions isolated (one connection only), + // semi-isolated (multiple connections between same region), + // and complex isolated (connection with multiple rings but all + // at same point) + for (it_type it = m_connected_regions.begin(); it != m_connected_regions.end(); ++it) { region_properties& properties = it->second; - if (properties.isolated == isolation_unknown) + if (one_connection_to_another_region(properties)) { - std::set<signed_size_type> visited; - properties.isolated = get_isolation(properties, properties.region_id, visited); + properties.isolated = isolation_yes; + } + else if (multiple_connections_to_one_region(properties)) + { + properties.isolated = isolation_multiple; + } + else if (one_connection_to_multiple_regions(properties)) + { + properties.isolated = isolation_yes; + } + } + + // Propagate isolation to next level + // TODO: should be optimized + std::size_t defensive_check = 0; + bool changed = true; + while (changed && defensive_check++ < m_connected_regions.size()) + { + changed = false; + for (it_type it = m_connected_regions.begin(); + it != m_connected_regions.end(); ++it) + { + region_properties& properties = it->second; + + if (properties.isolated == isolation_unknown + && has_only_isolated_children(properties)) + { + properties.isolated = isolation_yes; + changed = true; + } } } } @@ -238,7 +368,7 @@ struct traversal_switch_detector } } - void assign_regions() + void assign_region_ids() { for (typename merge_map::const_iterator it = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) @@ -259,39 +389,53 @@ struct traversal_switch_detector op.enriched.region_id = properties.region_id; } } - signed_size_type const& id0 = turn.operations[0].enriched.region_id; - signed_size_type const& id1 = turn.operations[1].enriched.region_id; - if (id0 != id1 && id0 != -1 && id1 != -1) - { - // Force insertion - m_connected_regions[id0].region_id = id0; - m_connected_regions[id1].region_id = id1; + } + } + } - connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1]; - connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0]; + void assign_connected_regions() + { + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type const& turn = m_turns[turn_index]; - if (turn.cluster_id < 0) - { - // Turn is not colocated, add reference to connection - prop0.count++; - prop1.count++; - } - else - { - // Turn is colocated, only add region reference if it was not yet registered - if (prop0.cluster_indices.count(turn.cluster_id) == 0) - { - prop0.count++; - } - if (prop1.cluster_indices.count(turn.cluster_id) == 0) - { - prop1.count++; - } - } - // Insert cluster-id (also -1 is inserted - reinsertion of - // same cluster id is OK) - prop0.cluster_indices.insert(turn.cluster_id); - prop1.cluster_indices.insert(turn.cluster_id); + signed_size_type const unique_turn_id + = turn.is_clustered() ? -turn.cluster_id : turn_index; + + turn_operation_type op0 = turn.operations[0]; + turn_operation_type op1 = turn.operations[1]; + + signed_size_type const& id0 = op0.enriched.region_id; + signed_size_type const& id1 = op1.enriched.region_id; + + // Add region (by assigning) and add involved turns + if (id0 != -1) + { + m_connected_regions[id0].region_id = id0; + m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id); + } + if (id1 != -1 && id0 != id1) + { + m_connected_regions[id1].region_id = id1; + m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id); + } + + if (id0 != id1 && id0 != -1 && id1 != -1) + { + // Assign connections + connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1]; + connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0]; + + // Reference this turn or cluster to later check uniqueness on ring + if (prop0.unique_turn_ids.count(unique_turn_id) == 0) + { + prop0.count++; + prop0.unique_turn_ids.insert(unique_turn_id); + } + if (prop1.unique_turn_ids.count(unique_turn_id) == 0) + { + prop1.count++; + prop1.unique_turn_ids.insert(unique_turn_id); } } } @@ -306,7 +450,7 @@ struct traversal_switch_detector return false; } - if (turn.cluster_id == -1) + if (! turn.is_clustered()) { // If it is a uu/ii-turn (non clustered), it is never same region return ! (turn.both(operation_union) || turn.both(operation_intersection)); @@ -320,39 +464,22 @@ struct traversal_switch_detector == turn.operations[1].enriched.zone; } - // If a cluster contains an ii/cc it is not same region (for intersection) - typename Clusters::const_iterator it = m_clusters.find(turn.cluster_id); - if (it == m_clusters.end()) - { - // Should not occur - return true; - } - - cluster_info const& cinfo = it->second; - for (set_iterator sit = cinfo.turn_indices.begin(); - sit != cinfo.turn_indices.end(); ++sit) - { - turn_type const& cluster_turn = m_turns[*sit]; - if (cluster_turn.both(operation_union) - || cluster_turn.both(operation_intersection)) - { - return false; - } - } - - // It is the same region - return false; + // For an intersection, two regions connect if they are not ii + // (ii-regions are isolated) or, in some cases, not iu (for example + // when a multi-polygon is inside an interior ring and connecting it) + return ! (turn.both(operation_intersection) + || turn.combination(operation_intersection, operation_union)); } - inline int get_region_id(turn_operation_type const& op) const + inline signed_size_type get_region_id(turn_operation_type const& op) const { return op.enriched.region_id; } void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id, - merged_ring_properties& properties, int region_id = -1) + merged_ring_properties& properties, signed_size_type region_id = -1) { if (properties.region_id > 0) { @@ -400,7 +527,7 @@ struct traversal_switch_detector } void propagate_region(signed_size_type& new_region_id, - ring_identifier const& ring_id, int region_id) + ring_identifier const& ring_id, signed_size_type region_id) { typename merge_map::iterator it = m_turns_per_ring.find(ring_id); if (it != m_turns_per_ring.end()) @@ -438,7 +565,7 @@ struct traversal_switch_detector } } - // All rings having turns are in the map. Now iterate them + // All rings having turns are in turns/ring map. Process them. { signed_size_type new_region_id = 1; for (typename merge_map::iterator it @@ -447,7 +574,8 @@ struct traversal_switch_detector create_region(new_region_id, it->first, it->second); } - assign_regions(); + assign_region_ids(); + assign_connected_regions(); get_isolated_regions(); assign_isolation(); } @@ -464,9 +592,8 @@ struct traversal_switch_detector } // A touching cluster, gather regions - std::set<int> regions; - - std::set<signed_size_type> const& ids = cinfo.turn_indices; + set_type regions; + set_type const& ids = cinfo.turn_indices; #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl; @@ -476,14 +603,10 @@ struct traversal_switch_detector { signed_size_type turn_index = *sit; turn_type const& turn = m_turns[turn_index]; - if (turn.colocated_ii && ! turn.colocated_uu) - { - continue; - } for (int oi = 0; oi < 2; oi++) { - int const region = get_region_id(turn.operations[oi]); - regions.insert(region); + signed_size_type const region_id = get_region_id(turn.operations[oi]); + regions.insert(region_id); } } // Switch source if this cluster connects the same region @@ -497,24 +620,16 @@ struct traversal_switch_detector if (turn.discarded || turn.blocked() - || turn.cluster_id >= 0 + || turn.is_clustered() || ! (turn.both(operation_union) || turn.both(operation_intersection))) { // Skip discarded, blocked, non-uu/ii and clustered turns continue; } - if (OverlayType == overlay_buffer) - { - // For deflate, the region approach does not work because many - // pieces are outside the real polygons - // TODO: implement this in another way for buffer - // (because now buffer might output invalid geometries) - continue; - } - int const region0 = get_region_id(turn.operations[0]); - int const region1 = get_region_id(turn.operations[1]); + signed_size_type const region0 = get_region_id(turn.operations[0]); + signed_size_type const region1 = get_region_id(turn.operations[1]); // Switch sources for same region turn.switch_source = region0 == region1; @@ -529,7 +644,7 @@ struct traversal_switch_detector turn_type const& turn = m_turns[turn_index]; if ((turn.both(operation_union) || turn.both(operation_intersection)) - && turn.cluster_id < 0) + && ! turn.is_clustered()) { std::cout << "UU/II SWITCH RESULT " << turn_index << " -> " diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index 058f6c9458..b9cbea3127 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -62,14 +62,16 @@ public : typename RobustPolicy, typename Turns, typename Rings, - typename Visitor, - typename Clusters + typename TurnInfoMap, + typename Clusters, + typename Visitor > static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy, Turns& turns, Rings& rings, + TurnInfoMap& turn_info_map, Clusters& clusters, Visitor& visitor) { @@ -89,11 +91,11 @@ public : < Reverse1, Reverse2, OverlayType, Geometry1, Geometry2, - Turns, Clusters, + Turns, TurnInfoMap, Clusters, IntersectionStrategy, RobustPolicy, Visitor, Backtrack - > trav(geometry1, geometry2, turns, clusters, + > trav(geometry1, geometry2, turns, turn_info_map, clusters, intersection_strategy, robust_policy, visitor); std::size_t finalized_ring_size = boost::size(rings); diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index 3a4c2e94a1..3ed75cf09e 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -90,12 +90,10 @@ struct turn_info Point point; method_type method; bool touch_only; // True in case of method touch(interior) and lines do not cross - signed_size_type cluster_id; // For multiple turns on same location, >= 0. Else -1 + signed_size_type cluster_id; // For multiple turns on same location, > 0. Else -1. 0 is unused. bool discarded; - // TODO: move this to enriched - bool colocated_ii; // Colocated with a ii turn (TODO: or a ix turn) - bool colocated_uu; // Colocated with a uu turn or a ux turn + bool has_colocated_both; // Colocated with a uu turn (for union) or ii (other) bool switch_source; // For u/u turns which can either switch or not Container operations; @@ -105,8 +103,7 @@ struct turn_info , touch_only(false) , cluster_id(-1) , discarded(false) - , colocated_ii(false) - , colocated_uu(false) + , has_colocated_both(false) , switch_source(false) {} @@ -138,6 +135,10 @@ struct turn_info { return has(operation_blocked); } + inline bool is_clustered() const + { + return cluster_id > 0; + } private : inline bool has12(operation_type type1, operation_type type2) const diff --git a/boost/geometry/algorithms/detail/relate/less.hpp b/boost/geometry/algorithms/detail/relate/less.hpp deleted file mode 100644 index 462fcc35f1..0000000000 --- a/boost/geometry/algorithms/detail/relate/less.hpp +++ /dev/null @@ -1,83 +0,0 @@ -// Boost.Geometry (aka GGL, Generic Geometry Library) - -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. - -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014, Oracle and/or its affiliates. - -// 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) - -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - -#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP -#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP - -#include <boost/geometry/core/coordinate_dimension.hpp> -#include <boost/geometry/core/coordinate_type.hpp> -#include <boost/geometry/util/math.hpp> - -namespace boost { namespace geometry -{ - -#ifndef DOXYGEN_NO_DISPATCH -namespace detail_dispatch { namespace relate { - -// TODO: Integrate it with geometry::less? - -template <typename Point1, - typename Point2, - std::size_t I = 0, - std::size_t D = geometry::dimension<Point1>::value> -struct less -{ - static inline bool apply(Point1 const& left, Point2 const& right) - { - typename geometry::coordinate_type<Point1>::type - cleft = geometry::get<I>(left); - typename geometry::coordinate_type<Point2>::type - cright = geometry::get<I>(right); - - if ( geometry::math::equals(cleft, cright) ) - { - return less<Point1, Point2, I + 1, D>::apply(left, right); - } - else - { - return cleft < cright; - } - } -}; - -template <typename Point1, typename Point2, std::size_t D> -struct less<Point1, Point2, D, D> -{ - static inline bool apply(Point1 const&, Point2 const&) - { - return false; - } -}; - -}} // namespace detail_dispatch::relate - -#endif - -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace relate { - -struct less -{ - template <typename Point1, typename Point2> - inline bool operator()(Point1 const& point1, Point2 const& point2) const - { - return detail_dispatch::relate::less<Point1, Point2>::apply(point1, point2); - } -}; - -}} // namespace detail::relate -#endif // DOXYGEN_NO_DETAIL - -}} // namespace boost::geometry - -#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LESS_HPP diff --git a/boost/geometry/algorithms/detail/relate/linear_areal.hpp b/boost/geometry/algorithms/detail/relate/linear_areal.hpp index f1b4fdf81a..ddbd7d615a 100644 --- a/boost/geometry/algorithms/detail/relate/linear_areal.hpp +++ b/boost/geometry/algorithms/detail/relate/linear_areal.hpp @@ -260,17 +260,19 @@ struct linear_areal if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) return; + typedef typename IntersectionStrategy::template point_in_geometry_strategy<Geometry1, Geometry2>::type within_strategy_type; + within_strategy_type const within_strategy = intersection_strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>(); boundary_checker<Geometry1> boundary_checker1(geometry1); no_turns_la_linestring_pred < Geometry2, Result, - typename IntersectionStrategy::template point_in_geometry_strategy<Geometry1, Geometry2>::type, + within_strategy_type, boundary_checker<Geometry1>, TransposeResult > pred1(geometry2, result, - intersection_strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>(), + within_strategy, boundary_checker1); for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1); if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) diff --git a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp index 47c6963b87..8d5f21555c 100644 --- a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp +++ b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp @@ -121,7 +121,7 @@ struct multi_point_geometry_eb<Geometry, multi_linestring_tag> template <typename Point> bool apply(Point const& boundary_point) { - if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, relate::less())) + if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, geometry::less<>())) { m_boundary_found = true; return false; @@ -143,7 +143,7 @@ struct multi_point_geometry_eb<Geometry, multi_linestring_tag> typedef typename boost::range_value<MultiPoint>::type point_type; typedef std::vector<point_type> points_type; points_type points(boost::begin(multi_point), boost::end(multi_point)); - std::sort(points.begin(), points.end(), relate::less()); + std::sort(points.begin(), points.end(), geometry::less<>()); boundary_visitor<points_type> visitor(points); tc.for_each_boundary_point(visitor); diff --git a/boost/geometry/algorithms/detail/relate/point_point.hpp b/boost/geometry/algorithms/detail/relate/point_point.hpp index 68d8be031e..e0bed72ba3 100644 --- a/boost/geometry/algorithms/detail/relate/point_point.hpp +++ b/boost/geometry/algorithms/detail/relate/point_point.hpp @@ -21,9 +21,10 @@ #include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/algorithms/detail/relate/result.hpp> +#include <boost/geometry/policies/compare.hpp> + namespace boost { namespace geometry { @@ -213,7 +214,9 @@ struct multipoint_multipoint // sort points from the 1 MPt typedef typename geometry::point_type<SortedMultiPoint>::type point_type; std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt)); - std::sort(points.begin(), points.end(), less()); + + geometry::less<> const less = geometry::less<>(); + std::sort(points.begin(), points.end(), less); bool found_inside = false; bool found_outside = false; @@ -224,7 +227,7 @@ struct multipoint_multipoint it != boost::end(iterated_mpt) ; ++it ) { bool ii = - std::binary_search(points.begin(), points.end(), *it, less()); + std::binary_search(points.begin(), points.end(), *it, less); if ( ii ) found_inside = true; else diff --git a/boost/geometry/algorithms/detail/relate/topology_check.hpp b/boost/geometry/algorithms/detail/relate/topology_check.hpp index 654999d8fb..810466ec05 100644 --- a/boost/geometry/algorithms/detail/relate/topology_check.hpp +++ b/boost/geometry/algorithms/detail/relate/topology_check.hpp @@ -13,7 +13,8 @@ #include <boost/geometry/algorithms/detail/equals/point_point.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> + +#include <boost/geometry/policies/compare.hpp> #include <boost/geometry/util/has_nan_coordinate.hpp> #include <boost/geometry/util/range.hpp> @@ -214,7 +215,7 @@ private: if (! m_endpoints.empty() ) { - std::sort(m_endpoints.begin(), m_endpoints.end(), relate::less()); + std::sort(m_endpoints.begin(), m_endpoints.end(), geometry::less<>()); m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end()); } @@ -224,7 +225,7 @@ private: template <typename It, typename Point> static inline std::size_t count_equal(It first, It last, Point const& point) { - std::pair<It, It> rng = std::equal_range(first, last, point, relate::less()); + std::pair<It, It> rng = std::equal_range(first, last, point, geometry::less<>()); return (std::size_t)std::distance(rng.first, rng.second); } diff --git a/boost/geometry/algorithms/detail/sections/section_functions.hpp b/boost/geometry/algorithms/detail/sections/section_functions.hpp index 67df3060c4..d283784e2c 100644 --- a/boost/geometry/algorithms/detail/sections/section_functions.hpp +++ b/boost/geometry/algorithms/detail/sections/section_functions.hpp @@ -19,6 +19,9 @@ #include <boost/geometry/algorithms/detail/recalculate.hpp> #include <boost/geometry/policies/robustness/robust_point_type.hpp> +// For spherical/geographic longitudes covered_by point/box +#include <boost/geometry/strategies/cartesian/point_in_box.hpp> + namespace boost { namespace geometry { @@ -61,17 +64,33 @@ struct preceding_check<0, Geometry, spherical_tag> calc_t const c0 = 0; + calc_t const value = get<0>(point); + calc_t const other_min = get<min_corner, 0>(other_box); + calc_t const other_max = get<max_corner, 0>(other_box); + + bool const pt_covered = strategy::within::covered_by_range + < + Point, 0, spherical_tag + >::apply(value, + other_min, + other_max); + + if (pt_covered) + { + return false; + } + if (dir == 1) { calc_t const diff_min = math::longitude_distance_signed < units_t, calc_t - >(get<min_corner, 0>(other_box), get<0>(point)); + >(other_min, value); calc_t const diff_min_min = math::longitude_distance_signed < units_t, calc_t - >(get<min_corner, 0>(other_box), get<min_corner, 0>(point_box)); + >(other_min, get<min_corner, 0>(point_box)); return diff_min < c0 && diff_min_min <= c0 && diff_min_min <= diff_min; } @@ -80,12 +99,12 @@ struct preceding_check<0, Geometry, spherical_tag> calc_t const diff_max = math::longitude_distance_signed < units_t, calc_t - >(get<max_corner, 0>(other_box), get<0>(point)); + >(other_max, value); calc_t const diff_max_max = math::longitude_distance_signed < units_t, calc_t - >(get<max_corner, 0>(other_box), get<max_corner, 0>(point_box)); + >(other_max, get<max_corner, 0>(point_box)); return diff_max > c0 && diff_max_max >= c0 && diff_max <= diff_max_max; } diff --git a/boost/geometry/algorithms/detail/touches/implementation.hpp b/boost/geometry/algorithms/detail/touches/implementation.hpp index 94f1fba581..0cdb8ad1d4 100644 --- a/boost/geometry/algorithms/detail/touches/implementation.hpp +++ b/boost/geometry/algorithms/detail/touches/implementation.hpp @@ -413,7 +413,8 @@ struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false> #endif // DOXYGEN_NO_DISPATCH -namespace resolve_variant { +namespace resolve_variant +{ template <typename Geometry> struct self_touches @@ -443,10 +444,11 @@ struct self_touches detail::touches::areal_interrupt_policy policy; strategy_type strategy; rescale_policy_type robust_policy; + // TODO: skip_adjacent should be set to false detail::self_get_turn_points::get_turns < false, policy_type - >::apply(geometry, strategy, robust_policy, turns, policy, 0); + >::apply(geometry, strategy, robust_policy, turns, policy, 0, true); return policy.result(); } diff --git a/boost/geometry/algorithms/detail/within/multi_point.hpp b/boost/geometry/algorithms/detail/within/multi_point.hpp index 7e85f33383..359853f6a4 100644 --- a/boost/geometry/algorithms/detail/within/multi_point.hpp +++ b/boost/geometry/algorithms/detail/within/multi_point.hpp @@ -21,7 +21,6 @@ #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> -#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> #include <boost/geometry/algorithms/envelope.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> @@ -33,6 +32,8 @@ #include <boost/geometry/index/rtree.hpp> +#include <boost/geometry/policies/compare.hpp> + #include <boost/geometry/strategies/covered_by.hpp> #include <boost/geometry/strategies/disjoint.hpp> @@ -63,7 +64,7 @@ struct multi_point_point } }; -// NOTE: currently the strategy is ignored, math::equals() is used inside relate::less +// NOTE: currently the strategy is ignored, math::equals() is used inside geometry::less<> struct multi_point_multi_point { template <typename MultiPoint1, typename MultiPoint2, typename Strategy> @@ -73,7 +74,7 @@ struct multi_point_multi_point { typedef typename boost::range_value<MultiPoint2>::type point2_type; - relate::less const less = relate::less(); + geometry::less<> const less = geometry::less<>(); std::vector<point2_type> points2(boost::begin(multi_point2), boost::end(multi_point2)); std::sort(points2.begin(), points2.end(), less); diff --git a/boost/geometry/algorithms/dispatch/expand.hpp b/boost/geometry/algorithms/dispatch/expand.hpp index 2c23d6a1ce..c7a7696480 100644 --- a/boost/geometry/algorithms/dispatch/expand.hpp +++ b/boost/geometry/algorithms/dispatch/expand.hpp @@ -5,10 +5,11 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France. -// This file was modified by Oracle on 2015. -// Modifications copyright (c) 2015, Oracle and/or its affiliates. +// This file was modified by Oracle on 2015, 2017. +// Modifications copyright (c) 2015-2017, 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 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. @@ -39,8 +40,6 @@ namespace dispatch template < typename GeometryOut, typename Geometry, - typename StrategyLess = strategy::compare::default_strategy, - typename StrategyGreater = strategy::compare::default_strategy, typename TagOut = typename tag<GeometryOut>::type, typename Tag = typename tag<Geometry>::type, typename CSTagOut = typename cs_tag<GeometryOut>::type, |