diff options
author | Anas Nashif <anas.nashif@intel.com> | 2013-08-26 08:15:55 -0400 |
---|---|---|
committer | Anas Nashif <anas.nashif@intel.com> | 2013-08-26 08:15:55 -0400 |
commit | bb4dd8289b351fae6b55e303f189127a394a1edd (patch) | |
tree | 77c9c35a31b1459dd7988c2448e797d142530c41 /boost/geometry/algorithms/detail/overlay | |
parent | 1a78a62555be32868418fe52f8e330c9d0f95d5a (diff) | |
download | boost-bb4dd8289b351fae6b55e303f189127a394a1edd.tar.gz boost-bb4dd8289b351fae6b55e303f189127a394a1edd.tar.bz2 boost-bb4dd8289b351fae6b55e303f189127a394a1edd.zip |
Imported Upstream version 1.51.0upstream/1.51.0
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
12 files changed, 247 insertions, 54 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/add_rings.hpp b/boost/geometry/algorithms/detail/overlay/add_rings.hpp index eb3e60e483..74595fedd0 100644 --- a/boost/geometry/algorithms/detail/overlay/add_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/add_rings.hpp @@ -9,6 +9,8 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp> #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> @@ -73,6 +75,21 @@ inline OutputIterator add_rings(SelectionMap const& map, OutputIterator out) { typedef typename SelectionMap::const_iterator iterator; + typedef typename SelectionMap::mapped_type property_type; + typedef typename property_type::area_type area_type; + + area_type const zero = 0; + std::size_t const min_num_points = core_detail::closure::minimum_ring_size + < + geometry::closure + < + typename boost::range_value + < + RingCollection const + >::type + >::value + >::value; + for (iterator it = boost::begin(map); it != boost::end(map); @@ -99,7 +116,16 @@ inline OutputIterator add_rings(SelectionMap const& map, *child_it, mit->second.reversed, true); } } - *out++ = result; + + // Only add rings if they satisfy minimal requirements. + // This cannot be done earlier (during traversal), not + // everything is figured out yet (sum of positive/negative rings) + // TODO: individual rings can still contain less than 3 points. + if (geometry::num_points(result) >= min_num_points + && math::larger(geometry::area(result), zero)) + { + *out++ = result; + } } } return out; diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 133530563e..5063f49eb4 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -130,7 +130,7 @@ struct assign_visitor return; } - if (outer.real_area > 0) + if (math::larger(outer.real_area, 0)) { if (inner.real_area < 0 || m_check_for_orientation) { @@ -317,13 +317,14 @@ template > inline void assign_parents(Geometry const& geometry, RingCollection const& collection, - RingMap& ring_map) + RingMap& ring_map, + bool check_for_orientation) { // Call it with an empty geometry // (ring_map should be empty for source_id==1) Geometry empty; - assign_parents(geometry, empty, collection, ring_map, true); + assign_parents(geometry, empty, collection, ring_map, check_for_orientation); } diff --git a/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp b/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp index 3e6a8897f5..2003d2350d 100644 --- a/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp +++ b/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp @@ -32,9 +32,18 @@ struct calculate_distance_policy { static bool const include_no_turn = false; static bool const include_degenerate = false; - - template <typename Point1, typename Point2, typename Info> - static inline void apply(Info& info, Point1 const& p1, Point2 const& p2) + static bool const include_opposite = false; + + template + < + typename Info, + typename Point1, + typename Point2, + typename IntersectionInfo, + typename DirInfo + > + static inline void apply(Info& info, Point1 const& p1, Point2 const& p2, + IntersectionInfo const&, DirInfo const&) { info.operations[0].enriched.distance = geometry::comparable_distance(info.point, p1); diff --git a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp index 379444428f..5e18d0453a 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp @@ -55,14 +55,14 @@ struct copy_segment_point_range if (second) { index++; - if (index >= boost::size(range)) + if (index >= int(boost::size(range))) { index = 0; } } // Exception? - if (index >= boost::size(range)) + if (index >= int(boost::size(range))) { return false; } diff --git a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp index b0183a3ac2..805f3923e3 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp @@ -78,7 +78,7 @@ struct copy_segments_ring int const from_index = seg_id.segment_index + 1; // Sanity check - BOOST_ASSERT(from_index < boost::size(view)); + BOOST_ASSERT(from_index < int(boost::size(view))); ec_iterator it(boost::begin(view), boost::end(view), boost::begin(view) + from_index); @@ -89,7 +89,7 @@ struct copy_segments_ring typedef typename boost::range_difference<Ring>::type size_type; size_type const count = from_index <= to_index ? to_index - from_index + 1 - : boost::size(view) - from_index + to_index + 1; + : int(boost::size(view)) - from_index + to_index + 1; for (size_type i = 0; i < count; ++i, ++it) { @@ -117,7 +117,7 @@ struct copy_segments_linestring int const from_index = seg_id.segment_index + 1; // Sanity check - if (from_index > to_index || from_index < 0 || to_index >= boost::size(ls)) + if (from_index > to_index || from_index < 0 || to_index >= int(boost::size(ls))) { return; } diff --git a/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp index 0bec816946..0cc34255ca 100644 --- a/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp @@ -28,6 +28,7 @@ inline char method_char(detail::overlay::method_type const& method) case method_touch_interior : return 'm'; case method_collinear : return 'c'; case method_equal : return 'e'; + case method_error : return '!'; default : return '?'; } } @@ -42,6 +43,7 @@ inline char operation_char(detail::overlay::operation_type const& operation) case operation_intersection : return 'i'; case operation_blocked : return 'x'; case operation_continue : return 'c'; + case operation_opposite : return 'o'; default : return '?'; } } diff --git a/boost/geometry/algorithms/detail/overlay/follow.hpp b/boost/geometry/algorithms/detail/overlay/follow.hpp index 087092a5f2..b110cc9602 100644 --- a/boost/geometry/algorithms/detail/overlay/follow.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow.hpp @@ -279,12 +279,12 @@ class follow { // In case of turn point at the same location, we want to have continue/blocked LAST // because that should be followed (intersection) or skipped (difference). - // By chance the enumeration is ordered like that but we keep the safe way here. inline int operation_order(Turn const& turn) const { operation_type const& operation = turn.operations[0].operation; switch(operation) { + case operation_opposite : return 0; case operation_none : return 0; case operation_union : return 1; case operation_intersection : return 2; diff --git a/boost/geometry/algorithms/detail/overlay/get_ring.hpp b/boost/geometry/algorithms/detail/overlay/get_ring.hpp index ad47665500..c2c6980577 100644 --- a/boost/geometry/algorithms/detail/overlay/get_ring.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_ring.hpp @@ -83,7 +83,7 @@ struct get_ring<polygon_tag> BOOST_ASSERT ( id.ring_index >= -1 - && id.ring_index < boost::size(interior_rings(polygon)) + && id.ring_index < int(boost::size(interior_rings(polygon))) ); return id.ring_index < 0 ? exterior_ring(polygon) diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 663d70d9af..b8320d9b7b 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -250,9 +250,15 @@ struct touch : public base_turn_handler int const side_pk_q2 = SideStrategy::apply(qj, qk, pk); int const side_pk_p = SideStrategy::apply(pi, pj, pk); int const side_qk_q = SideStrategy::apply(qi, qj, qk); + + bool const both_continue = side_pk_p == 0 && side_qk_q == 0; + bool const robustness_issue_in_continue = both_continue && side_pk_q2 != 0; + bool const q_turns_left = side_qk_q == 1; bool const block_q = side_qk_p1 == 0 - && ! same(side_qi_p1, side_qk_q); + && ! same(side_qi_p1, side_qk_q) + && ! robustness_issue_in_continue + ; // If Pk at same side as Qi/Qk // (the "or" is for collinear case) @@ -278,7 +284,7 @@ struct touch : public base_turn_handler if (side_pk_q1 == 0) { ti.operations[0].operation = operation_blocked; - // Q turns right -> union (both independant), + // Q turns right -> union (both independent), // Q turns left -> intersection ti.operations[1].operation = block_q ? operation_blocked : q_turns_left ? operation_intersection @@ -466,6 +472,45 @@ struct equal : public base_turn_handler template < typename TurnInfo, + typename AssignPolicy +> +struct equal_opposite : public base_turn_handler +{ + template + < + typename Point1, + typename Point2, + typename OutputIterator, + typename IntersectionInfo, + typename DirInfo + > + static inline void apply(Point1 const& pi, Point2 const& qi, + /* by value: */ TurnInfo tp, + OutputIterator& out, + IntersectionInfo const& intersection_info, + DirInfo const& dir_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++) + { + tp.operations[i].operation = operation_opposite; + } + for (unsigned int i = 0; i < intersection_info.count; i++) + { + geometry::convert(intersection_info.intersections[i], tp.point); + AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + *out++ = tp; + } + } + } +}; + +template +< + typename TurnInfo, typename SideStrategy > struct collinear : public base_turn_handler @@ -494,6 +539,13 @@ struct collinear : public base_turn_handler - if P arrives and P turns right: intersection for P - if Q arrives and Q turns left: union for Q (=intersection for P) - if Q arrives and Q turns right: intersection for Q (=union for P) + + ROBUSTNESS: p and q are collinear, so you would expect + that side qk//p1 == pk//q1. But that is not always the case + in near-epsilon ranges. Then decision logic is different. + If p arrives, q is further, so the angle qk//p1 is (normally) + more precise than pk//p1 + */ template < @@ -516,12 +568,18 @@ struct collinear : public base_turn_handler // Should not be 0, this is checked before BOOST_ASSERT(arrival != 0); + int const side_p = SideStrategy::apply(pi, pj, pk); + int const side_q = SideStrategy::apply(qi, qj, qk); + // If p arrives, use p, else use q int const side_p_or_q = arrival == 1 - ? SideStrategy::apply(pi, pj, pk) - : SideStrategy::apply(qi, qj, qk) + ? side_p + : side_q ; + int const side_pk = SideStrategy::apply(qi, qj, pk); + int const side_qk = SideStrategy::apply(pi, pj, qk); + // See comments above, // resulting in a strange sort of mathematic rule here: // The arrival-info multiplied by the relevant side @@ -529,7 +587,15 @@ struct collinear : public base_turn_handler int const product = arrival * side_p_or_q; - if(product == 0) + // Robustness: side_p is supposed to be equal to side_pk (because p/q are collinear) + // and side_q to side_qk + bool const robustness_issue = side_pk != side_p || side_qk != side_q; + + if (robustness_issue) + { + handle_robustness(ti, arrival, side_p, side_q, side_pk, side_qk); + } + else if(product == 0) { both(ti, operation_continue); } @@ -538,6 +604,38 @@ struct collinear : public base_turn_handler ui_else_iu(product == 1, ti); } } + + static inline void handle_robustness(TurnInfo& ti, int arrival, + int side_p, int side_q, int side_pk, int side_qk) + { + // We take the longer one, i.e. if q arrives in p (arrival == -1), + // then p exceeds q and we should take p for a union... + + bool use_p_for_union = arrival == -1; + + // ... unless one of the sides consistently directs to the other side + int const consistent_side_p = side_p == side_pk ? side_p : 0; + int const consistent_side_q = side_q == side_qk ? side_q : 0; + if (arrival == -1 && (consistent_side_p == -1 || consistent_side_q == 1)) + { + use_p_for_union = false; + } + if (arrival == 1 && (consistent_side_p == 1 || consistent_side_q == -1)) + { + use_p_for_union = true; + } + + //std::cout << "ROBUSTNESS -> Collinear " + // << " arr: " << arrival + // << " dir: " << side_p << " " << side_q + // << " rev: " << side_pk << " " << side_qk + // << " cst: " << cside_p << " " << cside_q + // << std::boolalpha << " " << use_p_for_union + // << std::endl; + + ui_else_iu(use_p_for_union, ti); + } + }; template @@ -583,6 +681,7 @@ private : TurnInfo& tp, IntersectionInfo const& intersection_info) { int const side_rk_r = SideStrategy::apply(ri, rj, rk); + operation_type blocked = operation_blocked; switch(side_rk_r) { @@ -596,15 +695,24 @@ private : break; case 0 : // No turn on opposite collinear: block, do not traverse - // But this "xx" is ignored here, it is useless to include - // two operation blocked, so the whole point does not need + // But this "xx" is usually ignored, it is useless to include + // two operations blocked, so the whole point does not need // to be generated. // So return false to indicate nothing is to be done. - return false; + if (AssignPolicy::include_opposite) + { + tp.operations[Index].operation = operation_opposite; + blocked = operation_opposite; + } + else + { + return false; + } + break; } // The other direction is always blocked when collinear opposite - tp.operations[1 - Index].operation = operation_blocked; + tp.operations[1 - Index].operation = blocked; // If P arrives within Q, set info on P (which is done above, index=0), // this turn-info belongs to the second intersection point, index=1 @@ -633,32 +741,45 @@ public: IntersectionInfo const& intersection_info, DirInfo const& dir_info) { - /* - std::cout << "arrivals: " - << dir_info.arrival[0] - << "/" << dir_info.arrival[1] - << std::endl; - */ - TurnInfo tp = tp_model; tp.method = method_collinear; - // If P arrives within Q, there is a turn dependant on P + // If P arrives within Q, there is a turn dependent on P if (dir_info.arrival[0] == 1 && set_tp<0>(pi, pj, pk, tp, intersection_info)) { - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); *out++ = tp; } - // If Q arrives within P, there is a turn dependant on Q + // If Q arrives within P, there is a turn dependent on Q if (dir_info.arrival[1] == 1 && set_tp<1>(qi, qj, qk, tp, intersection_info)) { - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, intersection_info, dir_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)) + { + for (int i = 0; i < 2; i++) + { + tp.operations[i].operation = operation_opposite; + } + for (unsigned int i = 0; i < intersection_info.count; i++) + { + geometry::convert(intersection_info.intersections[i], tp.point); + AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info); + *out++ = tp; + } + } + } + } }; @@ -722,9 +843,17 @@ struct assign_null_policy { static bool const include_no_turn = false; static bool const include_degenerate = false; - - template <typename Point1, typename Point2, typename Info> - static inline void apply(Info& , Point1 const& , Point2 const& ) + static bool const include_opposite = false; + + template + < + typename Info, + typename Point1, + typename Point2, + typename IntersectionInfo, + typename DirInfo + > + static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&) {} }; @@ -763,8 +892,9 @@ struct get_turn_info typedef typename si::segment_intersection_strategy_type strategy; - - + // Intersect pi-pj with qi-qj + // The points pk and qk are only used do determine more information + // about the turn. template <typename OutputIterator> static inline OutputIterator apply( Point1 const& pi, Point1 const& pj, Point1 const& pk, @@ -796,7 +926,7 @@ struct get_turn_info { only_convert<TurnInfo>::apply(tp, result.template get<0>()); - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } break; @@ -824,7 +954,7 @@ struct get_turn_info policy::template apply<1>(qi, qj, qk, pi, pj, pk, tp, result.template get<0>(), result.template get<1>()); } - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } break; @@ -838,7 +968,7 @@ struct get_turn_info policy::apply(pi, pj, pk, qi, qj, qk, tp, result.template get<0>(), result.template get<1>()); - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } break; @@ -853,7 +983,7 @@ struct get_turn_info policy::apply(pi, pj, pk, qi, qj, qk, tp, result.template get<0>(), result.template get<1>()); - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } break; @@ -871,10 +1001,18 @@ struct get_turn_info policy::apply(pi, pj, pk, qi, qj, qk, tp, result.template get<0>(), result.template get<1>()); - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } - // If they ARE opposite, don't do anything. + else + { + equal_opposite + < + TurnInfo, + AssignPolicy + >::apply(pi, qi, + tp, out, result.template get<0>(), result.template get<1>()); + } } break; case 'c' : @@ -906,7 +1044,7 @@ struct get_turn_info tp, result.template get<0>(), result.template get<1>()); } - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } else @@ -927,7 +1065,7 @@ struct get_turn_info if (AssignPolicy::include_degenerate) { only_convert<TurnInfo>::apply(tp, result.template get<0>()); - AssignPolicy::apply(tp, pi, qi); + AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>()); *out++ = tp; } } diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index 5740a8b7ba..26629043cb 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -495,7 +495,7 @@ struct get_turns_cs int source_id1, Range const& range, int source_id2, Box const& box, Turns& turns, - InterruptPolicy& , + InterruptPolicy& interrupt_policy, int multi_index = -1, int ring_index = -1) { if (boost::size(range) <= 1) @@ -557,7 +557,7 @@ struct get_turns_cs get_turns_with_box(seg_id, source_id2, *prev, *it, *next, bp[0], bp[1], bp[2], bp[3], - turns); + turns, interrupt_policy); // Future performance enhancement: // return if told by the interrupt policy } @@ -596,7 +596,8 @@ private: box_point_type const& bp2, box_point_type const& bp3, // Output - Turns& turns) + Turns& turns, + InterruptPolicy& interrupt_policy) { // Depending on code some relations can be left out @@ -622,6 +623,12 @@ private: ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3); TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1, ti, std::back_inserter(turns)); + + if (InterruptPolicy::enabled) + { + interrupt_policy.apply(turns); + } + } }; diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index ab5b6d123d..41665e0af1 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -233,7 +233,7 @@ std::cout << "traverse" << std::endl; std::cout << "map_turns: " << timer.elapsed() << std::endl; #endif - typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties; + 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()); diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index aa6b428f19..89a60b21ab 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -28,7 +28,8 @@ enum operation_type operation_union, operation_intersection, operation_blocked, - operation_continue + operation_continue, + operation_opposite }; @@ -102,6 +103,12 @@ struct turn_info { return has12(type, type); } + + inline bool has(operation_type type) const + { + return this->operations[0].operation == type + || this->operations[1].operation == type; + } inline bool combination(operation_type type1, operation_type type2) const { @@ -114,10 +121,13 @@ struct turn_info { return both(operation_blocked); } + inline bool opposite() const + { + return both(operation_opposite); + } inline bool any_blocked() const { - return this->operations[0].operation == operation_blocked - || this->operations[1].operation == operation_blocked; + return has(operation_blocked); } |