diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
27 files changed, 690 insertions, 178 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/add_rings.hpp b/boost/geometry/algorithms/detail/overlay/add_rings.hpp index 5ff0b57d6e..fcb240941f 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/range.hpp> + #include <boost/geometry/core/closure.hpp> #include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 178f3825d7..047eb4993e 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -9,6 +9,8 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP +#include <boost/range.hpp> + #include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/envelope.hpp> #include <boost/geometry/algorithms/expand.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/check_enrich.hpp b/boost/geometry/algorithms/detail/overlay/check_enrich.hpp index 03be18e07a..25e442982b 100644 --- a/boost/geometry/algorithms/detail/overlay/check_enrich.hpp +++ b/boost/geometry/algorithms/detail/overlay/check_enrich.hpp @@ -12,12 +12,8 @@ #include <cstddef> - -#include <boost/assert.hpp> #include <boost/range.hpp> - - #include <boost/geometry/algorithms/detail/ring_identifier.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp index fc4f657322..b1a25c9f5e 100644 --- a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp +++ b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp @@ -1,6 +1,11 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015 Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, 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 @@ -160,10 +165,12 @@ template typename OutputLinestring, typename OutputIterator, typename Range, + typename RobustPolicy, typename Box, typename Strategy > OutputIterator clip_range_with_box(Box const& b, Range const& range, + RobustPolicy const&, OutputIterator out, Strategy const& strategy) { if (boost::begin(range) == boost::end(range)) diff --git a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp index 13e0a5a51e..dbf3770357 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp @@ -11,10 +11,10 @@ #include <boost/array.hpp> -#include <boost/assert.hpp> #include <boost/mpl/assert.hpp> #include <boost/range.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/ring_type.hpp> #include <boost/geometry/core/exterior_ring.hpp> #include <boost/geometry/core/interior_rings.hpp> @@ -43,8 +43,8 @@ struct copy_segment_point_range { detail::normalized_view<Range const> view(range); - signed_index_type const n = boost::size(view); - signed_index_type index = seg_id.segment_index; + signed_size_type const n = boost::size(view); + signed_size_type index = seg_id.segment_index; if (second) { index++; @@ -54,7 +54,7 @@ struct copy_segment_point_range } } - BOOST_ASSERT(index >= 0 && index < n); + BOOST_GEOMETRY_ASSERT(index >= 0 && index < n); geometry::convert(*(boost::begin(view) + index), point); return true; @@ -95,7 +95,7 @@ struct copy_segment_point_box SegmentIdentifier const& seg_id, bool second, PointOut& point) { - signed_index_type index = seg_id.segment_index; + signed_size_type index = seg_id.segment_index; if (second) { index++; @@ -123,7 +123,7 @@ struct copy_segment_point_multi PointOut& point) { - BOOST_ASSERT + BOOST_GEOMETRY_ASSERT ( seg_id.multi_index >= 0 && seg_id.multi_index < int(boost::size(multi)) @@ -306,7 +306,7 @@ 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); + BOOST_GEOMETRY_ASSERT(seg_id.source_index == 0 || seg_id.source_index == 1); if (seg_id.source_index == 0) { diff --git a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp index ceeb1a3b8b..2eefa03c67 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp @@ -19,14 +19,11 @@ #include <vector> #include <boost/array.hpp> -#include <boost/assert.hpp> #include <boost/mpl/assert.hpp> #include <boost/range.hpp> #include <boost/type_traits/integral_constant.hpp> -#include <boost/geometry/core/tags.hpp> - -#include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/exterior_ring.hpp> #include <boost/geometry/core/interior_rings.hpp> #include <boost/geometry/core/ring_type.hpp> @@ -64,7 +61,7 @@ struct copy_segments_ring > static inline void apply(Ring const& ring, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -93,10 +90,10 @@ struct copy_segments_ring // So we use the ever-circling iterator and determine when to step out - signed_index_type const from_index = seg_id.segment_index + 1; + signed_size_type const from_index = seg_id.segment_index + 1; // Sanity check - BOOST_ASSERT(from_index < static_cast<signed_index_type>(boost::size(view))); + BOOST_GEOMETRY_ASSERT(from_index < static_cast<signed_size_type>(boost::size(view))); ec_iterator it(boost::begin(view), boost::end(view), boost::begin(view) + from_index); @@ -104,12 +101,12 @@ struct copy_segments_ring // [2..4] -> 4 - 2 + 1 = 3 -> {2,3,4} -> OK // [4..2],size=6 -> 6 - 4 + 2 + 1 = 5 -> {4,5,0,1,2} -> OK // [1..1], travel the whole ring round - signed_index_type const count = from_index <= to_index + signed_size_type const count = from_index <= to_index ? to_index - from_index + 1 - : static_cast<signed_index_type>(boost::size(view)) + : static_cast<signed_size_type>(boost::size(view)) - from_index + to_index + 1; - for (signed_index_type i = 0; i < count; ++i, ++it) + for (signed_size_type i = 0; i < count; ++i, ++it) { detail::overlay::append_no_dups_or_spikes(current_output, *it, robust_policy); } @@ -151,26 +148,26 @@ public: > static inline void apply(LineString const& ls, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& current_output) { - signed_index_type const from_index = seg_id.segment_index + 1; + signed_size_type const from_index = seg_id.segment_index + 1; // Sanity check if ( from_index > to_index || from_index < 0 - || to_index >= static_cast<signed_index_type>(boost::size(ls)) ) + || to_index >= static_cast<signed_size_type>(boost::size(ls)) ) { return; } - signed_index_type const count = to_index - from_index + 1; + signed_size_type const count = to_index - from_index + 1; typename boost::range_iterator<LineString const>::type it = boost::begin(ls) + from_index; - for (signed_index_type i = 0; i < count; ++i, ++it) + for (signed_size_type i = 0; i < count; ++i, ++it) { append_to_output(current_output, *it, robust_policy, boost::integral_constant<bool, RemoveSpikes>()); @@ -190,7 +187,7 @@ struct copy_segments_polygon > static inline void apply(Polygon const& polygon, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& current_output) { @@ -220,14 +217,14 @@ struct copy_segments_box > static inline void apply(Box const& box, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& current_output) { - signed_index_type index = seg_id.segment_index + 1; - BOOST_ASSERT(index < 5); + signed_size_type index = seg_id.segment_index + 1; + BOOST_GEOMETRY_ASSERT(index < 5); - signed_index_type const count = index <= to_index + signed_size_type const count = index <= to_index ? to_index - index + 1 : 5 - index + to_index + 1; @@ -238,7 +235,7 @@ struct copy_segments_box // (possibly cyclic) copy to output // (see comments in ring-version) - for (signed_index_type i = 0; i < count; i++, index++) + for (signed_size_type i = 0; i < count; i++, index++) { detail::overlay::append_no_dups_or_spikes(current_output, bp[index % 5], robust_policy); @@ -260,15 +257,15 @@ struct copy_segments_multi > static inline void apply(MultiGeometry const& multi_geometry, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& current_output) { - BOOST_ASSERT + BOOST_GEOMETRY_ASSERT ( seg_id.multi_index >= 0 - && seg_id.multi_index < int(boost::size(multi_geometry)) + && static_cast<std::size_t>(seg_id.multi_index) < boost::size(multi_geometry) ); // Call the single-version @@ -348,7 +345,7 @@ template > inline void copy_segments(Geometry const& geometry, SegmentIdentifier const& seg_id, - signed_index_type to_index, + signed_size_type to_index, RobustPolicy const& robust_policy, RangeOut& range_out) { diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index 7ed93f542a..3f81c4dca9 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -22,7 +22,6 @@ # define BOOST_GEOMETRY_DEBUG_IDENTIFIER #endif -#include <boost/assert.hpp> #include <boost/range.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> @@ -358,14 +357,14 @@ inline void enrich_assign(Container& operations, = turn_points[it->turn_index].operations[it->operation_index]; prev_op.enriched.travels_to_ip_index - = static_cast<int>(it->turn_index); + = static_cast<signed_size_type>(it->turn_index); prev_op.enriched.travels_to_vertex_index = it->subject->seg_id.segment_index; if (! first && prev_op.seg_id.segment_index == op.seg_id.segment_index) { - prev_op.enriched.next_ip_index = static_cast<int>(it->turn_index); + prev_op.enriched.next_ip_index = static_cast<signed_size_type>(it->turn_index); } first = false; } diff --git a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp index ef32edeefa..5964f3ba44 100644 --- a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp @@ -37,13 +37,13 @@ struct enrichment_info // vertex to which is free travel after this IP, // so from "segment_index+1" to "travels_to_vertex_index", without IP-s, // can be -1 - signed_index_type travels_to_vertex_index; + signed_size_type travels_to_vertex_index; // same but now IP index, so "next IP index" but not on THIS segment - int travels_to_ip_index; + signed_size_type travels_to_ip_index; // index of next IP on this segment, -1 if there is no one - int next_ip_index; + signed_size_type next_ip_index; }; diff --git a/boost/geometry/algorithms/detail/overlay/follow.hpp b/boost/geometry/algorithms/detail/overlay/follow.hpp index acf38d09ab..22807b5140 100644 --- a/boost/geometry/algorithms/detail/overlay/follow.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow.hpp @@ -163,7 +163,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> static inline void enter(LineStringOut& current_piece, LineString const& , segment_identifier& segment_id, - signed_index_type , Point const& point, + signed_size_type , Point const& point, Operation const& operation, RobustPolicy const& , OutputIterator& ) @@ -186,7 +186,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, - signed_index_type index, Point const& point, + signed_size_type index, Point const& point, Operation const& , RobustPolicy const& robust_policy, OutputIterator& out) @@ -217,7 +217,7 @@ struct action_selector<overlay_intersection, RemoveSpikes> static inline void isolated_point(LineStringOut&, LineString const&, segment_identifier&, - signed_index_type, Point const& point, + signed_size_type, Point const& point, Operation const& , OutputIterator& out) { LineStringOut isolated_point_ls; @@ -268,7 +268,7 @@ struct action_selector<overlay_difference, RemoveSpikes> static inline void enter(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, - signed_index_type index, Point const& point, + signed_size_type index, Point const& point, Operation const& operation, RobustPolicy const& robust_policy, OutputIterator& out) @@ -289,7 +289,7 @@ struct action_selector<overlay_difference, RemoveSpikes> static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, - signed_index_type index, Point const& point, + signed_size_type index, Point const& point, Operation const& operation, RobustPolicy const& robust_policy, OutputIterator& out) @@ -309,7 +309,7 @@ struct action_selector<overlay_difference, RemoveSpikes> static inline void isolated_point(LineStringOut&, LineString const&, segment_identifier&, - signed_index_type, Point const&, + signed_size_type, Point const&, Operation const&, OutputIterator&) { } @@ -496,7 +496,7 @@ public : false, RemoveSpikes >::apply(linestring, current_segment_id, - static_cast<signed_index_type>(boost::size(linestring) - 1), + static_cast<signed_size_type>(boost::size(linestring) - 1), robust_policy, current_piece); } diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp index 7bcc0b951e..b2c3836712 100644 --- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp @@ -14,9 +14,9 @@ #include <algorithm> #include <iterator> -#include <boost/assert.hpp> #include <boost/range.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/tag.hpp> #include <boost/geometry/core/tags.hpp> @@ -142,7 +142,7 @@ static inline bool is_isolated_point(Turn const& turn, if ( turn.method == method_none ) { - BOOST_ASSERT( operation.operation == operation_continue ); + BOOST_GEOMETRY_ASSERT( operation.operation == operation_continue ); return true; } @@ -282,7 +282,7 @@ protected: false, false // do not reverse; do not remove spikes >::apply(linestring, current_segment_id, - static_cast<signed_index_type>(boost::size(linestring) - 1), + static_cast<signed_size_type>(boost::size(linestring) - 1), robust_policy, current_piece); } @@ -327,7 +327,7 @@ public: throw inconsistent_turns_exception(); } #else - BOOST_ASSERT(enter_count == 0); + BOOST_GEOMETRY_ASSERT(enter_count == 0); #endif return process_end(entered, linestring, @@ -404,7 +404,7 @@ protected: }; template <typename TurnIterator> - static inline signed_index_type get_multi_index(TurnIterator it) + static inline signed_size_type get_multi_index(TurnIterator it) { return boost::begin(it->operations)->seg_id.multi_index; } @@ -412,10 +412,10 @@ protected: class has_other_multi_id { private: - signed_index_type m_multi_id; + signed_size_type m_multi_id; public: - has_other_multi_id(signed_index_type multi_id) + has_other_multi_id(signed_size_type multi_id) : m_multi_id(multi_id) {} template <typename Turn> @@ -433,7 +433,7 @@ public: TurnIterator first, TurnIterator beyond, OutputIterator oit) { - BOOST_ASSERT( first != beyond ); + BOOST_GEOMETRY_ASSERT( first != beyond ); typedef copy_linestrings_in_range < @@ -446,7 +446,7 @@ public: // Iterate through all intersection points (they are // ordered along the each linestring) - signed_index_type current_multi_id = get_multi_index(first); + signed_size_type current_multi_id = get_multi_index(first); oit = copy_linestrings::apply(ls_first, ls_first + current_multi_id, @@ -463,7 +463,7 @@ public: oit = Base::apply(*(ls_first + current_multi_id), linear, per_ls_current, per_ls_next, oit); - signed_index_type next_multi_id(-1); + signed_size_type next_multi_id = -1; linestring_iterator ls_next = ls_beyond; if ( per_ls_next != beyond ) { diff --git a/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp index 63011c7d48..4668189924 100644 --- a/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp @@ -12,6 +12,9 @@ #include <cstddef> +#include <boost/mpl/if.hpp> +#include <boost/range.hpp> + #include <boost/geometry/algorithms/convert.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/get_ring.hpp b/boost/geometry/algorithms/detail/overlay/get_ring.hpp index 131d58d582..460c30def3 100644 --- a/boost/geometry/algorithms/detail/overlay/get_ring.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_ring.hpp @@ -10,9 +10,9 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RING_HPP -#include <boost/assert.hpp> #include <boost/range.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/exterior_ring.hpp> #include <boost/geometry/core/interior_rings.hpp> #include <boost/geometry/core/ring_type.hpp> @@ -82,7 +82,7 @@ struct get_ring<polygon_tag> ring_identifier const& id, Polygon const& polygon) { - BOOST_ASSERT + BOOST_GEOMETRY_ASSERT ( id.ring_index >= -1 && id.ring_index < int(boost::size(interior_rings(polygon))) @@ -102,7 +102,7 @@ struct get_ring<multi_polygon_tag> ring_identifier const& id, MultiPolygon const& multi_polygon) { - BOOST_ASSERT + BOOST_GEOMETRY_ASSERT ( id.multi_index >= 0 && id.multi_index < int(boost::size(multi_polygon)) diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index b3b1a06f68..717f0b47a9 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -15,10 +15,10 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP -#include <boost/assert.hpp> #include <boost/core/ignore_unused.hpp> #include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/strategies/intersection.hpp> #include <boost/geometry/algorithms/convert.hpp> @@ -115,7 +115,7 @@ struct base_turn_handler { ti.method = method; - BOOST_ASSERT(index < info.count); + BOOST_GEOMETRY_ASSERT(index < info.count); geometry::convert(info.intersections[index], ti.point); ti.operations[0].fraction = info.fractions[index].robust_ra; @@ -597,7 +597,7 @@ struct collinear : public base_turn_handler int const arrival = dir_info.arrival[0]; // Should not be 0, this is checked before - BOOST_ASSERT(arrival != 0); + BOOST_GEOMETRY_ASSERT(arrival != 0); int const side_p = side.pk_wrt_p1(); int const side_q = side.qk_wrt_q1(); 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 4a3cacbedd..0b3cb72747 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 @@ -14,6 +14,7 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> @@ -153,7 +154,7 @@ public: } else { - BOOST_ASSERT(result.template get<0>().count == 1); + BOOST_GEOMETRY_ASSERT(result.template get<0>().count == 1); ips[0].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last); ips[0].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last); @@ -297,10 +298,10 @@ struct get_turn_info_for_endpoint // may this give false positives for INTs? typename IntersectionResult::point_type const& inters_pt = result.template get<0>().intersections[ip_index]; - BOOST_ASSERT(ip_info.is_pi == equals::equals_point_point(pi, inters_pt)); - BOOST_ASSERT(ip_info.is_qi == equals::equals_point_point(qi, inters_pt)); - BOOST_ASSERT(ip_info.is_pj == equals::equals_point_point(pj, inters_pt)); - BOOST_ASSERT(ip_info.is_qj == equals::equals_point_point(qj, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_info.is_pi == equals::equals_point_point(pi, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_info.is_qi == equals::equals_point_point(qi, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_info.is_pj == equals::equals_point_point(pj, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_info.is_qj == equals::equals_point_point(qj, inters_pt)); #endif // TODO - calculate first/last only if needed @@ -412,8 +413,8 @@ struct get_turn_info_for_endpoint // may this give false positives for INTs? typename IntersectionResult::point_type const& inters_pt = inters.i_info().intersections[ip_index]; - BOOST_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt)); - BOOST_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt)); #endif if ( ip_i2 ) { @@ -448,7 +449,7 @@ struct get_turn_info_for_endpoint } else { - BOOST_ASSERT(operations_combination(operations, operation_intersection, operation_union)); + BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union)); //op1 = operation_union; //op2 = operation_union; } @@ -463,8 +464,8 @@ struct get_turn_info_for_endpoint // may this give false positives for INTs? typename IntersectionResult::point_type const& inters_pt = inters.i_info().intersections[ip_index]; - BOOST_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt)); - BOOST_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt)); + BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt)); #endif if ( ip_i2 ) { @@ -499,7 +500,7 @@ struct get_turn_info_for_endpoint } else { - BOOST_ASSERT(operations_combination(operations, operation_intersection, operation_union)); + BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union)); //op1 = operation_blocked; //op2 = operation_union; } @@ -560,7 +561,7 @@ struct get_turn_info_for_endpoint // NOTE: is_collinear is NOT set for the first endpoint // for which there is no preceding segment - //BOOST_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 ); + //BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 ); if ( ! is_p_first_ip ) { tp.operations[0].is_collinear = op0 != operation_intersection 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 e0d75108b9..e4f8de42e1 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -42,7 +42,8 @@ template <typename PointP, typename PointQ, > struct side_calculator { - typedef boost::geometry::strategy::side::side_by_triangle<> side; // todo: get from coordinate system + // todo: get from coordinate system + typedef boost::geometry::strategy::side::side_by_triangle<> side; inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk, Qi const& qi, Qj const& qj, Qk const& qk) @@ -71,8 +72,9 @@ struct robust_points { typedef typename geometry::robust_point_type < - Point1, RobustPolicy + Point1, RobustPolicy >::type robust_point1_type; + // TODO: define robust_point2_type using Point2? typedef robust_point1_type robust_point2_type; @@ -96,23 +98,23 @@ template <typename Point1, typename Point2, typename RobustPolicy> class intersection_info_base : private robust_points<Point1, Point2, RobustPolicy> { - typedef robust_points<Point1, Point2, RobustPolicy> base_t; + typedef robust_points<Point1, Point2, RobustPolicy> base; public: typedef Point1 point1_type; typedef Point2 point2_type; - typedef typename base_t::robust_point1_type robust_point1_type; - typedef typename base_t::robust_point2_type robust_point2_type; + typedef typename base::robust_point1_type robust_point1_type; + typedef typename base::robust_point2_type robust_point2_type; typedef side_calculator<robust_point1_type, robust_point2_type> side_calculator_type; intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, Point2 const& qi, Point2 const& qj, Point2 const& qk, RobustPolicy const& robust_policy) - : base_t(pi, pj, pk, qi, qj, qk, robust_policy) - , m_side_calc(base_t::m_rpi, base_t::m_rpj, base_t::m_rpk, - base_t::m_rqi, base_t::m_rqj, base_t::m_rqk) + : base(pi, pj, pk, qi, qj, qk, robust_policy) + , m_side_calc(base::m_rpi, base::m_rpj, base::m_rpk, + base::m_rqi, base::m_rqj, base::m_rqk) , m_pi(pi), m_pj(pj), m_pk(pk) , m_qi(qi), m_qj(qj), m_qk(qk) {} @@ -125,13 +127,13 @@ public: inline Point2 const& qj() const { return m_qj; } inline Point2 const& qk() const { return m_qk; } - inline robust_point1_type const& rpi() const { return base_t::m_rpi; } - inline robust_point1_type const& rpj() const { return base_t::m_rpj; } - inline robust_point1_type const& rpk() const { return base_t::m_rpk; } + inline robust_point1_type const& rpi() const { return base::m_rpi; } + inline robust_point1_type const& rpj() const { return base::m_rpj; } + inline robust_point1_type const& rpk() const { return base::m_rpk; } - inline robust_point2_type const& rqi() const { return base_t::m_rqi; } - inline robust_point2_type const& rqj() const { return base_t::m_rqj; } - inline robust_point2_type const& rqk() const { return base_t::m_rqk; } + inline robust_point2_type const& rqi() const { return base::m_rqi; } + inline robust_point2_type const& rqj() const { return base::m_rqj; } + inline robust_point2_type const& rqk() const { return base::m_rqk; } inline side_calculator_type const& sides() const { return m_side_calc; } @@ -187,11 +189,17 @@ private: }; -template <typename Point1, typename Point2, typename TurnPoint, typename RobustPolicy> +template +< + typename Point1, + typename Point2, + typename TurnPoint, + typename RobustPolicy +> class intersection_info : public intersection_info_base<Point1, Point2, RobustPolicy> { - typedef intersection_info_base<Point1, Point2, RobustPolicy> base_t; + typedef intersection_info_base<Point1, Point2, RobustPolicy> base; typedef typename strategy_intersection < @@ -205,7 +213,7 @@ class intersection_info public: typedef model::referring_segment<Point1 const> segment_type1; typedef model::referring_segment<Point2 const> segment_type2; - typedef typename base_t::side_calculator_type side_calculator_type; + typedef typename base::side_calculator_type side_calculator_type; typedef typename strategy::return_type result_type; typedef typename boost::tuples::element<0, result_type>::type i_info_type; // intersection_info @@ -214,10 +222,12 @@ public: intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk, Point2 const& qi, Point2 const& qj, Point2 const& qk, RobustPolicy const& robust_policy) - : base_t(pi, pj, pk, qi, qj, qk, robust_policy) + : base(pi, pj, pk, qi, qj, qk, robust_policy) , m_result(strategy::apply(segment_type1(pi, pj), segment_type2(qi, qj), - robust_policy)) + robust_policy, + base::rpi(), base::rpj(), + base::rqi(), base::rqj())) , m_robust_policy(robust_policy) {} @@ -228,19 +238,22 @@ public: // TODO: it's more like is_spike_ip_p inline bool is_spike_p() const { - if ( base_t::sides().pk_wrt_p1() == 0 ) + if (base::sides().pk_wrt_p1() == 0) { - if ( ! is_ip_j<0>() ) + if (! is_ip_j<0>()) + { return false; + } - int const qk_p1 = base_t::sides().qk_wrt_p1(); - int const qk_p2 = base_t::sides().qk_wrt_p2(); + int const qk_p1 = base::sides().qk_wrt_p1(); + int const qk_p2 = base::sides().qk_wrt_p2(); - if ( qk_p1 == -qk_p2 ) + if (qk_p1 == -qk_p2) { - if ( qk_p1 == 0 ) + if (qk_p1 == 0) { - return is_spike_of_collinear(base_t::pi(), base_t::pj(), base_t::pk()); + return is_spike_of_collinear(base::pi(), base::pj(), + base::pk()); } return true; @@ -253,19 +266,22 @@ public: // TODO: it's more like is_spike_ip_q inline bool is_spike_q() const { - if ( base_t::sides().qk_wrt_q1() == 0 ) + if (base::sides().qk_wrt_q1() == 0) { - if ( ! is_ip_j<1>() ) + if (! is_ip_j<1>()) + { return false; + } - int const pk_q1 = base_t::sides().pk_wrt_q1(); - int const pk_q2 = base_t::sides().pk_wrt_q2(); + int const pk_q1 = base::sides().pk_wrt_q1(); + int const pk_q2 = base::sides().pk_wrt_q2(); - if ( pk_q1 == -pk_q2 ) + if (pk_q1 == -pk_q2) { - if ( pk_q1 == 0 ) + if (pk_q1 == 0) { - return is_spike_of_collinear(base_t::qi(), base_t::qj(), base_t::qk()); + return is_spike_of_collinear(base::qi(), base::qj(), + base::qk()); } return true; @@ -277,9 +293,10 @@ public: private: template <typename Point> - inline bool is_spike_of_collinear(Point const& i, Point const& j, Point const& k) const + inline bool is_spike_of_collinear(Point const& i, Point const& j, + Point const& k) const { - typedef model::referring_segment<Point const> seg_t; + typedef model::referring_segment<Point const> seg; typedef strategy_intersection < @@ -289,7 +306,7 @@ private: typedef typename si::segment_intersection_strategy_type strategy; typename strategy::return_type result - = strategy::apply(seg_t(i, j), seg_t(j, k), m_robust_policy); + = strategy::apply(seg(i, j), seg(j, k), m_robust_policy); return result.template get<0>().count == 2; } @@ -300,9 +317,9 @@ private: int arrival = d_info().arrival[OpId]; bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0; - if ( same_dirs ) + if (same_dirs) { - if ( i_info().count == 2 ) + if (i_info().count == 2) { return arrival != -1; } 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 71946543ee..ccb42d4c92 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp @@ -14,6 +14,8 @@ #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/core/assert.hpp> + #include <boost/geometry/util/condition.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> @@ -569,7 +571,7 @@ struct get_turn_info_linear_areal tp.operations[0].is_collinear = true; //tp.operations[1].is_collinear = false; - BOOST_ASSERT(inters.i_info().count > 1); + BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1); base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); @@ -816,7 +818,7 @@ struct get_turn_info_linear_areal if ( inters.i_info().count > 1 ) { - //BOOST_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 ); + //BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 ); tp.operations[0].is_collinear = true; tp.operations[1].operation = opposite ? operation_continue : operation_union; } 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 1ec88e54a0..19f0859cbb 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp @@ -14,6 +14,8 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP +#include <boost/geometry/core/assert.hpp> + #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp> @@ -579,7 +581,7 @@ struct get_turn_info_linear_linear tp.operations[0].is_collinear = true; tp.operations[1].is_collinear = false; - BOOST_ASSERT(inters.i_info().count > 1); + BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1); base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); @@ -612,7 +614,7 @@ struct get_turn_info_linear_linear tp.operations[0].is_collinear = false; tp.operations[1].is_collinear = true; - BOOST_ASSERT(inters.i_info().count > 0); + BOOST_GEOMETRY_ASSERT(inters.i_info().count > 0); base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 0); @@ -686,7 +688,7 @@ struct get_turn_info_linear_linear operation_type & op0 = turn.operations[0].operation; operation_type & op1 = turn.operations[1].operation; - BOOST_ASSERT(op0 != operation_blocked || op1 != operation_blocked ); + BOOST_GEOMETRY_ASSERT(op0 != operation_blocked || op1 != operation_blocked ); if ( op0 == operation_blocked ) { diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index a5d8f3f023..098c7b5642 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -22,6 +22,7 @@ #include <boost/array.hpp> #include <boost/concept_check.hpp> #include <boost/mpl/if.hpp> +#include <boost/mpl/vector_c.hpp> #include <boost/range.hpp> #include <boost/geometry/core/access.hpp> @@ -142,7 +143,7 @@ class get_turns_in_sections template <typename Geometry, typename Section> static inline bool neighbouring(Section const& section, - int index1, int index2) + signed_size_type index1, signed_size_type index2) { // About n-2: // (square: range_count=5, indices 0,1,2,3 @@ -150,7 +151,7 @@ class get_turns_in_sections // Also tested for open polygons, and/or duplicates // About first condition: will be optimized by compiler (static) // It checks if it is areal (box,ring,(multi)polygon - int const n = int(section.range_count); + signed_size_type const n = static_cast<signed_size_type>(section.range_count); boost::ignore_unused_variable_warning(n); boost::ignore_unused_variable_warning(index1); @@ -207,8 +208,8 @@ public : int const dir1 = sec1.directions[0]; int const dir2 = sec2.directions[0]; - int index1 = sec1.begin_index; - int ndi1 = sec1.non_duplicate_index; + signed_size_type index1 = sec1.begin_index; + signed_size_type ndi1 = sec1.non_duplicate_index; bool const same_source = source_id1 == source_id2 @@ -236,8 +237,8 @@ public : begin_range_1, end_range_1, next1, true); advance_to_non_duplicate_next(nd_next1, it1, sec1, robust_policy); - int index2 = sec2.begin_index; - int ndi2 = sec2.non_duplicate_index; + signed_size_type index2 = sec2.begin_index; + signed_size_type ndi2 = sec2.non_duplicate_index; range2_iterator prev2, it2, end2; @@ -359,7 +360,7 @@ private : typename boost::range_iterator<Range const>::type& it, typename boost::range_iterator<Range const>::type& prev, typename boost::range_iterator<Range const>::type& end, - int& index, int& ndi, + signed_size_type& index, signed_size_type& ndi, int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy) { it = boost::begin(range) + section.begin_index; @@ -524,8 +525,8 @@ struct get_turns_cs RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - signed_index_type multi_index = -1, - signed_index_type ring_index = -1) + signed_size_type multi_index = -1, + signed_size_type ring_index = -1) { if ( boost::size(range) <= 1) { @@ -552,7 +553,7 @@ struct get_turns_cs //char previous_side[2] = {0, 0}; - signed_index_type index = 0; + signed_size_type index = 0; for (iterator_type prev = it++; it != boost::end(view); @@ -696,7 +697,7 @@ struct get_turns_polygon_cs int source_id2, Box const& box, RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy, - signed_index_type multi_index = -1) + signed_size_type multi_index = -1) { typedef typename geometry::ring_type<Polygon>::type ring_type; @@ -714,7 +715,7 @@ struct get_turns_polygon_cs turns, interrupt_policy, multi_index, -1); - signed_index_type i = 0; + signed_size_type i = 0; typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -753,7 +754,7 @@ struct get_turns_multi_polygon_cs Multi const >::type iterator_type; - signed_index_type i = 0; + signed_size_type i = 0; for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it, ++i) diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index 3101de8c35..af0731f5a9 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -1,9 +1,9 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2014. -// Modifications copyright (c) 2014 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015. +// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -39,9 +39,11 @@ #include <boost/geometry/policies/robustness/get_rescale_policy.hpp> #include <boost/geometry/views/segment_view.hpp> +#include <boost/geometry/views/detail/boundary_view.hpp> #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp> #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> +#include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp> #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW) #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> @@ -283,7 +285,8 @@ namespace dispatch template < // real types - typename Geometry1, typename Geometry2, + typename Geometry1, + typename Geometry2, typename GeometryOut, overlay_type OverlayType, // orientation @@ -409,13 +412,13 @@ struct intersection_insert template <typename RobustPolicy, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Linestring const& linestring, Box const& box, - RobustPolicy const& , + RobustPolicy const& robust_policy, OutputIterator out, Strategy const& ) { typedef typename point_type<GeometryOut>::type point_type; strategy::intersection::liang_barsky<Box, point_type> lb_strategy; return detail::intersection::clip_range_with_box - <GeometryOut>(box, linestring, out, lb_strategy); + <GeometryOut>(box, linestring, robust_policy, out, lb_strategy); } }; @@ -487,7 +490,7 @@ struct intersection_insert template <typename RobustPolicy, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Segment const& segment, Box const& box, - RobustPolicy const& ,// TODO: propagate to clip_range_with_box + RobustPolicy const& robust_policy, OutputIterator out, Strategy const& ) { geometry::segment_view<Segment> range(segment); @@ -495,7 +498,7 @@ struct intersection_insert typedef typename point_type<GeometryOut>::type point_type; strategy::intersection::liang_barsky<Box, point_type> lb_strategy; return detail::intersection::clip_range_with_box - <GeometryOut>(box, range, out, lb_strategy); + <GeometryOut>(box, range, robust_policy, out, lb_strategy); } }; @@ -573,6 +576,46 @@ struct intersection_insert_reversed }; +// dispatch for intersection(areal, areal, linear) +template +< + typename Geometry1, typename Geometry2, + typename LinestringOut, + bool Reverse1, bool Reverse2, bool ReverseOut, + typename Tag1, typename Tag2 +> +struct intersection_insert + < + Geometry1, Geometry2, + LinestringOut, + overlay_intersection, + Reverse1, Reverse2, ReverseOut, + Tag1, Tag2, linestring_tag, + true, true, false + > +{ + template + < + typename RobustPolicy, typename OutputIterator, typename Strategy + > + static inline OutputIterator apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + RobustPolicy const& robust_policy, + OutputIterator oit, + Strategy const& strategy) + { + detail::boundary_view<Geometry1 const> view1(geometry1); + detail::boundary_view<Geometry2 const> view2(geometry2); + + return detail::overlay::linear_linear_linestring + < + detail::boundary_view<Geometry1 const>, + detail::boundary_view<Geometry2 const>, + LinestringOut, + overlay_intersection + >::apply(view1, view2, robust_policy, oit, strategy); + } +}; // dispatch for non-areal geometries template @@ -700,6 +743,79 @@ struct intersection_insert {}; +// dispatch for difference/intersection of pointlike-linear geometries +template +< + typename Point, typename Linear, typename PointOut, + overlay_type OverlayType, + bool Reverse1, bool Reverse2, bool ReverseOut, + typename Tag +> +struct intersection_insert + < + Point, Linear, PointOut, OverlayType, + Reverse1, Reverse2, ReverseOut, + point_tag, Tag, point_tag, + false, false, false + > : detail_dispatch::overlay::pointlike_linear_point + < + Point, Linear, PointOut, OverlayType, + point_tag, typename tag_cast<Tag, segment_tag, linear_tag>::type + > +{}; + + +template +< + typename MultiPoint, typename Linear, typename PointOut, + overlay_type OverlayType, + bool Reverse1, bool Reverse2, bool ReverseOut, + typename Tag +> +struct intersection_insert + < + MultiPoint, Linear, PointOut, OverlayType, + Reverse1, Reverse2, ReverseOut, + multi_point_tag, Tag, point_tag, + false, false, false + > : detail_dispatch::overlay::pointlike_linear_point + < + MultiPoint, Linear, PointOut, OverlayType, + multi_point_tag, + typename tag_cast<Tag, segment_tag, linear_tag>::type + > +{}; + + +template +< + typename Linestring, typename MultiPoint, typename PointOut, + bool Reverse1, bool Reverse2, bool ReverseOut +> +struct intersection_insert + < + Linestring, MultiPoint, PointOut, overlay_intersection, + Reverse1, Reverse2, ReverseOut, + linestring_tag, multi_point_tag, point_tag, + false, false, false + > +{ + template <typename RobustPolicy, typename OutputIterator, typename Strategy> + static inline OutputIterator apply(Linestring const& linestring, + MultiPoint const& multipoint, + RobustPolicy const& robust_policy, + OutputIterator out, + Strategy const& strategy) + { + return detail_dispatch::overlay::pointlike_linear_point + < + MultiPoint, Linestring, PointOut, overlay_intersection, + multi_point_tag, linear_tag + >::apply(multipoint, linestring, robust_policy, out, strategy); + } +}; + + } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH diff --git a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp index d4ebcf296b..34517f6590 100644 --- a/boost/geometry/algorithms/detail/overlay/linear_linear.hpp +++ b/boost/geometry/algorithms/detail/overlay/linear_linear.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2015, Oracle and/or its affiliates. // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -157,13 +157,18 @@ protected: < typename Turns, typename LinearGeometry1, - typename LinearGeometry2 + typename LinearGeometry2, + typename RobustPolicy > static inline void compute_turns(Turns& turns, LinearGeometry1 const& linear1, - LinearGeometry2 const& linear2) + LinearGeometry2 const& linear2, + RobustPolicy const& robust_policy) { turns.clear(); + + detail::get_turns::no_interrupt_policy interrupt_policy; + geometry::detail::relate::turns::get_turns < LinearGeometry1, @@ -173,8 +178,9 @@ protected: LinearGeometry1, LinearGeometry2, assign_policy - > - >::apply(turns, linear1, linear2); + >, + RobustPolicy + >::apply(turns, linear1, linear2, interrupt_policy, robust_policy); } @@ -229,19 +235,27 @@ public: > static inline OutputIterator apply(Linear1 const& linear1, Linear2 const& linear2, - RobustPolicy const&, + RobustPolicy const& robust_policy, OutputIterator oit, Strategy const& ) { typedef typename detail::relate::turns::get_turns < - Linear1, Linear2 + Linear1, + Linear2, + detail::get_turns::get_turn_info_type + < + Linear1, + Linear2, + assign_policy + >, + RobustPolicy >::turn_info turn_info; typedef std::vector<turn_info> turns_container; turns_container turns; - compute_turns(turns, linear1, linear2); + compute_turns(turns, linear1, linear2, robust_policy); if ( turns.empty() ) { diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index a2f52848d1..baf9d4777d 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -1,7 +1,12 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, 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 @@ -28,7 +33,7 @@ #include <boost/geometry/algorithms/detail/recalculate.hpp> -#include <boost/geometry/algorithms/num_points.hpp> +#include <boost/geometry/algorithms/is_empty.hpp> #include <boost/geometry/algorithms/reverse.hpp> #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp> @@ -125,8 +130,7 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, // Intersection: return nothing // Difference: return first of them if (Direction == overlay_intersection - || (Direction == overlay_difference - && geometry::num_points(geometry1) == 0)) + || (Direction == overlay_difference && geometry::is_empty(geometry1))) { return out; } @@ -162,14 +166,15 @@ struct overlay OutputIterator out, Strategy const& ) { - if ( geometry::num_points(geometry1) == 0 - && geometry::num_points(geometry2) == 0 ) + bool const is_empty1 = geometry::is_empty(geometry1); + bool const is_empty2 = geometry::is_empty(geometry2); + + if (is_empty1 && is_empty2) { return out; } - if ( geometry::num_points(geometry1) == 0 - || geometry::num_points(geometry2) == 0 ) + if (is_empty1 || is_empty2) { return return_if_one_input_is_empty < diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp new file mode 100644 index 0000000000..156cb54867 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp @@ -0,0 +1,343 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015, Oracle and/or its affiliates. + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP + +#include <iterator> +#include <vector> + +#include <boost/range.hpp> + +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/geometries/box.hpp> + +#include <boost/geometry/iterators/segment_iterator.hpp> + +#include <boost/geometry/algorithms/disjoint.hpp> +#include <boost/geometry/algorithms/envelope.hpp> +#include <boost/geometry/algorithms/expand.hpp> +#include <boost/geometry/algorithms/not_implemented.hpp> + +#include <boost/geometry/algorithms/detail/not.hpp> +#include <boost/geometry/algorithms/detail/partition.hpp> +#include <boost/geometry/algorithms/detail/relate/less.hpp> +#include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> +#include <boost/geometry/algorithms/detail/equals/point_point.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> +#include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + + +// action struct for pointlike-linear difference/intersection +// it works the same as its pointlike-pointlike counterpart, hence the +// derivation +template <typename PointOut, overlay_type OverlayType> +struct action_selector_pl_l + : action_selector_pl_pl<PointOut, OverlayType> +{}; + +// difference/intersection of point-linear +template +< + typename Point, + typename Linear, + typename PointOut, + overlay_type OverlayType, + typename Policy +> +struct point_linear_point +{ + template <typename RobustPolicy, typename OutputIterator, typename Strategy> + static inline OutputIterator apply(Point const& point, + Linear const& linear, + RobustPolicy const&, + OutputIterator oit, + Strategy const&) + { + action_selector_pl_l + < + PointOut, OverlayType + >::apply(point, Policy::apply(point, linear), oit); + return oit; + } +}; + +// difference/intersection of multipoint-segment +template +< + typename MultiPoint, + typename Segment, + typename PointOut, + overlay_type OverlayType, + typename Policy +> +struct multipoint_segment_point +{ + template <typename RobustPolicy, typename OutputIterator, typename Strategy> + static inline OutputIterator apply(MultiPoint const& multipoint, + Segment const& segment, + RobustPolicy const&, + OutputIterator oit, + Strategy const&) + { + for (typename boost::range_iterator<MultiPoint const>::type + it = boost::begin(multipoint); + it != boost::end(multipoint); + ++it) + { + action_selector_pl_l + < + PointOut, OverlayType + >::apply(*it, Policy::apply(*it, segment), oit); + } + + return oit; + } +}; + + +// difference/intersection of multipoint-linear +template +< + typename MultiPoint, + typename Linear, + typename PointOut, + overlay_type OverlayType, + typename Policy +> +class multipoint_linear_point +{ +private: + // structs for partition -- start + struct expand_box + { + template <typename Box, typename Geometry> + static inline void apply(Box& total, Geometry const& geometry) + { + geometry::expand(total, geometry::return_envelope<Box>(geometry)); + } + + }; + + struct overlaps_box + { + template <typename Box, typename Geometry> + static inline bool apply(Box const& box, Geometry const& geometry) + { + return ! geometry::disjoint(geometry, box); + } + }; + + template <typename OutputIterator> + class item_visitor_type + { + public: + item_visitor_type(OutputIterator& oit) : m_oit(oit) {} + + template <typename Item1, typename Item2> + inline void apply(Item1 const& item1, Item2 const& item2) + { + action_selector_pl_l + < + PointOut, overlay_intersection + >::apply(item1, Policy::apply(item1, item2), m_oit); + } + + private: + OutputIterator& m_oit; + }; + // structs for partition -- end + + class segment_range + { + public: + typedef geometry::segment_iterator<Linear const> const_iterator; + typedef const_iterator iterator; + + segment_range(Linear const& linear) + : m_linear(linear) + {} + + const_iterator begin() const + { + return geometry::segments_begin(m_linear); + } + + const_iterator end() const + { + return geometry::segments_end(m_linear); + } + + private: + Linear const& m_linear; + }; + + template <typename OutputIterator> + static inline OutputIterator get_common_points(MultiPoint const& multipoint, + Linear const& linear, + OutputIterator oit) + { + item_visitor_type<OutputIterator> item_visitor(oit); + + segment_range rng(linear); + + geometry::partition + < + geometry::model::box + < + typename boost::range_value<MultiPoint>::type + >, + expand_box, + overlaps_box + >::apply(multipoint, rng, item_visitor); + + return oit; + } + +public: + template <typename RobustPolicy, typename OutputIterator, typename Strategy> + static inline OutputIterator apply(MultiPoint const& multipoint, + Linear const& linear, + RobustPolicy const& robust_policy, + OutputIterator oit, + Strategy const& strategy) + { + typedef std::vector + < + typename boost::range_value<MultiPoint>::type + > point_vector_type; + + point_vector_type common_points; + + // compute the common points + get_common_points(multipoint, linear, + std::back_inserter(common_points)); + + return multipoint_multipoint_point + < + MultiPoint, point_vector_type, PointOut, OverlayType + >::apply(multipoint, common_points, robust_policy, oit, strategy); + } +}; + + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace detail_dispatch { namespace overlay +{ + +// dispatch struct for pointlike-linear difference/intersection computation +template +< + typename PointLike, + typename Linear, + typename PointOut, + overlay_type OverlayType, + typename Tag1, + typename Tag2 +> +struct pointlike_linear_point + : not_implemented<PointLike, Linear, PointOut> +{}; + + +template +< + typename Point, + typename Linear, + typename PointOut, + overlay_type OverlayType +> +struct pointlike_linear_point + < + Point, Linear, PointOut, OverlayType, point_tag, linear_tag + > : detail::overlay::point_linear_point + < + Point, Linear, PointOut, OverlayType, + detail::not_<detail::disjoint::reverse_covered_by> + > +{}; + + +template +< + typename Point, + typename Segment, + typename PointOut, + overlay_type OverlayType +> +struct pointlike_linear_point + < + Point, Segment, PointOut, OverlayType, point_tag, segment_tag + > : detail::overlay::point_linear_point + < + Point, Segment, PointOut, OverlayType, + detail::not_<detail::disjoint::reverse_covered_by> + > +{}; + + +template +< + typename MultiPoint, + typename Linear, + typename PointOut, + overlay_type OverlayType +> +struct pointlike_linear_point + < + MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag + > : detail::overlay::multipoint_linear_point + < + MultiPoint, Linear, PointOut, OverlayType, + detail::not_<detail::disjoint::reverse_covered_by> + > +{}; + + +template +< + typename MultiPoint, + typename Segment, + typename PointOut, + overlay_type OverlayType +> +struct pointlike_linear_point + < + MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag + > : detail::overlay::multipoint_segment_point + < + MultiPoint, Segment, PointOut, OverlayType, + detail::not_<detail::disjoint::reverse_covered_by> + > +{}; + + +}} // namespace detail_dispatch::overlay +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP diff --git a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp index 0af062d271..438a377876 100644 --- a/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp +++ b/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2015, Oracle and/or its affiliates. // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -14,9 +14,9 @@ #include <algorithm> #include <vector> -#include <boost/assert.hpp> #include <boost/range.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/point_type.hpp> #include <boost/geometry/core/tag.hpp> #include <boost/geometry/core/tags.hpp> @@ -182,7 +182,7 @@ struct multipoint_point_point OutputIterator oit, Strategy const&) { - BOOST_ASSERT( OverlayType == overlay_difference ); + BOOST_GEOMETRY_ASSERT( OverlayType == overlay_difference ); for (typename boost::range_iterator<MultiPoint const>::type it = boost::begin(multipoint); @@ -264,7 +264,7 @@ struct multipoint_multipoint_point >::apply(multipoint2, multipoint1, robust_policy, oit, strategy); } - std::vector<typename point_type<MultiPoint2>::type> + std::vector<typename boost::range_value<MultiPoint2>::type> points2(boost::begin(multipoint2), boost::end(multipoint2)); std::sort(points2.begin(), points2.end(), detail::relate::less()); diff --git a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp index b469052c84..0f2da67b62 100644 --- a/boost/geometry/algorithms/detail/overlay/ring_properties.hpp +++ b/boost/geometry/algorithms/detail/overlay/ring_properties.hpp @@ -29,6 +29,8 @@ struct ring_properties typedef Point point_type; typedef typename default_area_result<Point>::type area_type; + bool valid; + // Filled by "select_rings" Point point; area_type area; @@ -43,7 +45,8 @@ struct ring_properties std::vector<ring_identifier> children; inline ring_properties() - : area(area_type()) + : valid(false) + , area(area_type()) , reversed(false) , discarded(false) , parent_area(-1) @@ -59,7 +62,7 @@ struct ring_properties // 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); + valid = geometry::point_on_border(this->point, ring_or_box, true); } inline area_type get_area() const diff --git a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp index 516ec349e8..e77a163dd5 100644 --- a/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp +++ b/boost/geometry/algorithms/detail/overlay/segment_identifier.hpp @@ -19,7 +19,7 @@ #endif -#include <boost/geometry/algorithms/detail/signed_index_type.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> namespace boost { namespace geometry @@ -40,10 +40,10 @@ struct segment_identifier , segment_index(-1) {} - inline segment_identifier(signed_index_type src, - signed_index_type mul, - signed_index_type rin, - signed_index_type seg) + inline segment_identifier(signed_size_type src, + signed_size_type mul, + signed_size_type rin, + signed_size_type seg) : source_index(src) , multi_index(mul) , ring_index(rin) @@ -81,10 +81,10 @@ struct segment_identifier } #endif - signed_index_type source_index; - signed_index_type multi_index; - signed_index_type ring_index; - signed_index_type segment_index; + signed_size_type source_index; + signed_size_type multi_index; + signed_size_type ring_index; + signed_size_type segment_index; }; diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp index b1f984ffe1..a74cb83f77 100644 --- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp @@ -12,6 +12,7 @@ #include <cstddef> +#include <boost/mpl/vector_c.hpp> #include <boost/range.hpp> #include <boost/geometry/core/access.hpp> diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index 59d2ba703e..803a164711 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -18,6 +18,7 @@ #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/algorithms/num_points.hpp> #include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/closure.hpp> #include <boost/geometry/core/coordinate_dimension.hpp> #include <boost/geometry/geometries/concepts/check.hpp> @@ -116,8 +117,8 @@ inline bool assign_next_ip(G1 const& g1, G2 const& g2, return false; } - BOOST_ASSERT(info.enriched.travels_to_vertex_index >= 0); - BOOST_ASSERT(info.enriched.travels_to_ip_index >= 0); + BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_vertex_index >= 0); + BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_ip_index >= 0); if (info.seg_id.source_index == 0) { @@ -150,8 +151,8 @@ inline bool assign_next_ip(G1 const& g1, G2 const& g2, inline bool select_source(operation_type operation, - signed_index_type source1, - signed_index_type source2) + signed_size_type source1, + signed_size_type source2) { return (operation == operation_intersection && source1 != source2) || (operation == operation_union && source1 == source2) |