diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
31 files changed, 2498 insertions, 746 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp index df62a1f2f6..106ecaad07 100644 --- a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp +++ b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp @@ -24,8 +24,12 @@ struct ring_with_direction { ring_identifier ring_id; direction_type direction; - bool only_turn_on_ring; + std::size_t turn_index; + int operation_index; + operation_type operation; + signed_size_type region_id; + bool isolated; inline bool operator<(ring_with_direction const& other) const { @@ -36,7 +40,11 @@ struct ring_with_direction ring_with_direction() : direction(dir_unknown) - , only_turn_on_ring(false) + , turn_index(-1) + , operation_index(0) + , operation(operation_none) + , region_id(-1) + , isolated(false) {} }; @@ -50,28 +58,168 @@ struct rank_with_rings { } + inline bool all_equal(direction_type dir_type) const + { + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + if (it->direction != dir_type) + { + return false; + } + } + return true; + } + inline bool all_to() const { + return all_equal(sort_by_side::dir_to); + } + + inline bool all_from() const + { + return all_equal(sort_by_side::dir_from); + } + + inline bool has_only(operation_type op) const + { + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + const ring_with_direction& rwd = *it; + if (rwd.operation != op) + { + return false; + } + } + return true; + } + + //! Check if set has both op1 and op2, but no others + inline bool has_only_both(operation_type op1, operation_type op2) const + { + bool has1 = false; + bool has2 = false; for (std::set<ring_with_direction>::const_iterator it = rings.begin(); it != rings.end(); ++it) { - if (it->direction == sort_by_side::dir_from) + const ring_with_direction& rwd = *it; + + if (rwd.operation == op1) { has1 = true; } + else if (rwd.operation == op2) { has2 = true; } + else { return false; } + } + return has1 && has2; + } + + inline bool is_isolated() const + { + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + const ring_with_direction& rwd = *it; + if (! rwd.isolated) { return false; } } return true; } + + inline bool has_unique_region_id() const + { + int region_id = -1; + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + const ring_with_direction& rwd = *it; + if (region_id == -1) + { + region_id = rwd.region_id; + } + else if (rwd.region_id != region_id) + { + return false; + } + } + return true; + } + + inline int region_id() const + { + int region_id = -1; + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + const ring_with_direction& rwd = *it; + if (region_id == -1) + { + region_id = rwd.region_id; + } + else if (rwd.region_id != region_id) + { + return -1; + } + } + return region_id; + } + + template <typename Turns> + inline bool traversable(Turns const& turns) const + { + 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(); + it != rings.end(); ++it) + { + const ring_with_direction& rwd = *it; + turn_type const& turn = turns[rwd.turn_index]; + turn_operation_type const& op = turn.operations[rwd.operation_index]; + + // TODO: this is still necessary, but makes it order-dependent + // which should not be done. + + // This would obsolete the whole function and should be solved + // in a different way + if (op.visited.finalized() || op.visited.visited()) + { + return false; + } + } + return true; + } + }; -template <typename Sbs> -inline void aggregate_operations(Sbs const& sbs, std::vector<rank_with_rings>& aggregation) +template <typename Sbs, typename Turns> +inline void aggregate_operations(Sbs const& sbs, std::vector<rank_with_rings>& aggregation, + Turns const& turns, + operation_type target_operation) { + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + aggregation.clear(); for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { typename Sbs::rp const& ranked_point = sbs.m_ranked_points[i]; + turn_type const& turn = turns[ranked_point.turn_index]; + + turn_operation_type const& op = turn.operations[ranked_point.operation_index]; + + if (! ((target_operation == operation_union && ranked_point.rank == 0) + || op.operation == target_operation + || op.operation == operation_continue + || (op.operation == operation_blocked && ranked_point.direction == dir_from))) + { + // Always take rank 0 (because self-turns are blocked) + // Don't consider union/blocked (aggregate is only used for intersections) + // Blocked is allowed for from + continue; + } + if (aggregation.empty() || aggregation.back().rank != ranked_point.rank) { rank_with_rings current; @@ -81,10 +229,14 @@ inline void aggregate_operations(Sbs const& sbs, std::vector<rank_with_rings>& a ring_with_direction rwd; segment_identifier const& sid = ranked_point.seg_id; + rwd.ring_id = ring_identifier(sid.source_index, sid.multi_index, sid.ring_index); rwd.direction = ranked_point.direction; - rwd.only_turn_on_ring = ranked_point.only_turn_on_ring; - + rwd.turn_index = ranked_point.turn_index; + rwd.operation_index = ranked_point.operation_index; + rwd.operation = op.operation; + rwd.region_id = op.enriched.region_id; + rwd.isolated = op.enriched.isolated; aggregation.back().rings.insert(rwd); } diff --git a/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp b/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp index 03c06c28d1..fb73840798 100644 --- a/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp +++ b/boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp @@ -2,8 +2,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2017. +// Modifications copyright (c) 2014-2017 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -63,8 +63,9 @@ inline bool points_equal_or_close(Point1 const& point1, } -template <typename Range, typename Point, typename RobustPolicy> +template <typename Range, typename Point, typename SideStrategy, typename RobustPolicy> inline void append_no_dups_or_spikes(Range& range, Point const& point, + SideStrategy const& strategy, RobustPolicy const& robust_policy) { #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION @@ -92,6 +93,7 @@ inline void append_no_dups_or_spikes(Range& range, Point const& point, && point_is_spike_or_equal(point, *(boost::end(range) - 3), *(boost::end(range) - 2), + strategy, robust_policy)) { // Use the Concept/traits, so resize and append again @@ -100,8 +102,9 @@ inline void append_no_dups_or_spikes(Range& range, Point const& point, } } -template <typename Range, typename RobustPolicy> +template <typename Range, typename SideStrategy, typename RobustPolicy> inline void clean_closing_dups_and_spikes(Range& range, + SideStrategy const& strategy, RobustPolicy const& robust_policy) { std::size_t const minsize @@ -135,7 +138,7 @@ inline void clean_closing_dups_and_spikes(Range& range, // Check if closing point is a spike (this is so if the second point is // considered as a spike w.r.t. the last segment) - if (point_is_spike_or_equal(*second, *ultimate, *first, robust_policy)) + if (point_is_spike_or_equal(*second, *ultimate, *first, strategy, robust_policy)) { range::erase(range, first); if (BOOST_GEOMETRY_CONDITION(closed)) diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 2408b4b68e..78160f5204 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -20,7 +20,8 @@ #include <boost/geometry/algorithms/expand.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> -#include <boost/geometry/algorithms/within.hpp> +#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp> +#include <boost/geometry/algorithms/covered_by.hpp> #include <boost/geometry/geometries/box.hpp> @@ -37,50 +38,88 @@ namespace detail { namespace overlay template < typename Item, + typename InnerGeometry, typename Geometry1, typename Geometry2, - typename RingCollection + typename RingCollection, + typename Strategy +> +static inline bool within_selected_input(Item const& item2, + InnerGeometry const& inner_geometry, + ring_identifier const& outer_id, + Geometry1 const& geometry1, Geometry2 const& geometry2, + RingCollection const& collection, + Strategy const& strategy) +{ + typedef typename geometry::tag<Geometry1>::type tag1; + typedef typename geometry::tag<Geometry2>::type tag2; + + // NOTE: range_in_geometry first checks the item2.point and then + // if this point is on boundary it checks points of inner_geometry + // ring until a point inside/outside other geometry ring is found + switch (outer_id.source_index) + { + // covered_by + case 0 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0; + case 1 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0; + case 2 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<void>::apply(outer_id, collection), strategy) >= 0; + } + return false; +} + +template +< + typename Item, + typename Geometry1, typename Geometry2, + typename RingCollection, + typename Strategy > -static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id, +static inline bool within_selected_input(Item const& item2, + ring_identifier const& inner_id, ring_identifier const& outer_id, Geometry1 const& geometry1, Geometry2 const& geometry2, - RingCollection const& collection) + RingCollection const& collection, + Strategy const& strategy) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; - switch (ring_id.source_index) + switch (inner_id.source_index) { case 0 : - return geometry::within(item2.point, - get_ring<tag1>::apply(ring_id, geometry1)); - break; + return within_selected_input(item2, + get_ring<tag1>::apply(inner_id, geometry1), + outer_id, geometry1, geometry2, collection, strategy); case 1 : - return geometry::within(item2.point, - get_ring<tag2>::apply(ring_id, geometry2)); - break; + return within_selected_input(item2, + get_ring<tag2>::apply(inner_id, geometry2), + outer_id, geometry1, geometry2, collection, strategy); case 2 : - return geometry::within(item2.point, - get_ring<void>::apply(ring_id, collection)); - break; + return within_selected_input(item2, + get_ring<void>::apply(inner_id, collection), + outer_id, geometry1, geometry2, collection, strategy); } return false; } -template <typename Point> +template <typename Point, typename AreaType> struct ring_info_helper { - typedef typename geometry::default_area_result<Point>::type area_type; - ring_identifier id; - area_type real_area; - area_type abs_area; + AreaType real_area; + AreaType abs_area; model::box<Point> envelope; inline ring_info_helper() : real_area(0), abs_area(0) {} - inline ring_info_helper(ring_identifier i, area_type a) + inline ring_info_helper(ring_identifier i, AreaType const& a) : id(i), real_area(a), abs_area(geometry::math::abs(a)) {} }; @@ -104,7 +143,14 @@ struct ring_info_helper_ovelaps_box } }; -template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap> +template +< + typename Geometry1, + typename Geometry2, + typename Collection, + typename RingMap, + typename Strategy +> struct assign_visitor { typedef typename RingMap::mapped_type ring_info_type; @@ -113,26 +159,27 @@ struct assign_visitor Geometry2 const& m_geometry2; Collection const& m_collection; RingMap& m_ring_map; + Strategy const& m_strategy; bool m_check_for_orientation; - inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c, - RingMap& map, bool check) + RingMap& map, Strategy const& strategy, bool check) : m_geometry1(g1) , m_geometry2(g2) , m_collection(c) , m_ring_map(map) + , m_strategy(strategy) , m_check_for_orientation(check) {} template <typename Item> - inline void apply(Item const& outer, Item const& inner, bool first = true) + inline bool apply(Item const& outer, Item const& inner, bool first = true) { if (first && outer.abs_area < inner.abs_area) { // Apply with reversed arguments apply(inner, outer, false); - return; + return true; } if (m_check_for_orientation @@ -141,8 +188,10 @@ struct assign_visitor { ring_info_type& inner_in_map = m_ring_map[inner.id]; - if (geometry::within(inner_in_map.point, outer.envelope) - && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection) + if (geometry::covered_by(inner_in_map.point, outer.envelope) + && within_selected_input(inner_in_map, inner.id, outer.id, + m_geometry1, m_geometry2, m_collection, + m_strategy) ) { // Assign a parent if there was no earlier parent, or the newly @@ -155,6 +204,8 @@ struct assign_visitor } } } + + return true; } }; @@ -165,12 +216,14 @@ template < typename Geometry1, typename Geometry2, typename RingCollection, - typename RingMap + typename RingMap, + typename Strategy > inline void assign_parents(Geometry1 const& geometry1, Geometry2 const& geometry2, RingCollection const& collection, RingMap& ring_map, + Strategy const& strategy, bool check_for_orientation = false) { typedef typename geometry::tag<Geometry1>::type tag1; @@ -179,11 +232,15 @@ inline void assign_parents(Geometry1 const& geometry1, typedef typename RingMap::mapped_type ring_info_type; typedef typename ring_info_type::point_type point_type; typedef model::box<point_type> box_type; + typedef typename Strategy::template area_strategy + < + point_type + >::type::return_type area_result_type; typedef typename RingMap::iterator map_iterator_type; { - typedef ring_info_helper<point_type> helper; + typedef ring_info_helper<point_type, area_result_type> helper; typedef std::vector<helper> vector_type; typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type; @@ -204,17 +261,21 @@ inline void assign_parents(Geometry1 const& geometry1, { case 0 : geometry::envelope(get_ring<tag1>::apply(it->first, geometry1), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; case 1 : geometry::envelope(get_ring<tag2>::apply(it->first, geometry2), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; case 2 : geometry::envelope(get_ring<void>::apply(it->first, collection), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; } + + // Expand envelope slightly + expand_by_epsilon(item.envelope); + if (item.real_area > 0) { count_positive++; @@ -257,8 +318,9 @@ inline void assign_parents(Geometry1 const& geometry1, assign_visitor < Geometry1, Geometry2, - RingCollection, RingMap - > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation); + RingCollection, RingMap, + Strategy + > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation); geometry::partition < @@ -315,18 +377,20 @@ template < typename Geometry, typename RingCollection, - typename RingMap + typename RingMap, + typename Strategy > inline void assign_parents(Geometry const& geometry, RingCollection const& collection, RingMap& ring_map, + Strategy const& strategy, bool check_for_orientation) { // 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, check_for_orientation); + assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation); } diff --git a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp index 795523d7a0..0e9bfe2ea0 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp @@ -20,6 +20,7 @@ #include <boost/geometry/core/interior_rings.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/algorithms/convert.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/util/range.hpp> #include <boost/geometry/iterators/ever_circling_iterator.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp index fe1a034f8b..c6f540a978 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp @@ -2,8 +2,8 @@ // 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. +// This file was modified by Oracle on 2014, 2017. +// Modifications 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 @@ -36,6 +36,7 @@ #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp> #include <boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> #include <boost/geometry/util/range.hpp> @@ -56,12 +57,14 @@ struct copy_segments_ring < typename Ring, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > static inline void apply(Ring const& ring, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -108,7 +111,7 @@ struct copy_segments_ring for (signed_size_type i = 0; i < count; ++i, ++it) { - detail::overlay::append_no_dups_or_spikes(current_output, *it, robust_policy); + detail::overlay::append_no_dups_or_spikes(current_output, *it, strategy, robust_policy); } } }; @@ -118,20 +121,23 @@ class copy_segments_linestring { private: // remove spikes - template <typename RangeOut, typename Point, typename RobustPolicy> + template <typename RangeOut, typename Point, typename SideStrategy, typename RobustPolicy> static inline void append_to_output(RangeOut& current_output, Point const& point, + SideStrategy const& strategy, RobustPolicy const& robust_policy, boost::true_type const&) { detail::overlay::append_no_dups_or_spikes(current_output, point, + strategy, robust_policy); } // keep spikes - template <typename RangeOut, typename Point, typename RobustPolicy> + template <typename RangeOut, typename Point, typename SideStrategy, typename RobustPolicy> static inline void append_to_output(RangeOut& current_output, Point const& point, + SideStrategy const&, RobustPolicy const&, boost::false_type const&) { @@ -143,12 +149,14 @@ public: < typename LineString, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > static inline void apply(LineString const& ls, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -169,7 +177,7 @@ public: for (signed_size_type i = 0; i < count; ++i, ++it) { - append_to_output(current_output, *it, robust_policy, + append_to_output(current_output, *it, strategy, robust_policy, boost::integral_constant<bool, RemoveSpikes>()); } } @@ -182,12 +190,14 @@ struct copy_segments_polygon < typename Polygon, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > static inline void apply(Polygon const& polygon, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -198,6 +208,7 @@ struct copy_segments_polygon ? geometry::exterior_ring(polygon) : range::at(geometry::interior_rings(polygon), seg_id.ring_index), seg_id, to_index, + strategy, robust_policy, current_output ); @@ -212,12 +223,14 @@ struct copy_segments_box < typename Box, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > static inline void apply(Box const& box, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -238,7 +251,7 @@ struct copy_segments_box for (signed_size_type i = 0; i < count; i++, index++) { detail::overlay::append_no_dups_or_spikes(current_output, - bp[index % 5], robust_policy); + bp[index % 5], strategy, robust_policy); } } @@ -252,12 +265,14 @@ struct copy_segments_multi < typename MultiGeometry, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > static inline void apply(MultiGeometry const& multi_geometry, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -271,6 +286,7 @@ struct copy_segments_multi // Call the single-version Policy::apply(range::at(multi_geometry, seg_id.multi_index), seg_id, to_index, + strategy, robust_policy, current_output); } @@ -340,12 +356,14 @@ template bool Reverse, typename Geometry, typename SegmentIdentifier, + typename SideStrategy, typename RobustPolicy, typename RangeOut > inline void copy_segments(Geometry const& geometry, SegmentIdentifier const& seg_id, signed_size_type to_index, + SideStrategy const& strategy, RobustPolicy const& robust_policy, RangeOut& range_out) { @@ -355,7 +373,7 @@ inline void copy_segments(Geometry const& geometry, < typename tag<Geometry>::type, Reverse - >::apply(geometry, seg_id, to_index, robust_policy, range_out); + >::apply(geometry, seg_id, to_index, strategy, robust_policy, range_out); } diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 5cab2b4cb8..47225328df 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -19,20 +24,21 @@ # include <iostream> # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> # include <boost/geometry/io/wkt/wkt.hpp> -# define BOOST_GEOMETRY_DEBUG_IDENTIFIER +# if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER) +# define BOOST_GEOMETRY_DEBUG_IDENTIFIER + #endif #endif #include <boost/range.hpp> -#include <boost/geometry/iterators/ever_circling_iterator.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> -#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp> +#include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp> +#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> -#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> #include <boost/geometry/policies/robustness/robust_type.hpp> -#include <boost/geometry/strategies/side.hpp> + #ifdef BOOST_GEOMETRY_DEBUG_ENRICH # include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp> #endif @@ -58,7 +64,7 @@ template typename Turns, typename Geometry1, typename Geometry2, typename RobustPolicy, - typename Strategy + typename SideStrategy > inline void enrich_sort(Operations& operations, Turns const& turns, @@ -66,7 +72,7 @@ inline void enrich_sort(Operations& operations, Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, - Strategy const& /*strategy*/) + SideStrategy const& strategy) { std::sort(boost::begin(operations), boost::end(operations), @@ -76,8 +82,9 @@ inline void enrich_sort(Operations& operations, typename boost::range_value<Operations>::type, Geometry1, Geometry2, RobustPolicy, + SideStrategy, Reverse1, Reverse2 - >(turns, for_operation, geometry1, geometry2, robust_policy)); + >(turns, for_operation, geometry1, geometry2, robust_policy, strategy)); } @@ -145,7 +152,7 @@ inline void enrich_assign(Operations& operations, Turns& turns) it != boost::end(operations); ++it) { - op_type& op = turns[it->turn_index] + op_type const& op = turns[it->turn_index] .operations[it->operation_index]; std::cout << it->turn_index @@ -171,9 +178,7 @@ inline void enrich_assign(Operations& operations, Turns& turns) template <typename Turns, typename MappedVector> -inline void create_map(Turns const& turns, - detail::overlay::operation_type for_operation, - MappedVector& mapped_vector) +inline void create_map(Turns const& turns, MappedVector& mapped_vector) { typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::container_type container_type; @@ -195,15 +200,6 @@ inline void create_map(Turns const& turns, continue; } - if (for_operation == operation_intersection - && turn.cluster_id == -1 - && turn.both(operation_union)) - { - // Only include uu turns if part of cluster (to block potential paths), - // otherwise they can block possibly viable paths - continue; - } - std::size_t op_index = 0; for (typename boost::range_iterator<container_type const>::type op_it = boost::begin(turn.operations); @@ -225,6 +221,56 @@ inline void create_map(Turns const& turns, } } +template <typename Point1, typename Point2> +inline typename geometry::coordinate_type<Point1>::type + distance_measure(Point1 const& a, Point2 const& b) +{ + // TODO: use comparable distance for point-point instead - but that + // causes currently cycling include problems + typedef typename geometry::coordinate_type<Point1>::type ctype; + ctype const dx = get<0>(a) - get<0>(b); + ctype const dy = get<1>(a) - get<1>(b); + return dx * dx + dy * dy; +} + +template <typename Turns> +inline void calculate_remaining_distance(Turns& turns) +{ + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type op_type; + + for (typename boost::range_iterator<Turns>::type + it = boost::begin(turns); + it != boost::end(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]; + + if (op0.remaining_distance != 0 + || op1.remaining_distance != 0) + { + continue; + } + + int const to_index0 = op0.enriched.get_next_turn_index(); + int const to_index1 = op1.enriched.get_next_turn_index(); + if (to_index1 >= 0 + && to_index1 >= 0 + && to_index0 != to_index1) + { + op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point); + op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point); + } + } +} + }} // namespace detail::overlay #endif //DOXYGEN_NO_DETAIL @@ -239,7 +285,7 @@ inline void create_map(Turns const& turns, \tparam Clusters type of cluster container \tparam Geometry1 \tparam_geometry \tparam Geometry2 \tparam_geometry -\tparam Strategy side strategy type +\tparam SideStrategy side strategy type \param turns container containing intersection points \param clusters container containing clusters \param geometry1 \param_geometry @@ -255,16 +301,21 @@ template typename Clusters, typename Geometry1, typename Geometry2, typename RobustPolicy, - typename Strategy + typename SideStrategy > inline void enrich_intersection_points(Turns& turns, Clusters& clusters, Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, - Strategy const& strategy) + SideStrategy const& strategy) { - static const detail::overlay::operation_type for_operation + static const detail::overlay::operation_type target_operation = detail::overlay::operation_from_overlay<OverlayType>::value; + static const detail::overlay::operation_type opposite_operation + = target_operation == detail::overlay::operation_union + ? detail::overlay::operation_intersection + : detail::overlay::operation_union; + typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type op_type; typedef detail::overlay::indexed_turn_operation @@ -278,27 +329,68 @@ inline void enrich_intersection_points(Turns& turns, std::vector<indexed_turn_operation> > mapped_vector_type; + bool has_cc = false; bool const has_colocations - = detail::overlay::handle_colocations<Reverse1, Reverse2>(turns, + = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns, clusters, geometry1, geometry2); - // Discard none turns, if any + // Discard turns not part of target overlay for (typename boost::range_iterator<Turns>::type it = boost::begin(turns); it != boost::end(turns); ++it) { - if (it->both(detail::overlay::operation_none)) + turn_type& turn = *it; + + if (turn.both(detail::overlay::operation_none)) + { + turn.discarded = true; + continue; + } + + if (turn.both(opposite_operation)) { - it->discarded = true; + // For intersections, remove uu to avoid the need to travel + // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33) + // Also, for union, discard ii + turn.discarded = true; + turn.cluster_id = -1; + continue; + } + + if (detail::overlay::is_self_turn<OverlayType>(turn) + && turn.cluster_id < 0 + && ! turn.both(target_operation)) + { + // Only keep self-uu-turns or self-ii-turns + turn.discarded = true; + turn.cluster_id = -1; + continue; + } + + if (! turn.discarded + && turn.both(detail::overlay::operation_continue)) + { + has_cc = true; } } + detail::overlay::discard_closed_turns + < + OverlayType, + target_operation + >::apply(turns, geometry1, geometry2); + detail::overlay::discard_open_turns + < + OverlayType, + target_operation + >::apply(turns, geometry1, geometry2); + // Create a map of vectors of indexed operation-types to be able // to sort intersection points PER RING mapped_vector_type mapped_vector; - detail::overlay::create_map(turns, for_operation, mapped_vector); + detail::overlay::create_map(turns, mapped_vector); // No const-iterator; contents of mapped copy is temporary, // and changed by enrich @@ -312,7 +404,7 @@ inline void enrich_intersection_points(Turns& turns, << mit->first << std::endl; #endif detail::overlay::enrich_sort<Reverse1, Reverse2>( - mit->second, turns, for_operation, + mit->second, turns, target_operation, geometry1, geometry2, robust_policy, strategy); } @@ -331,8 +423,22 @@ inline void enrich_intersection_points(Turns& turns, if (has_colocations) { - detail::overlay::gather_cluster_properties<Reverse1, Reverse2>( - clusters, turns, for_operation, geometry1, geometry2); + // First gather cluster properties (using even clusters with + // discarded turns - for open turns), then clean up clusters + detail::overlay::gather_cluster_properties + < + Reverse1, + Reverse2, + OverlayType + >(clusters, turns, target_operation, + geometry1, geometry2, strategy); + + detail::overlay::cleanup_clusters(turns, clusters); + } + + if (has_cc) + { + detail::overlay::calculate_remaining_distance(turns); } #ifdef BOOST_GEOMETRY_DEBUG_ENRICH diff --git a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp index 2643415343..fdffd665e4 100644 --- a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp @@ -37,10 +37,17 @@ struct enrichment_info , startable(true) , count_left(0) , count_right(0) + , rank(-1) , zone(-1) - , only_turn_on_ring(false) + , region_id(-1) + , isolated(false) {} + inline signed_size_type get_next_turn_index() const + { + return next_ip_index == -1 ? travels_to_ip_index : next_ip_index; + } + // vertex to which is free travel after this IP, // so from "segment_index+1" to "travels_to_vertex_index", without IP-s, // can be -1 @@ -57,8 +64,10 @@ struct enrichment_info // Counts if polygons left/right of this operation std::size_t count_left; std::size_t count_right; + signed_size_type rank; // in cluster signed_size_type zone; // open zone, in cluster - bool only_turn_on_ring; // True if it is the only turn on a ring (for clusters) + signed_size_type region_id; + bool isolated; }; diff --git a/boost/geometry/algorithms/detail/overlay/follow.hpp b/boost/geometry/algorithms/detail/overlay/follow.hpp index 22807b5140..589e12cc2b 100644 --- a/boost/geometry/algorithms/detail/overlay/follow.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow.hpp @@ -2,10 +2,10 @@ // 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. - +// This file was modified by Oracle on 2014, 2017. +// Modifications 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 // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -55,21 +55,14 @@ template typename Turn, typename Operation, typename LineString, - typename Polygon + typename Polygon, + typename PtInPolyStrategy > static inline bool last_covered_by(Turn const& turn, Operation const& op, - LineString const& linestring, Polygon const& polygon) + LineString const& linestring, Polygon const& polygon, + PtInPolyStrategy const& strategy) { - // Check any point between the this one and the first IP - typedef typename geometry::point_type<LineString>::type point_type; - point_type point_in_between; - detail::point_on_border::midpoint_helper - < - point_type, - 0, dimension<point_type>::value - >::apply(point_in_between, *(::boost::begin(linestring) + op.seg_id.segment_index), turn.point); - - return geometry::covered_by(point_in_between, polygon); + return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy); } @@ -78,17 +71,19 @@ template typename Turn, typename Operation, typename LineString, - typename Polygon + typename Polygon, + typename PtInPolyStrategy > static inline bool is_leaving(Turn const& turn, Operation const& op, bool entered, bool first, - LineString const& linestring, Polygon const& polygon) + LineString const& linestring, Polygon const& polygon, + PtInPolyStrategy const& strategy) { if (op.operation == operation_union) { return entered || turn.method == method_crosses - || (first && last_covered_by(turn, op, linestring, polygon)) + || (first && last_covered_by(turn, op, linestring, polygon, strategy)) ; } return false; @@ -100,11 +95,13 @@ template typename Turn, typename Operation, typename LineString, - typename Polygon + typename Polygon, + typename PtInPolyStrategy > static inline bool is_staying_inside(Turn const& turn, Operation const& op, bool entered, bool first, - LineString const& linestring, Polygon const& polygon) + LineString const& linestring, Polygon const& polygon, + PtInPolyStrategy const& strategy) { if (turn.method == method_crosses) { @@ -115,7 +112,7 @@ static inline bool is_staying_inside(Turn const& turn, Operation const& op, if (is_entering(turn, op)) { - return entered || (first && last_covered_by(turn, op, linestring, polygon)); + return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy)); } return false; @@ -126,14 +123,16 @@ template typename Turn, typename Operation, typename Linestring, - typename Polygon + typename Polygon, + typename PtInPolyStrategy > static inline bool was_entered(Turn const& turn, Operation const& op, bool first, - Linestring const& linestring, Polygon const& polygon) + Linestring const& linestring, Polygon const& polygon, + PtInPolyStrategy const& strategy) { if (first && (turn.method == method_collinear || turn.method == method_equal)) { - return last_covered_by(turn, op, linestring, polygon); + return last_covered_by(turn, op, linestring, polygon, strategy); } return false; } @@ -158,6 +157,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> typename LineString, typename Point, typename Operation, + typename SideStrategy, typename RobustPolicy > static inline void enter(LineStringOut& current_piece, @@ -165,6 +165,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> segment_identifier& segment_id, signed_size_type , Point const& point, Operation const& operation, + SideStrategy const& , RobustPolicy const& , OutputIterator& ) { @@ -181,6 +182,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> typename LineString, typename Point, typename Operation, + typename SideStrategy, typename RobustPolicy > static inline void leave(LineStringOut& current_piece, @@ -188,6 +190,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> segment_identifier& segment_id, signed_size_type index, Point const& point, Operation const& , + SideStrategy const& strategy, RobustPolicy const& robust_policy, OutputIterator& out) { @@ -196,7 +199,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> detail::copy_segments::copy_segments_linestring < false, RemoveSpikes - >::apply(linestring, segment_id, index, robust_policy, current_piece); + >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece); detail::overlay::append_no_duplicates(current_piece, point); if (::boost::size(current_piece) > 1) { @@ -235,17 +238,9 @@ struct action_selector<overlay_intersection, RemoveSpikes> return entered; } - template - < - typename Point, - typename Geometry, - typename RobustPolicy - > - static inline bool included(Point const& point, - Geometry const& geometry, - RobustPolicy const& ) + static inline bool included(int inside_value) { - return geometry::covered_by(point, geometry); + return inside_value >= 0; // covered_by } }; @@ -263,6 +258,7 @@ struct action_selector<overlay_difference, RemoveSpikes> typename LineString, typename Point, typename Operation, + typename SideStrategy, typename RobustPolicy > static inline void enter(LineStringOut& current_piece, @@ -270,11 +266,12 @@ struct action_selector<overlay_difference, RemoveSpikes> segment_identifier& segment_id, signed_size_type index, Point const& point, Operation const& operation, + SideStrategy const& strategy, RobustPolicy const& robust_policy, OutputIterator& out) { normal_action::leave(current_piece, linestring, segment_id, index, - point, operation, robust_policy, out); + point, operation, strategy, robust_policy, out); } template @@ -284,6 +281,7 @@ struct action_selector<overlay_difference, RemoveSpikes> typename LineString, typename Point, typename Operation, + typename SideStrategy, typename RobustPolicy > static inline void leave(LineStringOut& current_piece, @@ -291,11 +289,12 @@ struct action_selector<overlay_difference, RemoveSpikes> segment_identifier& segment_id, signed_size_type index, Point const& point, Operation const& operation, + SideStrategy const& strategy, RobustPolicy const& robust_policy, OutputIterator& out) { normal_action::enter(current_piece, linestring, segment_id, index, - point, operation, robust_policy, out); + point, operation, strategy, robust_policy, out); } template @@ -319,17 +318,9 @@ struct action_selector<overlay_difference, RemoveSpikes> return ! normal_action::is_entered(entered); } - template - < - typename Point, - typename Geometry, - typename RobustPolicy - > - static inline bool included(Point const& point, - Geometry const& geometry, - RobustPolicy const& robust_policy) + static inline bool included(int inside_value) { - return ! normal_action::included(point, geometry, robust_policy); + return ! normal_action::included(inside_value); } }; @@ -403,33 +394,27 @@ class follow public : - template - < - typename Point, - typename Geometry, - typename RobustPolicy - > - static inline bool included(Point const& point, - Geometry const& geometry, - RobustPolicy const& robust_policy) + static inline bool included(int inside_value) { return following::action_selector < OverlayType, RemoveSpikes - >::included(point, geometry, robust_policy); + >::included(inside_value); } template < typename Turns, typename OutputIterator, - typename RobustPolicy + typename RobustPolicy, + typename Strategy > static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon, detail::overlay::operation_type , // TODO: this parameter might be redundant Turns& turns, RobustPolicy const& robust_policy, - OutputIterator out) + OutputIterator out, + Strategy const& strategy) { typedef typename boost::range_iterator<Turns>::type turn_iterator; typedef typename boost::range_value<Turns>::type turn_type; @@ -440,6 +425,12 @@ public : typedef following::action_selector<OverlayType, RemoveSpikes> action; + typename Strategy::template point_in_geometry_strategy + < + LineString, Polygon + >::type const pt_in_poly_strategy + = strategy.template get_point_in_geometry_strategy<LineString, Polygon>(); + // Sort intersection points on segments-along-linestring, and distance // (like in enrich is done for poly/poly) std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>()); @@ -454,13 +445,13 @@ public : { turn_operation_iterator_type iit = boost::begin(it->operations); - if (following::was_entered(*it, *iit, first, linestring, polygon)) + if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy)) { debug_traverse(*it, *iit, "-> Was entered"); entered = true; } - if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon)) + if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy)) { debug_traverse(*it, *iit, "-> Staying inside"); @@ -473,17 +464,17 @@ public : entered = true; action::enter(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, - robust_policy, + strategy, robust_policy, out); } - else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon)) + else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy)) { debug_traverse(*it, *iit, "-> Leaving"); entered = false; action::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, - robust_policy, + strategy, robust_policy, out); } first = false; @@ -497,7 +488,7 @@ public : >::apply(linestring, current_segment_id, static_cast<signed_size_type>(boost::size(linestring) - 1), - robust_policy, + strategy, robust_policy, current_piece); } diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp index c249ff57ff..2a374bf0b0 100644 --- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp @@ -2,12 +2,14 @@ // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. -// 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_FOLLOW_LINEAR_LINEAR_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP @@ -183,7 +185,8 @@ protected: typename TurnIterator, typename TurnOperationIterator, typename SegmentIdentifier, - typename OutputIterator + typename OutputIterator, + typename SideStrategy > static inline OutputIterator process_turn(TurnIterator it, @@ -193,7 +196,8 @@ protected: Linestring const& linestring, LinestringOut& current_piece, SegmentIdentifier& current_segment_id, - OutputIterator oit) + OutputIterator oit, + SideStrategy const& strategy) { // We don't rescale linear/linear detail::no_rescale_policy robust_policy; @@ -208,7 +212,7 @@ protected: action::enter(current_piece, linestring, current_segment_id, op_it->seg_id.segment_index, - it->point, *op_it, robust_policy, oit); + it->point, *op_it, strategy, robust_policy, oit); } ++enter_count; } @@ -223,7 +227,7 @@ protected: action::leave(current_piece, linestring, current_segment_id, op_it->seg_id.segment_index, - it->point, *op_it, robust_policy, oit); + it->point, *op_it, strategy, robust_policy, oit); } } else if ( FollowIsolatedPoints @@ -249,14 +253,16 @@ protected: template < typename SegmentIdentifier, - typename OutputIterator + typename OutputIterator, + typename SideStrategy > static inline OutputIterator process_end(bool entered, Linestring const& linestring, SegmentIdentifier const& current_segment_id, LinestringOut& current_piece, - OutputIterator oit) + OutputIterator oit, + SideStrategy const& strategy) { if ( action::is_entered(entered) ) { @@ -269,6 +275,7 @@ protected: >::apply(linestring, current_segment_id, static_cast<signed_size_type>(boost::size(linestring) - 1), + strategy, robust_policy, current_piece); } @@ -283,11 +290,12 @@ protected: } public: - template <typename TurnIterator, typename OutputIterator> + template <typename TurnIterator, typename OutputIterator, typename SideStrategy> static inline OutputIterator apply(Linestring const& linestring, Linear const&, TurnIterator first, TurnIterator beyond, - OutputIterator oit) + OutputIterator oit, + SideStrategy const& strategy) { // Iterate through all intersection points (they are // ordered along the each line) @@ -304,7 +312,8 @@ public: entered, enter_count, linestring, current_piece, current_segment_id, - oit); + oit, + strategy); } #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) @@ -318,7 +327,8 @@ public: return process_end(entered, linestring, current_segment_id, current_piece, - oit); + oit, + strategy); } }; @@ -413,11 +423,12 @@ protected: }; public: - template <typename TurnIterator, typename OutputIterator> + template <typename TurnIterator, typename OutputIterator, typename SideStrategy> static inline OutputIterator apply(MultiLinestring const& multilinestring, Linear const& linear, TurnIterator first, TurnIterator beyond, - OutputIterator oit) + OutputIterator oit, + SideStrategy const& strategy) { BOOST_GEOMETRY_ASSERT( first != beyond ); @@ -447,7 +458,7 @@ public: has_other_multi_id(current_multi_id)); oit = Base::apply(*(ls_first + current_multi_id), - linear, per_ls_current, per_ls_next, oit); + linear, per_ls_current, per_ls_next, oit, strategy); signed_size_type next_multi_id = -1; linestring_iterator ls_next = ls_beyond; diff --git a/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp b/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp index ea9aa29f19..2eec6af665 100644 --- a/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -31,20 +36,15 @@ namespace detail { namespace overlay but we still need to know which comes first. Therefore, it is useful that using sides we are able to discover this. */ -template <typename Point1> struct get_relative_order { - typedef typename strategy::side::services::default_strategy - < - typename cs_tag<Point1>::type - >::type strategy; - - template <typename Point> + template <typename Point, typename SideStrategy> static inline int value_via_product(Point const& ti, Point const& tj, - Point const& ui, Point const& uj, int factor) + Point const& ui, Point const& uj, int factor, + SideStrategy const& strategy) { - int const side_ti_u = strategy::apply(ti, tj, ui); - int const side_tj_u = strategy::apply(ti, tj, uj); + int const side_ti_u = strategy.apply(ti, tj, ui); + int const side_tj_u = strategy.apply(ti, tj, uj); #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER std::cout << (factor == 1 ? " r//s " : " s//r ") @@ -57,13 +57,15 @@ struct get_relative_order } + template <typename Point1, typename SideStrategy> static inline int apply( Point1 const& pi, Point1 const& pj, Point1 const& ri, Point1 const& rj, - Point1 const& si, Point1 const& sj) + Point1 const& si, Point1 const& sj, + SideStrategy const& strategy) { - int const side_ri_p = strategy::apply(pi, pj, ri); - int const side_si_p = strategy::apply(pi, pj, si); + int const side_ri_p = strategy.apply(pi, pj, ri); + int const side_si_p = strategy.apply(pi, pj, si); #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER int const side_rj_p = strategy::apply(pi, pj, rj); @@ -72,10 +74,10 @@ struct get_relative_order std::cout << " s//p: " << side_si_p << " / " << side_sj_p; #endif - int value = value_via_product(si, sj, ri, rj, 1); + int value = value_via_product(si, sj, ri, rj, 1, strategy); if (value == 0) { - value = value_via_product(ri, rj, si, sj, -1); + value = value_via_product(ri, rj, si, sj, -1, strategy); } int const order = side_ri_p * side_ri_p * side_si_p * value; diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 08bc342186..895952c8fc 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -190,6 +190,7 @@ struct touch_interior : public base_turn_handler // Q turns left on the right side of P (test "MR3") // Both directions for "intersection" both(ti, operation_intersection); + ti.touch_only = true; } else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1) { @@ -197,6 +198,7 @@ struct touch_interior : public base_turn_handler // Union: take both operation // Intersection: skip both(ti, operation_union); + ti.touch_only = true; } else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q) { @@ -207,6 +209,7 @@ struct touch_interior : public base_turn_handler unsigned int index = side_qk_q == 1 ? index_q : index_p; ti.operations[index].operation = operation_union; ti.operations[1 - index].operation = operation_intersection; + ti.touch_only = true; } else if (side_qk_p == 0) { @@ -346,6 +349,7 @@ struct touch : public base_turn_handler if (side_pk_q2 == -side_qk_q) { ui_else_iu(! q_turns_left, ti); + ti.touch_only = true; return; } @@ -358,6 +362,10 @@ struct touch : public base_turn_handler { ti.operations[1].operation = operation_blocked; } + else + { + ti.touch_only = true; + } //block_second(block_q, ti); return; } @@ -373,6 +381,10 @@ struct touch : public base_turn_handler : side_qi_p1 == 1 || side_qk_p1 == 1 ? operation_union : operation_intersection; + if (! block_q) + { + ti.touch_only = true; + } return; } @@ -400,6 +412,7 @@ struct touch : public base_turn_handler if (side_pk_q1 == side_qk_p1) { uu_else_ii(right_to_left, ti); + ti.touch_only = true; return; } } @@ -418,6 +431,7 @@ struct touch : public base_turn_handler if (side_pk_q2 == side_qk_p1) { ui_else_iu(right_to_left, ti); + ti.touch_only = true; return; } } diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp index 5f2cb07faf..f8247cd240 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -66,7 +66,7 @@ struct side_calculator Qj const& m_qj; Qk const& m_qk; - SideStrategy const& m_side_strategy; + SideStrategy m_side_strategy; }; template <typename Point1, typename Point2, typename RobustPolicy> diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index 4e97a84a37..f88dfe8422 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -1,7 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2014, 2016, 2017. // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates. @@ -90,6 +90,9 @@ struct no_interrupt_policy { static bool const enabled = false; + // variable required by self_get_turn_points::get_turns + static bool const has_intersections = false; + template <typename Range> static inline bool apply(Range const&) { @@ -230,7 +233,7 @@ public : // section 2: [--------------] // section 1: |----|---|---|---|---| for (prev1 = it1++, next1++; - it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy); + it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy); ++prev1, ++it1, ++index1, ++next1, ++ndi1) { ever_circling_iterator<range1_iterator> nd_next1( @@ -248,7 +251,7 @@ public : next2++; for (prev2 = it2++, next2++; - it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy); + 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; @@ -356,7 +359,7 @@ private : // skips to the begin-point, we loose the index or have to recalculate it) // So we mimic it here template <typename Range, typename Section, typename Box, typename RobustPolicy> - static inline void get_start_point_iterator(Section & section, + static inline void get_start_point_iterator(Section const& section, Range const& range, typename boost::range_iterator<Range const>::type& it, typename boost::range_iterator<Range const>::type& prev, @@ -370,7 +373,7 @@ private : // Mimic section-iterator: // Skip to point such that section interects other box prev = it++; - for(; it != end && detail::section::preceding<0>(dir, *it, other_bounding_box, robust_policy); + for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy); prev = it++, index++, ndi++) {} // Go back one step because we want to start completely preceding @@ -418,6 +421,7 @@ struct section_visitor { if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)) { + // false if interrupted return get_turns_in_sections < Geometry1, @@ -425,13 +429,12 @@ struct section_visitor Reverse1, Reverse2, Section, Section, TurnPolicy - >::apply( - m_source_id1, m_geometry1, sec1, - m_source_id2, m_geometry2, sec2, - false, - m_intersection_strategy, - m_rescale_policy, - m_turns, m_interrupt_policy); + >::apply(m_source_id1, m_geometry1, sec1, + m_source_id2, m_geometry2, sec2, + false, + m_intersection_strategy, + m_rescale_policy, + m_turns, m_interrupt_policy); } return true; } @@ -473,10 +476,13 @@ public: sections_type sec1, sec2; typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions; + typename IntersectionStrategy::envelope_strategy_type const + envelope_strategy = intersection_strategy.get_envelope_strategy(); + geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy, - sec1, 0); + sec1, envelope_strategy, 0); geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy, - sec2, 1); + sec2, envelope_strategy, 1); // ... and then partition them, intersecting overlapping sections in visitor method section_visitor diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp index 400ed3b881..f3311b34e9 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -262,15 +267,6 @@ inline void handle_colocation_cluster(Turns& turns, add_cluster_id(other_op, cluster_per_segment, ref_id); id = ref_id; } - - // In case of colocated xx turns, all other turns may NOT be - // followed at all. xx cannot be discarded (otherwise colocated - // turns are followed). - if (ref_turn.both(operation_blocked)) - { - turn.discarded = true; - // We can either set or not set colocated because it is not effective on blocked turns - } } else { @@ -331,11 +327,7 @@ inline void assign_cluster_to_turns(Turns& turns, } } -template -< - typename Turns, - typename Clusters -> +template <typename Turns, typename Clusters> inline void remove_clusters(Turns& turns, Clusters& clusters) { typename Clusters::iterator it = clusters.begin(); @@ -350,17 +342,44 @@ inline void remove_clusters(Turns& turns, Clusters& clusters) = current_it->second.turn_indices; if (turn_indices.size() == 1) { - signed_size_type turn_index = *turn_indices.begin(); + signed_size_type const turn_index = *turn_indices.begin(); turns[turn_index].cluster_id = -1; clusters.erase(current_it); } } } +template <typename Turns, typename Clusters> +inline void cleanup_clusters(Turns& turns, Clusters& clusters) +{ + // Removes discarded turns from clusters + for (typename Clusters::iterator mit = clusters.begin(); + mit != clusters.end(); ++mit) + { + cluster_info& cinfo = mit->second; + std::set<signed_size_type>& ids = cinfo.turn_indices; + for (std::set<signed_size_type>::iterator sit = ids.begin(); + sit != ids.end(); /* no increment */) + { + std::set<signed_size_type>::iterator current_it = sit; + ++sit; + + signed_size_type const turn_index = *current_it; + if (turns[turn_index].discarded) + { + ids.erase(current_it); + } + } + } + + remove_clusters(turns, clusters); +} + template <typename Turn, typename IdSet> inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id) { turn.discarded = true; + // Set cluster id to -1, but don't clear colocated flags turn.cluster_id = -1; // To remove it later from clusters ids.insert(id); @@ -378,6 +397,13 @@ inline bool is_ie_turn(segment_identifier const& ext_seg_0, segment_identifier const& int_seg_0, segment_identifier const& other_seg_1) { + if (ext_seg_0.source_index == ext_seg_1.source_index) + { + // External turn is a self-turn, dont discard internal turn for this + return false; + } + + // Compares two segment identifiers from two turns (external / one internal) // From first turn [0], both are from same polygon (multi_index), @@ -411,6 +437,7 @@ inline bool is_ie_turn(segment_identifier const& ext_seg_0, template < bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior + overlay_type OverlayType, typename Turns, typename Clusters > @@ -435,19 +462,6 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) segment_identifier const& seg_0 = turn.operations[0].seg_id; segment_identifier const& seg_1 = turn.operations[1].seg_id; - if (turn.both(operation_intersection) - && Reverse0 == Reverse1) - { - if ( is_interior<Reverse0>(seg_0) - && is_interior<Reverse1>(seg_1)) - { - // ii touch with, two interior rings - discard_ie_turn(turn, ids_to_remove, *it); - } - - continue; - } - if (! (turn.both(operation_union) || turn.combination(operation_union, operation_blocked))) { @@ -487,6 +501,53 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) } } +template +< + typename Turns, + typename Clusters +> +inline void set_colocation(Turns& turns, Clusters const& clusters) +{ + typedef std::set<signed_size_type>::const_iterator set_iterator; + typedef typename boost::range_value<Turns>::type turn_type; + + for (typename Clusters::const_iterator cit = clusters.begin(); + cit != clusters.end(); ++cit) + { + cluster_info const& cinfo = cit->second; + std::set<signed_size_type> const& ids = cinfo.turn_indices; + + bool has_ii = false; + bool has_uu = 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)) + { + has_uu = true; + } + } + if (has_ii || has_uu) + { + 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) + { + turn.colocated_uu = true; + } + } + } + } +} // Checks colocated turns and flags combinations of uu/other, possibly a // combination of a ring touching another geometry's interior ring which is @@ -498,6 +559,7 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) template < bool Reverse1, bool Reverse2, + overlay_type OverlayType, typename Turns, typename Clusters, typename Geometry1, @@ -578,12 +640,13 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters, } assign_cluster_to_turns(turns, clusters, cluster_per_segment); + set_colocation(turns, clusters); discard_interior_exterior_turns < do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1, - do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2 + do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2, + OverlayType >(turns, clusters); - remove_clusters(turns, clusters); #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) std::cout << "*** Colocations " << map.size() << std::endl; @@ -598,7 +661,8 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters, std::cout << geometry::wkt(turns[toi.turn_index].point) << std::boolalpha << " discarded=" << turns[toi.turn_index].discarded - << " colocated=" << turns[toi.turn_index].colocated + << " colocated(uu)=" << turns[toi.turn_index].colocated_uu + << " colocated(ii)=" << turns[toi.turn_index].colocated_ii << " " << operation_char(turns[toi.turn_index].operations[0].operation) << " " << turns[toi.turn_index].operations[0].seg_id << " " << turns[toi.turn_index].operations[0].fraction @@ -634,14 +698,17 @@ struct is_turn_index template < bool Reverse1, bool Reverse2, + overlay_type OverlayType, typename Turns, typename Clusters, typename Geometry1, - typename Geometry2 + typename Geometry2, + typename SideStrategy > inline void gather_cluster_properties(Clusters& clusters, Turns& turns, operation_type for_operation, - Geometry1 const& geometry1, Geometry2 const& geometry2) + Geometry1 const& geometry1, Geometry2 const& geometry2, + SideStrategy const& strategy) { typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::point_type point_type; @@ -651,7 +718,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, // right side typedef sort_by_side::side_sorter < - Reverse1, Reverse2, point_type, std::less<int> + Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int> > sbs_type; for (typename Clusters::iterator mit = clusters.begin(); @@ -664,11 +731,11 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, continue; } - sbs_type sbs; + sbs_type sbs(strategy); point_type turn_point; // should be all the same for all turns in cluster bool first = true; - for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); + for (std::set<signed_size_type>::const_iterator sit = ids.begin(); sit != ids.end(); ++sit) { signed_size_type turn_index = *sit; @@ -689,6 +756,8 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, sbs.find_open(); sbs.assign_zones(for_operation); + cinfo.open_count = sbs.open_count(for_operation); + // Unset the startable flag for all 'closed' zones for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { @@ -696,6 +765,11 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, 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) + { + op.enriched.startable = false; + } + if (ranked.direction != sort_by_side::dir_to) { continue; @@ -703,6 +777,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, op.enriched.count_left = ranked.count_left; op.enriched.count_right = ranked.count_right; + op.enriched.rank = ranked.rank; op.enriched.zone = ranked.zone; if ((for_operation == operation_union @@ -714,7 +789,6 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, } } - cinfo.open_count = sbs.open_count(for_operation); } } diff --git a/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp new file mode 100644 index 0000000000..39c55db759 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp @@ -0,0 +1,143 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// 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_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP + +#include <boost/range.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> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +struct discard_turns +{ + template <typename Turns, typename Geometry0, typename Geometry1> + static inline + void apply(Turns& , Geometry0 const& , Geometry1 const& ) + {} +}; + +template <overlay_type OverlayType, operation_type OperationType> +struct discard_closed_turns : discard_turns {}; + +// It is only implemented for operation_union, not in buffer +template <> +struct discard_closed_turns<overlay_union, operation_union> +{ + + template <typename Turns, typename Geometry0, typename Geometry1> + static inline + void apply(Turns& turns, + Geometry0 const& geometry0, Geometry1 const& geometry1) + { + typedef typename boost::range_value<Turns>::type turn_type; + + for (typename boost::range_iterator<Turns>::type + it = boost::begin(turns); + it != boost::end(turns); + ++it) + { + turn_type& turn = *it; + + if (turn.cluster_id >= 0 + || turn.discarded + || ! is_self_turn<overlay_union>(turn)) + { + continue; + } + + bool const within = + turn.operations[0].seg_id.source_index == 0 + ? geometry::within(turn.point, geometry1) + : geometry::within(turn.point, geometry0); + + if (within) + { + // It is in the interior of the other geometry + turn.discarded = true; + } + } + } +}; + +struct discard_self_intersection_turns +{ + template <typename Turns, typename Geometry0, typename Geometry1> + static inline + void apply(Turns& turns, + Geometry0 const& geometry0, Geometry1 const& geometry1) + { + typedef typename boost::range_value<Turns>::type turn_type; + + for (typename boost::range_iterator<Turns>::type + it = boost::begin(turns); + it != boost::end(turns); + ++it) + { + turn_type& turn = *it; + + if (turn.cluster_id >= 0 + || turn.discarded + || ! is_self_turn<overlay_intersection>(turn)) + { + continue; + } + + segment_identifier const& id0 = turn.operations[0].seg_id; + segment_identifier const& id1 = turn.operations[1].seg_id; + if (id0.multi_index != id1.multi_index + || (id0.ring_index == -1 && id1.ring_index == -1) + || (id0.ring_index >= 0 && id1.ring_index >= 0)) + { + // Not an ii ring (int/ext) on same ring + continue; + } + + // It is a non co-located 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) + { + // It is not within another geometry, discard the turn + turn.discarded = true; + } + } + } +}; + +template <overlay_type OverlayType, operation_type OperationType> +struct discard_open_turns : discard_turns {}; + +// Handler it for intersection +template <> +struct discard_open_turns<overlay_intersection, operation_intersection> + : discard_self_intersection_turns {}; + +// For difference, it should be done in a different way (TODO) + +}} // namespace detail::overlay +#endif //DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index 3244480f48..7106e7b480 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -30,10 +30,11 @@ #include <boost/geometry/algorithms/convert.hpp> #include <boost/geometry/algorithms/detail/point_on_border.hpp> #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp> +#include <boost/geometry/algorithms/detail/overlay/follow.hpp> #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> -#include <boost/geometry/algorithms/detail/overlay/follow.hpp> +#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp> #include <boost/geometry/policies/robustness/robust_point_type.hpp> #include <boost/geometry/policies/robustness/segment_ratio_type.hpp> @@ -288,6 +289,27 @@ struct intersection_of_linestring_with_areal >::apply(boost::begin(turns), boost::end(turns)); } + template <typename Turns> + static inline int inside_or_outside_turn(Turns const& turns) + { + using namespace overlay; + for (typename Turns::const_iterator it = turns.begin(); + it != turns.end(); ++it) + { + operation_type op0 = it->operations[0].operation; + operation_type op1 = it->operations[1].operation; + if (op0 == operation_intersection && op1 == operation_intersection) + { + return 1; // inside + } + else if (op0 == operation_union && op1 == operation_union) + { + return -1; // outside + } + } + return 0; + } + template < typename LineString, typename Areal, @@ -331,19 +353,21 @@ struct intersection_of_linestring_with_areal if (no_crossing_turns_or_empty(turns)) { - // No intersection points, it is either completely + // No intersection points, it is either // inside (interior + borders) - // or completely outside + // or outside (exterior + borders) - // Use border point (on a segment) to check this - // (because turn points might skip some cases) - point_type border_point; - if (! geometry::point_on_border(border_point, linestring, true)) + // analyse the turns + int inside_value = inside_or_outside_turn(turns); + if (inside_value == 0) { - return out; + // if needed analyse points of a linestring + // NOTE: range_in_geometry checks points of a linestring + // until a point inside/outside areal is found + inside_value = overlay::range_in_geometry(linestring, areal, strategy); } - - if (follower::included(border_point, areal, robust_policy)) + // add point to the output if conditions are met + if (inside_value != 0 && follower::included(inside_value)) { LineStringOut copy; geometry::convert(linestring, copy); @@ -365,7 +389,7 @@ struct intersection_of_linestring_with_areal ( linestring, areal, geometry::detail::overlay::operation_intersection, - turns, robust_policy, out + turns, robust_policy, out, strategy ); } }; diff --git a/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp new file mode 100644 index 0000000000..9cb7a0fca9 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/is_self_turn.hpp @@ -0,0 +1,68 @@ +// 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_IS_SELF_TURN_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_IS_SELF_TURN_HPP + +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +template <overlay_type OverlayType> +struct is_self_turn_check +{ + template <typename Turn> + static inline bool apply(Turn const& turn) + { + return turn.operations[0].seg_id.source_index + == turn.operations[1].seg_id.source_index; + } +}; + +template <> +struct is_self_turn_check<overlay_buffer> +{ + template <typename Turn> + static inline bool apply(Turn const& turn) + { + return false; + } +}; + +template <> +struct is_self_turn_check<overlay_dissolve> +{ + 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) +{ + return is_self_turn_check<OverlayType>::apply(turn); +} + + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_IS_SELF_TURN_HPP diff --git a/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp b/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp index 21868a2939..dd30635ee2 100644 --- a/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp +++ b/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -60,6 +65,7 @@ template typename Indexed, typename Geometry1, typename Geometry2, typename RobustPolicy, + typename SideStrategy, bool Reverse1, bool Reverse2 > struct less_by_segment_ratio @@ -68,12 +74,14 @@ struct less_by_segment_ratio , operation_type for_operation , Geometry1 const& geometry1 , Geometry2 const& geometry2 - , RobustPolicy const& robust_policy) + , RobustPolicy const& robust_policy + , SideStrategy const& strategy) : m_turns(turns) , m_for_operation(for_operation) , m_geometry1(geometry1) , m_geometry2(geometry2) , m_robust_policy(robust_policy) + , m_strategy(strategy) { } @@ -84,6 +92,7 @@ private : Geometry1 const& m_geometry1; Geometry2 const& m_geometry2; RobustPolicy const& m_robust_policy; + SideStrategy const& m_strategy; typedef typename geometry::point_type<Geometry1>::type point_type; @@ -108,13 +117,8 @@ private : *right.other_seg_id, si, sj); - typedef typename strategy::side::services::default_strategy - < - typename cs_tag<point_type>::type - >::type strategy; - - int const side_rj_p = strategy::apply(pi, pj, rj); - int const side_sj_p = strategy::apply(pi, pj, sj); + int const side_rj_p = m_strategy.apply(pi, pj, rj); + int const side_sj_p = m_strategy.apply(pi, pj, sj); // Put the one turning left (1; right == -1) as last if (side_rj_p != side_sj_p) @@ -122,8 +126,8 @@ private : return side_rj_p < side_sj_p; } - int const side_sj_r = strategy::apply(ri, rj, sj); - int const side_rj_s = strategy::apply(si, sj, rj); + int const side_sj_r = m_strategy.apply(ri, rj, sj); + int const side_rj_s = m_strategy.apply(si, sj, rj); // If they both turn left: the most left as last // If they both turn right: this is not relevant, but take also here most left diff --git a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp index a74bb33ba1..21d079d95c 100644 --- a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp @@ -194,13 +194,15 @@ protected: typename Turns, typename LinearGeometry1, typename LinearGeometry2, - typename OutputIterator + typename OutputIterator, + typename IntersectionStrategy > static inline OutputIterator sort_and_follow_turns(Turns& turns, LinearGeometry1 const& linear1, LinearGeometry2 const& linear2, - OutputIterator oit) + OutputIterator oit, + IntersectionStrategy const& strategy) { // remove turns that have no added value turns::filter_continue_turns @@ -228,7 +230,7 @@ protected: FollowIsolatedPoints, !EnableFilterContinueTurns || OverlayType == overlay_intersection >::apply(linear1, linear2, boost::begin(turns), boost::end(turns), - oit); + oit, strategy.get_side_strategy()); } public: @@ -277,7 +279,7 @@ public: OverlayType, EnableFollowIsolatedPoints && OverlayType == overlay_intersection - >(turns, linear1, linear2, oit); + >(turns, linear1, linear2, oit, strategy); } }; diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index f1af2f1949..10829abd4f 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -28,9 +28,11 @@ #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> #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/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> +#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/algorithms/detail/recalculate.hpp> @@ -87,29 +89,58 @@ struct overlay_null_visitor {} }; -template <typename Turns, typename TurnInfoMap> -inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns) +template +< + overlay_type OverlayType, + typename TurnInfoMap, + typename Turns, + typename Clusters +> +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::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; + + signed_size_type turn_index = 0; for (typename boost::range_iterator<Turns const>::type it = boost::begin(turns); it != boost::end(turns); - ++it) + ++it, turn_index++) { - typename boost::range_value<Turns>::type const& turn_info = *it; - - if (turn_info.discarded - && ! turn_info.any_blocked() - && ! turn_info.colocated) + 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) { - continue; + typename Clusters::const_iterator mit = clusters.find(turn.cluster_id); + BOOST_ASSERT(mit != clusters.end()); + + cluster_info const& cinfo = mit->second; + is_closed = cinfo.open_count == 0; } for (typename boost::range_iterator<container_type const>::type - op_it = boost::begin(turn_info.operations); - op_it != boost::end(turn_info.operations); + op_it = boost::begin(turn.operations); + op_it != boost::end(turn.operations); ++op_it) { ring_identifier const ring_id @@ -118,7 +149,34 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns) op_it->seg_id.multi_index, op_it->seg_id.ring_index ); - turn_info_map[ring_id].has_normal_turn = true; + + if (traversed || is_closed || ! op_it->enriched.startable) + { + turn_info_map[ring_id].has_traversed_turn = true; + } + 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 + } + else if (both_opposite && ! is_self_turn<OverlayType>(turn)) + { + // 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; + } + else if (colocated_opp && ! colocated_target) + { + // 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; + } } } } @@ -128,18 +186,27 @@ template < typename GeometryOut, overlay_type OverlayType, bool ReverseOut, typename Geometry1, typename Geometry2, - typename OutputIterator + typename OutputIterator, typename Strategy > inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, Geometry2 const& geometry2, - OutputIterator out) + OutputIterator out, Strategy const& strategy) { typedef std::deque < typename geometry::ring_type<GeometryOut>::type > ring_container_type; - typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties; + typedef typename geometry::point_type<Geometry1>::type point_type1; + + typedef ring_properties + < + point_type1, + typename Strategy::template area_strategy + < + point_type1 + >::type::return_type + > properties; // Silence warning C4127: conditional expression is constant #if defined(_MSC_VER) @@ -164,9 +231,9 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, std::map<ring_identifier, ring_turn_info> empty; std::map<ring_identifier, properties> all_of_one_of_them; - select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them); + 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); + assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy); return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out); } @@ -201,7 +268,7 @@ struct overlay return return_if_one_input_is_empty < GeometryOut, OverlayType, ReverseOut - >(geometry1, geometry2, out); + >(geometry1, geometry2, out, strategy); } typedef typename geometry::point_type<GeometryOut>::type point_type; @@ -238,10 +305,20 @@ std::cout << "get turns" << std::endl; visitor.visit_turns(1, turns); +#ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS + { + self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1, + strategy, robust_policy, turns, policy, 0); + self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2, + strategy, robust_policy, turns, policy, 1); + } +#endif + + #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "enrich" << std::endl; #endif - typename Strategy::side_strategy_type side_strategy; + typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy(); cluster_type clusters; geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, @@ -271,33 +348,38 @@ std::cout << "traverse" << std::endl; ); std::map<ring_identifier, ring_turn_info> turn_info_per_ring; - get_ring_turn_info(turn_info_per_ring, turns); + get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters); + + typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type; typedef ring_properties - < - typename geometry::point_type<GeometryOut>::type - > properties; + < + point_type, + typename area_strategy_type::return_type + > properties; // Select all rings which are NOT touched by any intersection point std::map<ring_identifier, properties> selected_ring_properties; select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring, - selected_ring_properties); + selected_ring_properties, strategy); // Add rings created during traversal { + 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); it != boost::end(rings); ++it) { - selected_ring_properties[id] = properties(*it); + selected_ring_properties[id] = properties(*it, area_strategy); selected_ring_properties[id].reversed = ReverseOut; id.multi_index++; } } - assign_parents(geometry1, geometry2, rings, selected_ring_properties); + assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy); return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out); } diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp index a26f54e008..0a7c3bc469 100644 --- a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp @@ -1,5 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. + // Copyright (c) 2015-2017, Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -127,25 +129,57 @@ class multipoint_linear_point { private: // structs for partition -- start - struct expand_box + struct expand_box_point { - template <typename Box, typename Geometry> - static inline void apply(Box& total, Geometry const& geometry) + template <typename Box, typename Point> + static inline void apply(Box& total, Point const& point) { - geometry::expand(total, geometry::return_envelope<Box>(geometry)); + geometry::expand(total, point); } + }; + + template <typename EnvelopeStrategy> + struct expand_box_segment + { + explicit expand_box_segment(EnvelopeStrategy const& strategy) + : m_strategy(strategy) + {} + template <typename Box, typename Segment> + inline void apply(Box& total, Segment const& segment) const + { + geometry::expand(total, + geometry::return_envelope<Box>(segment, m_strategy)); + } + + EnvelopeStrategy const& m_strategy; }; - struct overlaps_box + struct overlaps_box_point { - template <typename Box, typename Geometry> - static inline bool apply(Box const& box, Geometry const& geometry) + template <typename Box, typename Point> + static inline bool apply(Box const& box, Point const& point) { - return ! geometry::disjoint(geometry, box); + return ! geometry::disjoint(point, box); } }; + template <typename DisjointStrategy> + struct overlaps_box_segment + { + explicit overlaps_box_segment(DisjointStrategy const& strategy) + : m_strategy(strategy) + {} + + template <typename Box, typename Segment> + inline bool apply(Box const& box, Segment const& segment) const + { + return ! geometry::disjoint(segment, box, m_strategy); + } + + DisjointStrategy const& m_strategy; + }; + template <typename OutputIterator, typename Strategy> class item_visitor_type { @@ -156,12 +190,14 @@ private: {} template <typename Item1, typename Item2> - inline void apply(Item1 const& item1, Item2 const& item2) + inline bool apply(Item1 const& item1, Item2 const& item2) { action_selector_pl_l < PointOut, overlay_intersection >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit); + + return true; } private: @@ -202,16 +238,25 @@ private: { item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy); - segment_range rng(linear); + typedef typename Strategy::envelope_strategy_type envelope_strategy_type; + typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; + // TODO: disjoint Segment/Box may be called in partition multiple times + // possibly for non-cartesian segments which could be slow. We should consider + // passing a range of bounding boxes of segments after calculating them once. + // Alternatively instead of a range of segments a range of Segment/Envelope pairs + // should be passed, where envelope would be lazily calculated when needed the first time geometry::partition < geometry::model::box < typename boost::range_value<MultiPoint>::type > - >::apply(multipoint, rng, item_visitor, - expand_box(), overlaps_box()); + >::apply(multipoint, segment_range(linear), item_visitor, + expand_box_point(), + overlaps_box_point(), + expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), + overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); return oit; } diff --git a/boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp b/boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp new file mode 100644 index 0000000000..d4a47abecf --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp @@ -0,0 +1,178 @@ +// Boost.Geometry + +// Copyright (c) 2017 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP + + +#include <boost/geometry/algorithms/covered_by.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/tags.hpp> +#include <boost/geometry/iterators/point_iterator.hpp> + +#include <boost/range.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + + +template +< + typename Geometry, + typename Tag = typename geometry::tag<Geometry>::type +> +struct points_range +{ + typedef geometry::point_iterator<Geometry const> iterator_type; + + explicit points_range(Geometry const& geometry) + : m_geometry(geometry) + {} + + iterator_type begin() const + { + return geometry::points_begin(m_geometry); + } + + iterator_type end() const + { + return geometry::points_end(m_geometry); + } + + Geometry const& m_geometry; +}; +// Specialized because point_iterator doesn't support boxes +template <typename Box> +struct points_range<Box, box_tag> +{ + typedef typename geometry::point_type<Box>::type point_type; + typedef const point_type * iterator_type; + + explicit points_range(Box const& box) + { + detail::assign_box_corners(box, + m_corners[0], m_corners[1], m_corners[2], m_corners[3]); + } + + iterator_type begin() const + { + return m_corners; + } + + iterator_type end() const + { + return m_corners + 4; + } + + point_type m_corners[4]; +}; + +template +< + typename Geometry, + typename Tag = typename geometry::tag<Geometry>::type +> +struct point_in_geometry_helper +{ + template <typename Point, typename Strategy> + static inline int apply(Point const& point, Geometry const& geometry, + Strategy const& strategy) + { + return detail::within::point_in_geometry(point, geometry, strategy); + } +}; +// Specialized because point_in_geometry doesn't support Boxes +template <typename Box> +struct point_in_geometry_helper<Box, box_tag> +{ + template <typename Point, typename Strategy> + static inline int apply(Point const& point, Box const& box, + Strategy const&) + { + return geometry::covered_by(point, box) ? 1 : -1; + } +}; + +// This function returns +// when it finds a point of geometry1 inside or outside geometry2 +template <typename Geometry1, typename Geometry2, typename Strategy> +static inline int range_in_geometry(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy, + bool skip_first = false) +{ + int result = 0; + points_range<Geometry1> points(geometry1); + typedef typename points_range<Geometry1>::iterator_type iterator_type; + iterator_type const end = points.end(); + iterator_type it = points.begin(); + if (it == end) + { + return result; + } + else if (skip_first) + { + ++it; + } + + typename Strategy::template point_in_geometry_strategy + < + Geometry1, Geometry2 + >::type const in_strategy + = strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>(); + + for ( ; it != end; ++it) + { + result = point_in_geometry_helper<Geometry2>::apply(*it, geometry2, in_strategy); + if (result != 0) + { + return result; + } + } + // all points contained entirely by the boundary + return result; +} + +// This function returns if first_point1 is inside or outside geometry2 or +// when it finds a point of geometry1 inside or outside geometry2 +template <typename Point1, typename Geometry1, typename Geometry2, typename Strategy> +inline int range_in_geometry(Point1 const& first_point1, + Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) +{ + // check a point on border of geometry1 first + int result = point_in_geometry_helper<Geometry2>::apply(first_point1, geometry2, + strategy.template get_point_in_geometry_strategy<Point1, Geometry2>()); + if (result == 0) + { + // if a point is on boundary of geometry2 + // check points of geometry1 until point inside/outside is found + // NOTE: skip first point because it should be already tested above + result = range_in_geometry(geometry1, geometry2, strategy, true); + } + return result; +} + + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP diff --git a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp index 0f2da67b62..7dbc5d5fab 100644 --- a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp +++ b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp @@ -2,6 +2,10 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -23,11 +27,11 @@ namespace boost { namespace geometry namespace detail { namespace overlay { -template <typename Point> +template <typename Point, typename AreaType> struct ring_properties { typedef Point point_type; - typedef typename default_area_result<Point>::type area_type; + typedef AreaType area_type; bool valid; @@ -52,17 +56,14 @@ struct ring_properties , parent_area(-1) {} - template <typename RingOrBox> - inline ring_properties(RingOrBox const& ring_or_box) + template <typename RingOrBox, typename AreaStrategy> + inline ring_properties(RingOrBox const& ring_or_box, AreaStrategy const& strategy) : reversed(false) , discarded(false) , parent_area(-1) { - this->area = geometry::area(ring_or_box); - // We should take a point somewhere in the middle of the ring, - // to avoid taking a point on a (self)tangency, - // in cases where multiple points come together - valid = geometry::point_on_border(this->point, ring_or_box, true); + this->area = geometry::area(ring_or_box, strategy); + valid = geometry::point_on_border(this->point, ring_or_box); } inline area_type get_area() const diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp index de5eac8acb..67a4f4bb75 100644 --- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp @@ -3,6 +3,10 @@ // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -18,9 +22,10 @@ #include <boost/geometry/core/tags.hpp> #include <boost/geometry/algorithms/area.hpp> -#include <boost/geometry/algorithms/within.hpp> +#include <boost/geometry/algorithms/covered_by.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp> #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> @@ -35,11 +40,11 @@ namespace detail { namespace overlay struct ring_turn_info { - bool has_normal_turn; + bool has_traversed_turn; bool within_other; ring_turn_info() - : has_normal_turn(false) + : has_traversed_turn(false) , within_other(false) {} }; @@ -54,41 +59,45 @@ namespace dispatch template <typename Box> struct select_rings<box_tag, Box> { - template <typename Geometry, typename RingPropertyMap> + template <typename Geometry, typename RingPropertyMap, typename AreaStrategy> static inline void apply(Box const& box, Geometry const& , - ring_identifier const& id, RingPropertyMap& ring_properties) + ring_identifier const& id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { - ring_properties[id] = typename RingPropertyMap::mapped_type(box); + ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy); } - template <typename RingPropertyMap> + template <typename RingPropertyMap, typename AreaStrategy> static inline void apply(Box const& box, - ring_identifier const& id, RingPropertyMap& ring_properties) + ring_identifier const& id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { - ring_properties[id] = typename RingPropertyMap::mapped_type(box); + ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy); } }; template <typename Ring> struct select_rings<ring_tag, Ring> { - template <typename Geometry, typename RingPropertyMap> + template <typename Geometry, typename RingPropertyMap, typename AreaStrategy> static inline void apply(Ring const& ring, Geometry const& , - ring_identifier const& id, RingPropertyMap& ring_properties) + ring_identifier const& id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { if (boost::size(ring) > 0) { - ring_properties[id] = typename RingPropertyMap::mapped_type(ring); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy); } } - template <typename RingPropertyMap> + template <typename RingPropertyMap, typename AreaStrategy> static inline void apply(Ring const& ring, - ring_identifier const& id, RingPropertyMap& ring_properties) + ring_identifier const& id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { if (boost::size(ring) > 0) { - ring_properties[id] = typename RingPropertyMap::mapped_type(ring); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy); } } }; @@ -97,14 +106,15 @@ namespace dispatch template <typename Polygon> struct select_rings<polygon_tag, Polygon> { - template <typename Geometry, typename RingPropertyMap> + template <typename Geometry, typename RingPropertyMap, typename AreaStrategy> static inline void apply(Polygon const& polygon, Geometry const& geometry, - ring_identifier id, RingPropertyMap& ring_properties) + ring_identifier id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { typedef typename geometry::ring_type<Polygon>::type ring_type; typedef select_rings<ring_tag, ring_type> per_ring; - per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties); + per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties, strategy); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -112,18 +122,19 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, geometry, id, ring_properties); + per_ring::apply(*it, geometry, id, ring_properties, strategy); } } - template <typename RingPropertyMap> + template <typename RingPropertyMap, typename AreaStrategy> static inline void apply(Polygon const& polygon, - ring_identifier id, RingPropertyMap& ring_properties) + ring_identifier id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { typedef typename geometry::ring_type<Polygon>::type ring_type; typedef select_rings<ring_tag, ring_type> per_ring; - per_ring::apply(exterior_ring(polygon), id, ring_properties); + per_ring::apply(exterior_ring(polygon), id, ring_properties, strategy); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -131,7 +142,7 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, id, ring_properties); + per_ring::apply(*it, id, ring_properties, strategy); } } }; @@ -139,9 +150,10 @@ namespace dispatch template <typename Multi> struct select_rings<multi_polygon_tag, Multi> { - template <typename Geometry, typename RingPropertyMap> + template <typename Geometry, typename RingPropertyMap, typename AreaStrategy> static inline void apply(Multi const& multi, Geometry const& geometry, - ring_identifier id, RingPropertyMap& ring_properties) + ring_identifier id, RingPropertyMap& ring_properties, + AreaStrategy const& strategy) { typedef typename boost::range_iterator < @@ -154,7 +166,7 @@ namespace dispatch for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it) { id.ring_index = -1; - per_polygon::apply(*it, geometry, id, ring_properties); + per_polygon::apply(*it, geometry, id, ring_properties, strategy); id.multi_index++; } } @@ -221,20 +233,21 @@ struct decide<overlay_intersection> } }; - template < overlay_type OverlayType, typename Geometry1, typename Geometry2, typename TurnInfoMap, - typename RingPropertyMap + typename RingPropertyMap, + typename Strategy > inline void update_ring_selection(Geometry1 const& geometry1, Geometry2 const& geometry2, TurnInfoMap const& turn_info_map, RingPropertyMap const& all_ring_properties, - RingPropertyMap& selected_ring_properties) + RingPropertyMap& selected_ring_properties, + Strategy const& strategy) { selected_ring_properties.clear(); @@ -252,9 +265,9 @@ inline void update_ring_selection(Geometry1 const& geometry1, info = tcit->second; // Copy by value } - if (info.has_normal_turn) + if (info.has_traversed_turn) { - // There are normal turns on this ring. It should be traversed, we + // This turn is traversed (or blocked), // don't include the original ring continue; } @@ -263,11 +276,16 @@ inline void update_ring_selection(Geometry1 const& geometry1, // a point lying on the ring switch(id.source_index) { + // within case 0 : - info.within_other = geometry::within(it->second.point, geometry2); + info.within_other = range_in_geometry(it->second.point, + geometry1, geometry2, + strategy) > 0; break; case 1 : - info.within_other = geometry::within(it->second.point, geometry1); + info.within_other = range_in_geometry(it->second.point, + geometry2, geometry1, + strategy) > 0; break; } @@ -290,23 +308,30 @@ template typename Geometry1, typename Geometry2, typename RingTurnInfoMap, - typename RingPropertyMap + typename RingPropertyMap, + typename Strategy > inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2, RingTurnInfoMap const& turn_info_per_ring, - RingPropertyMap& selected_ring_properties) + RingPropertyMap& selected_ring_properties, + Strategy const& strategy) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; + typedef typename geometry::point_type<Geometry1>::type point1_type; + typedef typename geometry::point_type<Geometry2>::type point2_type; RingPropertyMap all_ring_properties; dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, - ring_identifier(0, -1, -1), all_ring_properties); + ring_identifier(0, -1, -1), all_ring_properties, + strategy.template get_area_strategy<point1_type>()); dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, - ring_identifier(1, -1, -1), all_ring_properties); + ring_identifier(1, -1, -1), all_ring_properties, + strategy.template get_area_strategy<point2_type>()); update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring, - all_ring_properties, selected_ring_properties); + all_ring_properties, selected_ring_properties, + strategy); } template @@ -314,20 +339,25 @@ template overlay_type OverlayType, typename Geometry, typename RingTurnInfoMap, - typename RingPropertyMap + typename RingPropertyMap, + typename Strategy > inline void select_rings(Geometry const& geometry, RingTurnInfoMap const& turn_info_per_ring, - RingPropertyMap& selected_ring_properties) + RingPropertyMap& selected_ring_properties, + Strategy const& strategy) { typedef typename geometry::tag<Geometry>::type tag; + typedef typename geometry::point_type<Geometry>::type point_type; RingPropertyMap all_ring_properties; dispatch::select_rings<tag, Geometry>::apply(geometry, - ring_identifier(0, -1, -1), all_ring_properties); + ring_identifier(0, -1, -1), all_ring_properties, + strategy.template get_area_strategy<point_type>()); update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring, - all_ring_properties, selected_ring_properties); + all_ring_properties, selected_ring_properties, + strategy); } diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp index 8540ef98a0..5e9d8efa8e 100644 --- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp @@ -1,6 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2017. // Modifications copyright (c) 2017 Oracle and/or its affiliates. @@ -22,12 +23,14 @@ #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/point_order.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> +#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> @@ -57,12 +60,9 @@ struct no_interrupt_policy }; - - -class self_ip_exception : public geometry::exception {}; - template < + bool Reverse, typename Geometry, typename Turns, typename TurnPolicy, @@ -77,17 +77,20 @@ struct self_section_visitor RobustPolicy const& m_rescale_policy; Turns& m_turns; InterruptPolicy& m_interrupt_policy; + std::size_t m_source_index; inline self_section_visitor(Geometry const& g, IntersectionStrategy const& is, RobustPolicy const& rp, Turns& turns, - InterruptPolicy& ip) + InterruptPolicy& ip, + std::size_t source_index) : m_geometry(g) , m_intersection_strategy(is) , m_rescale_policy(rp) , m_turns(turns) , m_interrupt_policy(ip) + , m_source_index(source_index) {} template <typename Section> @@ -97,26 +100,21 @@ struct self_section_visitor && ! sec1.duplicate && ! sec2.duplicate) { - detail::get_turns::get_turns_in_sections + // false if interrupted + return detail::get_turns::get_turns_in_sections < Geometry, Geometry, - false, false, + Reverse, Reverse, Section, Section, TurnPolicy - >::apply( - 0, m_geometry, sec1, - 0, m_geometry, sec2, - false, - m_intersection_strategy, - m_rescale_policy, - m_turns, m_interrupt_policy); - } - if (BOOST_GEOMETRY_CONDITION(m_interrupt_policy.has_intersections)) - { - // TODO: we should give partition an interrupt policy. - // Now we throw, and catch below, to stop the partition loop. - throw self_ip_exception(); + >::apply(m_source_index, m_geometry, sec1, + m_source_index, m_geometry, sec2, + false, + m_intersection_strategy, + m_rescale_policy, + m_turns, m_interrupt_policy); } + return true; } @@ -124,7 +122,7 @@ struct self_section_visitor -template<typename TurnPolicy> +template <bool Reverse, typename TurnPolicy> struct get_turns { template <typename Geometry, typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy> @@ -133,7 +131,8 @@ struct get_turns IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy, Turns& turns, - InterruptPolicy& interrupt_policy) + InterruptPolicy& interrupt_policy, + std::size_t source_index) { typedef model::box < @@ -149,29 +148,24 @@ struct get_turns typedef boost::mpl::vector_c<std::size_t, 0> dimensions; sections_type sec; - geometry::sectionalize<false, dimensions>(geometry, robust_policy, sec); + geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec, + intersection_strategy.get_envelope_strategy()); self_section_visitor < - Geometry, + Reverse, Geometry, Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy - > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy); + > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index); - try - { - geometry::partition - < - box_type - >::apply(sec, visitor, - detail::section::get_section_box(), - detail::section::overlaps_section_box()); - } - catch(self_ip_exception const& ) - { - return false; - } + // false if interrupted + geometry::partition + < + box_type + >::apply(sec, visitor, + detail::section::get_section_box(), + detail::section::overlaps_section_box()); - return true; + return ! interrupt_policy.has_intersections; } }; @@ -186,6 +180,7 @@ namespace dispatch template < + bool Reverse, typename GeometryTag, typename Geometry, typename TurnPolicy @@ -197,26 +192,28 @@ struct self_get_turn_points template < + bool Reverse, typename Ring, typename TurnPolicy > struct self_get_turn_points < - ring_tag, Ring, + Reverse, ring_tag, Ring, TurnPolicy > - : detail::self_get_turn_points::get_turns<TurnPolicy> + : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> {}; template < + bool Reverse, typename Box, typename TurnPolicy > struct self_get_turn_points < - box_tag, Box, + Reverse, box_tag, Box, TurnPolicy > { @@ -226,7 +223,8 @@ struct self_get_turn_points Strategy const& , RobustPolicy const& , Turns& , - InterruptPolicy& ) + InterruptPolicy& , + std::size_t) { return true; } @@ -235,29 +233,31 @@ struct self_get_turn_points template < + bool Reverse, typename Polygon, typename TurnPolicy > struct self_get_turn_points < - polygon_tag, Polygon, + Reverse, polygon_tag, Polygon, TurnPolicy > - : detail::self_get_turn_points::get_turns<TurnPolicy> + : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> {}; template < + bool Reverse, typename MultiPolygon, typename TurnPolicy > struct self_get_turn_points < - multi_polygon_tag, MultiPolygon, + Reverse, multi_polygon_tag, MultiPolygon, TurnPolicy > - : detail::self_get_turn_points::get_turns<TurnPolicy> + : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> {}; @@ -265,6 +265,45 @@ struct self_get_turn_points #endif // DOXYGEN_NO_DISPATCH +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace self_get_turn_points +{ + +// Version where Reverse can be specified manually. TODO: +// can most probably be merged with self_get_turn_points::get_turn +template +< + bool Reverse, + typename AssignPolicy, + typename Geometry, + typename IntersectionStrategy, + typename RobustPolicy, + typename Turns, + typename InterruptPolicy +> +inline void self_turns(Geometry const& geometry, + IntersectionStrategy const& strategy, + RobustPolicy const& robust_policy, + Turns& turns, + InterruptPolicy& interrupt_policy, + std::size_t source_index = 0) +{ + concepts::check<Geometry const>(); + + typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy; + + dispatch::self_get_turn_points + < + Reverse, + typename tag<Geometry>::type, + Geometry, + turn_policy + >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, source_index); +} + +}} // namespace detail::self_get_turn_points +#endif // DOXYGEN_NO_DETAIL + /*! \brief Calculate self intersections of a geometry \ingroup overlay @@ -290,18 +329,22 @@ template inline void self_turns(Geometry const& geometry, IntersectionStrategy const& strategy, RobustPolicy const& robust_policy, - Turns& turns, InterruptPolicy& interrupt_policy) + Turns& turns, + InterruptPolicy& interrupt_policy, + std::size_t source_index = 0) { concepts::check<Geometry const>(); - typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy; + static bool const reverse = detail::overlay::do_reverse + < + geometry::point_order<Geometry>::value + >::value; - dispatch::self_get_turn_points + detail::self_get_turn_points::self_turns < - typename tag<Geometry>::type, - Geometry, - turn_policy - >::apply(geometry, strategy, robust_policy, turns, interrupt_policy); + reverse, + AssignPolicy + >(geometry, strategy, robust_policy, turns, interrupt_policy, source_index); } diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp index bbba623eee..5ad2e41b12 100644 --- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp +++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -10,11 +15,14 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP #include <algorithm> +#include <map> #include <vector> +#include <boost/geometry/algorithms/num_points.hpp> +#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> +#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> #include <boost/geometry/algorithms/detail/direction_code.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> -#include <boost/geometry/strategies/side.hpp> namespace boost { namespace geometry { @@ -37,7 +45,6 @@ struct ranked_point , count_left(0) , count_right(0) , operation(operation_none) - , only_turn_on_ring(false) {} template <typename Op> @@ -53,7 +60,6 @@ struct ranked_point , count_right(0) , operation(op.operation) , seg_id(op.seg_id) - , only_turn_on_ring(op.enriched.only_turn_on_ring) {} Point point; @@ -66,7 +72,6 @@ struct ranked_point std::size_t count_right; operation_type operation; segment_identifier seg_id; - bool only_turn_on_ring; }; struct less_by_turn_index @@ -105,17 +110,13 @@ struct less_false } }; -template <typename Point, typename LessOnSame, typename Compare> +template <typename Point, typename SideStrategy, typename LessOnSame, typename Compare> struct less_by_side { - typedef typename strategy::side::services::default_strategy - < - typename cs_tag<Point>::type - >::type side; - - less_by_side(const Point& p1, const Point& p2) + less_by_side(const Point& p1, const Point& p2, SideStrategy const& strategy) : m_p1(p1) , m_p2(p2) + , m_strategy(strategy) {} template <typename T> @@ -124,8 +125,8 @@ struct less_by_side LessOnSame on_same; Compare compare; - int const side_first = side::apply(m_p1, m_p2, first.point); - int const side_second = side::apply(m_p1, m_p2, second.point); + int const side_first = m_strategy.apply(m_p1, m_p2, first.point); + int const side_second = m_strategy.apply(m_p1, m_p2, second.point); if (side_first == 0 && side_second == 0) { @@ -165,7 +166,7 @@ struct less_by_side // They are both left, both right, and/or both collinear (with each other and/or with p1,p2) // Check mutual side - int const side_second_wrt_first = side::apply(m_p2, first.point, second.point); + int const side_second_wrt_first = m_strategy.apply(m_p2, first.point, second.point); if (side_second_wrt_first == 0) { @@ -183,10 +184,19 @@ struct less_by_side private : Point m_p1, m_p2; + SideStrategy const& m_strategy; }; // Sorts vectors in counter clockwise order (by default) -template <bool Reverse1, bool Reverse2, typename Point, typename Compare> +template +< + bool Reverse1, + bool Reverse2, + overlay_type OverlayType, + typename Point, + typename SideStrategy, + typename Compare +> struct side_sorter { typedef ranked_point<Point> rp; @@ -215,13 +225,14 @@ private : }; public : - inline void set_origin(Point const& origin) - { - m_origin = origin; - } + side_sorter(SideStrategy const& strategy) + : m_origin_count(0) + , m_origin_segment_distance(0) + , m_strategy(strategy) + {} template <typename Operation, typename Geometry1, typename Geometry2> - void add(Operation const& op, signed_size_type turn_index, signed_size_type op_index, + Point add(Operation const& op, signed_size_type turn_index, signed_size_type op_index, Geometry1 const& geometry1, Geometry2 const& geometry2, bool is_origin) @@ -233,11 +244,63 @@ public : m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op)); m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op)); - if (is_origin) { m_origin = point1; + m_origin_count++; } + return point1; + } + + template <typename Operation, typename Geometry1, typename Geometry2> + void add(Operation const& op, signed_size_type turn_index, signed_size_type op_index, + segment_identifier const& departure_seg_id, + Geometry1 const& geometry1, + Geometry2 const& geometry2, + bool check_origin) + { + Point const point1 = add(op, turn_index, op_index, geometry1, geometry2, false); + + if (check_origin) + { + bool const is_origin + = op.seg_id.source_index == departure_seg_id.source_index + && op.seg_id.ring_index == departure_seg_id.ring_index + && op.seg_id.multi_index == departure_seg_id.multi_index; + + if (is_origin) + { + int const segment_distance = calculate_segment_distance(op, departure_seg_id, geometry1, geometry2); + if (m_origin_count == 0 || + segment_distance < m_origin_segment_distance) + { + m_origin = point1; + m_origin_segment_distance = segment_distance; + } + m_origin_count++; + } + } + } + + template <typename Operation, typename Geometry1, typename Geometry2> + static int calculate_segment_distance(Operation const& op, + segment_identifier const& departure_seg_id, + Geometry1 const& geometry1, + Geometry2 const& geometry2) + { + if (op.seg_id.segment_index >= departure_seg_id.segment_index) + { + return op.seg_id.segment_index - departure_seg_id.segment_index; + } + // Take wrap into account + // Suppose ring_count=10 (10 points, 9 segments), dep.seg_id=7, op.seg_id=2, then distance=10-9+2 + // Generic function (is this used somewhere else too?) + ring_identifier const rid(op.seg_id.source_index, op.seg_id.multi_index, op.seg_id.ring_index); + int const segment_count + (op.seg_id.source_index == 0 + ? geometry::num_points(detail::overlay::get_ring<typename geometry::tag<Geometry1>::type>::apply(rid, geometry1)) + : geometry::num_points(detail::overlay::get_ring<typename geometry::tag<Geometry2>::type>::apply(rid, geometry2))); + return ((segment_count - 1) - departure_seg_id.segment_index) + op.seg_id.segment_index; } void apply(Point const& turn_point) @@ -249,8 +312,8 @@ public : // to give colinear points // Sort by side and assign rank - less_by_side<Point, less_by_index, Compare> less_unique(m_origin, turn_point); - less_by_side<Point, less_false, Compare> less_non_unique(m_origin, turn_point); + less_by_side<Point, SideStrategy, less_by_index, Compare> less_unique(m_origin, turn_point, m_strategy); + less_by_side<Point, SideStrategy, less_false, Compare> less_non_unique(m_origin, turn_point, m_strategy); std::sort(m_ranked_points.begin(), m_ranked_points.end(), less_unique); @@ -269,7 +332,7 @@ public : } template <signed_size_type segment_identifier::*Member, typename Map> - void find_open_generic(Map& handled) + void find_open_generic(Map& handled, bool check) { for (std::size_t i = 0; i < m_ranked_points.size(); i++) { @@ -280,6 +343,11 @@ public : } signed_size_type const& index = ranked.seg_id.*Member; + if (check && (index < 0 || index > 1)) + { + // Should not occur + continue; + } if (! handled[index]) { find_polygons_for_source<Member>(index, i); @@ -290,36 +358,23 @@ public : void find_open() { - // TODO: we might pass Buffer as overlay_type, instead on the fly below - bool one_source = true; - for (std::size_t i = 0; i < m_ranked_points.size(); i++) - { - const rp& ranked = m_ranked_points[i]; - signed_size_type const& src = ranked.seg_id.source_index; - if (src != 0) - { - one_source = false; - break; - } - } - - if (one_source) + if (OverlayType == overlay_buffer) { - // by multi index + // For buffers, use piece index std::map<signed_size_type, bool> handled; find_open_generic < &segment_identifier::piece_index - >(handled); + >(handled, false); } else { - // by source (there should only source 0,1) TODO assert this + // For other operations, by source (there should only source 0,1) bool handled[2] = {false, false}; find_open_generic < &segment_identifier::source_index - >(handled); + >(handled, true); } } @@ -361,11 +416,19 @@ public : } } + bool has_origin() const + { + return m_origin_count > 0; + } + //private : typedef std::vector<rp> container_type; container_type m_ranked_points; Point m_origin; + std::size_t m_origin_count; + int m_origin_segment_distance; + SideStrategy m_strategy; private : @@ -439,9 +502,10 @@ private : void find_polygons_for_source(signed_size_type the_index, std::size_t start_index) { - int state = 1; // 'closed', because start_index is "from", arrives at the turn - std::size_t last_from_rank = m_ranked_points[start_index].rank; - std::size_t previous_rank = m_ranked_points[start_index].rank; + bool in_polygon = true; // Because start_index is "from", arrives at the turn + rp const& start_rp = m_ranked_points[start_index]; + std::size_t last_from_rank = start_rp.rank; + std::size_t previous_rank = start_rp.rank; for (std::size_t index = move<Member>(the_index, start_index); ; @@ -449,7 +513,7 @@ private : { rp& ranked = m_ranked_points[index]; - if (ranked.rank != previous_rank && state == 0) + if (ranked.rank != previous_rank && ! in_polygon) { assign_ranks(last_from_rank, previous_rank - 1, 1); assign_ranks(last_from_rank + 1, previous_rank, 2); @@ -463,11 +527,11 @@ private : if (ranked.direction == dir_from) { last_from_rank = ranked.rank; - state++; + in_polygon = true; } else if (ranked.direction == dir_to) { - state--; + in_polygon = false; } previous_rank = ranked.rank; diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp index bc828920e9..69d62b788b 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2017. +// Modifications copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -14,7 +19,9 @@ #include <boost/range.hpp> #include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp> +#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> +#include <boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> @@ -37,9 +44,13 @@ namespace detail { namespace overlay template <typename Turn, typename Operation> #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE inline void debug_traverse(Turn const& turn, Operation op, - std::string const& header) + std::string const& header, bool condition = true) { - std::cout << header + if (! condition) + { + return; + } + std::cout << " " << header << " at " << op.seg_id << " meth: " << method_char(turn.method) << " op: " << operation_char(op.operation) @@ -55,7 +66,7 @@ inline void debug_traverse(Turn const& turn, Operation op, } } #else -inline void debug_traverse(Turn const& , Operation, const char*) +inline void debug_traverse(Turn const& , Operation, const char*, bool = true) { } #endif @@ -88,6 +99,7 @@ template typename Turns, typename Clusters, typename RobustPolicy, + typename SideStrategy, typename Visitor > struct traversal @@ -101,18 +113,20 @@ struct traversal typedef typename geometry::point_type<Geometry1>::type point_type; typedef sort_by_side::side_sorter < - Reverse1, Reverse2, - point_type, side_compare_type + Reverse1, Reverse2, OverlayType, + point_type, SideStrategy, side_compare_type > sbs_type; inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2, Turns& turns, Clusters const& clusters, - RobustPolicy const& robust_policy, Visitor& visitor) + RobustPolicy const& robust_policy, SideStrategy const& strategy, + Visitor& visitor) : m_geometry1(geometry1) , m_geometry2(geometry2) , m_turns(turns) , m_clusters(clusters) , m_robust_policy(robust_policy) + , m_strategy(strategy) , m_visitor(visitor) { } @@ -133,11 +147,38 @@ struct traversal } } + //! Sets visited for ALL turns traveling to the same turn + inline void set_visited_in_cluster(signed_size_type cluster_id, + signed_size_type rank) + { + typename Clusters::const_iterator mit = m_clusters.find(cluster_id); + BOOST_ASSERT(mit != m_clusters.end()); + + cluster_info const& cinfo = mit->second; + std::set<signed_size_type> const& ids = cinfo.turn_indices; + + for (typename std::set<signed_size_type>::const_iterator it = ids.begin(); + it != ids.end(); ++it) + { + signed_size_type const turn_index = *it; + turn_type& turn = m_turns[turn_index]; + + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + if (op.visited.none() + && op.enriched.rank == rank) + { + op.visited.set_visited(); + } + } + } + } inline void set_visited(turn_type& turn, turn_operation_type& op) { - // On "continue", set "visited" for ALL directions in this turn if (op.operation == detail::overlay::operation_continue) { + // On "continue", all go in same direction so set "visited" for ALL for (int i = 0; i < 2; i++) { turn_operation_type& turn_op = turn.operations[i]; @@ -151,6 +192,10 @@ struct traversal { op.visited.set_visited(); } + if (turn.cluster_id >= 0) + { + set_visited_in_cluster(turn.cluster_id, op.enriched.rank); + } } inline bool is_visited(turn_type const& , turn_operation_type const& op, @@ -160,8 +205,8 @@ struct traversal } inline bool select_source(signed_size_type turn_index, - segment_identifier const& seg_id1, - segment_identifier const& seg_id2) const + segment_identifier const& candidate_seg_id, + segment_identifier const& previous_seg_id) const { // For uu/ii, only switch sources if indicated turn_type const& turn = m_turns[turn_index]; @@ -170,8 +215,16 @@ struct traversal { // Buffer does not use source_index (always 0) return turn.switch_source - ? seg_id1.multi_index != seg_id2.multi_index - : seg_id1.multi_index == seg_id2.multi_index; + ? 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) @@ -185,16 +238,8 @@ struct traversal } #endif return turn.switch_source - ? seg_id1.source_index != seg_id2.source_index - : seg_id1.source_index == seg_id2.source_index; - } - - inline - signed_size_type get_next_turn_index(turn_operation_type const& op) const - { - return op.enriched.next_ip_index == -1 - ? op.enriched.travels_to_ip_index - : op.enriched.next_ip_index; + ? candidate_seg_id.source_index != previous_seg_id.source_index + : candidate_seg_id.source_index == previous_seg_id.source_index; } inline bool traverse_possible(signed_size_type turn_index) const @@ -220,39 +265,39 @@ struct traversal { // For "cc", take either one, but if there is a starting one, // take that one. If next is dead end, skip that one. + // If both are valid candidates, take the one with minimal remaining + // distance (important for #mysql_23023665 in buffer). - bool result = false; - + // Initialize with 0, automatically assigned on first result typename turn_operation_type::comparable_distance_type - max_remaining_distance = 0; + min_remaining_distance = 0; + + bool result = false; for (int i = 0; i < 2; i++) { turn_operation_type const& op = turn.operations[i]; - signed_size_type const next_turn_index = get_next_turn_index(op); + signed_size_type const next_turn_index = op.enriched.get_next_turn_index(); - if (! result && traverse_possible(next_turn_index)) + if (! traverse_possible(next_turn_index)) { - max_remaining_distance = op.remaining_distance; - selected_op_index = i; - debug_traverse(turn, op, " Candidate"); - result = true; + continue; } - if (result) + if (! result + || next_turn_index == start_turn_index + || op.remaining_distance < min_remaining_distance) { - if (next_turn_index == start_turn_index) - { - selected_op_index = i; - debug_traverse(turn, op, " Candidate cc override (start)"); - } - else if (op.remaining_distance > max_remaining_distance) - { - max_remaining_distance = op.remaining_distance; - selected_op_index = i; - debug_traverse(turn, op, " Candidate cc override (remaining)"); - } + debug_traverse(turn, op, "First candidate cc", ! result); + debug_traverse(turn, op, "Candidate cc override (start)", + result && next_turn_index == start_turn_index); + debug_traverse(turn, op, "Candidate cc override (remaining)", + result && op.remaining_distance < min_remaining_distance); + + selected_op_index = i; + min_remaining_distance = op.remaining_distance; + result = true; } } @@ -262,7 +307,7 @@ struct traversal inline bool select_noncc_operation(turn_type const& turn, signed_size_type turn_index, - segment_identifier const& seg_id, + segment_identifier const& previous_seg_id, int& selected_op_index) const { bool result = false; @@ -273,10 +318,10 @@ struct traversal if (op.operation == target_operation && ! op.visited.finished() - && (! result || select_source(turn_index, op.seg_id, seg_id))) + && (! result || select_source(turn_index, op.seg_id, previous_seg_id))) { selected_op_index = i; - debug_traverse(turn, op, " Candidate"); + debug_traverse(turn, op, "Candidate"); result = true; } } @@ -305,7 +350,7 @@ struct traversal } if (result) { - debug_traverse(turn, turn.operations[selected_op_index], " Accepted"); + debug_traverse(turn, turn.operations[selected_op_index], "Accepted"); } return result; @@ -336,108 +381,164 @@ struct traversal } inline bool select_from_cluster_union(signed_size_type& turn_index, - int& op_index, signed_size_type start_turn_index, - sbs_type const& sbs, bool is_touching) const + int& op_index, sbs_type& sbs) 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 std::size_t selected_rank = 0; - std::size_t min_rank = 0; - bool result = false; - for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + for (std::size_t i = 1; i < aggregation.size(); i++) + { + sort_by_side::rank_with_rings const& rwr = aggregation[i]; + if (rwr.all_to() + && rwr.region_id() == incoming.region_id()) + { + selected_rank = rwr.rank; + break; + } + } + + 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 (result && ranked_point.rank > selected_rank) + if (ranked_point.rank == selected_rank + && ranked_point.direction == sort_by_side::dir_to) { - return result; + 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; + } - turn_type const& ranked_turn = m_turns[ranked_point.turn_index]; - turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index]; - if (result && ranked_op.visited.finalized()) + 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) { - // One of the arcs in the same direction as the selected result - // is already traversed. return false; } - - if (! is_touching && ranked_op.visited.finalized()) + turn_type const& turn = m_turns[rwd.turn_index]; + if (! turn.both(op_type)) { - // Skip this one, go to next - min_rank = ranked_point.rank; - continue; + return false; } - if (ranked_point.direction == sort_by_side::dir_to - && (ranked_point.rank > min_rank - || ranked_turn.both(operation_continue))) + // Check if this is not yet taken + turn_operation_type const& op = turn.operations[rwd.operation_index]; + if (op.visited.finalized()) { - if (ranked_op.enriched.count_left == 0 - && ranked_op.enriched.count_right > 0) - { - if (result && ranked_point.turn_index != start_turn_index) - { - // Don't override - only override if arrive at start - continue; - } - - turn_index = ranked_point.turn_index; - op_index = ranked_point.operation_index; - - result = true; - selected_rank = ranked_point.rank; - } - else if (! is_touching) - { - return result; - } + return false; } + } - return result; + return true; } inline bool analyze_cluster_intersection(signed_size_type& turn_index, - int& op_index, - sbs_type const& sbs) const + int& op_index, sbs_type const& sbs) const { std::vector<sort_by_side::rank_with_rings> aggregation; - sort_by_side::aggregate_operations(sbs, aggregation); + sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_intersection); std::size_t selected_rank = 0; - for (std::size_t i = 0; i < aggregation.size(); i++) + + // Detect specific pattern(s) + bool const detected + = intersection_pattern_common_interior1(selected_rank, aggregation) + || intersection_pattern_common_interior2(selected_rank, aggregation) + || intersection_pattern_common_interior3(selected_rank, aggregation) + || intersection_pattern_common_interior4(selected_rank, aggregation) + ; + + if (! detected) { - sort_by_side::rank_with_rings const& rwr = aggregation[i]; + int incoming_region_id = 0; + std::set<int> outgoing_region_ids; - if (i > 1 - && i - 1 == selected_rank - && rwr.rings.size() == 1) + for (std::size_t i = 0; i < aggregation.size(); i++) { - sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + sort_by_side::rank_with_rings const& rwr = aggregation[i]; - if (rwd.only_turn_on_ring) + if (rwr.all_to() + && rwr.traversable(m_turns) + && selected_rank == 0) { - // Find if this arriving ring was leaving previously - sort_by_side::ring_with_direction leaving = rwd; - leaving.direction = sort_by_side::dir_to; - - sort_by_side::rank_with_rings const& previous = aggregation[i - 1]; + // Take the first (= right) where segments leave, + // having the polygon on the right side + selected_rank = rwr.rank; + } - if (previous.rings.size() == 1 - && previous.rings.count(leaving) == 1) - { - // It arrives back - if this is one of the selected, unselect it - selected_rank = 0; - } + if (rwr.all_from() + && selected_rank > 0 + && outgoing_region_ids.empty()) + { + // Incoming + break; } - } - if (rwr.all_to()) - { - if (selected_rank == 0) + if (incoming_region_id == 0) { - // Take the first (= right) where segments leave, - // having the polygon on the right side - selected_rank = rwr.rank; + sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + turn_type const& turn = m_turns[rwd.turn_index]; + incoming_region_id = turn.operations[rwd.operation_index].enriched.region_id; + } + else + { + if (rwr.rings.size() == 1) + { + sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + turn_type const& turn = m_turns[rwd.turn_index]; + if (rwd.direction == sort_by_side::dir_to + && turn.both(operation_intersection)) + { + + turn_operation_type const& op = turn.operations[rwd.operation_index]; + if (op.enriched.region_id != incoming_region_id + && op.enriched.isolated) + { + outgoing_region_ids.insert(op.enriched.region_id); + } + } + else if (! outgoing_region_ids.empty()) + { + for (int i = 0; i < 2; i++) + { + int const region_id = turn.operations[i].enriched.region_id; + if (outgoing_region_ids.count(region_id) == 1) + { + selected_rank = 0; + outgoing_region_ids.erase(region_id); + } + } + } + } } } } @@ -458,7 +559,7 @@ struct traversal { // This direction is already traveled before, the same // cannot be traveled again - return false; + continue; } // Take the last turn from this rank @@ -479,10 +580,9 @@ struct traversal } inline bool select_turn_from_cluster(signed_size_type& turn_index, - int& op_index, bool& is_touching, + int& op_index, signed_size_type start_turn_index, - segment_identifier const& previous_seg_id, - bool is_start) const + segment_identifier const& previous_seg_id) const { bool const is_union = target_operation == operation_union; @@ -495,15 +595,14 @@ struct traversal cluster_info const& cinfo = mit->second; std::set<signed_size_type> const& ids = cinfo.turn_indices; - sbs_type sbs; - - bool has_origin = false; + sbs_type sbs(m_strategy); for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); sit != ids.end(); ++sit) { signed_size_type cluster_turn_index = *sit; turn_type const& cluster_turn = m_turns[cluster_turn_index]; + bool const departure_turn = cluster_turn_index == turn_index; if (cluster_turn.discarded) { // Defensive check, discarded turns should not be in cluster @@ -512,79 +611,27 @@ struct traversal for (int i = 0; i < 2; i++) { - turn_operation_type const& op = cluster_turn.operations[i]; - bool is_origin = false; - if (cluster_turn_index == turn_index) - { - // Check if this is the origin - if (OverlayType == overlay_buffer) - { - is_origin = op.seg_id.multi_index == previous_seg_id.multi_index; - } - else - { - is_origin = op.seg_id.source_index - == previous_seg_id.source_index; - } - if (is_origin) - { - has_origin = true; - } - } - - sbs.add(op, cluster_turn_index, i, m_geometry1, m_geometry2, - is_origin); + sbs.add(cluster_turn.operations[i], + cluster_turn_index, i, previous_seg_id, + m_geometry1, m_geometry2, + departure_turn); } } - if (! has_origin) + if (! sbs.has_origin()) { return false; } - sbs.apply(turn.point); bool result = false; if (is_union) { - #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) - is_touching = cinfo.open_count > 1; - if (is_touching) - { - if (cinfo.switch_source) - { - is_touching = false; - std::cout << "CLUSTER: SWITCH SOURCES at " << turn_index << std::endl; - } - else - { - std::cout << "CLUSTER: CONTINUE at " << turn_index << std::endl; - } - } - #else - is_touching = cinfo.open_count > 1 && ! cinfo.switch_source; - #endif - - if (is_touching) - { - sbs.reverse(); - } - - result = select_from_cluster_union(turn_index, op_index, start_turn_index, sbs, - is_touching); + result = select_from_cluster_union(turn_index, op_index, sbs); } else { - if (is_start - && turn.both(operation_intersection) - && turn.operations[op_index].enriched.only_turn_on_ring) - { - // For an ii (usually interior ring), only turn on ring, - // reverse to take first exit - sbs.reverse(); - } - result = analyze_cluster_intersection(turn_index, op_index, sbs); } return result; @@ -594,26 +641,27 @@ struct traversal turn_type const& current_turn, segment_identifier const& previous_seg_id) { - sbs_type sbs; + sbs_type sbs(m_strategy); // Add this turn to the sort-by-side sorter - bool has_origin = false; for (int i = 0; i < 2; i++) { - turn_operation_type const& op = current_turn.operations[i]; - bool const is_origin = op.seg_id.source_index - == previous_seg_id.source_index; - has_origin = has_origin || is_origin; - sbs.add(op, turn_index, i, m_geometry1, m_geometry2, is_origin); + sbs.add(current_turn.operations[i], + turn_index, i, previous_seg_id, + m_geometry1, m_geometry2, + true); } - if (! has_origin) + if (! sbs.has_origin()) { return false; } sbs.apply(current_turn.point); - return analyze_cluster_intersection(turn_index, op_index, sbs); + + bool result = analyze_cluster_intersection(turn_index, op_index, sbs); + + return result; } inline void change_index_for_self_turn(signed_size_type& to_vertex_index, @@ -712,7 +760,6 @@ struct traversal bool select_turn(signed_size_type start_turn_index, int start_op_index, signed_size_type& turn_index, int& op_index, - bool& is_touching, int previous_op_index, signed_size_type previous_turn_index, segment_identifier const& previous_seg_id, @@ -737,8 +784,8 @@ struct traversal if (current_turn.cluster_id < 0 && current_turn.both(operation_intersection)) { - if (analyze_ii_intersection(turn_index, op_index, current_turn, - previous_seg_id)) + if (analyze_ii_intersection(turn_index, op_index, + current_turn, previous_seg_id)) { return true; } @@ -747,8 +794,8 @@ struct traversal if (current_turn.cluster_id >= 0) { - if (! select_turn_from_cluster(turn_index, op_index, is_touching, - start_turn_index, previous_seg_id, is_start)) + if (! select_turn_from_cluster(turn_index, op_index, + start_turn_index, previous_seg_id)) { return false; } @@ -786,6 +833,7 @@ private : Turns& m_turns; Clusters const& m_clusters; RobustPolicy const& m_robust_policy; + SideStrategy m_strategy; Visitor& m_visitor; }; diff --git a/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp new file mode 100644 index 0000000000..12279d762f --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp @@ -0,0 +1,306 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-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_TRAVERSAL_INTERSECTION_PATTERNS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP + +#include <cstddef> +#include <vector> + +#include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp> +#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggregation, + signed_size_type incoming_region_id, + std::size_t first, std::size_t last) +{ + // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy + + for (std::size_t i = first; i <= last; i += 2) + { + 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(); + + bool const possible = + curr.rings.size() == 2 + && curr.is_isolated() + && curr.has_unique_region_id() + && next.rings.size() == 2 + && next.is_isolated() + && next.has_unique_region_id() + && curr_id == next_id + && curr_id != incoming_region_id; + + if (! possible) + { + return false; + } + } + + return true; +} + +inline bool intersection_pattern_common_interior1(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: coming from exterior ring, encountering an isolated + // parallel interior ring, which should be skipped, and the first + // left (normally intersection takes first right) should be taken. + // Solves cases #case_133_multi + // and #case_recursive_boxes_49 + + std::size_t const n = aggregation.size(); + if (n < 4) + { + 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.rings.size() == 1 + && incoming.has_only(operation_intersection); + + if (! incoming_ok) + { + return false; + } + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.rings.size() == 1 + && outgoing.has_only(operation_intersection) + && outgoing.region_id() == incoming.region_id(); + + if (! outgoing_ok) + { + return false; + } + + if (check_pairs(aggregation, incoming.region_id(), 1, n - 2)) + { + selected_rank = n - 1; + return true; + } + return false; +} + +inline bool intersection_pattern_common_interior2(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: coming from two exterior rings, encountering two isolated + // equal interior rings + + // See (for example, for ii) #case_recursive_boxes_53: + + // INCOMING: + // Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {13[1] (s:1, m:0) i F rgn: 1 ISO} + + // PAIR: + // Rank 1 {13[0] (s:0, r:1, m:0) i T rgn: 3 ISO ->16} {11[1] (s:1, r:5, m:0) i T rgn: 3 ISO ->16} + // Rank 2 {13[0] (s:0, r:1, m:0) i F rgn: 3 ISO} {11[1] (s:1, r:5, m:0) i F rgn: 3 ISO} + + // LEAVING (in the same direction, take last one) + // Rank 3 {11[0] (s:0, m:0) i T rgn: 1 ISO ->10} {13[1] (s:1, m:0) i T rgn: 1 ISO ->10} + + + std::size_t const n = aggregation.size(); + if (n < 4) + { + 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.rings.size() == 2 + && incoming.has_unique_region_id(); + + if (! incoming_ok) + { + return false; + } + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.rings.size() == 2 + && outgoing.has_unique_region_id() + && outgoing.region_id() == incoming.region_id(); + + if (! outgoing_ok) + { + return false; + } + + bool const operation_ok = + (incoming.has_only(operation_continue) && outgoing.has_only(operation_continue)) + || (incoming.has_only(operation_intersection) && outgoing.has_only(operation_intersection)); + + if (! operation_ok) + { + return false; + } + + // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy + if (check_pairs(aggregation, incoming.region_id(), 1, n - 2)) + { + selected_rank = n - 1; + return true; + } + return false; +} + +inline bool intersection_pattern_common_interior3(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: approaches colocated turn (exterior+interior) from two + // different directions, and both leaves in the same direction + + // See #case_136_multi: + // INCOMING: + //Rank 0 {10[0] (s:0, m:0) c F rgn: 1 ISO} + + // PAIR: + //Rank 1 {14[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->16} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->16} + //Rank 2 {14[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 (select this one): + //Rank 3 {10[0] (s:0, m:0) c T rgn: 1 ISO ->12} {10[1] (s:1, m:0) c T rgn: 1 ISO ->12} + + // ADDITIONALLY: (other polygon coming in) + //Rank 4 {10[1] (s:1, m:0) c F rgn: 1 ISO} + + std::size_t const n = aggregation.size(); + if (n < 4) + { + return false; + } + + sort_by_side::rank_with_rings const& incoming = aggregation.front(); + sort_by_side::rank_with_rings const& outgoing = aggregation[n - 2]; + sort_by_side::rank_with_rings const& last = aggregation.back(); + + bool const incoming_ok = + incoming.all_from() + && incoming.rings.size() == 1 + && incoming.has_only(operation_continue); + + if (! incoming_ok) + { + return false; + } + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.rings.size() == 2 + && outgoing.has_only(operation_continue) + && outgoing.has_unique_region_id() + && outgoing.region_id() == incoming.region_id() + && last.all_from() + && last.rings.size() == 1 + && last.region_id() == incoming.region_id() + && last.all_from(); + + if (! outgoing_ok) + { + return false; + } + + // 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 - 2; + return true; + } + return false; +} + + +inline bool intersection_pattern_common_interior4(std::size_t& selected_rank, + std::vector<sort_by_side::rank_with_rings> const& aggregation) +{ + // Pattern: approaches colocated turn (exterior+interior) from same + // direction, but leaves in two different directions + + // See #case_137_multi: + + // INCOMING: + //Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {10[1] (s:1, m:0) i F rgn: 1 ISO} + + // PAIR: + //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) + //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} + + std::size_t const n = aggregation.size(); + if (n < 4) + { + return false; + } + + sort_by_side::rank_with_rings const& incoming = aggregation.front(); + sort_by_side::rank_with_rings const& extra = aggregation[n - 2]; + sort_by_side::rank_with_rings const& outgoing = aggregation.back(); + + bool const incoming_ok = + incoming.all_from() + && incoming.rings.size() == 2 + && incoming.has_unique_region_id() + && incoming.has_only(operation_intersection); + + if (! incoming_ok) + { + return false; + } + + bool const outgoing_ok = + outgoing.all_to() + && outgoing.rings.size() == 1 + && outgoing.has_only(operation_intersection) + && outgoing.region_id() == incoming.region_id() + && extra.all_to() + && extra.rings.size() == 1 + && extra.has_only(operation_intersection) + && extra.region_id() == incoming.region_id(); + + if (! outgoing_ok) + { + return false; + } + + // 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; + return true; + } + return false; +} + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp index 9ab82a77c1..af643a822b 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp @@ -49,9 +49,13 @@ template > struct traversal_ring_creator { - typedef traversal<Reverse1, Reverse2, OverlayType, - Geometry1, Geometry2, Turns, Clusters, RobustPolicy, Visitor> - traversal_type; + typedef traversal + < + Reverse1, Reverse2, OverlayType, + Geometry1, Geometry2, Turns, Clusters, + RobustPolicy, typename IntersectionStrategy::side_strategy_type, + Visitor + > traversal_type; typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; @@ -63,7 +67,9 @@ struct traversal_ring_creator Turns& turns, Clusters const& clusters, IntersectionStrategy const& intersection_strategy, RobustPolicy const& robust_policy, Visitor& visitor) - : m_trav(geometry1, geometry2, turns, clusters, robust_policy,visitor) + : m_trav(geometry1, geometry2, turns, clusters, + robust_policy, intersection_strategy.get_side_strategy(), + visitor) , m_geometry1(geometry1) , m_geometry2(geometry2) , m_turns(turns) @@ -103,12 +109,14 @@ struct traversal_ring_creator { geometry::copy_segments<Reverse1>(m_geometry1, previous_op.seg_id, to_vertex_index, + m_intersection_strategy.get_side_strategy(), m_robust_policy, current_ring); } else { geometry::copy_segments<Reverse2>(m_geometry2, previous_op.seg_id, to_vertex_index, + m_intersection_strategy.get_side_strategy(), m_robust_policy, current_ring); } } @@ -127,10 +135,8 @@ struct traversal_ring_creator m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); } - bool is_touching = false; if (! m_trav.select_turn(start_turn_index, start_op_index, turn_index, op_index, - is_touching, previous_op_index, previous_turn_index, previous_seg_id, is_start)) { @@ -154,6 +160,7 @@ struct traversal_ring_creator turn_type& current_turn = m_turns[turn_index]; turn_operation_type& op = current_turn.operations[op_index]; detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point, + m_intersection_strategy.get_side_strategy(), m_robust_policy); // Register the visit @@ -171,6 +178,7 @@ struct traversal_ring_creator turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; detail::overlay::append_no_dups_or_spikes(ring, start_turn.point, + m_intersection_strategy.get_side_strategy(), m_robust_policy); signed_size_type current_turn_index = start_turn_index; @@ -273,7 +281,9 @@ struct traversal_ring_creator if (geometry::num_points(ring) >= min_num_points) { - clean_closing_dups_and_spikes(ring, m_robust_policy); + clean_closing_dups_and_spikes(ring, + m_intersection_strategy.get_side_strategy(), + m_robust_policy); rings.push_back(ring); m_trav.finalize_visit_info(); @@ -307,11 +317,27 @@ struct traversal_ring_creator continue; } - for (int op_index = 0; op_index < 2; op_index++) + if (turn.both(operation_continue)) { + // Traverse only one turn, the one with the SMALLEST remaining distance + // to avoid skipping a turn in between, which can happen in rare cases + // (e.g. #130) + turn_operation_type const& op0 = turn.operations[0]; + turn_operation_type const& op1 = turn.operations[1]; + int const op_index + = op0.remaining_distance <= op1.remaining_distance ? 0 : 1; + traverse_with_operation(turn, turn_index, op_index, rings, finalized_ring_size, state); } + else + { + for (int op_index = 0; op_index < 2; op_index++) + { + traverse_with_operation(turn, turn_index, op_index, + rings, finalized_ring_size, state); + } + } } } diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp index 183131c74b..0b4f393ef4 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp @@ -16,6 +16,7 @@ #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/copy_segments.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/turn_info.hpp> #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> @@ -47,10 +48,54 @@ template > struct traversal_switch_detector { + enum isolation_type { isolation_unknown = -1, isolation_no = 0, isolation_yes = 1 }; + typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; - // For convenience + // 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; + + merged_ring_properties() + : region_id(-1) + {} + }; + + struct connection_properties + { + std::size_t count; + std::set<signed_size_type> cluster_indices; + connection_properties() + : count(0) + {} + }; + + typedef std::map<signed_size_type, connection_properties> connection_map; + + // Per region, a set of properties is maintained, including its connections + // to other regions + struct region_properties + { + signed_size_type region_id; + isolation_type isolated; + + // Maps from connected region_id to their properties + connection_map connected_region_counts; + + region_properties() + : region_id(-1) + , isolated(isolation_unknown) + {} + }; + + // Keeps turn indices per ring + 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; inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2, @@ -62,135 +107,309 @@ struct traversal_switch_detector , m_clusters(clusters) , m_robust_policy(robust_policy) , m_visitor(visitor) - , m_region_id(0) { + } + + isolation_type get_isolation(region_properties const& properties, + signed_size_type parent_region_id, + const std::set<signed_size_type>& visited) + { + if (properties.isolated != isolation_unknown) + { + return properties.isolated; + } + + 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) + { + 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) + { + all_colocated = false; + } + else if (unique_cluster_id == -1) + { + unique_cluster_id = cluster_id; + } + else if (unique_cluster_id != cluster_id) + { + all_colocated = false; + } + } + if (all_colocated) + { + return isolation_yes; + } + + + // 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) + { + signed_size_type const region_id = it->first; + connection_properties const& cprop = it->second; + + if (region_id == parent_region_id) + { + // Normal situation, skip its direct parent + continue; + } + if (visited.count(region_id) > 0) + { + // Find one of its ancestors again, this is a ring. Not isolated. + return isolation_no; + } + if (cprop.count > 1) + { + return isolation_no; + } + + typename region_connection_map::iterator mit = m_connected_regions.find(region_id); + if (mit == m_connected_regions.end()) + { + // Should not occur + continue; + } + + std::set<signed_size_type> vis = visited; + vis.insert(parent_region_id); + region_properties& prop = mit->second; + if (prop.isolated == isolation_unknown) + { + isolation_type const iso = get_isolation(prop, properties.region_id, vis); + prop.isolated = iso; + if (iso == isolation_no) + { + child_not_isolated = true; + } + } + if (prop.isolated == isolation_no) + { + non_isolation_count++; + } + } + + return child_not_isolated || non_isolation_count > 1 ? isolation_no : isolation_yes; } - static inline bool connects_same_zone(turn_type const& turn) + void get_isolated_regions() { + for (typename region_connection_map::iterator it = m_connected_regions.begin(); + it != m_connected_regions.end(); ++it) + { + region_properties& properties = it->second; + if (properties.isolated == isolation_unknown) + { + std::set<signed_size_type> visited; + properties.isolated = get_isolation(properties, properties.region_id, visited); + } + } + } + + void assign_isolation() + { + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type& turn = m_turns[turn_index]; + + for (int op_index = 0; op_index < 2; op_index++) + { + turn_operation_type& op = turn.operations[op_index]; + typename region_connection_map::const_iterator mit = m_connected_regions.find(op.enriched.region_id); + if (mit != m_connected_regions.end()) + { + region_properties const& prop = mit->second; + op.enriched.isolated = prop.isolated == isolation_yes; + } + } + } + } + + void assign_regions() + { + for (typename merge_map::const_iterator it + = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) + { + ring_identifier const& ring_id = it->first; + merged_ring_properties const& properties = it->second; + + for (set_iterator sit = properties.turn_indices.begin(); + sit != properties.turn_indices.end(); ++sit) + { + turn_type& turn = m_turns[*sit]; + + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + if (ring_id_by_seg_id(op.seg_id) == ring_id) + { + 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]; + + 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); + } + } + } + } + + inline bool connects_same_region(turn_type const& turn) const + { + if (turn.discarded) + { + // Discarded turns don't connect same region (otherwise discarded colocated uu turn + // could make a connection) + return false; + } + if (turn.cluster_id == -1) { - // If it is a uu/ii-turn (non clustered), it is never same zone + // If it is a uu/ii-turn (non clustered), it is never same region return ! (turn.both(operation_union) || turn.both(operation_intersection)); } - // It is a cluster, check zones of both operations - return turn.operations[0].enriched.zone - == turn.operations[1].enriched.zone; + if (operation_from_overlay<OverlayType>::value == operation_union) + { + // It is a cluster, check zones + // (assigned by sort_by_side/handle colocations) of both operations + return turn.operations[0].enriched.zone + == 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; } + inline int get_region_id(turn_operation_type const& op) const { - std::map<ring_identifier, int>::const_iterator it - = m_regions.find(ring_id_by_seg_id(op.seg_id)); - return it == m_regions.end() ? -1 : it->second; + return op.enriched.region_id; } - void create_region(ring_identifier const& ring_id, std::set<signed_size_type> const& ring_turn_indices, int region_id = -1) + + void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id, + merged_ring_properties& properties, int region_id = -1) { - std::map<ring_identifier, int>::const_iterator it = m_regions.find(ring_id); - if (it != m_regions.end()) + if (properties.region_id > 0) { - // The ring is already gathered in a region, quit + // Already handled return; } + + // Assign new id if this is a new region if (region_id == -1) { - region_id = m_region_id++; + region_id = new_region_id++; } // Assign this ring to specified region - m_regions[ring_id] = region_id; + properties.region_id = region_id; + #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl; #endif // Find connecting rings, recursively - for (set_iterator sit = ring_turn_indices.begin(); - sit != ring_turn_indices.end(); ++sit) + for (set_iterator sit = properties.turn_indices.begin(); + sit != properties.turn_indices.end(); ++sit) { signed_size_type const turn_index = *sit; turn_type const& turn = m_turns[turn_index]; - if (! connects_same_zone(turn)) + if (! connects_same_region(turn)) { // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones' continue; } - // This turn connects two rings (interior connected), create the - // same region + // Union: This turn connects two rings (interior connected), create the region + // Intersection: This turn connects two rings, set same regions for these two rings for (int op_index = 0; op_index < 2; op_index++) { turn_operation_type const& op = turn.operations[op_index]; ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id); if (connected_ring_id != ring_id) { - propagate_region(connected_ring_id, region_id); + propagate_region(new_region_id, connected_ring_id, region_id); } } } } - void check_turns_per_ring(ring_identifier const& ring_id, - std::set<signed_size_type> const& ring_turn_indices) + void propagate_region(signed_size_type& new_region_id, + ring_identifier const& ring_id, int region_id) { - bool only_turn_on_ring = true; - if (ring_turn_indices.size() > 1) - { - // More turns on this ring. Only leave only_turn_on_ring true - // if they are all of the same cluster - int cluster_id = -1; - for (set_iterator sit = ring_turn_indices.begin(); - sit != ring_turn_indices.end(); ++sit) - { - turn_type const& turn = m_turns[*sit]; - if (turn.cluster_id == -1) - { - // Unclustered turn - and there are 2 or more turns - // so the ring has different turns - only_turn_on_ring = false; - break; - } - - // Clustered turn, check if it is the first or same as previous - if (cluster_id == -1) - { - cluster_id = turn.cluster_id; - } - else if (turn.cluster_id != cluster_id) - { - only_turn_on_ring = false; - break; - } - } - } - - // Assign result to matching operation (a turn is always on two rings) - for (set_iterator sit = ring_turn_indices.begin(); - sit != ring_turn_indices.end(); ++sit) - { - turn_type& turn = m_turns[*sit]; - for (int i = 0; i < 2; i++) - { - turn_operation_type& op = turn.operations[i]; - if (ring_id_by_seg_id(op.seg_id) == ring_id) - { - op.enriched.only_turn_on_ring = only_turn_on_ring; - } - } - } - } - - void propagate_region(ring_identifier const& ring_id, int region_id) - { - std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it = m_turns_per_ring.find(ring_id); + typename merge_map::iterator it = m_turns_per_ring.find(ring_id); if (it != m_turns_per_ring.end()) { - create_region(ring_id, it->second, region_id); + create_region(new_region_id, ring_id, it->second, region_id); } } + void iterate() { #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) @@ -199,26 +418,38 @@ struct traversal_switch_detector // Collect turns per ring m_turns_per_ring.clear(); - m_regions.clear(); - m_region_id = 1; + m_connected_regions.clear(); for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) { turn_type const& turn = m_turns[turn_index]; + if (turn.discarded + && operation_from_overlay<OverlayType>::value == operation_intersection) + { + // Discarded turn (union currently still needs it to determine regions) + continue; + } + for (int op_index = 0; op_index < 2; op_index++) { turn_operation_type const& op = turn.operations[op_index]; - m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].insert(turn_index); + m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].turn_indices.insert(turn_index); } } // All rings having turns are in the map. Now iterate them - for (std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it - = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) { - create_region(it->first, it->second); - check_turns_per_ring(it->first, it->second); + signed_size_type new_region_id = 1; + for (typename merge_map::iterator it + = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) + { + create_region(new_region_id, it->first, it->second); + } + + assign_regions(); + get_isolated_regions(); + assign_isolation(); } // Now that all regions are filled, assign switch_source property @@ -245,6 +476,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]); @@ -252,7 +487,7 @@ struct traversal_switch_detector } } // Switch source if this cluster connects the same region - cinfo.switch_source = regions.size() == 1; + cinfo.switch_source = regions.size() <= 1; } // Iterate through all uu/ii turns (non-clustered) @@ -326,13 +561,10 @@ private: Geometry2 const& m_geometry2; Turns& m_turns; Clusters& m_clusters; + merge_map m_turns_per_ring; + region_connection_map m_connected_regions; RobustPolicy const& m_robust_policy; Visitor& m_visitor; - - std::map<ring_identifier, int> m_regions; - std::map<ring_identifier, std::set<signed_size_type> > m_turns_per_ring; - int m_region_id; - }; }} // namespace detail::overlay diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index e09af126c6..3a4c2e94a1 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -89,18 +89,24 @@ 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 bool discarded; - bool colocated; + + // 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 switch_source; // For u/u turns which can either switch or not Container operations; inline turn_info() : method(method_none) + , touch_only(false) , cluster_id(-1) , discarded(false) - , colocated(false) + , colocated_ii(false) + , colocated_uu(false) , switch_source(false) {} @@ -133,7 +139,6 @@ struct turn_info return has(operation_blocked); } - private : inline bool has12(operation_type type1, operation_type type2) const { |