diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
14 files changed, 557 insertions, 69 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp index b1a25c9f5e..8cb37d6954 100644 --- a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp +++ b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp @@ -51,14 +51,14 @@ class liang_barsky private: typedef model::referring_segment<Point> segment_type; - template <typename T> - inline bool check_edge(T const& p, T const& q, T& t1, T& t2) const + template <typename CoordinateType, typename CalcType> + inline bool check_edge(CoordinateType const& p, CoordinateType const& q, CalcType& t1, CalcType& t2) const { bool visible = true; if(p < 0) { - T const r = q / p; + CalcType const r = static_cast<CalcType>(q) / p; if (r > t2) visible = false; else if (r > t1) @@ -66,7 +66,7 @@ private: } else if(p > 0) { - T const r = q / p; + CalcType const r = static_cast<CalcType>(q) / p; if (r < t1) visible = false; else if (r < t2) @@ -86,9 +86,10 @@ public: inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const { typedef typename select_coordinate_type<Box, Point>::type coordinate_type; + typedef typename select_most_precise<coordinate_type, double>::type calc_type; - coordinate_type t1 = 0; - coordinate_type t2 = 1; + calc_type t1 = 0; + calc_type t2 = 1; coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s); coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s); diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 3f81c4dca9..bc84286241 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -26,7 +26,9 @@ #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> +#include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp> #include <boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/policies/robustness/robust_type.hpp> #include <boost/geometry/strategies/side.hpp> #ifdef BOOST_GEOMETRY_DEBUG_ENRICH @@ -466,6 +468,7 @@ inline void create_map(TurnPoints const& turn_points, MappedVector& mapped_vecto template < bool Reverse1, bool Reverse2, + overlay_type OverlayType, typename TurnPoints, typename Geometry1, typename Geometry2, typename RobustPolicy, @@ -490,10 +493,9 @@ inline void enrich_intersection_points(TurnPoints& turn_points, std::vector<indexed_turn_operation> > mapped_vector_type; - // DISCARD ALL UU - // #76 is the reason that this is necessary... - // With uu, at all points there is the risk that rings are being traversed twice or more. - // Without uu, all rings having only uu will be untouched and gathered by assemble + // Iterate through turns and discard uu + // and check if there are possible colocations + bool check_colocations = false; for (typename boost::range_iterator<TurnPoints>::type it = boost::begin(turn_points); it != boost::end(turn_points); @@ -501,14 +503,34 @@ inline void enrich_intersection_points(TurnPoints& turn_points, { if (it->both(detail::overlay::operation_union)) { + // Discard (necessary for a.o. #76). With uu, at all points there + // is the risk that rings are being traversed twice or more. + // Without uu, all rings having only uu will be untouched + // and gathered by assemble it->discarded = true; + check_colocations = true; } - if (it->both(detail::overlay::operation_none)) + else if (it->combination(detail::overlay::operation_union, + detail::overlay::operation_blocked)) + { + check_colocations = true; + } + else if (OverlayType == overlay_difference + && it->both(detail::overlay::operation_intersection)) + { + // For difference operation (u/u -> i/i) + check_colocations = true; + } + else if (it->both(detail::overlay::operation_none)) { it->discarded = true; } } + if (check_colocations) + { + detail::overlay::handle_colocations<OverlayType>(turn_points); + } // Create a map of vectors of indexed operation-types to be able // to sort intersection points PER RING diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp index b2c3836712..b9e48cdbfc 100644 --- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2015, Oracle and/or its affiliates. // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -22,6 +22,7 @@ #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> #include <boost/geometry/algorithms/detail/overlay/follow.hpp> +#include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -35,24 +36,6 @@ namespace boost { namespace geometry { -#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) -class inconsistent_turns_exception : public geometry::exception -{ -public: - - inline inconsistent_turns_exception() {} - - virtual ~inconsistent_turns_exception() throw() - {} - - virtual char const* what() const throw() - { - return "Boost.Geometry Inconsistent Turns exception"; - } -}; -#endif - - #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace overlay { diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 717f0b47a9..ac36c530bf 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -585,8 +585,8 @@ struct collinear : public base_turn_handler typename SidePolicy > static inline void apply( - Point1 const& , Point1 const& , Point1 const& , - Point2 const& , Point2 const& , Point2 const& , + Point1 const& , Point1 const& pj, Point1 const& pk, + Point2 const& , Point2 const& qj, Point2 const& qk, TurnInfo& ti, IntersectionInfo const& info, DirInfo const& dir_info, @@ -623,8 +623,30 @@ struct collinear : public base_turn_handler { ui_else_iu(product == 1, ti); } + + // Calculate remaining distance. If it continues collinearly it is + // measured until the end of the next segment + ti.operations[0].remaining_distance + = side_p == 0 + ? distance_measure(ti.point, pk) + : distance_measure(ti.point, pj); + ti.operations[1].remaining_distance + = side_q == 0 + ? distance_measure(ti.point, qk) + : distance_measure(ti.point, qj); } + template <typename Point1, typename Point2> + static inline typename geometry::coordinate_type<Point1>::type + distance_measure(Point1 const& a, Point2 const& b) + { + // TODO: use comparable distance for point-point instead - but that + // causes currently cycling include problems + typedef typename geometry::coordinate_type<Point1>::type ctype; + ctype const dx = get<0>(a) - get<0>(b); + ctype const dy = get<1>(b) - get<1>(b); + return dx * dx + dy * dy; + } }; template diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp index e4f8de42e1..ee0a93ae7e 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -23,9 +23,9 @@ namespace detail { namespace overlay { enum turn_position { position_middle, position_front, position_back }; -template <typename SegmentRatio> +template <typename Point, typename SegmentRatio> struct turn_operation_linear - : public turn_operation<SegmentRatio> + : public turn_operation<Point, SegmentRatio> { turn_operation_linear() : position(position_middle) diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index 098c7b5642..b2b97c0337 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -802,19 +802,19 @@ template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type> struct turn_operation_type { - typedef overlay::turn_operation<SegmentRatio> type; + typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type; }; template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag> { - typedef overlay::turn_operation_linear<SegmentRatio> type; + typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; }; template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag> { - typedef overlay::turn_operation_linear<SegmentRatio> type; + typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; }; }} // namespace detail::get_turns diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp new file mode 100644 index 0000000000..6f332ddff2 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -0,0 +1,278 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP + +#include <cstddef> +#include <algorithm> +#include <map> +#include <vector> + +#include <boost/range.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/algorithms/detail/ring_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> + +#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) +# include <iostream> +# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> +# include <boost/geometry/io/wkt/wkt.hpp> +# define BOOST_GEOMETRY_DEBUG_IDENTIFIER +#endif + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +struct turn_operation_index +{ + turn_operation_index(signed_size_type ti = -1, + signed_size_type oi = -1) + : turn_index(ti) + , op_index(oi) + {} + + signed_size_type turn_index; + signed_size_type op_index; // basically only 0,1 +}; + + +template <typename TurnPoints> +struct less_by_fraction_and_type +{ + inline less_by_fraction_and_type(TurnPoints const& turn_points) + : m_turns(turn_points) + { + } + + inline bool operator()(turn_operation_index const& left, + turn_operation_index const& right) const + { + typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + turn_type const& left_turn = m_turns[left.turn_index]; + turn_type const& right_turn = m_turns[right.turn_index]; + turn_operation_type const& left_op + = left_turn.operations[left.op_index]; + + turn_operation_type const& right_op + = right_turn.operations[right.op_index]; + + if (! (left_op.fraction == right_op.fraction)) + { + return left_op.fraction < right_op.fraction; + } + + turn_operation_type const& left_other_op + = left_turn.operations[1 - left.op_index]; + + turn_operation_type const& right_other_op + = right_turn.operations[1 - right.op_index]; + + // Fraction is the same, now sort on ring id, first outer ring, + // then interior rings + return left_other_op.seg_id < right_other_op.seg_id; + } + +private: + TurnPoints const& m_turns; +}; + +template <overlay_type OverlayType, typename TurnPoints, typename OperationVector> +inline void handle_colocation_cluster(TurnPoints& turn_points, + segment_identifier const& current_ring_seg_id, + OperationVector const& vec) +{ + typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + std::vector<turn_operation_index>::const_iterator vit = vec.begin(); + + turn_type cluster_turn = turn_points[vit->turn_index]; + turn_operation_type cluster_op + = cluster_turn.operations[vit->op_index]; + segment_identifier cluster_other_id + = cluster_turn.operations[1 - vit->op_index].seg_id; + bool const discard_colocated + = cluster_turn.both(operation_union) + || cluster_turn.combination(operation_blocked, operation_union); + + for (++vit; vit != vec.end(); ++vit) + { + turn_operation_index const& toi = *vit; + turn_type& turn = turn_points[toi.turn_index]; + turn_operation_type const& op = turn.operations[toi.op_index]; + segment_identifier const& other_id + = turn.operations[1 - toi.op_index].seg_id; + + if (cluster_op.fraction == op.fraction) + { + // Two turns of current ring with same source are colocated, + // one is from exterior ring, one from interior ring + bool const colocated_ext_int + = cluster_other_id.multi_index == other_id.multi_index + && cluster_other_id.ring_index == -1 + && other_id.ring_index >= 0; + + // Turn of current interior ring with other interior ring + bool const touch_int_int + = current_ring_seg_id.ring_index >= 0 + && other_id.ring_index >= 0; + + if (discard_colocated && colocated_ext_int) + { + // If the two turns on this same segment are a + // colocation with two different segments on the + // other geometry, of the same polygon but with + // the outer (u/u or u/x) and the inner ring (non u/u), + // that turn with inner ring should be discarded + turn.discarded = true; + turn.colocated = true; + } + else if (cluster_turn.colocated + && touch_int_int + && turn.both(operation_intersection)) + { + // Two holes touch each other at a point where the + // exterior ring also touches + turn.discarded = true; + turn.colocated = true; + } + else if (OverlayType == overlay_difference + && turn.both(operation_intersection) + && colocated_ext_int) + { + // For difference (polygon inside out) we need to + // discard i/i instead, in case of colocations + turn.discarded = true; + turn.colocated = true; + } + } + else + { + // Not on same fraction on this segment + // assign for next potential cluster + cluster_turn = turn; + cluster_op = op; + cluster_other_id = other_id; + } + + } +} + + +// Checks colocated turns and flags combinations of uu/other, possibly a +// combination of a ring touching another geometry's interior ring which is +// tangential to the exterior ring + +// This function can be extended to replace handle_tangencies: at each +// colocation incoming and outgoing vectors should be inspected + +template <overlay_type OverlayType, typename TurnPoints> +inline void handle_colocations(TurnPoints& turn_points) +{ + typedef std::map + < + segment_identifier, + std::vector<turn_operation_index> + > map_type; + + // Create and fill map on segment-identifier Map is sorted on seg_id, + // meaning it is sorted on ring_identifier too. This means that exterior + // rings are handled first. If there is a colocation on the exterior ring, + // that information can be used for the interior ring too + map_type map; + + int index = 0; + for (typename boost::range_iterator<TurnPoints>::type + it = boost::begin(turn_points); + it != boost::end(turn_points); + ++it, ++index) + { + map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0)); + map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1)); + } + + // Check if there are multiple turns on one or more segments, + // if not then nothing is to be done + bool colocations = 0; + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); + ++it) + { + if (it->second.size() > 1u) + { + colocations = true; + break; + } + } + + if (! colocations) + { + return; + } + + // Sort all vectors, per same segment + less_by_fraction_and_type<TurnPoints> less(turn_points); + for (typename map_type::iterator it = map.begin(); + it != map.end(); ++it) + { + std::sort(it->second.begin(), it->second.end(), less); + } + + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); ++it) + { + if (it->second.size() > 1) + { + handle_colocation_cluster<OverlayType>(turn_points, + it->first, it->second); + } + } + +#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) + std::cout << "*** Colocations " << map.size() << std::endl; + for (typename map_type::const_iterator it = map.begin(); + it != map.end(); ++it) + { + std::cout << it->first << std::endl; + for (std::vector<turn_operation_index>::const_iterator vit + = it->second.begin(); vit != it->second.end(); ++vit) + { + turn_operation_index const& toi = *vit; + std::cout << geometry::wkt(turn_points[toi.turn_index].point) + << std::boolalpha + << " discarded=" << turn_points[toi.turn_index].discarded + << " colocated=" << turn_points[toi.turn_index].colocated + << " " << operation_char(turn_points[toi.turn_index].operations[0].operation) + << " " << turn_points[toi.turn_index].operations[0].seg_id + << " " << turn_points[toi.turn_index].operations[0].fraction + << " // " << operation_char(turn_points[toi.turn_index].operations[1].operation) + << " " << turn_points[toi.turn_index].operations[1].seg_id + << " " << turn_points[toi.turn_index].operations[1].fraction + << std::endl; + } + } +#endif // DEBUG + +} + + +}} // namespace detail::overlay +#endif //DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp new file mode 100644 index 0000000000..1486f94fbd --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp @@ -0,0 +1,38 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014-2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP + +#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) +#include <boost/geometry/core/exception.hpp> + +namespace boost { namespace geometry +{ + +class inconsistent_turns_exception : public geometry::exception +{ +public: + + inline inconsistent_turns_exception() {} + + virtual ~inconsistent_turns_exception() throw() + {} + + virtual char const* what() const throw() + { + return "Boost.Geometry Inconsistent Turns exception"; + } +}; + +}} // boost::geometry + +#endif // BOOST_GEOMETRY_OVERLAY_NO_THROW + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP diff --git a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp index dd041b0d7d..c62b7d2834 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp @@ -1,6 +1,11 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -39,19 +44,26 @@ struct intersection_box_box { typedef typename coordinate_type<BoxOut>::type ct; - ct min1 = get<min_corner, Dimension>(box1); - ct min2 = get<min_corner, Dimension>(box2); ct max1 = get<max_corner, Dimension>(box1); + ct min2 = get<min_corner, Dimension>(box2); + + if (max1 < min2) + { + return false; + } + ct max2 = get<max_corner, Dimension>(box2); + ct min1 = get<min_corner, Dimension>(box1); - if (max1 < min2 || max2 < min1) + if (max2 < min1) { return false; } + // Set dimensions of output coordinate set<min_corner, Dimension>(box_out, min1 < min2 ? min2 : min1); set<max_corner, Dimension>(box_out, max1 > max2 ? max2 : max1); - + return intersection_box_box<Dimension + 1, DimensionCount> ::apply(box1, box2, robust_policy, box_out, strategy); } diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index af0731f5a9..59c8f6f1ff 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -41,6 +41,7 @@ #include <boost/geometry/views/segment_view.hpp> #include <boost/geometry/views/detail/boundary_view.hpp> +#include <boost/geometry/algorithms/detail/check_iterator_range.hpp> #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp> @@ -175,21 +176,115 @@ template struct intersection_of_linestring_with_areal { #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) - template <typename Turn, typename Operation> - static inline void debug_follow(Turn const& turn, Operation op, - int index) + template <typename Turn, typename Operation> + static inline void debug_follow(Turn const& turn, Operation op, + int index) + { + std::cout << index + << " at " << op.seg_id + << " meth: " << method_char(turn.method) + << " op: " << operation_char(op.operation) + << " vis: " << visited_char(op.visited) + << " of: " << operation_char(turn.operations[0].operation) + << operation_char(turn.operations[1].operation) + << " " << geometry::wkt(turn.point) + << std::endl; + } + + template <typename Turn> + static inline void debug_turn(Turn const& t, bool non_crossing) + { + std::cout << "checking turn @" + << geometry::wkt(t.point) + << "; " << method_char(t.method) + << ":" << operation_char(t.operations[0].operation) + << "/" << operation_char(t.operations[1].operation) + << "; non-crossing? " + << std::boolalpha << non_crossing << std::noboolalpha + << std::endl; + } +#endif + + class is_crossing_turn + { + // return true is the operation is intersection or blocked + template <std::size_t Index, typename Turn> + static inline bool has_op_i_or_b(Turn const& t) { - std::cout << index - << " at " << op.seg_id - << " meth: " << method_char(turn.method) - << " op: " << operation_char(op.operation) - << " vis: " << visited_char(op.visited) - << " of: " << operation_char(turn.operations[0].operation) - << operation_char(turn.operations[1].operation) - << " " << geometry::wkt(turn.point) - << std::endl; + return + t.operations[Index].operation == overlay::operation_intersection + || + t.operations[Index].operation == overlay::operation_blocked; } + + template <typename Turn> + static inline bool has_method_crosses(Turn const& t) + { + return t.method == overlay::method_crosses; + } + + template <typename Turn> + static inline bool is_cc(Turn const& t) + { + return + (t.method == overlay::method_touch_interior + || + t.method == overlay::method_equal + || + t.method == overlay::method_collinear) + && + t.operations[0].operation == t.operations[1].operation + && + t.operations[0].operation == overlay::operation_continue + ; + } + + template <typename Turn> + static inline bool has_i_or_b_ops(Turn const& t) + { + return + (t.method == overlay::method_touch + || + t.method == overlay::method_touch_interior + || + t.method == overlay::method_collinear) + && + t.operations[1].operation != t.operations[0].operation + && + (has_op_i_or_b<0>(t) || has_op_i_or_b<1>(t)); + } + + public: + template <typename Turn> + static inline bool apply(Turn const& t) + { + bool const is_crossing + = has_method_crosses(t) || is_cc(t) || has_i_or_b_ops(t); +#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) + debug_turn(t, ! is_crossing); #endif + return is_crossing; + } + }; + + struct is_non_crossing_turn + { + template <typename Turn> + static inline bool apply(Turn const& t) + { + return ! is_crossing_turn::apply(t); + } + }; + + template <typename Turns> + static inline bool no_crossing_turns_or_empty(Turns const& turns) + { + return detail::check_iterator_range + < + is_non_crossing_turn, + true // allow an empty turns range + >::apply(boost::begin(turns), boost::end(turns)); + } template < @@ -212,7 +307,8 @@ struct intersection_of_linestring_with_areal LineStringOut, LineString, Areal, - OverlayType + OverlayType, + false // do not remove spikes for linear geometries > follower; typedef typename point_type<LineStringOut>::type point_type; @@ -231,7 +327,7 @@ struct intersection_of_linestring_with_areal detail::overlay::assign_null_policy >(linestring, areal, robust_policy, turns, policy); - if (turns.empty()) + if (no_crossing_turns_or_empty(turns)) { // No intersection points, it is either completely // inside (interior + borders) diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index baf9d4777d..6eb0b8864c 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -78,6 +78,11 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, && ! turn_info.both(operation_intersection) ; + if (! both_uu && turn_info.colocated) + { + skip = true; + } + for (typename boost::range_iterator<container_type const>::type op_it = boost::begin(turn_info.operations); op_it != boost::end(turn_info.operations); @@ -105,7 +110,7 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, template < - typename GeometryOut, overlay_type Direction, bool ReverseOut, + typename GeometryOut, overlay_type OverlayType, bool ReverseOut, typename Geometry1, typename Geometry2, typename OutputIterator > @@ -129,8 +134,8 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, // Union: return either of them // Intersection: return nothing // Difference: return first of them - if (Direction == overlay_intersection - || (Direction == overlay_difference && geometry::is_empty(geometry1))) + if (OverlayType == overlay_intersection + || (OverlayType == overlay_difference && geometry::is_empty(geometry1))) { return out; } @@ -143,7 +148,7 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, std::map<ring_identifier, ring_turn_info> empty; std::map<ring_identifier, properties> all_of_one_of_them; - select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them); + select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them); ring_container_type rings; assign_parents(geometry1, geometry2, rings, all_of_one_of_them); return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out); @@ -155,7 +160,7 @@ template typename Geometry1, typename Geometry2, bool Reverse1, bool Reverse2, bool ReverseOut, typename GeometryOut, - overlay_type Direction + overlay_type OverlayType > struct overlay { @@ -178,7 +183,7 @@ struct overlay { return return_if_one_input_is_empty < - GeometryOut, Direction, ReverseOut + GeometryOut, OverlayType, ReverseOut >(geometry1, geometry2, out); } @@ -211,8 +216,8 @@ std::cout << "get turns" << std::endl; std::cout << "enrich" << std::endl; #endif typename Strategy::side_strategy_type side_strategy; - geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points, - Direction == overlay_union + geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turn_points, + OverlayType == overlay_union ? geometry::detail::overlay::operation_union : geometry::detail::overlay::operation_intersection, geometry1, geometry2, @@ -229,7 +234,7 @@ std::cout << "traverse" << std::endl; traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply ( geometry1, geometry2, - Direction == overlay_union + OverlayType == overlay_union ? geometry::detail::overlay::operation_union : geometry::detail::overlay::operation_intersection, robust_policy, @@ -246,7 +251,7 @@ std::cout << "traverse" << std::endl; // Select all rings which are NOT touched by any intersection point std::map<ring_identifier, properties> selected_ring_properties; - select_rings<Direction>(geometry1, geometry2, turn_info_per_ring, + select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring, selected_ring_properties); // Add rings created during traversal diff --git a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp index 6ee32c17c0..8cabfb0d8d 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp @@ -25,7 +25,7 @@ namespace detail { namespace overlay template <typename Point, typename SegmentRatio> -struct traversal_turn_operation : public turn_operation<SegmentRatio> +struct traversal_turn_operation : public turn_operation<Point, SegmentRatio> { enrichment_info<Point> enriched; visit_info visited; diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index 803a164711..45e15d13d0 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -174,7 +174,17 @@ inline bool select_next_ip(operation_type operation, { return false; } + bool has_tp = false; + + typedef typename std::iterator_traits + < + Iterator + >::value_type operation_type; + + typename operation_type::comparable_distance_type + max_remaining_distance = 0; + selected = boost::end(turn.operations); for (Iterator it = boost::begin(turn.operations); it != boost::end(turn.operations); @@ -206,10 +216,24 @@ inline bool select_next_ip(operation_type operation, ) ) { + if (it->operation == operation_continue) + { + max_remaining_distance = it->remaining_distance; + } selected = it; debug_traverse(turn, *it, " Candidate"); has_tp = true; } + + if (it->operation == operation_continue && has_tp) + { + if (it->remaining_distance > max_remaining_distance) + { + max_remaining_distance = it->remaining_distance; + selected = it; + debug_traverse(turn, *it, " Candidate override"); + } + } } if (has_tp) diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index 26669a4b1f..1ac77d5796 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -12,6 +12,7 @@ #include <boost/array.hpp> +#include <boost/geometry/core/coordinate_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> namespace boost { namespace geometry @@ -54,15 +55,19 @@ enum method_type The class is to be included in the turn_info class, either direct or a derived or similar class with more (e.g. enrichment) information. */ -template <typename SegmentRatio> +template <typename Point, typename SegmentRatio> struct turn_operation { operation_type operation; segment_identifier seg_id; SegmentRatio fraction; + typedef typename coordinate_type<Point>::type comparable_distance_type; + comparable_distance_type remaining_distance; + inline turn_operation() : operation(operation_none) + , remaining_distance(0) {} }; @@ -80,7 +85,7 @@ template < typename Point, typename SegmentRatio, - typename Operation = turn_operation<SegmentRatio>, + typename Operation = turn_operation<Point, SegmentRatio>, typename Container = boost::array<Operation, 2> > struct turn_info @@ -93,6 +98,7 @@ struct turn_info method_type method; bool discarded; bool selectable_start; // Can be used as starting-turn in traverse + bool colocated; Container operations; @@ -101,6 +107,7 @@ struct turn_info : method(method_none) , discarded(false) , selectable_start(true) + , colocated(false) {} inline bool both(operation_type type) const |