diff options
| author | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-03-21 15:45:20 +0900 |
|---|---|---|
| committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-03-21 15:46:37 +0900 |
| commit | 733b5d5ae2c5d625211e2985ac25728ac3f54883 (patch) | |
| tree | a5b214744b256f07e1dc2bd7273035a7808c659f /boost/geometry/algorithms/detail/overlay | |
| parent | 08c1e93fa36a49f49325a07fe91ff92c964c2b6c (diff) | |
| download | boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.gz boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.bz2 boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.zip | |
Imported Upstream version 1.58.0upstream/1.58.0
Change-Id: If0072143aa26874812e0db6872e1efb10a3e5e94
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
18 files changed, 573 insertions, 480 deletions
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 d44db17ad3..285edfdd6c 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 @@ -20,6 +20,7 @@ #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp> #include <boost/geometry/algorithms/detail/equals/point_point.hpp> +#include <boost/geometry/util/condition.hpp> #include <boost/geometry/util/range.hpp> @@ -42,7 +43,7 @@ inline bool points_equal_or_close(Point1 const& point1, return true; } - if (! RobustPolicy::enabled) + if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled)) { return false; } @@ -127,7 +128,7 @@ inline void clean_closing_dups_and_spikes(Range& range, iterator_type first = boost::begin(range); iterator_type second = first + 1; iterator_type ultimate = boost::end(range) - 1; - if (closed) + if (BOOST_GEOMETRY_CONDITION(closed)) { ultimate--; } @@ -137,7 +138,7 @@ inline void clean_closing_dups_and_spikes(Range& range, if (point_is_spike_or_equal(*second, *ultimate, *first, robust_policy)) { range::erase(range, first); - if (closed) + if (BOOST_GEOMETRY_CONDITION(closed)) { // Remove closing last point range::resize(range, boost::size(range) - 1); diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 67b48cc471..178f3825d7 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -18,11 +18,6 @@ #include <boost/geometry/geometries/box.hpp> -#ifdef BOOST_GEOMETRY_TIME_OVERLAY -# include <boost/timer.hpp> -#endif - - namespace boost { namespace geometry { @@ -186,11 +181,6 @@ inline void assign_parents(Geometry1 const& geometry1, typedef std::vector<helper> vector_type; typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type; -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - boost::timer timer; -#endif - - std::size_t count_total = ring_map.size(); std::size_t count_positive = 0; std::size_t index_positive = 0; // only used if count_positive>0 @@ -226,10 +216,6 @@ inline void assign_parents(Geometry1 const& geometry1, } } -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << " ap: created helper vector: " << timer.elapsed() << std::endl; -#endif - if (! check_for_orientation) { if (count_positive == count_total) @@ -272,11 +258,6 @@ inline void assign_parents(Geometry1 const& geometry1, < box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box >::apply(vector, visitor); - -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << " ap: quadradic loop: " << timer.elapsed() << std::endl; - std::cout << " ap: check_for_orientation " << check_for_orientation << std::endl; -#endif } if (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 20a6d7f48d..13e0a5a51e 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp @@ -11,6 +11,7 @@ #include <boost/array.hpp> +#include <boost/assert.hpp> #include <boost/mpl/assert.hpp> #include <boost/range.hpp> @@ -21,8 +22,7 @@ #include <boost/geometry/algorithms/convert.hpp> #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/util/range.hpp> -#include <boost/geometry/views/closeable_view.hpp> -#include <boost/geometry/views/reversible_view.hpp> +#include <boost/geometry/views/detail/normalized_view.hpp> namespace boost { namespace geometry @@ -37,41 +37,24 @@ namespace detail { namespace copy_segments template <typename Range, bool Reverse, typename SegmentIdentifier, typename PointOut> struct copy_segment_point_range { - typedef typename closeable_view - < - Range const, - closure<Range>::value - >::type cview_type; - - typedef typename reversible_view - < - cview_type const, - Reverse ? iterate_reverse : iterate_forward - >::type rview_type; - static inline bool apply(Range const& range, SegmentIdentifier const& seg_id, bool second, PointOut& point) { + detail::normalized_view<Range const> view(range); + + signed_index_type const n = boost::size(view); signed_index_type index = seg_id.segment_index; if (second) { index++; - if (index >= int(boost::size(range))) + if (index >= n) { index = 0; } } - // Exception? - if (index >= int(boost::size(range))) - { - return false; - } - - cview_type cview(range); - rview_type view(cview); - + BOOST_ASSERT(index >= 0 && index < n); geometry::convert(*(boost::begin(view) + index), point); return true; @@ -323,6 +306,8 @@ inline bool copy_segment_point(Geometry1 const& geometry1, Geometry2 const& geom concept::check<Geometry1 const>(); concept::check<Geometry2 const>(); + BOOST_ASSERT(seg_id.source_index == 0 || seg_id.source_index == 1); + if (seg_id.source_index == 0) { return dispatch::copy_segment_point diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 9484479b45..7ed93f542a 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -56,13 +56,13 @@ struct indexed_turn_operation TurnOperation const* subject; inline indexed_turn_operation(std::size_t ti, std::size_t oi, - TurnOperation const& s, + TurnOperation const& sub, segment_identifier const& oid) : turn_index(ti) , operation_index(oi) , discarded(false) , other_seg_id(&oid) - , subject(&s) + , subject(boost::addressof(sub)) {} }; @@ -114,6 +114,12 @@ private : typedef typename geometry::point_type<Geometry1>::type point_type; + inline bool default_order(Indexed const& left, Indexed const& right) const + { + // We've nothing to sort on. Take the indexes + return left.turn_index < right.turn_index; + } + inline bool consider_relative_order(Indexed const& left, Indexed const& right) const { @@ -148,7 +154,12 @@ private : // 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 - return side_rj_s < side_sj_r; + if (side_rj_s != side_sj_r) + { + return side_rj_s < side_sj_r; + } + + return default_order(left, right); } public : @@ -157,30 +168,32 @@ public : // but to the "indexed_turn_operation" inline bool operator()(Indexed const& left, Indexed const& right) const { - segment_identifier const& sl = left.subject->seg_id; - segment_identifier const& sr = right.subject->seg_id; + if (! (left.subject->seg_id == right.subject->seg_id)) + { + return left.subject->seg_id < right.subject->seg_id; + } + + // Both left and right are located on the SAME segment. - if (sl == sr) + if (! (left.subject->fraction == right.subject->fraction)) { - // Both left and right are located on the SAME segment. - if (left.subject->fraction == right.subject->fraction) - { - // First check "real" intersection (crosses) - // -> distance zero due to precision, solve it by sorting - if (m_turn_points[left.turn_index].method == method_crosses - && m_turn_points[right.turn_index].method == method_crosses) - { - return consider_relative_order(left, right); - } + return left.subject->fraction < right.subject->fraction; + } - // If that is not the case, cluster it later on. - // Indicate that this is necessary. - *m_clustered = true; - } + + // First check "real" intersection (crosses) + // -> distance zero due to precision, solve it by sorting + if (m_turn_points[left.turn_index].method == method_crosses + && m_turn_points[right.turn_index].method == method_crosses) + { + return consider_relative_order(left, right); } - return sl == sr - ? left.subject->fraction < right.subject->fraction - : sl < sr; + + // If that is not the case, cluster it later on. + // Indicate that this is necessary. + *m_clustered = true; + + return default_order(left, right); } }; diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp index 85378e08b0..7bcc0b951e 100644 --- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp @@ -35,6 +35,23 @@ 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 @@ -304,7 +321,14 @@ public: oit); } - BOOST_ASSERT( enter_count == 0 ); +#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) + if (enter_count != 0) + { + throw inconsistent_turns_exception(); + } +#else + BOOST_ASSERT(enter_count == 0); +#endif return process_end(entered, linestring, current_segment_id, current_piece, diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 240b6de036..b3b1a06f68 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -11,6 +16,8 @@ #include <boost/assert.hpp> +#include <boost/core/ignore_unused.hpp> + #include <boost/geometry/core/access.hpp> #include <boost/geometry/strategies/intersection.hpp> @@ -104,17 +111,19 @@ struct base_turn_handler template <typename TurnInfo, typename IntersectionInfo> static inline void assign_point(TurnInfo& ti, method_type method, - IntersectionInfo const& info, int index) + IntersectionInfo const& info, unsigned int index) { ti.method = method; - BOOST_ASSERT(index >= 0 && unsigned(index) < info.count); // TODO remove this + + BOOST_ASSERT(index < info.count); + geometry::convert(info.intersections[index], ti.point); ti.operations[0].fraction = info.fractions[index].robust_ra; ti.operations[1].fraction = info.fractions[index].robust_rb; } template <typename IntersectionInfo> - static inline int non_opposite_to_index(IntersectionInfo const& info) + static inline unsigned int non_opposite_to_index(IntersectionInfo const& info) { return info.fractions[0].robust_rb < info.fractions[1].robust_rb ? 1 : 0; @@ -132,7 +141,7 @@ struct touch_interior : public base_turn_handler // Index: 0, P is the interior, Q is touching and vice versa template < - int Index, + unsigned int Index, typename Point1, typename Point2, typename IntersectionInfo, @@ -155,8 +164,9 @@ struct touch_interior : public base_turn_handler // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR // and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i - static int const index_p = Index; - static int const index_q = 1 - Index; + BOOST_STATIC_ASSERT(Index <= 1); + static unsigned int const index_p = Index; + static unsigned int const index_q = 1 - Index; int const side_qi_p = dir_info.sides.template get<index_q, 0>(); int const side_qk_p = side.qk_wrt_p1(); @@ -166,7 +176,7 @@ struct touch_interior : public base_turn_handler // Q crosses P from left->right or from right->left (test "ML1") // Union: folow P (left->right) or Q (right->left) // Intersection: other turn - int index = side_qk_p == -1 ? index_p : index_q; + unsigned int index = side_qk_p == -1 ? index_p : index_q; ti.operations[index].operation = operation_union; ti.operations[1 - index].operation = operation_intersection; return; @@ -193,7 +203,7 @@ struct touch_interior : public base_turn_handler // or Q turns right on the right side of P (test "MR2") // Union: take left turn (Q if Q turns left, P if Q turns right) // Intersection: other turn - int index = side_qk_q == 1 ? index_q : index_p; + unsigned int index = side_qk_q == 1 ? index_q : index_p; ti.operations[index].operation = operation_union; ti.operations[1 - index].operation = operation_intersection; } @@ -215,10 +225,10 @@ struct touch_interior : public base_turn_handler // Opposite direction, which is never travelled. // If Q turns left, P continues for intersection // If Q turns right, P continues for union - ti.operations[Index].operation = side_qk_q == 1 + ti.operations[index_p].operation = side_qk_q == 1 ? operation_intersection : operation_union; - ti.operations[1 - Index].operation = operation_blocked; + ti.operations[index_q].operation = operation_blocked; } } else @@ -503,27 +513,25 @@ struct equal_opposite : public base_turn_handler typename Point1, typename Point2, typename OutputIterator, - typename IntersectionInfo, - typename DirInfo + typename IntersectionInfo > static inline void apply(Point1 const& pi, Point2 const& qi, /* by value: */ TurnInfo tp, OutputIterator& out, - IntersectionInfo const& intersection_info, - DirInfo const& dir_info) + IntersectionInfo const& intersection_info) { // For equal-opposite segments, normally don't do anything. if (AssignPolicy::include_opposite) { tp.method = method_equal; - for (int i = 0; i < 2; i++) + for (unsigned int i = 0; i < 2; i++) { tp.operations[i].operation = operation_opposite; } - for (unsigned int i = 0; i < intersection_info.count; i++) + for (unsigned int i = 0; i < intersection_info.i_info().count; i++) { - assign_point(tp, method_none, intersection_info, i); - AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + assign_point(tp, method_none, intersection_info.i_info(), i); + AssignPolicy::apply(tp, pi, qi, intersection_info); *out++ = tp; } } @@ -653,7 +661,7 @@ private : template < - int Index, + unsigned int Index, typename Point1, typename Point2, typename IntersectionInfo @@ -663,8 +671,9 @@ private : Point2 const& , Point2 const& , int side_rk_s, TurnInfo& tp, IntersectionInfo const& intersection_info) { - boost::ignore_unused_variable_warning(handle_robustness); - boost::ignore_unused_variable_warning(side_rk_s); + BOOST_STATIC_ASSERT(Index <= 1); + + boost::ignore_unused(handle_robustness, side_rk_s); operation_type blocked = operation_blocked; switch(side_rk_r) @@ -715,7 +724,6 @@ public: typename Point2, typename OutputIterator, typename IntersectionInfo, - typename DirInfo, typename SidePolicy > static inline void apply( @@ -727,10 +735,9 @@ public: OutputIterator& out, IntersectionInfo const& intersection_info, - DirInfo const& dir_info, SidePolicy const& side) { - apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, dir_info, side, empty_transformer); + apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, side, empty_transformer); } public: @@ -740,7 +747,6 @@ public: typename Point2, typename OutputIterator, typename IntersectionInfo, - typename DirInfo, typename SidePolicy, typename TurnTransformer > @@ -752,50 +758,52 @@ public: TurnInfo const& tp_model, OutputIterator& out, - IntersectionInfo const& intersection_info, - DirInfo const& dir_info, + IntersectionInfo const& info, SidePolicy const& side, TurnTransformer turn_transformer, bool const is_pk_valid = true, bool const is_qk_valid = true) { TurnInfo tp = tp_model; + int const p_arrival = info.d_info().arrival[0]; + int const q_arrival = info.d_info().arrival[1]; + // If P arrives within Q, there is a turn dependent on P - if ( dir_info.arrival[0] == 1 + if ( p_arrival == 1 && is_pk_valid - && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, intersection_info) ) + && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, info.i_info()) ) { turn_transformer(tp); - AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + AssignPolicy::apply(tp, pi, qi, info); *out++ = tp; } // If Q arrives within P, there is a turn dependent on Q - if ( dir_info.arrival[1] == 1 + if ( q_arrival == 1 && is_qk_valid - && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, intersection_info) ) + && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, info.i_info()) ) { turn_transformer(tp); - AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + AssignPolicy::apply(tp, pi, qi, info); *out++ = tp; } if (AssignPolicy::include_opposite) { // Handle cases not yet handled above - if ((dir_info.arrival[1] == -1 && dir_info.arrival[0] == 0) - || (dir_info.arrival[0] == -1 && dir_info.arrival[1] == 0)) + if ((q_arrival == -1 && p_arrival == 0) + || (p_arrival == -1 && q_arrival == 0)) { - for (int i = 0; i < 2; i++) + for (unsigned int i = 0; i < 2; i++) { tp.operations[i].operation = operation_opposite; } - for (unsigned int i = 0; i < intersection_info.count; i++) + for (unsigned int i = 0; i < info.i_info().count; i++) { - assign_point(tp, method_collinear, intersection_info, i); - AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + assign_point(tp, method_collinear, info.i_info(), i); + AssignPolicy::apply(tp, pi, qi, info); *out++ = tp; } } @@ -833,7 +841,7 @@ struct crosses : public base_turn_handler // Intersection: take Q // Otherwise: vice versa int const side_qi_p1 = dir_info.sides.template get<1, 0>(); - int const index = side_qi_p1 == 1 ? 0 : 1; + unsigned int const index = side_qi_p1 == 1 ? 0 : 1; ti.operations[index].operation = operation_union; ti.operations[1 - index].operation = operation_intersection; } @@ -867,10 +875,9 @@ struct assign_null_policy typename Info, typename Point1, typename Point2, - typename IntersectionInfo, - typename DirInfo + typename IntersectionInfo > - static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&) + static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&) {} }; @@ -933,7 +940,7 @@ struct get_turn_info && inters.i_info().count > 0) { only_convert::apply(tp, inters.i_info()); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -968,7 +975,7 @@ struct get_turn_info tp, inters.i_info(), inters.d_info(), swapped_side_calc); } - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -976,7 +983,7 @@ struct get_turn_info { crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, tp, inters.i_info(), inters.d_info()); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -985,7 +992,7 @@ struct get_turn_info // Both touch (both arrive there) touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, tp, inters.i_info(), inters.d_info(), inters.sides()); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -997,7 +1004,7 @@ struct get_turn_info // or collinear-and-ending at intersection point equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, tp, inters.i_info(), inters.d_info(), inters.sides()); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } else @@ -1007,7 +1014,7 @@ struct get_turn_info TurnInfo, AssignPolicy >::apply(pi, qi, - tp, out, inters.i_info(), inters.d_info()); + tp, out, inters); } } break; @@ -1032,7 +1039,7 @@ struct get_turn_info tp, inters.i_info(), inters.d_info(), inters.sides()); } - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } else @@ -1042,7 +1049,7 @@ struct get_turn_info TurnInfo, AssignPolicy >::apply(pi, pj, pk, qi, qj, qk, - tp, out, inters.i_info(), inters.d_info(), inters.sides()); + tp, out, inters, inters.sides()); } } break; @@ -1052,7 +1059,7 @@ struct get_turn_info if (AssignPolicy::include_degenerate) { only_convert::apply(tp, inters.i_info()); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } } diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp index ca1b9d9d0c..4a3cacbedd 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp @@ -290,7 +290,7 @@ struct get_turn_info_for_endpoint linear_intersections::ip_info const& ip_info, TurnInfo const& tp_model, IntersectionInfo const& inters, - int ip_index, + unsigned int ip_index, OutputIterator out) { #ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR @@ -396,7 +396,7 @@ struct get_turn_info_for_endpoint RobustPoint2 const& ri2, RobustPoint2 const& rj2, RobustPoint2 const& rk2, bool first1, bool last1, bool first2, bool last2, bool ip_i2, bool ip_j2, TurnInfo const& tp_model, - IntersectionInfo const& inters, int ip_index, + IntersectionInfo const& inters, unsigned int ip_index, operation_type & op1, operation_type & op2) { boost::ignore_unused_variable_warning(i2); @@ -535,7 +535,7 @@ struct get_turn_info_for_endpoint typename OutputIterator> static inline void assign(Point1 const& pi, Point2 const& qi, IntersectionResult const& result, - int ip_index, + unsigned int ip_index, method_type method, operation_type op0, operation_type op1, turn_position pos0, turn_position pos1, @@ -585,7 +585,9 @@ struct get_turn_info_for_endpoint } } - AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); + // TODO: this should get an intersection_info, which is unavailable here + // Because the assign_null policy accepts any structure, we pass the result instead for now + AssignPolicy::apply(tp, pi, qi, result); *out++ = tp; } 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 eead0d719b..e0d75108b9 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -2,8 +2,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2013, 2014. -// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015 Oracle and/or its affiliates. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp index 873567bbf5..71946543ee 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp @@ -2,18 +2,20 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2013, 2014. -// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP +#include <boost/geometry/util/condition.hpp> + #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp> @@ -28,6 +30,8 @@ namespace detail { namespace overlay { template<typename AssignPolicy> struct get_turn_info_linear_areal { + // Currently only Linear spikes are handled + // Areal spikes are ignored static const bool handle_spikes = true; template @@ -122,7 +126,7 @@ struct get_turn_info_linear_areal calculate_spike_operation(tp.operations[0].operation, inters, is_p_last); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } @@ -135,7 +139,7 @@ struct get_turn_info_linear_areal replace_operations_i(tp.operations[0].operation, tp.operations[1].operation); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -220,9 +224,9 @@ struct get_turn_info_linear_areal inters, is_p_last); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ignore_spike || ! append_opposite_spikes<append_touches>( // for 'i' or 'c' i??? tp, inters, is_p_last, is_q_last, out) ) @@ -256,10 +260,10 @@ struct get_turn_info_linear_areal transformer(tp); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); // conditionally handle spikes - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, method_touch, append_equal, out) ) { @@ -273,7 +277,7 @@ struct get_turn_info_linear_areal TurnInfo, AssignPolicy >::apply(pi, qi, - tp, out, inters.i_info(), inters.d_info()); + tp, out, inters); } } } @@ -319,10 +323,10 @@ struct get_turn_info_linear_areal transformer(tp); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); // conditionally handle spikes - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, method_replace, version, out) ) { @@ -336,7 +340,7 @@ struct get_turn_info_linear_areal turn_transformer_ec<false> transformer(method_touch_interior); // conditionally handle spikes - if ( handle_spikes ) + if ( BOOST_GEOMETRY_CONDITION(handle_spikes) ) { append_opposite_spikes<append_collinear_opposite>( tp, inters, is_p_last, is_q_last, out); @@ -351,8 +355,9 @@ struct get_turn_info_linear_areal TurnInfo, AssignPolicy >::apply(pi, pj, pk, qi, qj, qk, - tp, out, inters.i_info(), inters.d_info(), - inters.sides(), transformer); + tp, out, inters, + inters.sides(), transformer, + !is_p_last, true); // qk is always valid } } } @@ -360,7 +365,7 @@ struct get_turn_info_linear_areal case '0' : { // degenerate points - if (AssignPolicy::include_degenerate) + if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) ) { only_convert::apply(tp, inters.i_info()); @@ -376,7 +381,7 @@ struct get_turn_info_linear_areal } // tp.operations[1].position = position_middle; - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } } @@ -408,20 +413,37 @@ struct get_turn_info_linear_areal if ( is_p_spike ) { - bool going_in = false, going_out = false; - int const pk_q1 = inters.sides().pk_wrt_q1(); - int const pk_q2 = inters.sides().pk_wrt_q2(); + + bool going_in = pk_q1 < 0; // Pk on the right + bool going_out = pk_q1 > 0; // Pk on the left - if ( inters.sides().qk_wrt_q1() <= 0 ) // Q turning R or C + int const qk_q1 = inters.sides().qk_wrt_q1(); + + // special cases + if ( qk_q1 < 0 ) // Q turning R { - going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both - going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them + // spike on the edge point + // if it's already known that the spike is going out this musn't be checked + if ( ! going_out + && equals::equals_point_point(inters.rpj(), inters.rqj()) ) + { + int const pk_q2 = inters.sides().pk_wrt_q2(); + going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both + going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them + } } - else + else if ( qk_q1 > 0 ) // Q turning L { - going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them - going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both + // spike on the edge point + // if it's already known that the spike is going in this musn't be checked + if ( ! going_in + && equals::equals_point_point(inters.rpj(), inters.rqj()) ) + { + int const pk_q2 = inters.sides().pk_wrt_q2(); + going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them + going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both + } } if ( going_in ) @@ -461,10 +483,16 @@ struct get_turn_info_linear_areal && inters.is_spike_p(); // TODO: throw an exception for spike in Areal? - /*bool is_q_spike = tp.operations[1].operation == spike_op - && ! is_q_last - && inters.is_spike_q();*/ + /*bool is_q_spike = tp.operations[1].operation == operation_continue + && inters.is_spike_q(); + // both are collinear spikes on the same IP, we can just follow both + if ( is_p_spike && is_q_spike ) + { + return false; + } + // spike on Linear - it's turning back on the boundary of Areal + else*/ if ( is_p_spike ) { tp.method = method; @@ -477,7 +505,18 @@ struct get_turn_info_linear_areal return true; } - + // spike on Areal - Linear is going outside + /*else if ( is_q_spike ) + { + tp.method = method; + tp.operations[0].operation = operation_union; + tp.operations[1].operation = operation_continue; + *out++ = tp; + *out++ = tp; + + return true; + }*/ + return false; } @@ -492,48 +531,71 @@ struct get_turn_info_linear_areal bool is_p_last, bool /*is_q_last*/, OutIt out) { - bool is_p_spike = ( Version == append_touches ? + static const bool is_version_touches = (Version == append_touches); + + bool is_p_spike = ( is_version_touches ? ( tp.operations[0].operation == operation_continue || tp.operations[0].operation == operation_intersection ) : // i ??? true ) && ! is_p_last && inters.is_spike_p(); + // TODO: throw an exception for spike in Areal? - /*bool is_q_spike = ( Version == append_touches ? - ( tp.operations[1].operation == operation_continue - || tp.operations[1].operation == operation_intersection ) : - true ) - && ! is_q_last - && inters.is_spike_q();*/ + /*bool is_q_spike = ( ( Version == append_touches + && tp.operations[1].operation == operation_continue ) + || ( Version == append_collinear_opposite + && tp.operations[1].operation == operation_none ) ) + && inters.is_spike_q(); - if ( is_p_spike && ( Version == append_touches || inters.d_info().arrival[0] == 1 ) ) + if ( is_p_spike && is_q_spike ) { - if ( Version == append_touches ) - { - tp.operations[0].is_collinear = true; - //tp.operations[1].is_collinear = false; - tp.method = method_touch; - } - else + // u/u or nothing? + return false; + } + else*/ + if ( is_p_spike ) + { + if ( BOOST_GEOMETRY_CONDITION(is_version_touches) + || inters.d_info().arrival[0] == 1 ) { - tp.operations[0].is_collinear = true; - //tp.operations[1].is_collinear = false; - - BOOST_ASSERT(inters.i_info().count > 1); - base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); + if ( BOOST_GEOMETRY_CONDITION(is_version_touches) ) + { + tp.operations[0].is_collinear = true; + //tp.operations[1].is_collinear = false; + tp.method = method_touch; + } + else + { + tp.operations[0].is_collinear = true; + //tp.operations[1].is_collinear = false; - AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters.i_info(), inters.d_info()); - } + BOOST_ASSERT(inters.i_info().count > 1); + base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); - tp.operations[0].operation = operation_blocked; + AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); + } + + tp.operations[0].operation = operation_blocked; + tp.operations[1].operation = operation_continue; // boundary + *out++ = tp; + tp.operations[0].operation = operation_continue; // boundary + //tp.operations[1].operation = operation_continue; // boundary + *out++ = tp; + + return true; + } + } + /*else if ( is_q_spike ) + { + tp.operations[0].is_collinear = true; + tp.method = is_version_touches ? method_touch : method_touch_interior; + tp.operations[0].operation = operation_continue; tp.operations[1].operation = operation_continue; // boundary *out++ = tp; - tp.operations[0].operation = operation_continue; // boundary - //tp.operations[1].operation = operation_continue; // boundary *out++ = tp; return true; - } + }*/ return false; } @@ -587,7 +649,7 @@ struct get_turn_info_linear_areal operation_type & op1 = turn.operations[1].operation; // NOTE: probably only if methods are WRT IPs, not segments! - if ( IsFront + if ( BOOST_GEOMETRY_CONDITION(IsFront) || op0 == operation_intersection || op0 == operation_union || op1 == operation_intersection || op1 == operation_union ) { @@ -666,7 +728,9 @@ struct get_turn_info_linear_areal // ANALYSE AND ASSIGN FIRST // IP on the first point of Linear Geometry - if ( EnableFirst && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication + bool was_first_point_handled = false; + if ( BOOST_GEOMETRY_CONDITION(EnableFirst) + && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication { TurnInfo tp = tp_model; tp.operations[0].position = position_front; @@ -735,14 +799,16 @@ struct get_turn_info_linear_areal // here is_p_first_ip == true tp.operations[0].is_collinear = false; - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; + + was_first_point_handled = true; } // ANALYSE AND ASSIGN LAST // IP on the last point of Linear Geometry - if ( EnableLast + if ( BOOST_GEOMETRY_CONDITION(EnableLast) && is_p_last && ( ip_count > 1 ? (ip1.is_pj && !ip1.is_qi) : (ip0.is_pj && !ip0.is_qi) ) ) // prevents duplication { @@ -783,13 +849,14 @@ struct get_turn_info_linear_areal // equals<> or collinear<> will assign the second point, // we'd like to assign the first one - int ip_index = ip_count > 1 ? 1 : 0; + unsigned int ip_index = ip_count > 1 ? 1 : 0; base_turn_handler::assign_point(tp, tp.method, inters.i_info(), ip_index); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; - return true; + // don't ignore the first IP if the segment is opposite + return !( opposite && ip_count > 1 ) || was_first_point_handled; } // don't ignore anything for now diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp index 4f0384877f..1ec88e54a0 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp @@ -2,8 +2,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2013, 2014. -// Modifications copyright (c) 2013-2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015 Oracle and/or its affiliates. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -17,6 +17,8 @@ #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp> +#include <boost/geometry/util/condition.hpp> + namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DETAIL @@ -120,7 +122,7 @@ struct get_turn_info_linear_linear tp.operations[0].operation, tp.operations[1].operation); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } } @@ -132,7 +134,7 @@ struct get_turn_info_linear_linear replace_operations_i(tp.operations[0].operation, tp.operations[1].operation); - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; @@ -260,9 +262,9 @@ struct get_turn_info_linear_linear tp.operations[1].operation); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ! append_opposite_spikes<append_touches>(tp, inters, is_p_last, is_q_last, out) ) @@ -293,18 +295,24 @@ struct get_turn_info_linear_linear equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, tp, inters.i_info(), inters.d_info(), inters.sides()); + operation_type spike_op + = ( tp.operations[0].operation != operation_continue + || tp.operations[1].operation != operation_continue ) ? + operation_union : + operation_continue; + // transform turn turn_transformer_ec transformer(method_touch); transformer(tp); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); // conditionally handle spikes - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, - method_touch, operation_union, + method_touch, spike_op, out) ) { *out++ = tp; // no spikes @@ -318,7 +326,7 @@ struct get_turn_info_linear_linear < TurnInfo, AssignPolicy - >::apply(pi, qi, tp, out, inters.i_info(), inters.d_info()); + >::apply(pi, qi, tp, out, inters); } } } @@ -351,7 +359,11 @@ struct get_turn_info_linear_linear tp, inters.i_info(), inters.d_info(), inters.sides()); method_replace = method_touch; - spike_op = operation_union; + if ( tp.operations[0].operation != operation_continue + || tp.operations[1].operation != operation_continue ) + { + spike_op = operation_union; + } } else { @@ -367,10 +379,10 @@ struct get_turn_info_linear_linear transformer(tp); // TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); // conditionally handle spikes - if ( ! handle_spikes + if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, method_replace, spike_op, @@ -386,7 +398,7 @@ struct get_turn_info_linear_linear turn_transformer_ec transformer(method_touch_interior); // conditionally handle spikes - if ( handle_spikes ) + if ( BOOST_GEOMETRY_CONDITION(handle_spikes) ) { append_opposite_spikes<append_collinear_opposite>(tp, inters, is_p_last, is_q_last, @@ -402,7 +414,7 @@ struct get_turn_info_linear_linear TurnInfo, AssignPolicy >::apply(pi, pj, pk, qi, qj, qk, - tp, out, inters.i_info(), inters.d_info(), inters.sides(), + tp, out, inters, inters.sides(), transformer, !is_p_last, !is_q_last); } } @@ -411,7 +423,7 @@ struct get_turn_info_linear_linear case '0' : { // degenerate points - if (AssignPolicy::include_degenerate) + if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) ) { only_convert::apply(tp, inters.i_info()); @@ -437,7 +449,7 @@ struct get_turn_info_linear_linear tp.operations[1].position = position_back; } - AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } } @@ -478,6 +490,14 @@ struct get_turn_info_linear_linear if ( is_p_spike && is_q_spike ) { + if ( tp.method == method_equal + && tp.operations[0].operation == operation_continue + && tp.operations[1].operation == operation_continue ) + { + // treat both non-opposite collinear spikes as no-spikes + return false; + } + tp.method = method; tp.operations[0].operation = operation_blocked; tp.operations[1].operation = operation_blocked; @@ -527,13 +547,15 @@ struct get_turn_info_linear_linear bool is_p_last, bool is_q_last, OutIt out) { - bool is_p_spike = ( Version == append_touches ? + static const bool is_version_touches = (Version == append_touches); + + bool is_p_spike = ( is_version_touches ? ( tp.operations[0].operation == operation_continue || tp.operations[0].operation == operation_intersection ) : true ) && ! is_p_last && inters.is_spike_p(); - bool is_q_spike = ( Version == append_touches ? + bool is_q_spike = ( is_version_touches ? ( tp.operations[1].operation == operation_continue || tp.operations[1].operation == operation_intersection ) : true ) @@ -542,9 +564,11 @@ struct get_turn_info_linear_linear bool res = false; - if ( is_p_spike && ( Version == append_touches || inters.d_info().arrival[0] == 1 ) ) + if ( is_p_spike + && ( BOOST_GEOMETRY_CONDITION(is_version_touches) + || inters.d_info().arrival[0] == 1 ) ) { - if ( Version == append_touches ) + if ( BOOST_GEOMETRY_CONDITION(is_version_touches) ) { tp.operations[0].is_collinear = true; tp.operations[1].is_collinear = false; @@ -560,8 +584,7 @@ struct get_turn_info_linear_linear base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); - AssignPolicy::apply(tp, inters.pi(), inters.qi(), - inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); } tp.operations[0].operation = operation_blocked; @@ -574,9 +597,11 @@ struct get_turn_info_linear_linear res = true; } - if ( is_q_spike && ( Version == append_touches || inters.d_info().arrival[1] == 1 ) ) + if ( is_q_spike + && ( BOOST_GEOMETRY_CONDITION(is_version_touches) + || inters.d_info().arrival[1] == 1 ) ) { - if ( Version == append_touches ) + if ( BOOST_GEOMETRY_CONDITION(is_version_touches) ) { tp.operations[0].is_collinear = false; tp.operations[1].is_collinear = true; @@ -591,8 +616,7 @@ struct get_turn_info_linear_linear base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 0); - AssignPolicy::apply(tp, inters.pi(), inters.qi(), - inters.i_info(), inters.d_info()); + AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); } tp.operations[0].operation = operation_intersection; diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index a96538c43a..a5d8f3f023 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -54,6 +54,7 @@ #include <boost/geometry/algorithms/detail/interior_iterator.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> #include <boost/geometry/algorithms/detail/recalculate.hpp> +#include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp> @@ -62,8 +63,7 @@ #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp> #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> - -#include <boost/geometry/algorithms/expand.hpp> +#include <boost/geometry/algorithms/detail/sections/section_functions.hpp> #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION # include <sstream> @@ -229,7 +229,7 @@ public : // section 2: [--------------] // section 1: |----|---|---|---|---| for (prev1 = it1++, next1++; - it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy); + it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy); ++prev1, ++it1, ++index1, ++next1, ++ndi1) { ever_circling_iterator<range1_iterator> nd_next1( @@ -247,7 +247,7 @@ public : next2++; for (prev2 = it2++, next2++; - it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy); + it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy); ++prev2, ++it2, ++index2, ++next2, ++ndi2) { bool skip = same_source; @@ -299,8 +299,8 @@ public : if (InterruptPolicy::enabled) { if (interrupt_policy.apply( - std::make_pair(boost::begin(turns) + size_before, - boost::end(turns)))) + std::make_pair(range::pos(turns, size_before), + boost::end(turns)))) { return false; } @@ -318,25 +318,6 @@ private : typedef typename model::referring_segment<point1_type const> segment1_type; typedef typename model::referring_segment<point2_type const> segment2_type; - - template <size_t Dim, typename Point, typename Box, typename RobustPolicy> - static inline bool preceding(int dir, Point const& point, Box const& box, RobustPolicy const& robust_policy) - { - typename robust_point_type<Point, RobustPolicy>::type robust_point; - geometry::recalculate(robust_point, point, robust_policy); - return (dir == 1 && get<Dim>(robust_point) < get<min_corner, Dim>(box)) - || (dir == -1 && get<Dim>(robust_point) > get<max_corner, Dim>(box)); - } - - template <size_t Dim, typename Point, typename Box, typename RobustPolicy> - static inline bool exceeding(int dir, Point const& point, Box const& box, RobustPolicy const& robust_policy) - { - typename robust_point_type<Point, RobustPolicy>::type robust_point; - geometry::recalculate(robust_point, point, robust_policy); - return (dir == 1 && get<Dim>(robust_point) > get<max_corner, Dim>(box)) - || (dir == -1 && get<Dim>(robust_point) < get<min_corner, Dim>(box)); - } - template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy> static inline void advance_to_non_duplicate_next(Iterator& next, RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy) @@ -387,7 +368,7 @@ private : // Mimic section-iterator: // Skip to point such that section interects other box prev = it++; - for(; it != end && preceding<0>(dir, *it, other_bounding_box, robust_policy); + for(; it != end && detail::section::preceding<0>(dir, *it, other_bounding_box, robust_policy); prev = it++, index++, ndi++) {} // Go back one step because we want to start completely preceding @@ -395,24 +376,6 @@ private : } }; -struct get_section_box -{ - template <typename Box, typename InputItem> - static inline void apply(Box& total, InputItem const& item) - { - geometry::expand(total, item.bounding_box); - } -}; - -struct ovelaps_section_box -{ - template <typename Box, typename InputItem> - static inline bool apply(Box const& box, InputItem const& item) - { - return ! detail::disjoint::disjoint_box_box(box, item.bounding_box); - } -}; - template < typename Geometry1, typename Geometry2, @@ -496,12 +459,15 @@ public: point_type, RobustPolicy >::type > box_type; - typedef typename geometry::sections<box_type, 2> sections_type; + typedef geometry::sections<box_type, 2> sections_type; sections_type sec1, sec2; + typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions; - geometry::sectionalize<Reverse1>(geometry1, robust_policy, true, sec1, 0); - geometry::sectionalize<Reverse2>(geometry2, robust_policy, true, sec2, 1); + geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy, + sec1, 0); + geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy, + sec2, 1); // ... and then partition them, intersecting overlapping sections in visitor method section_visitor @@ -513,7 +479,9 @@ public: geometry::partition < - box_type, get_section_box, ovelaps_section_box + box_type, + detail::section::get_section_box, + detail::section::overlaps_section_box >::apply(sec1, sec2, visitor); } }; @@ -556,7 +524,8 @@ struct get_turns_cs RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - int multi_index = -1, int ring_index = -1) + signed_index_type multi_index = -1, + signed_index_type ring_index = -1) { if ( boost::size(range) <= 1) { @@ -569,7 +538,8 @@ struct get_turns_cs cview_type cview(range); view_type view(cview); - typename boost::range_size<view_type>::type segments_count1 = boost::size(view) - 1; + typedef typename boost::range_size<view_type>::type size_type; + size_type segments_count1 = boost::size(view) - 1; iterator_type it = boost::begin(view); @@ -582,7 +552,7 @@ struct get_turns_cs //char previous_side[2] = {0, 0}; - int index = 0; + signed_index_type index = 0; for (iterator_type prev = it++; it != boost::end(view); @@ -621,7 +591,7 @@ struct get_turns_cs bp[0], bp[1], bp[2], bp[3], // NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes index == 0, - unsigned(index) == segments_count1, + size_type(index) == segments_count1, robust_policy, turns, interrupt_policy); // Future performance enhancement: @@ -726,7 +696,7 @@ struct get_turns_polygon_cs int source_id2, Box const& box, RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - int multi_index = -1) + signed_index_type multi_index = -1) { typedef typename geometry::ring_type<Polygon>::type ring_type; @@ -744,7 +714,7 @@ struct get_turns_polygon_cs turns, interrupt_policy, multi_index, -1); - int i = 0; + signed_index_type i = 0; typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -783,7 +753,7 @@ struct get_turns_multi_polygon_cs Multi const >::type iterator_type; - int i = 0; + signed_index_type i = 0; for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it, ++i) diff --git a/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp b/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp index 085933dd7a..277a223d47 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp @@ -28,6 +28,11 @@ #include <boost/geometry/geometries/segment.hpp> +// TODO: the approach below should be completely replaced by the new +// get_left_turns, to keep the outgoing vector which has open space one of its +// sides. + + namespace boost { namespace geometry { @@ -76,6 +81,12 @@ private : RobustPolicy >::type robust_point_type; + inline bool default_order(Indexed const& left, Indexed const& right) const + { + // We've nothing to sort on. Take the indexes + return left.turn_index < right.turn_index; + } + // Still necessary in some situations, // for example #case_102_multi, #case_107_multi, #case_recursive_boxes_3 inline void get_situation_map(Indexed const& left, Indexed const& right, @@ -336,7 +347,7 @@ private : #endif //debug_consider(0, left, right, header, false, "-> return", ret); - return left.turn_index < right.turn_index; + return default_order(left, right); } @@ -369,11 +380,17 @@ private : // Both located at same side (#58, pie_21_7_21_0_3) if (side_ri_p * side_si_p == 1 && side_si_r != 0) { - // Take the most left one if (left.subject->operation == operation_union && right.subject->operation == operation_union) { - bool ret = side_si_r == 1; + int const side_ri_s = m_strategy.apply(si, sj, ri); + if (side_si_r == side_ri_s) + { + return default_order(left, right); + } + + // Take the most left one + bool const ret = side_si_r == 1; //debug_consider(0, left, right, header, false, "same side", ret); return ret; } @@ -407,6 +424,12 @@ private : // One coming from left (#90, #94, #95) if (side_si_r != 0 && (side_ri_p != 0 || side_si_p != 0)) { + int const side_ri_s = m_strategy.apply(si, sj, ri); + if (side_si_r == side_ri_s) + { + return default_order(left, right); + } + bool ret = false; #if BOOST_GEOMETRY_HANDLE_TANGENCIES_WITH_OVERLAP_INFO @@ -464,7 +487,7 @@ private : return ! consider_iu_iu(right, left, header, true); } - return left.turn_index < right.turn_index; + return default_order(left, right); } inline bool consider_ii(Indexed const& left, Indexed const& right, @@ -488,19 +511,17 @@ private : bool const ret = side_si_r != 1; return ret; } - return left.turn_index < right.turn_index; + return default_order(left, right); } public : inline bool operator()(Indexed const& left, Indexed const& right) const { - bool const default_order = left.turn_index < right.turn_index; - if ((m_turn_points[left.turn_index].discarded || left.discarded) && (m_turn_points[right.turn_index].discarded || right.discarded)) { - return default_order; + return default_order(left, right); } else if (m_turn_points[left.turn_index].discarded || left.discarded) { @@ -525,7 +546,7 @@ public : // uu/uu, Order is arbitrary // Note: uu/uu is discarded now before so this point will // not be reached. - return default_order; + return default_order(left, right); } else if (m_turn_points[left.turn_index].combination(operation_intersection, operation_union) && m_turn_points[right.turn_index].combination(operation_intersection, operation_union)) @@ -587,7 +608,7 @@ public : << std::endl; #endif - return default_order; + return default_order(left, right); } }; @@ -708,7 +729,7 @@ inline void handle_cluster(Iterator begin_cluster, Iterator end_cluster, for_operation, geometry1, geometry2, strategy); - // Then sort this range (discard rows will be ordered first and will be removed in enrich_assign) + // Then sort this range (discarded rows will be ordered first and will be removed in enrich_assign) std::sort(begin_cluster, end_cluster, sort_in_cluster < diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index a13a627456..3101de8c35 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -43,9 +43,9 @@ #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> - #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) -#include <boost/foreach.hpp> +#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> +#include <boost/geometry/io/wkt/wkt.hpp> #endif namespace boost { namespace geometry @@ -254,9 +254,10 @@ struct intersection_of_linestring_with_areal #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) int index = 0; - BOOST_FOREACH(turn_info const& turn, turns) + for(typename std::deque<turn_info>::const_iterator + it = turns.begin(); it != turns.end(); ++it) { - debug_follow(turn, turn.operations[0], index++); + debug_follow(*it, it->operations[0], index++); } #endif diff --git a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp index 3a7a7a7f3e..d4ebcf296b 100644 --- a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp @@ -144,11 +144,10 @@ protected: typename Info, typename Point1, typename Point2, - typename IntersectionInfo, - typename DirInfo + typename IntersectionInfo > static inline void apply(Info& , Point1 const& , Point2 const& , - IntersectionInfo const& , DirInfo const& ) + IntersectionInfo const& ) { } }; diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index 44b5a0df3c..a2f52848d1 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -44,10 +44,6 @@ # include <boost/geometry/io/dsv/write.hpp> #endif -#ifdef BOOST_GEOMETRY_TIME_OVERLAY -# include <boost/timer.hpp> -#endif - namespace boost { namespace geometry { @@ -57,19 +53,10 @@ namespace boost { namespace geometry namespace detail { namespace overlay { -// Skip for assemble process -template <typename TurnInfo> -inline bool skip(TurnInfo const& turn_info) -{ - return (turn_info.discarded || turn_info.both(operation_union)) - && ! turn_info.any_blocked() - && ! turn_info.both(operation_intersection) - ; -} - -template <typename TurnPoints, typename Map> -inline void map_turns(Map& map, TurnPoints const& turn_points) +template <typename TurnPoints, typename TurnInfoMap> +inline void get_ring_turn_info(TurnInfoMap& turn_info_map, + TurnPoints const& turn_points) { typedef typename boost::range_value<TurnPoints>::type turn_point_type; typedef typename turn_point_type::container_type container_type; @@ -79,20 +66,32 @@ inline void map_turns(Map& map, TurnPoints const& turn_points) it != boost::end(turn_points); ++it) { - if (! skip(*it)) + typename boost::range_value<TurnPoints>::type const& turn_info = *it; + bool both_uu = turn_info.both(operation_union); + bool skip = (turn_info.discarded || both_uu) + && ! turn_info.any_blocked() + && ! turn_info.both(operation_intersection) + ; + + 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) { - for (typename boost::range_iterator<container_type const>::type - op_it = boost::begin(it->operations); - op_it != boost::end(it->operations); - ++op_it) + ring_identifier ring_id + ( + op_it->seg_id.source_index, + op_it->seg_id.multi_index, + op_it->seg_id.ring_index + ); + + if (! skip) { - ring_identifier ring_id - ( - op_it->seg_id.source_index, - op_it->seg_id.multi_index, - op_it->seg_id.ring_index - ); - map[ring_id]++; + turn_info_map[ring_id].has_normal_turn = true; + } + else if (both_uu) + { + turn_info_map[ring_id].has_uu_turn = true; } } } @@ -137,10 +136,10 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, #endif - std::map<ring_identifier, int> empty; + 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, false); + select_rings<Direction>(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); @@ -193,10 +192,6 @@ struct overlay container_type turn_points; -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - boost::timer timer; -#endif - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "get turns" << std::endl; #endif @@ -207,10 +202,6 @@ std::cout << "get turns" << std::endl; detail::overlay::assign_null_policy >(geometry1, geometry2, robust_policy, turn_points, policy); -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "get_turns: " << timer.elapsed() << std::endl; -#endif - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "enrich" << std::endl; #endif @@ -223,11 +214,6 @@ std::cout << "enrich" << std::endl; robust_policy, side_strategy); -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "enrich_intersection_points: " << timer.elapsed() << std::endl; -#endif - - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "traverse" << std::endl; #endif @@ -245,27 +231,18 @@ std::cout << "traverse" << std::endl; turn_points, rings ); -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "traverse: " << timer.elapsed() << std::endl; -#endif - - - std::map<ring_identifier, int> map; - map_turns(map, turn_points); - -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "map_turns: " << timer.elapsed() << std::endl; -#endif - - typedef ring_properties<typename geometry::point_type<GeometryOut>::type> properties; - - std::map<ring_identifier, properties> selected; - select_rings<Direction>(geometry1, geometry2, map, selected, ! turn_points.empty()); + std::map<ring_identifier, ring_turn_info> turn_info_per_ring; + get_ring_turn_info(turn_info_per_ring, turn_points); -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "select_rings: " << timer.elapsed() << std::endl; -#endif + typedef ring_properties + < + typename geometry::point_type<GeometryOut>::type + > properties; + // 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, + selected_ring_properties); // Add rings created during traversal { @@ -275,24 +252,15 @@ std::cout << "traverse" << std::endl; it != boost::end(rings); ++it) { - selected[id] = properties(*it, true); - selected[id].reversed = ReverseOut; + selected_ring_properties[id] = properties(*it); + selected_ring_properties[id].reversed = ReverseOut; id.multi_index++; } } -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "add traversal rings: " << timer.elapsed() << std::endl; -#endif - - - assign_parents(geometry1, geometry2, rings, selected); - -#ifdef BOOST_GEOMETRY_TIME_OVERLAY - std::cout << "assign_parents: " << timer.elapsed() << std::endl; -#endif + assign_parents(geometry1, geometry2, rings, selected_ring_properties); - return add_rings<GeometryOut>(selected, geometry1, geometry2, rings, out); + return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out); } }; diff --git a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp index a6088694da..b469052c84 100644 --- a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp +++ b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp @@ -33,8 +33,7 @@ struct ring_properties Point point; area_type area; - // Filled by "update_selection_map" - int within_code; + // Filled by "update_ring_selection" bool reversed; // Filled/used by "assign_rings" @@ -45,21 +44,22 @@ struct ring_properties inline ring_properties() : area(area_type()) - , within_code(-1) , reversed(false) , discarded(false) , parent_area(-1) {} template <typename RingOrBox> - inline ring_properties(RingOrBox const& ring_or_box, bool midpoint) - : within_code(-1) - , reversed(false) + inline ring_properties(RingOrBox const& ring_or_box) + : reversed(false) , discarded(false) , parent_area(-1) { this->area = geometry::area(ring_or_box); - geometry::point_on_border(this->point, ring_or_box, midpoint); + // 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 + geometry::point_on_border(this->point, ring_or_box, true); } 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 385658a190..d18e012b2d 100644 --- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. // Use, modification and distribution is subject to the Boost Software License, @@ -20,7 +20,6 @@ #include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/within.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> -#include <boost/geometry/algorithms/detail/point_on_border.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> @@ -34,6 +33,18 @@ namespace boost { namespace geometry namespace detail { namespace overlay { +struct ring_turn_info +{ + bool has_uu_turn; + bool has_normal_turn; + bool within_other; + + ring_turn_info() + : has_uu_turn(false) + , has_normal_turn(false) + , within_other(false) + {} +}; namespace dispatch { @@ -45,41 +56,41 @@ namespace dispatch template <typename Box> struct select_rings<box_tag, Box> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Box const& box, Geometry const& , - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { - map[id] = typename Map::mapped_type(box, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(box); } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Box const& box, - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { - map[id] = typename Map::mapped_type(box, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(box); } }; template <typename Ring> struct select_rings<ring_tag, Ring> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Ring const& ring, Geometry const& , - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { if (boost::size(ring) > 0) { - map[id] = typename Map::mapped_type(ring, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring); } } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Ring const& ring, - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { if (boost::size(ring) > 0) { - map[id] = typename Map::mapped_type(ring, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring); } } }; @@ -88,14 +99,14 @@ namespace dispatch template <typename Polygon> struct select_rings<polygon_tag, Polygon> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Polygon const& polygon, Geometry const& geometry, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { 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, map, midpoint); + per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -103,18 +114,18 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, geometry, id, map, midpoint); + per_ring::apply(*it, geometry, id, ring_properties); } } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Polygon const& polygon, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { 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, map, midpoint); + per_ring::apply(exterior_ring(polygon), id, ring_properties); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -122,7 +133,7 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, id, map, midpoint); + per_ring::apply(*it, id, ring_properties); } } }; @@ -130,9 +141,9 @@ namespace dispatch template <typename Multi> struct select_rings<multi_polygon_tag, Multi> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Multi const& multi, Geometry const& geometry, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { typedef typename boost::range_iterator < @@ -145,7 +156,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, map, midpoint); + per_polygon::apply(*it, geometry, id, ring_properties); id.multi_index++; } } @@ -161,14 +172,12 @@ struct decide template<> struct decide<overlay_union> { - template <typename Code> - static bool include(ring_identifier const& , Code const& code) + static bool include(ring_identifier const& , ring_turn_info const& info) { - return code.within_code * -1 == 1; + return info.has_uu_turn || ! info.within_other; } - template <typename Code> - static bool reversed(ring_identifier const& , Code const& ) + static bool reversed(ring_identifier const& , ring_turn_info const& ) { return false; } @@ -177,31 +186,43 @@ struct decide<overlay_union> template<> struct decide<overlay_difference> { - template <typename Code> - static bool include(ring_identifier const& id, Code const& code) + static bool include(ring_identifier const& id, ring_turn_info const& info) { - bool is_first = id.source_index == 0; - return code.within_code * -1 * (is_first ? 1 : -1) == 1; + // Difference: A - B + + // If this is A (source_index=0) and there is only a u/u turn, + // then the ring is inside B + // If this is B (source_index=1) and there is only a u/u turn, + // then the ring is NOT inside A + + // If this is A and the ring is within the other geometry, + // then we should NOT include it. + // If this is B then we SHOULD include it. + + bool const is_first = id.source_index == 0; + bool const within_other = info.within_other + || (is_first && info.has_uu_turn); + return is_first ? ! within_other : within_other; } - template <typename Code> - static bool reversed(ring_identifier const& id, Code const& code) + static bool reversed(ring_identifier const& id, ring_turn_info const& info) { - return include(id, code) && id.source_index == 1; + // Difference: A - B + // If this is B, and the ring is included, it should be reversed afterwards + + return id.source_index == 1 && include(id, info); } }; template<> struct decide<overlay_intersection> { - template <typename Code> - static bool include(ring_identifier const& , Code const& code) + static bool include(ring_identifier const& , ring_turn_info const& info) { - return code.within_code * 1 == 1; + return ! info.has_uu_turn && info.within_other; } - template <typename Code> - static bool reversed(ring_identifier const& , Code const& ) + static bool reversed(ring_identifier const& , ring_turn_info const& ) { return false; } @@ -211,61 +232,60 @@ struct decide<overlay_intersection> template < overlay_type OverlayType, - typename Geometry1, typename Geometry2, - typename IntersectionMap, typename SelectionMap + typename Geometry1, + typename Geometry2, + typename TurnInfoMap, + typename RingPropertyMap > -inline void update_selection_map(Geometry1 const& geometry1, +inline void update_ring_selection(Geometry1 const& geometry1, Geometry2 const& geometry2, - IntersectionMap const& intersection_map, - SelectionMap const& map_with_all, SelectionMap& selection_map) + TurnInfoMap const& turn_info_map, + RingPropertyMap const& all_ring_properties, + RingPropertyMap& selected_ring_properties) { - selection_map.clear(); + selected_ring_properties.clear(); - for (typename SelectionMap::const_iterator it = boost::begin(map_with_all); - it != boost::end(map_with_all); + for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties); + it != boost::end(all_ring_properties); ++it) { - /* - int union_code = it->second.within_code * -1; - bool is_first = it->first.source_index == 0; - std::cout << it->first << " " << it->second.area - << ": " << it->second.within_code - << " union: " << union_code - << " intersection: " << (it->second.within_code * 1) - << " G1-G2: " << (union_code * (is_first ? 1 : -1)) - << " G2-G1: " << (union_code * (is_first ? -1 : 1)) - << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "") - << decide<OverlayType>::reverse(it->first, it->second) - << std::endl; - */ - - bool found = intersection_map.find(it->first) != intersection_map.end(); - if (! found) + ring_identifier const& id = it->first; + + ring_turn_info info; + + typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id); + if (tcit != turn_info_map.end()) { - ring_identifier const id = it->first; - typename SelectionMap::mapped_type properties = it->second; // Copy by value + info = tcit->second; // Copy by value + } - // Calculate the "within code" (previously this was done earlier but is - // much efficienter here - it can be even more efficient doing it all at once, - // using partition, TODO) - // So though this is less elegant than before, it avoids many unused point-in-poly calculations + if (info.has_normal_turn) + { + // There are normal turns on this ring. It should be traversed, we + // don't include the original ring + continue; + } + + if (! info.has_uu_turn) + { + // Check if the ring is within the other geometry, by taking + // a point lying on the ring switch(id.source_index) { case 0 : - properties.within_code - = geometry::within(properties.point, geometry2) ? 1 : -1; + info.within_other = geometry::within(it->second.point, geometry2); break; case 1 : - properties.within_code - = geometry::within(properties.point, geometry1) ? 1 : -1; + info.within_other = geometry::within(it->second.point, geometry1); break; } + } - if (decide<OverlayType>::include(id, properties)) - { - properties.reversed = decide<OverlayType>::reversed(id, properties); - selection_map[id] = properties; - } + if (decide<OverlayType>::include(id, info)) + { + typename RingPropertyMap::mapped_type properties = it->second; // Copy by value + properties.reversed = decide<OverlayType>::reversed(id, info); + selected_ring_properties[id] = properties; } } } @@ -277,44 +297,47 @@ inline void update_selection_map(Geometry1 const& geometry1, template < overlay_type OverlayType, - typename Geometry1, typename Geometry2, - typename IntersectionMap, typename SelectionMap + typename Geometry1, + typename Geometry2, + typename RingTurnInfoMap, + typename RingPropertyMap > inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2, - IntersectionMap const& intersection_map, - SelectionMap& selection_map, bool midpoint) + RingTurnInfoMap const& turn_info_per_ring, + RingPropertyMap& selected_ring_properties) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; - SelectionMap map_with_all; + RingPropertyMap all_ring_properties; dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, - ring_identifier(0, -1, -1), map_with_all, midpoint); + ring_identifier(0, -1, -1), all_ring_properties); dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, - ring_identifier(1, -1, -1), map_with_all, midpoint); + ring_identifier(1, -1, -1), all_ring_properties); - update_selection_map<OverlayType>(geometry1, geometry2, intersection_map, - map_with_all, selection_map); + update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring, + all_ring_properties, selected_ring_properties); } template < overlay_type OverlayType, typename Geometry, - typename IntersectionMap, typename SelectionMap + typename RingTurnInfoMap, + typename RingPropertyMap > inline void select_rings(Geometry const& geometry, - IntersectionMap const& intersection_map, - SelectionMap& selection_map, bool midpoint) + RingTurnInfoMap const& turn_info_per_ring, + RingPropertyMap& selected_ring_properties) { typedef typename geometry::tag<Geometry>::type tag; - SelectionMap map_with_all; + RingPropertyMap all_ring_properties; dispatch::select_rings<tag, Geometry>::apply(geometry, - ring_identifier(0, -1, -1), map_with_all, midpoint); + ring_identifier(0, -1, -1), all_ring_properties); - update_selection_map<OverlayType>(geometry, geometry, intersection_map, - map_with_all, selection_map); + update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring, + all_ring_properties, selected_ring_properties); } diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp index 8dffeae283..b1f984ffe1 100644 --- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp @@ -23,9 +23,12 @@ #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> +#include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> #include <boost/geometry/geometries/box.hpp> +#include <boost/geometry/util/condition.hpp> + namespace boost { namespace geometry { @@ -96,7 +99,7 @@ struct self_section_visitor m_rescale_policy, m_turns, m_interrupt_policy); } - if (m_interrupt_policy.has_intersections) + 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. @@ -121,15 +124,19 @@ struct get_turns { typedef model::box < - typename geometry::point_type<Geometry>::type + typename geometry::robust_point_type + < + typename geometry::point_type<Geometry>::type, + RobustPolicy + >::type > box_type; - typedef typename geometry::sections - < - box_type, 1 - > sections_type; + + typedef geometry::sections<box_type, 1> sections_type; + + typedef boost::mpl::vector_c<std::size_t, 0> dimensions; sections_type sec; - geometry::sectionalize<false>(geometry, robust_policy, false, sec); + geometry::sectionalize<false, dimensions>(geometry, robust_policy, sec); self_section_visitor < @@ -142,8 +149,8 @@ struct get_turns geometry::partition < box_type, - detail::get_turns::get_section_box, - detail::get_turns::ovelaps_section_box + detail::section::get_section_box, + detail::section::overlaps_section_box >::apply(sec, visitor); } catch(self_ip_exception const& ) |