diff options
| author | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:41:18 +0900 |
|---|---|---|
| committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2016-10-06 10:43:11 +0900 |
| commit | f763a99a501650eff2c60288aa6f10ef916d769e (patch) | |
| tree | 02af7e13f9a38c888ebf340fe764cbe7dae99da9 /boost/geometry/algorithms/detail | |
| parent | 5cde13f21d36c7224b0e13d11c4b49379ae5210d (diff) | |
| download | boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.gz boost-f763a99a501650eff2c60288aa6f10ef916d769e.tar.bz2 boost-f763a99a501650eff2c60288aa6f10ef916d769e.zip | |
Imported Upstream version 1.62.0upstream/1.62.0
Change-Id: I9d4c1ddb7b7d8f0069217ecc582700f9fda6dd4c
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail')
53 files changed, 2201 insertions, 1364 deletions
diff --git a/boost/geometry/algorithms/detail/assign_box_corners.hpp b/boost/geometry/algorithms/detail/assign_box_corners.hpp index 669d6d3655..bd8b84afcf 100644 --- a/boost/geometry/algorithms/detail/assign_box_corners.hpp +++ b/boost/geometry/algorithms/detail/assign_box_corners.hpp @@ -54,8 +54,8 @@ inline void assign_box_corners(Box const& box, Point& lower_left, Point& lower_right, Point& upper_left, Point& upper_right) { - concept::check<Box const>(); - concept::check<Point>(); + concepts::check<Box const>(); + concepts::check<Point>(); detail::assign::assign_box_2d_corner <min_corner, min_corner>(box, lower_left); diff --git a/boost/geometry/algorithms/detail/assign_indexed_point.hpp b/boost/geometry/algorithms/detail/assign_indexed_point.hpp index acfc37e250..e5d9358c13 100644 --- a/boost/geometry/algorithms/detail/assign_indexed_point.hpp +++ b/boost/geometry/algorithms/detail/assign_indexed_point.hpp @@ -46,8 +46,8 @@ namespace detail template <std::size_t Index, typename Geometry, typename Point> inline void assign_point_to_index(Point const& point, Geometry& geometry) { - concept::check<Point const>(); - concept::check<Geometry>(); + concepts::check<Point const>(); + concepts::check<Geometry>(); detail::assign::assign_point_to_index < @@ -74,8 +74,8 @@ inline void assign_point_to_index(Point const& point, Geometry& geometry) template <std::size_t Index, typename Point, typename Geometry> inline void assign_point_from_index(Geometry const& geometry, Point& point) { - concept::check<Geometry const>(); - concept::check<Point>(); + concepts::check<Geometry const>(); + concepts::check<Point>(); detail::assign::assign_point_from_index < diff --git a/boost/geometry/algorithms/detail/azimuth.hpp b/boost/geometry/algorithms/detail/azimuth.hpp index f0a8d65c86..8948bf6afd 100644 --- a/boost/geometry/algorithms/detail/azimuth.hpp +++ b/boost/geometry/algorithms/detail/azimuth.hpp @@ -49,7 +49,7 @@ struct azimuth<ReturnType, geographic_tag> template <typename P1, typename P2, typename Spheroid> static inline ReturnType apply(P1 const& p1, P2 const& p2, Spheroid const& spheroid) { - return geometry::detail::vincenty_inverse<ReturnType, false, true> + return geometry::detail::vincenty_inverse<ReturnType, false, true>().apply ( get_as_radian<0>(p1), get_as_radian<1>(p1), get_as_radian<0>(p2), get_as_radian<1>(p2), spheroid ).azimuth; diff --git a/boost/geometry/algorithms/detail/buffer/buffer_policies.hpp b/boost/geometry/algorithms/detail/buffer/buffer_policies.hpp index c0fa7b0e33..c1f04f93b5 100644 --- a/boost/geometry/algorithms/detail/buffer/buffer_policies.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffer_policies.hpp @@ -58,14 +58,14 @@ public : static inline void apply(std::size_t size_at_start, Rings& rings, typename boost::range_value<Rings>::type& ring, Turns& turns, - typename boost::range_value<Turns>::type const& turn, + typename boost::range_value<Turns>::type const& /*turn*/, Operation& operation, - detail::overlay::traverse_error_type traverse_error, + detail::overlay::traverse_error_type /*traverse_error*/, Geometry const& , Geometry const& , RobustPolicy const& , state_type& state, - Visitor& visitor + Visitor& /*visitor*/ ) { #if defined(BOOST_GEOMETRY_COUNT_BACKTRACK_WARNINGS) @@ -92,17 +92,17 @@ g_backtrack_warning_count++; struct buffer_overlay_visitor { public : - void print(char const* header) + void print(char const* /*header*/) { } template <typename Turns> - void print(char const* header, Turns const& turns, int turn_index) + void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/) { } template <typename Turns> - void print(char const* header, Turns const& turns, int turn_index, int op_index) + void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/, int /*op_index*/) { } @@ -113,7 +113,7 @@ public : void visit_clusters(Clusters const& , Turns const& ) {} template <typename Turns, typename Turn, typename Operation> - void visit_traverse(Turns const& turns, Turn const& turn, Operation const& op, const char* header) + void visit_traverse(Turns const& /*turns*/, Turn const& /*turn*/, Operation const& /*op*/, const char* /*header*/) { } diff --git a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp index 3fc3c2347a..e7214428e6 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp @@ -35,6 +35,7 @@ #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp> #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> +#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp> #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp> #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp> @@ -297,7 +298,7 @@ struct buffered_piece_collection typedef std::map < signed_size_type, - std::set<signed_size_type> + detail::overlay::cluster_info > cluster_type; cluster_type m_clusters; @@ -1216,9 +1217,8 @@ struct buffered_piece_collection typename cs_tag<Ring>::type >::type side_strategy_type; - enrich_intersection_points<false, false, overlay_union>(m_turns, - m_clusters, detail::overlay::operation_union, - offsetted_rings, offsetted_rings, + enrich_intersection_points<false, false, overlay_buffer>(m_turns, + m_clusters, offsetted_rings, offsetted_rings, m_robust_policy, side_strategy_type()); } @@ -1330,17 +1330,12 @@ struct buffered_piece_collection for (typename boost::range_iterator<turn_vector_type>::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { - if (it->location != location_ok) + buffer_turn_info_type& turn = *it; + if (turn.location != location_ok) { - // Set it to blocked. They should not be discarded, to avoid - // generating rings over these turns - // Performance goes down a tiny bit from 161 s to 173 because there - // are sometimes much more turns. - // We might speed it up a bit by keeping only one blocked - // intersection per segment, but that is complex to program - // because each turn involves two segments - it->operations[0].operation = detail::overlay::operation_blocked; - it->operations[1].operation = detail::overlay::operation_blocked; + // Discard this turn (don't set it to blocked to avoid colocated + // clusters being discarded afterwards + turn.discarded = true; } } } @@ -1352,7 +1347,7 @@ struct buffered_piece_collection false, false, buffered_ring_collection<buffered_ring<Ring> >, buffered_ring_collection<buffered_ring<Ring > >, - detail::overlay::operation_union, + overlay_buffer, backtrack_for_buffer > traverser; diff --git a/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp b/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp index db6136e1ae..4fd24b1451 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_ring.hpp @@ -16,6 +16,8 @@ #include <boost/geometry/core/assert.hpp> #include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/point_order.hpp> #include <boost/geometry/core/point_type.hpp> #include <boost/geometry/strategies/buffer.hpp> @@ -147,6 +149,20 @@ struct ring_type typedef Ring type; }; + +// There is a specific tag, so this specialization cannot be placed in traits +template <typename Ring> +struct point_order<detail::buffer::buffered_ring_collection_tag, + geometry::detail::buffer::buffered_ring_collection + < + geometry::detail::buffer::buffered_ring<Ring> + > > +{ + static const order_selector value + = core_dispatch::point_order<ring_tag, Ring>::value; +}; + + } diff --git a/boost/geometry/algorithms/detail/comparable_distance/interface.hpp b/boost/geometry/algorithms/detail/comparable_distance/interface.hpp index 86eec4c036..3e48a05ba9 100644 --- a/boost/geometry/algorithms/detail/comparable_distance/interface.hpp +++ b/boost/geometry/algorithms/detail/comparable_distance/interface.hpp @@ -318,8 +318,8 @@ inline typename comparable_distance_result<Geometry1, Geometry2, Strategy>::type comparable_distance(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return resolve_variant::comparable_distance < @@ -350,8 +350,8 @@ template <typename Geometry1, typename Geometry2> inline typename default_comparable_distance_result<Geometry1, Geometry2>::type comparable_distance(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return geometry::comparable_distance(geometry1, geometry2, default_strategy()); } diff --git a/boost/geometry/algorithms/detail/disjoint/interface.hpp b/boost/geometry/algorithms/detail/disjoint/interface.hpp index 18c010731e..ce7fe6d45c 100644 --- a/boost/geometry/algorithms/detail/disjoint/interface.hpp +++ b/boost/geometry/algorithms/detail/disjoint/interface.hpp @@ -73,7 +73,7 @@ struct disjoint { static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check_concepts_and_equal_dimensions + concepts::check_concepts_and_equal_dimensions < Geometry1 const, Geometry2 const diff --git a/boost/geometry/algorithms/detail/distance/interface.hpp b/boost/geometry/algorithms/detail/distance/interface.hpp index 1e7cc433ef..53d24d9920 100644 --- a/boost/geometry/algorithms/detail/distance/interface.hpp +++ b/boost/geometry/algorithms/detail/distance/interface.hpp @@ -361,8 +361,8 @@ distance(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); detail::throw_on_empty_input(geometry1); detail::throw_on_empty_input(geometry2); @@ -392,8 +392,8 @@ inline typename default_distance_result<Geometry1, Geometry2>::type distance(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return geometry::distance(geometry1, geometry2, default_strategy()); } diff --git a/boost/geometry/algorithms/detail/envelope/interface.hpp b/boost/geometry/algorithms/detail/envelope/interface.hpp index 997ac1b23e..befe4e42db 100644 --- a/boost/geometry/algorithms/detail/envelope/interface.hpp +++ b/boost/geometry/algorithms/detail/envelope/interface.hpp @@ -40,8 +40,8 @@ struct envelope template <typename Box> static inline void apply(Geometry const& geometry, Box& box) { - concept::check<Geometry const>(); - concept::check<Box>(); + concepts::check<Geometry const>(); + concepts::check<Box>(); dispatch::envelope<Geometry>::apply(geometry, box); } diff --git a/boost/geometry/algorithms/detail/envelope/transform_units.hpp b/boost/geometry/algorithms/detail/envelope/transform_units.hpp index 0c5382a47b..790f6e386b 100644 --- a/boost/geometry/algorithms/detail/envelope/transform_units.hpp +++ b/boost/geometry/algorithms/detail/envelope/transform_units.hpp @@ -92,7 +92,7 @@ inline void transform_units(GeometryIn const& geometry_in, < GeometryIn, GeometryOut >::apply(geometry_in, geometry_out); -}; +} }} // namespace detail::envelope diff --git a/boost/geometry/algorithms/detail/equals/collect_vectors.hpp b/boost/geometry/algorithms/detail/equals/collect_vectors.hpp index dc1cd74900..eab73ea680 100644 --- a/boost/geometry/algorithms/detail/equals/collect_vectors.hpp +++ b/boost/geometry/algorithms/detail/equals/collect_vectors.hpp @@ -19,11 +19,14 @@ #include <boost/numeric/conversion/cast.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> +#include <boost/geometry/algorithms/detail/normalize.hpp> #include <boost/geometry/core/cs.hpp> #include <boost/geometry/core/interior_rings.hpp> #include <boost/geometry/core/tags.hpp> +#include <boost/geometry/formulas/spherical.hpp> + #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/util/math.hpp> @@ -33,31 +36,61 @@ namespace boost { namespace geometry { -// TODO: if Boost.LA of Emil Dotchevski is accepted, adapt this -template <typename T> +// Since these vectors (though ray would be a better name) are used in the +// implementation of equals() for Areal geometries the internal representation +// should be consistent with the default side strategy for CS because currently +// it's used in other relops. + +template < + typename T, + typename Geometry, + typename CSTag = typename cs_tag<Geometry>::type +> struct collected_vector { typedef T type; - + inline collected_vector() {} inline collected_vector(T const& px, T const& py, - T const& pdx, T const& pdy) + T const& pdx, T const& pdy) : x(px) , y(py) , dx(pdx) , dy(pdy) - , dx_0(T()) - , dy_0(T()) + //, dx_0(dx) + //, dy_0(dy) {} - T x, y; - T dx, dy; - T dx_0, dy_0; + template <typename Point> + inline collected_vector(Point const& p1, Point const& p2) + : x(get<0>(p1)) + , y(get<1>(p1)) + , dx(get<0>(p2) - x) + , dy(get<1>(p2) - y) + //, dx_0(dx) + //, dy_0(dy) + {} + + bool normalize() + { + T magnitude = math::sqrt( + boost::numeric_cast<T>(dx * dx + dy * dy)); + + // NOTE: shouldn't here math::equals() be called? + if (magnitude > 0) + { + dx /= magnitude; + dy /= magnitude; + return true; + } + + return false; + } // For sorting - inline bool operator<(collected_vector<T> const& other) const + inline bool operator<(collected_vector const& other) const { if (math::equals(x, other.x)) { @@ -74,7 +107,21 @@ struct collected_vector return x < other.x; } - inline bool same_direction(collected_vector<T> const& other) const + inline bool next_is_collinear(collected_vector const& other) const + { + return same_direction(other); + } + + // For std::equals + inline bool operator==(collected_vector const& other) const + { + return math::equals(x, other.x) + && math::equals(y, other.y) + && same_direction(other); + } + +private: + inline bool same_direction(collected_vector const& other) const { // For high precision arithmetic, we have to be // more relaxed then using == @@ -84,13 +131,156 @@ struct collected_vector && math::equals_with_epsilon(dy, other.dy); } + T x, y; + T dx, dy; + //T dx_0, dy_0; +}; + +template <typename T, typename Geometry> +struct collected_vector<T, Geometry, spherical_equatorial_tag> +{ + typedef T type; + + typedef typename coordinate_system<Geometry>::type cs_type; + typedef model::point<T, 2, cs_type> point_type; + typedef model::point<T, 3, cs::cartesian> vector_type; + + collected_vector() + {} + + template <typename Point> + collected_vector(Point const& p1, Point const& p2) + : origin(get<0>(p1), get<1>(p1)) + { + origin = detail::return_normalized<point_type>(origin); + + using namespace geometry::formula; + prev = sph_to_cart3d<vector_type>(p1); + next = sph_to_cart3d<vector_type>(p2); + direction = cross_product(prev, next); + } + + bool normalize() + { + T magnitude_sqr = dot_product(direction, direction); + + // NOTE: shouldn't here math::equals() be called? + if (magnitude_sqr > 0) + { + divide_value(direction, math::sqrt(magnitude_sqr)); + return true; + } + + return false; + } + + bool operator<(collected_vector const& other) const + { + if (math::equals(get<0>(origin), get<0>(other.origin))) + { + if (math::equals(get<1>(origin), get<1>(other.origin))) + { + if (math::equals(get<0>(direction), get<0>(other.direction))) + { + if (math::equals(get<1>(direction), get<1>(other.direction))) + { + return get<2>(direction) < get<2>(other.direction); + } + return get<1>(direction) < get<1>(other.direction); + } + return get<0>(direction) < get<0>(other.direction); + } + return get<1>(origin) < get<1>(other.origin); + } + return get<0>(origin) < get<0>(other.origin); + } + + // For consistency with side and intersection strategies used by relops + // IMPORTANT: this method should be called for previous vector + // and next vector should be passed as parameter + bool next_is_collinear(collected_vector const& other) const + { + return formula::sph_side_value(direction, other.next) == 0; + } + // For std::equals - inline bool operator==(collected_vector<T> const& other) const + bool operator==(collected_vector const& other) const { - return math::equals(x, other.x) - && math::equals(y, other.y) - && same_direction(other); + return math::equals(get<0>(origin), get<0>(other.origin)) + && math::equals(get<1>(origin), get<1>(other.origin)) + && is_collinear(other); + } + +private: + // For consistency with side and intersection strategies used by relops + bool is_collinear(collected_vector const& other) const + { + return formula::sph_side_value(direction, other.prev) == 0 + && formula::sph_side_value(direction, other.next) == 0; } + + /*bool same_direction(collected_vector const& other) const + { + return math::equals_with_epsilon(get<0>(direction), get<0>(other.direction)) + && math::equals_with_epsilon(get<1>(direction), get<1>(other.direction)) + && math::equals_with_epsilon(get<2>(direction), get<2>(other.direction)); + }*/ + + point_type origin; // used for sorting and equality check + vector_type direction; // used for sorting, only in operator< + vector_type prev; // used for collinearity check, only in operator== + vector_type next; // used for collinearity check +}; + +template <typename T, typename Geometry> +struct collected_vector<T, Geometry, spherical_polar_tag> + : public collected_vector<T, Geometry, spherical_equatorial_tag> +{ + typedef collected_vector<T, Geometry, spherical_equatorial_tag> base_type; + + collected_vector() {} + + template <typename Point> + collected_vector(Point const& p1, Point const& p2) + : base_type(to_equatorial(p1), to_equatorial(p2)) + {} + +private: + template <typename Point> + Point polar_to_equatorial(Point const& p) + { + typedef typename coordinate_type<Point>::type coord_type; + + typedef math::detail::constants_on_spheroid + < + coord_type, + typename coordinate_system<Point>::type::units + > constants; + + coord_type const pi_2 = constants::half_period() / 2; + + Point res = p; + set<1>(res, pi_2 - get<1>(p)); + return res; + } +}; + +// This is consistent with the currently used default geographic side +// and intersection strategies. Spherical strategies are used by default. +// When default strategies are changed in the future this specialization +// should be changed too. +template <typename T, typename Geometry> +struct collected_vector<T, Geometry, geographic_tag> + : public collected_vector<T, Geometry, spherical_equatorial_tag> +{ + typedef collected_vector<T, Geometry, spherical_equatorial_tag> base_type; + + collected_vector() {} + + template <typename Point> + collected_vector(Point const& p1, Point const& p2) + : base_type(p1, p2) + {} }; @@ -117,39 +307,26 @@ struct range_collect_vectors typedef typename boost::range_iterator<Range const>::type iterator; - bool first = true; + bool is_first = true; iterator it = boost::begin(range); for (iterator prev = it++; it != boost::end(range); prev = it++) { - typename boost::range_value<Collection>::type v; - - v.x = get<0>(*prev); - v.y = get<1>(*prev); - v.dx = get<0>(*it) - v.x; - v.dy = get<1>(*it) - v.y; - v.dx_0 = v.dx; - v.dy_0 = v.dy; + typename boost::range_value<Collection>::type v(*prev, *it); // Normalize the vector -> this results in points+direction // and is comparible between geometries - calculation_type magnitude = math::sqrt( - boost::numeric_cast<calculation_type>(v.dx * v.dx + v.dy * v.dy)); - // Avoid non-duplicate points (AND division by zero) - if (magnitude > 0) + if (v.normalize()) { - v.dx /= magnitude; - v.dy /= magnitude; - // Avoid non-direction changing points - if (first || ! v.same_direction(collection.back())) + if (is_first || ! collection.back().next_is_collinear(v)) { collection.push_back(v); } - first = false; + is_first = false; } } @@ -160,7 +337,7 @@ struct range_collect_vectors typedef typename boost::range_iterator<Collection>::type c_iterator; c_iterator first = range::pos(collection, c_old_size); - if ( first->same_direction(collection.back()) ) + if (collection.back().next_is_collinear(*first) ) { //collection.erase(first); // O(1) instead of O(N) @@ -172,7 +349,8 @@ struct range_collect_vectors }; -template <typename Box, typename Collection> +// Default version (cartesian) +template <typename Box, typename Collection, typename CSTag = typename cs_tag<Box>::type> struct box_collect_vectors { // Calculate on coordinate type, but if it is integer, @@ -183,9 +361,9 @@ struct box_collect_vectors static inline void apply(Collection& collection, Box const& box) { typename point_type<Box>::type lower_left, lower_right, - upper_left, upper_right; + upper_left, upper_right; geometry::detail::assign_box_corners(box, lower_left, lower_right, - upper_left, upper_right); + upper_left, upper_right); typedef typename boost::range_value<Collection>::type item; @@ -196,6 +374,37 @@ struct box_collect_vectors } }; +// NOTE: This is not fully correct because Box in spherical and geographic +// cordinate systems cannot be seen as Polygon +template <typename Box, typename Collection> +struct box_collect_vectors<Box, Collection, spherical_equatorial_tag> +{ + static inline void apply(Collection& collection, Box const& box) + { + typename point_type<Box>::type lower_left, lower_right, + upper_left, upper_right; + geometry::detail::assign_box_corners(box, lower_left, lower_right, + upper_left, upper_right); + + typedef typename boost::range_value<Collection>::type item; + + collection.push_back(item(lower_left, upper_left)); + collection.push_back(item(upper_left, upper_right)); + collection.push_back(item(upper_right, lower_right)); + collection.push_back(item(lower_right, lower_left)); + } +}; + +template <typename Box, typename Collection> +struct box_collect_vectors<Box, Collection, spherical_polar_tag> + : box_collect_vectors<Box, Collection, spherical_equatorial_tag> +{}; + +template <typename Box, typename Collection> +struct box_collect_vectors<Box, Collection, geographic_tag> + : box_collect_vectors<Box, Collection, spherical_equatorial_tag> +{}; + template <typename Polygon, typename Collection> struct polygon_collect_vectors @@ -312,7 +521,7 @@ struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon> template <typename Collection, typename Geometry> inline void collect_vectors(Collection& collection, Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); dispatch::collect_vectors < diff --git a/boost/geometry/algorithms/detail/expand/interface.hpp b/boost/geometry/algorithms/detail/expand/interface.hpp index 01936387a7..140754af4e 100644 --- a/boost/geometry/algorithms/detail/expand/interface.hpp +++ b/boost/geometry/algorithms/detail/expand/interface.hpp @@ -42,9 +42,9 @@ struct expand template <typename Box> static inline void apply(Box& box, Geometry const& geometry) { - concept::check<Box>(); - concept::check<Geometry const>(); - concept::check_concepts_and_equal_dimensions<Box, Geometry const>(); + concepts::check<Box>(); + concepts::check<Geometry const>(); + concepts::check_concepts_and_equal_dimensions<Box, Geometry const>(); dispatch::expand<Box, Geometry>::apply(box, geometry); } @@ -100,7 +100,7 @@ inline void expand(Box& box, Geometry const& geometry, StrategyLess const& strategy_less, StrategyGreater const& strategy_greater) { - concept::check_concepts_and_equal_dimensions<Box, Geometry const>(); + concepts::check_concepts_and_equal_dimensions<Box, Geometry const>(); dispatch::expand<Box, Geometry>::apply(box, geometry); } diff --git a/boost/geometry/algorithms/detail/extreme_points.hpp b/boost/geometry/algorithms/detail/extreme_points.hpp index 61839d296a..65795cd05b 100644 --- a/boost/geometry/algorithms/detail/extreme_points.hpp +++ b/boost/geometry/algorithms/detail/extreme_points.hpp @@ -492,15 +492,15 @@ struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag> template <std::size_t Edge, typename Geometry, typename Extremes, typename Intruders> inline bool extreme_points(Geometry const& geometry, Extremes& extremes, Intruders& intruders) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); // Extremes is not required to follow a geometry concept (but it should support an output iterator), // but its elements should fulfil the point-concept - concept::check<typename boost::range_value<Extremes>::type>(); + concepts::check<typename boost::range_value<Extremes>::type>(); // Intruders should contain collections which value type is point-concept // Extremes might be anything (supporting an output iterator), but its elements should fulfil the point-concept - concept::check + concepts::check < typename boost::range_value < diff --git a/boost/geometry/algorithms/detail/intersection/interface.hpp b/boost/geometry/algorithms/detail/intersection/interface.hpp index fd989866dd..e0955de3d8 100644 --- a/boost/geometry/algorithms/detail/intersection/interface.hpp +++ b/boost/geometry/algorithms/detail/intersection/interface.hpp @@ -110,8 +110,8 @@ struct intersection const Geometry2& geometry2, GeometryOut& geometry_out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename geometry::rescale_overlay_policy_type < @@ -123,7 +123,7 @@ struct intersection = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2); - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<Geometry1>::type, Geometry1, diff --git a/boost/geometry/algorithms/detail/is_simple/interface.hpp b/boost/geometry/algorithms/detail/is_simple/interface.hpp index fd84826970..6d425232b0 100644 --- a/boost/geometry/algorithms/detail/is_simple/interface.hpp +++ b/boost/geometry/algorithms/detail/is_simple/interface.hpp @@ -30,7 +30,7 @@ struct is_simple { static inline bool apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::is_simple<Geometry>::apply(geometry); } }; diff --git a/boost/geometry/algorithms/detail/is_valid/interface.hpp b/boost/geometry/algorithms/detail/is_valid/interface.hpp index 0ec13b1b38..5a04a92824 100644 --- a/boost/geometry/algorithms/detail/is_valid/interface.hpp +++ b/boost/geometry/algorithms/detail/is_valid/interface.hpp @@ -37,7 +37,7 @@ struct is_valid template <typename VisitPolicy> static inline bool apply(Geometry const& geometry, VisitPolicy& visitor) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::is_valid<Geometry>::apply(geometry, visitor); } }; diff --git a/boost/geometry/algorithms/detail/overlay/cluster_info.hpp b/boost/geometry/algorithms/detail/overlay/cluster_info.hpp new file mode 100644 index 0000000000..5b460919f1 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/cluster_info.hpp @@ -0,0 +1,49 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2016 Barend Gehrels, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_INFO_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_INFO_HPP + + +#include <set> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + + +struct cluster_info +{ + std::set<signed_size_type> turn_indices; + + bool switch_source; // For clusters with a touch, conform turn_info uu + + //! Number of open spaces (e.g. 2 for touch) + std::size_t open_count; + + inline cluster_info() + : switch_source(false) + , open_count(0) + {} +}; + + +}} // namespace detail::overlay +#endif //DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_INFO_HPP + diff --git a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp index 790819917c..795523d7a0 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp @@ -284,7 +284,7 @@ inline bool copy_segment_point(Geometry const& geometry, SegmentIdentifier const& seg_id, int offset, PointOut& point_out) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::copy_segment_point < @@ -313,8 +313,8 @@ inline bool copy_segment_point(Geometry1 const& geometry1, Geometry2 const& geom SegmentIdentifier const& seg_id, int offset, PointOut& point_out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); BOOST_GEOMETRY_ASSERT(seg_id.source_index == 0 || seg_id.source_index == 1); @@ -361,8 +361,8 @@ inline bool copy_segment_points(Geometry1 const& geometry1, Geometry2 const& geo SegmentIdentifier const& seg_id, PointOut& point1, PointOut& point2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return copy_segment_point<Reverse1, Reverse2>(geometry1, geometry2, seg_id, 0, point1) && copy_segment_point<Reverse1, Reverse2>(geometry1, geometry2, seg_id, 1, point2); @@ -384,8 +384,8 @@ inline bool copy_segment_points(Geometry1 const& geometry1, Geometry2 const& geo SegmentIdentifier const& seg_id, PointOut& point1, PointOut& point2, PointOut& point3) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return copy_segment_point<Reverse1, Reverse2>(geometry1, geometry2, seg_id, 0, point1) && copy_segment_point<Reverse1, Reverse2>(geometry1, geometry2, seg_id, 1, point2) diff --git a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp index 2eefa03c67..fe1a034f8b 100644 --- a/boost/geometry/algorithms/detail/overlay/copy_segments.hpp +++ b/boost/geometry/algorithms/detail/overlay/copy_segments.hpp @@ -349,7 +349,7 @@ inline void copy_segments(Geometry const& geometry, RobustPolicy const& robust_policy, RangeOut& range_out) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); dispatch::copy_segments < diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp index c79c9cf500..5cab2b4cb8 100644 --- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp @@ -66,7 +66,7 @@ inline void enrich_sort(Operations& operations, Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, - Strategy const& strategy) + Strategy const& /*strategy*/) { std::sort(boost::begin(operations), boost::end(operations), @@ -159,6 +159,7 @@ inline void enrich_assign(Operations& operations, Turns& turns) << " nxt=" << op.enriched.next_ip_index << " / " << op.enriched.travels_to_ip_index << " [vx " << op.enriched.travels_to_vertex_index << "]" + << std::boolalpha << turns[it->turn_index].discarded << std::endl; ; } @@ -235,11 +236,12 @@ inline void create_map(Turns const& turns, \ingroup overlay \tparam Turns type of intersection container (e.g. vector of "intersection/turn point"'s) +\tparam Clusters type of cluster container \tparam Geometry1 \tparam_geometry \tparam Geometry2 \tparam_geometry \tparam Strategy side strategy type -\param turns container containing intersectionpoints -\param for_operation operation_type (union or intersection) +\param turns container containing intersection points +\param clusters container containing clusters \param geometry1 \param_geometry \param geometry2 \param_geometry \param robust_policy policy to handle robustness issues @@ -257,11 +259,12 @@ template > inline void enrich_intersection_points(Turns& turns, Clusters& clusters, - detail::overlay::operation_type for_operation, Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, Strategy const& strategy) { + static const detail::overlay::operation_type for_operation + = detail::overlay::operation_from_overlay<OverlayType>::value; typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type op_type; typedef detail::overlay::indexed_turn_operation @@ -328,7 +331,7 @@ inline void enrich_intersection_points(Turns& turns, if (has_colocations) { - detail::overlay::assign_startable_in_clusters<Reverse1, Reverse2>( + detail::overlay::gather_cluster_properties<Reverse1, Reverse2>( clusters, turns, for_operation, geometry1, geometry2); } diff --git a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp index f5c5cc6a2e..cc55414870 100644 --- a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp @@ -9,6 +9,8 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICHMENT_INFO_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICHMENT_INFO_HPP +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> + namespace boost { namespace geometry { @@ -25,7 +27,7 @@ namespace detail { namespace overlay of the overlay process). The information is gathered during the enrichment phase */ -template<typename P> +template<typename Point> struct enrichment_info { inline enrichment_info() @@ -35,6 +37,7 @@ struct enrichment_info , startable(true) , count_left(0) , count_right(0) + , zone(-1) {} // vertex to which is free travel after this IP, @@ -53,6 +56,7 @@ struct enrichment_info // Counts if polygons left/right of this operation std::size_t count_left; std::size_t count_right; + signed_size_type zone; // open zone, in cluster }; diff --git a/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp index 4668189924..99281eaecb 100644 --- a/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp @@ -49,7 +49,7 @@ struct get_turn_without_info RobustPolicy const& robust_policy, OutputIterator out) { - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<typename TurnInfo::point_type>::type, Point1, @@ -109,7 +109,7 @@ inline void get_intersection_points(Geometry1 const& geometry1, RobustPolicy const& robust_policy, Turns& turns) { - concept::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>(); + concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>(); typedef detail::get_intersection_points::get_turn_without_info < diff --git a/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp b/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp index d71f4ad51f..ea9aa29f19 100644 --- a/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_relative_order.hpp @@ -10,7 +10,7 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP -#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_strategies.hpp> namespace boost { namespace geometry diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index ac36c530bf..a4cce3fd32 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -19,7 +19,7 @@ #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> -#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_strategies.hpp> #include <boost/geometry/algorithms/convert.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -989,6 +989,7 @@ struct get_turn_info // Swap p/q side_calculator < + typename inters_info::cs_tag, typename inters_info::robust_point2_type, typename inters_info::robust_point1_type > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), 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 0b3cb72747..85cdfbc02d 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 @@ -400,6 +400,8 @@ struct get_turn_info_for_endpoint IntersectionInfo const& inters, unsigned int ip_index, operation_type & op1, operation_type & op2) { + typedef typename cs_tag<typename TurnInfo::point_type>::type cs_tag; + boost::ignore_unused_variable_warning(i2); boost::ignore_unused_variable_warning(j2); boost::ignore_unused_variable_warning(ip_index); @@ -425,7 +427,7 @@ struct get_turn_info_for_endpoint } else if ( ip_j2 ) { - side_calculator<RobustPoint1, RobustPoint2, RobustPoint2> + side_calculator<cs_tag, RobustPoint1, RobustPoint2, RobustPoint2> side_calc(ri2, ri1, rj1, ri2, rj2, rk2); std::pair<operation_type, operation_type> @@ -476,7 +478,7 @@ struct get_turn_info_for_endpoint } else if ( ip_j2 ) { - side_calculator<RobustPoint1, RobustPoint2, RobustPoint2> + side_calculator<cs_tag, RobustPoint1, RobustPoint2, RobustPoint2> side_calc(ri2, rj1, ri1, ri2, rj2, rk2); std::pair<operation_type, operation_type> 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 ee0a93ae7e..3e7da1d797 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp @@ -36,14 +36,19 @@ struct turn_operation_linear bool is_collinear; // valid only for Linear geometry }; -template <typename PointP, typename PointQ, +template <typename TurnPointCSTag, typename PointP, typename PointQ, typename Pi = PointP, typename Pj = PointP, typename Pk = PointP, typename Qi = PointQ, typename Qj = PointQ, typename Qk = PointQ > struct side_calculator { - // todo: get from coordinate system - typedef boost::geometry::strategy::side::side_by_triangle<> side; + // This strategy should be the same as side strategy defined in + // intersection_strategies<> which is used in various places + // of the library + typedef typename strategy::side::services::default_strategy + < + TurnPointCSTag + >::type side; inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk, Qi const& qi, Qj const& qj, Qk const& qk) @@ -94,7 +99,7 @@ struct robust_points robust_point2_type m_rqi, m_rqj, m_rqk; }; -template <typename Point1, typename Point2, typename RobustPolicy> +template <typename Point1, typename Point2, typename TurnPoint, typename RobustPolicy> class intersection_info_base : private robust_points<Point1, Point2, RobustPolicy> { @@ -107,7 +112,9 @@ public: 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; + typedef typename cs_tag<TurnPoint>::type cs_tag; + + typedef side_calculator<cs_tag, 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, @@ -148,8 +155,8 @@ private: point2_type const& m_qk; }; -template <typename Point1, typename Point2> -class intersection_info_base<Point1, Point2, detail::no_rescale_policy> +template <typename Point1, typename Point2, typename TurnPoint> +class intersection_info_base<Point1, Point2, TurnPoint, detail::no_rescale_policy> { public: typedef Point1 point1_type; @@ -158,7 +165,9 @@ public: typedef Point1 robust_point1_type; typedef Point2 robust_point2_type; - typedef side_calculator<Point1, Point2> side_calculator_type; + typedef typename cs_tag<TurnPoint>::type cs_tag; + + typedef side_calculator<cs_tag, Point1, Point2> side_calculator_type; intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, Point2 const& qi, Point2 const& qj, Point2 const& qk, @@ -197,13 +206,13 @@ template typename RobustPolicy > class intersection_info - : public intersection_info_base<Point1, Point2, RobustPolicy> + : public intersection_info_base<Point1, Point2, TurnPoint, RobustPolicy> { - typedef intersection_info_base<Point1, Point2, RobustPolicy> base; + typedef intersection_info_base<Point1, Point2, TurnPoint, RobustPolicy> base; - typedef typename strategy_intersection + typedef typename intersection_strategies < - typename cs_tag<TurnPoint>::type, + typename base::cs_tag, Point1, Point2, TurnPoint, @@ -298,9 +307,9 @@ private: { typedef model::referring_segment<Point const> seg; - typedef strategy_intersection + typedef intersection_strategies < - typename cs_tag<Point>::type, Point, Point, Point, RobustPolicy + typename base::cs_tag, Point, Point, Point, RobustPolicy > si; typedef typename si::segment_intersection_strategy_type strategy; 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 ccb42d4c92..121728d822 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp @@ -106,6 +106,7 @@ struct get_turn_info_linear_areal // Swap p/q side_calculator < + typename inters_info::cs_tag, typename inters_info::robust_point2_type, typename inters_info::robust_point1_type > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), @@ -752,6 +753,7 @@ struct get_turn_info_linear_areal { side_calculator < + typename IntersectionInfo::cs_tag, typename IntersectionInfo::robust_point1_type, typename IntersectionInfo::robust_point2_type, typename IntersectionInfo::robust_point2_type @@ -770,6 +772,7 @@ struct get_turn_info_linear_areal { side_calculator < + typename IntersectionInfo::cs_tag, typename IntersectionInfo::robust_point1_type, typename IntersectionInfo::robust_point2_type, typename IntersectionInfo::robust_point2_type, @@ -826,6 +829,7 @@ struct get_turn_info_linear_areal { side_calculator < + typename IntersectionInfo::cs_tag, typename IntersectionInfo::robust_point1_type, typename IntersectionInfo::robust_point2_type, typename IntersectionInfo::robust_point2_type 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 19f0859cbb..6bb3a74bb8 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp @@ -101,6 +101,7 @@ struct get_turn_info_linear_linear // Swap p/q side_calculator < + typename inters_info::cs_tag, typename inters_info::robust_point2_type, typename inters_info::robust_point1_type > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp index b2b97c0337..1eb18b74d4 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp @@ -3,8 +3,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. -// 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, 2016. +// Modifications copyright (c) 2014, 2016 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 @@ -46,7 +46,7 @@ #include <boost/geometry/iterators/ever_circling_iterator.hpp> #include <boost/geometry/strategies/cartesian/cart_intersect.hpp> -#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_strategies.hpp> #include <boost/geometry/strategies/intersection_result.hpp> #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> @@ -972,7 +972,7 @@ inline void get_turns(Geometry1 const& geometry1, Turns& turns, InterruptPolicy& interrupt_policy) { - concept::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>(); + concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>(); typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy; //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy; diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp index ad75127fab..110e1be2f1 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -15,6 +15,9 @@ #include <vector> #include <boost/range.hpp> +#include <boost/geometry/core/point_order.hpp> +#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> +#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> @@ -201,7 +204,6 @@ inline signed_size_type add_turn_to_cluster(Turn const& turn, template < - bool Reverse1, bool Reverse2, typename Turns, typename ClusterPerSegment, typename Operations, @@ -212,7 +214,7 @@ inline void handle_colocation_cluster(Turns& turns, signed_size_type& cluster_id, ClusterPerSegment& cluster_per_segment, Operations const& operations, - Geometry1 const& geometry1, Geometry2 const& geometry2) + Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/) { typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; @@ -318,7 +320,7 @@ inline void assign_cluster_to_turns(Turns& turns, std::cout << " CONFLICT " << std::endl; } turn.cluster_id = it->second; - clusters[turn.cluster_id].insert(turn_index); + clusters[turn.cluster_id].turn_indices.insert(turn_index); } } } @@ -339,7 +341,8 @@ inline void remove_clusters(Turns& turns, Clusters& clusters) typename Clusters::iterator current_it = it; ++it; - std::set<signed_size_type> const& turn_indices = current_it->second; + std::set<signed_size_type> const& turn_indices + = current_it->second.turn_indices; if (turn_indices.size() == 1) { signed_size_type turn_index = *turn_indices.begin(); @@ -349,6 +352,134 @@ inline void remove_clusters(Turns& turns, Clusters& clusters) } } +template <typename Turn, typename IdSet> +inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id) +{ + turn.discarded = true; + turn.cluster_id = -1; + // To remove it later from clusters + ids.insert(id); +} + +template <bool Reverse> +inline bool is_interior(segment_identifier const& seg_id) +{ + return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0; +} + +template <bool Reverse0, bool Reverse1> +inline bool is_ie_turn(segment_identifier const& ext_seg_0, + segment_identifier const& ext_seg_1, + segment_identifier const& int_seg_0, + segment_identifier const& other_seg_1) +{ + // Compares two segment identifiers from two turns (external / one internal) + + // From first turn [0], both are from same polygon (multi_index), + // one is exterior (-1), the other is interior (>= 0), + // and the second turn [1] handles the same ring + + // For difference, where the rings are processed in reversal, all interior + // rings become exterior and vice versa. But also the multi property changes: + // rings originally from the same multi should now be considered as from + // different multi polygons. + // But this is not always the case, and at this point hard to figure out + // (not yet implemented, TODO) + + bool const same_multi0 = ! Reverse0 + && ext_seg_0.multi_index == int_seg_0.multi_index; + + bool const same_multi1 = ! Reverse1 + && ext_seg_1.multi_index == other_seg_1.multi_index; + + return same_multi0 + && same_multi1 + && ! is_interior<Reverse0>(ext_seg_0) + && is_interior<Reverse0>(int_seg_0) + && ext_seg_1.ring_index == other_seg_1.ring_index; + + // The other way round is tested in another call +} + +template +< + bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior + typename Turns, + typename Clusters +> +inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) +{ + typedef std::set<signed_size_type>::const_iterator set_iterator; + typedef typename boost::range_value<Turns>::type turn_type; + + std::set<signed_size_type> ids_to_remove; + + for (typename Clusters::iterator cit = clusters.begin(); + cit != clusters.end(); ++cit) + { + cluster_info& cinfo = cit->second; + std::set<signed_size_type>& ids = cinfo.turn_indices; + + ids_to_remove.clear(); + + for (set_iterator it = ids.begin(); it != ids.end(); ++it) + { + turn_type& turn = turns[*it]; + segment_identifier const& seg_0 = turn.operations[0].seg_id; + segment_identifier const& seg_1 = turn.operations[1].seg_id; + + if (turn.both(operation_intersection) + && Reverse0 == Reverse1) + { + if ( is_interior<Reverse0>(seg_0) + && is_interior<Reverse1>(seg_1)) + { + // ii touch with, two interior rings + discard_ie_turn(turn, ids_to_remove, *it); + } + + continue; + } + + if (! (turn.both(operation_union) + || turn.combination(operation_union, operation_blocked))) + { + // Not a uu/ux, so cannot be colocated with a iu turn + continue; + } + + for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it) + { + if (*it == *int_it) + { + continue; + } + + // Turn with, possibly, an interior ring involved + turn_type& int_turn = turns[*int_it]; + segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id; + segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id; + + if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1)) + { + discard_ie_turn(int_turn, ids_to_remove, *int_it); + } + if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0)) + { + discard_ie_turn(int_turn, ids_to_remove, *int_it); + } + } + } + + // Erase from the ids (which cannot be done above) + for (set_iterator sit = ids_to_remove.begin(); + sit != ids_to_remove.end(); ++sit) + { + ids.erase(*sit); + } + } +} + // Checks colocated turns and flags combinations of uu/other, possibly a // combination of a ring touching another geometry's interior ring which is @@ -434,13 +565,17 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters, { if (it->second.size() > 1u) { - handle_colocation_cluster<Reverse1, Reverse2>(turns, cluster_id, - cluster_per_segment, it->second, - geometry1, geometry2); + handle_colocation_cluster(turns, cluster_id, cluster_per_segment, + it->second, geometry1, geometry2); } } assign_cluster_to_turns(turns, clusters, cluster_per_segment); + discard_interior_exterior_turns + < + do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1, + do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2 + >(turns, clusters); remove_clusters(turns, clusters); #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) @@ -497,7 +632,7 @@ template typename Geometry1, typename Geometry2 > -inline void assign_startable_in_clusters(Clusters& clusters, Turns& turns, +inline void gather_cluster_properties(Clusters& clusters, Turns& turns, operation_type for_operation, Geometry1 const& geometry1, Geometry2 const& geometry2) { @@ -515,7 +650,8 @@ inline void assign_startable_in_clusters(Clusters& clusters, Turns& turns, for (typename Clusters::iterator mit = clusters.begin(); mit != clusters.end(); ++mit) { - std::set<signed_size_type> const& ids = mit->second; + cluster_info& cinfo = mit->second; + std::set<signed_size_type> const& ids = cinfo.turn_indices; if (ids.empty()) { continue; @@ -545,30 +681,32 @@ inline void assign_startable_in_clusters(Clusters& clusters, Turns& turns, sbs.find_open(); - // Unset the startable flag for all 'closed' spaces + // Unset the startable flag for all 'closed' zones for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { const typename sbs_type::rp& ranked = sbs.m_ranked_points[i]; turn_type& turn = turns[ranked.turn_index]; - turn_operation_type& op = turn.operations[ranked.op_index]; + turn_operation_type& op = turn.operations[ranked.operation_index]; - if (ranked.index != sort_by_side::index_to) + if (ranked.direction != sort_by_side::dir_to) { continue; } - op.enriched.count_left = ranked.left_count; - op.enriched.count_right = ranked.right_count; + op.enriched.count_left = ranked.count_left; + op.enriched.count_right = ranked.count_right; + op.enriched.zone = ranked.zone; if ((for_operation == operation_union - && ranked.left_count != 0) + && ranked.count_left != 0) || (for_operation == operation_intersection - && ranked.right_count != 2)) + && ranked.count_right != 2)) { op.enriched.startable = false; } } + cinfo.open_count = sbs.open_count(turns); } } diff --git a/boost/geometry/algorithms/detail/overlay/handle_touch.hpp b/boost/geometry/algorithms/detail/overlay/handle_touch.hpp deleted file mode 100644 index 1febefc83a..0000000000 --- a/boost/geometry/algorithms/detail/overlay/handle_touch.hpp +++ /dev/null @@ -1,336 +0,0 @@ -// Boost.Geometry (aka GGL, Generic Geometry Library) - -// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. - -// Use, modification and distribution is subject to the Boost Software License, -// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at -// http://www.boost.org/LICENSE_1_0.txt) - -#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TOUCH_HPP -#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TOUCH_HPP - -#include <cstddef> - -#include <boost/range.hpp> - -#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> -#include <boost/geometry/geometries/concepts/check.hpp> -#include <boost/geometry/algorithms/detail/ring_identifier.hpp> -#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> - - -namespace boost { namespace geometry -{ - -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace overlay -{ - - -template <typename Turns, typename Visitor> -class handle_touch_uu -{ -private : - typedef typename boost::range_value<Turns>::type turn_type; - typedef typename boost::range_iterator<Turns>::type turn_iterator; - typedef typename boost::range_iterator<Turns const>::type turn_const_iterator; - - typedef typename boost::range_iterator - < - typename turn_type::container_type const - >::type operation_const_iterator; - -public : - - handle_touch_uu(Visitor& visitor) - : m_visitor(visitor) - {} - - inline void apply(detail::overlay::operation_type operation, Turns& turns) - { - if (! has_uu(turns)) - { - // Performance - if there is no u/u at all, nothing to be done - return; - } - - // Iterate through all u/u points - int turn_index = 0; - for (turn_iterator it = boost::begin(turns); - it != boost::end(turns); - ++it, ++turn_index) - { - turn_type& turn = *it; - if (! turn.both(operation_union)) - { - continue; - } - - m_visitor.print("handle_touch uu:", turns, turn_index); - - bool const traverse = turn_should_be_traversed(turns, turn, turn_index); - bool const start = traverse - && turn_should_be_startable(turns, turn, turn_index); - m_visitor.print("handle_touch, ready ", turns, turn_index); -// << std::boolalpha -// << traverse << " " << start - - if (traverse) - { - // Indicate the sources should switch here to create - // separate rings (outer ring / inner ring) - turn.switch_source = true; - } - // TODO: this is often not correct, fix this - turn.operations[0].enriched.startable = start; - turn.operations[1].enriched.startable = start; - } - } - -private : - - // Generic utility to be moved somewhere else - static inline - ring_identifier ring_id_from_seg_id(const segment_identifier& seg_id) - { - return ring_identifier(seg_id.source_index, - seg_id.multi_index, - seg_id.ring_index); - } - - static inline - ring_identifier ring_id_from_op(const turn_type& turn, - int operation_index) - { - return ring_id_from_seg_id(turn.operations[operation_index].seg_id); - } - - static inline bool in_range(const Turns& turns, signed_size_type index) - { - signed_size_type const turns_size = - static_cast<signed_size_type>(boost::size(turns)); - return index >= 0 && index < turns_size; - } - - static inline bool has_uu(const Turns& turns) - { - for (turn_const_iterator it = boost::begin(turns); - it != boost::end(turns); - ++it) - { - const turn_type& turn = *it; - if (turn.both(operation_union)) - { - return true; - } - } - return false; - } - - static inline - bool turn_should_be_startable(const Turns& turns, - const turn_type& uu_turn, - signed_size_type uu_turn_index) - { - return turn_startable(turns, uu_turn, 0, uu_turn_index) - || turn_startable(turns, uu_turn, 1, uu_turn_index); - - } - - static inline - bool turn_startable(const Turns& turns, - const turn_type& uu_turn, - std::size_t op_index, - signed_size_type original_turn_index, - std::size_t iteration = 0) - { - if (iteration >= boost::size(turns)) - { - // Defensive check to avoid infinite recursion - return false; - } - - signed_size_type const index - = uu_turn.operations[op_index].enriched.travels_to_ip_index; - if (index == original_turn_index) - { - // Completely traveled, having u/u only, via this op_index - return true; - } - - if (! in_range(turns, index)) - { - return false; - } - - const turn_type& new_turn = turns[index]; - - if (new_turn.operations[0].enriched.startable) - { - // Already selectable - no need to select u/u turn too - return false; - } - - // If this u/u turn is traversed normally (without skipping), sources are switched - return turn_startable(turns, new_turn, 1 - op_index, - original_turn_index, iteration + 1); - } - - inline bool turn_should_be_traversed(const Turns& turns, - const turn_type& uu_turn, - signed_size_type uu_turn_index) - { - return turn_should_be_traversed(turns, uu_turn, uu_turn_index, 0) - || turn_should_be_traversed(turns, uu_turn, uu_turn_index, 1); - } - - inline bool turn_should_be_traversed(const Turns& turns, - const turn_type& uu_turn, - signed_size_type uu_turn_index, - int uu_operation_index) - { - // Suppose this is a u/u turn between P and Q - // Examine all other turns on P and check if Q can be reached - // Use one of the operations and check if you can reach the other - signed_size_type const to_turn_index - = uu_turn.operations[uu_operation_index].enriched.travels_to_ip_index; - if (! in_range(turns, to_turn_index)) - { - return false; - } - - m_visitor.print("Examine:", turns, to_turn_index); - ring_identifier const other_ring_id - = ring_id_from_op(uu_turn, 1 - uu_operation_index); - - bool complete = false; - return can_reach(complete, turns, turns[to_turn_index], uu_operation_index, - other_ring_id, uu_turn_index, to_turn_index); - } - - inline bool can_reach(bool& complete, const Turns& turns, - const turn_type& turn, - signed_size_type uu_operation_index, - const ring_identifier& target_ring_id, - signed_size_type uu_turn_index, - signed_size_type to_turn_index, - std::size_t iteration = 0) - { - if (complete) - { - return false; - } - - if (turn.cluster_id >= 0) - { - // Clustered turns are yet not supported - return false; - } - - if (iteration >= boost::size(turns)) - { - m_visitor.print("Too much iterations"); - // Defensive check to avoid infinite recursion - return false; - } - - if (uu_operation_index != -1 && turn.both(operation_union)) - { - // If we end up in a u/u turn, check the way how, for this operation - m_visitor.print("Via u/u"); - return can_reach_via(complete, turns, uu_operation_index, - turn.operations[uu_operation_index], - target_ring_id, - uu_turn_index, to_turn_index, iteration); - } - else - { - // Check if specified ring can be reached via one of both operations - return can_reach_via(complete, turns, 0, turn.operations[0], target_ring_id, - uu_turn_index, to_turn_index, iteration) - || can_reach_via(complete, turns, 1, turn.operations[1], target_ring_id, - uu_turn_index, to_turn_index, iteration); - } - } - - template <typename Operation> - inline bool can_reach_via(bool& complete, const Turns& turns, - signed_size_type operation_index, - const Operation& operation, - const ring_identifier& target_ring_id, - signed_size_type uu_turn_index, - signed_size_type to_turn_index, - std::size_t iteration = 0) - { - if (operation.operation != operation_union - && operation.operation != operation_continue) - { - return false; - } - - signed_size_type const index = operation.enriched.travels_to_ip_index; - if (index == to_turn_index) - { - m_visitor.print("Dead end at", turns, index); - // Completely traveled, the target is not found - return false; - } - if (index == uu_turn_index) - { - // End up where trial was started - m_visitor.print("Travel complete at", turns, index); - complete = true; - return false; - } - - if (! in_range(turns, index)) - { - return false; - } - - m_visitor.print("Now to", turns, index, operation_index); - const turn_type& new_turn = turns[index]; - - if (new_turn.both(operation_union)) - { - ring_identifier const ring_id = ring_id_from_op(new_turn, operation_index); - if (ring_id == target_ring_id) - { - m_visitor.print("Found (at u/u)!"); - return true; - } - } - else - { - ring_identifier const ring_id1 = ring_id_from_op(new_turn, 0); - ring_identifier const ring_id2 = ring_id_from_op(new_turn, 1); - if (ring_id1 == target_ring_id || ring_id2 == target_ring_id) - { - m_visitor.print("Found!"); - return true; - } - } - - // Recursively check this turn - return can_reach(complete, turns, new_turn, operation_index, target_ring_id, - uu_turn_index, to_turn_index, iteration + 1); - } - -private : - Visitor m_visitor; -}; - -template <typename Turns, typename Visitor> -inline void handle_touch(detail::overlay::operation_type operation, - Turns& turns, Visitor& visitor) -{ - handle_touch_uu<Turns, Visitor> handler(visitor); - handler.apply(operation, turns); -} - -}} // namespace detail::overlay -#endif // DOXYGEN_NO_DETAIL - -}} // namespace boost::geometry - -#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_TOUCH_HPP diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp index 59c8f6f1ff..bb82003a23 100644 --- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp +++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp @@ -993,8 +993,8 @@ inline OutputIterator intersection_insert(Geometry1 const& geometry1, OutputIterator out, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename Strategy::rescale_policy_type rescale_policy_type; rescale_policy_type robust_policy @@ -1034,15 +1034,15 @@ inline OutputIterator intersection_insert(Geometry1 const& geometry1, Geometry2 const& geometry2, OutputIterator out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename geometry::rescale_policy_type < typename geometry::point_type<Geometry1>::type // TODO from both >::type rescale_policy_type; - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<GeometryOut>::type, Geometry1, diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index c3ecaa0b01..09c80025a0 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -23,10 +23,10 @@ #include <boost/mpl/assert.hpp> +#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> -#include <boost/geometry/algorithms/detail/overlay/handle_touch.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> @@ -220,11 +220,9 @@ struct overlay typedef std::map < signed_size_type, - std::set<signed_size_type> + cluster_info > cluster_type; - cluster_type clusters; - turn_container_type turns; #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE @@ -239,18 +237,14 @@ std::cout << "get turns" << std::endl; visitor.visit_turns(1, turns); - static const operation_type op_type - = OverlayType == overlay_union - ? geometry::detail::overlay::operation_union - : geometry::detail::overlay::operation_intersection; - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "enrich" << std::endl; #endif typename Strategy::side_strategy_type side_strategy; + cluster_type clusters; + geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, - clusters, op_type, - geometry1, geometry2, + clusters, geometry1, geometry2, robust_policy, side_strategy); @@ -258,19 +252,6 @@ std::cout << "enrich" << std::endl; visitor.visit_clusters(clusters, turns); - -#if 0 - // TODO: does not work always correctly, move to traverse and fix - if (op_type == geometry::detail::overlay::operation_union) - { - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE - std::cout << "handle_touch" << std::endl; - #endif - - handle_touch(op_type, turns, visitor); - } -#endif - #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "traverse" << std::endl; #endif @@ -278,7 +259,7 @@ std::cout << "traverse" << std::endl; // Note that these rings are always in clockwise order, even in CCW polygons, // and are marked as "to be reversed" below ring_container_type rings; - traverse<Reverse1, Reverse2, Geometry1, Geometry2, op_type>::apply + traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply ( geometry1, geometry2, robust_policy, diff --git a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp index af62131f0e..0f60840973 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay_type.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay_type.hpp @@ -14,14 +14,52 @@ namespace boost { namespace geometry { +// TODO: move to detail enum overlay_type { overlay_union, overlay_intersection, overlay_difference, + overlay_buffer, overlay_dissolve }; +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +enum operation_type +{ + operation_none, + operation_union, + operation_intersection, + operation_blocked, + operation_continue, + operation_opposite +}; + + +template <overlay_type OverlayType> +struct operation_from_overlay +{ + static const operation_type value = operation_union; +}; + +template <> +struct operation_from_overlay<overlay_intersection> +{ + static const operation_type value = operation_intersection; +}; + +template <> +struct operation_from_overlay<overlay_difference> +{ + static const operation_type value = operation_intersection; +}; + +}} // namespace detail::overlay +#endif //DOXYGEN_NO_DETAIL + }} // namespace boost::geometry diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp index 1b3cd866d7..de5eac8acb 100644 --- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp @@ -165,11 +165,8 @@ namespace dispatch template<overlay_type OverlayType> struct decide -{}; - -template<> -struct decide<overlay_union> { + // Default implementation (union, inflate, deflate, dissolve) static bool include(ring_identifier const& , ring_turn_info const& info) { return ! info.within_other; @@ -179,6 +176,7 @@ struct decide<overlay_union> { return false; } + }; template<> diff --git a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp index a74cb83f77..aedf22e1fb 100644 --- a/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp +++ b/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp @@ -276,7 +276,7 @@ inline void self_turns(Geometry const& geometry, RobustPolicy const& robust_policy, Turns& turns, InterruptPolicy& interrupt_policy) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy; diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp index 894cddab87..91b0f8ae24 100644 --- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp +++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp @@ -23,42 +23,44 @@ namespace boost { namespace geometry namespace detail { namespace overlay { namespace sort_by_side { -enum index_type { index_unknown = -1, index_from = 0, index_to = 1 }; +enum direction_type { dir_unknown = -1, dir_from = 0, dir_to = 1 }; // Point-wrapper, adding some properties template <typename Point> struct ranked_point { ranked_point() - : main_rank(0) + : rank(0) , turn_index(-1) - , op_index(-1) - , index(index_unknown) - , left_count(0) - , right_count(0) + , operation_index(-1) + , direction(dir_unknown) + , count_left(0) + , count_right(0) , operation(operation_none) {} ranked_point(const Point& p, signed_size_type ti, signed_size_type oi, - index_type i, operation_type op, segment_identifier sid) + direction_type d, operation_type op, segment_identifier sid) : point(p) - , main_rank(0) + , rank(0) + , zone(-1) , turn_index(ti) - , op_index(oi) - , index(i) - , left_count(0) - , right_count(0) + , operation_index(oi) + , direction(d) + , count_left(0) + , count_right(0) , operation(op) , seg_id(sid) {} Point point; - std::size_t main_rank; + std::size_t rank; + signed_size_type zone; // index of closed zone, in uu turn there would be 2 zones signed_size_type turn_index; - signed_size_type op_index; - index_type index; - std::size_t left_count; - std::size_t right_count; + signed_size_type operation_index; + direction_type direction; + std::size_t count_left; + std::size_t count_right; operation_type operation; segment_identifier seg_id; }; @@ -81,9 +83,9 @@ struct less_by_index inline bool operator()(const T& first, const T& second) const { // First order by from/to - if (first.index != second.index) + if (first.direction != second.direction) { - return first.index < second.index; + return first.direction < second.direction; } // All the same, order by turn index (we might consider length too) return first.turn_index < second.turn_index; @@ -200,8 +202,8 @@ struct side_sorter op.seg_id, point1, point2, point3); Point const& point_to = op.fraction.is_one() ? point3 : point2; - m_ranked_points.push_back(rp(point1, turn_index, op_index, index_from, op.operation, op.seg_id)); - m_ranked_points.push_back(rp(point_to, turn_index, op_index, index_to, op.operation, op.seg_id)); + m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op.operation, op.seg_id)); + m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op.operation, op.seg_id)); if (is_origin) { @@ -233,7 +235,7 @@ struct side_sorter colinear_rank++; } - m_ranked_points[i].main_rank = colinear_rank; + m_ranked_points[i].rank = colinear_rank; } } @@ -243,7 +245,7 @@ struct side_sorter for (std::size_t i = 0; i < m_ranked_points.size(); i++) { const rp& ranked = m_ranked_points[i]; - if (ranked.index != index_from) + if (ranked.direction != dir_from) { continue; } @@ -290,6 +292,8 @@ struct side_sorter &segment_identifier::source_index >(handled); } + + assign_zones(); } void reverse() @@ -299,25 +303,25 @@ struct side_sorter return; } - int const last = 1 + m_ranked_points.back().main_rank; + int const last = 1 + m_ranked_points.back().rank; - // Move iterator after main_rank==0 + // Move iterator after rank==0 bool has_first = false; typename container_type::iterator it = m_ranked_points.begin() + 1; - for (; it != m_ranked_points.end() && it->main_rank == 0; ++it) + for (; it != m_ranked_points.end() && it->rank == 0; ++it) { has_first = true; } if (has_first) { - // Reverse first part (having main_rank == 0), if any, + // Reverse first part (having rank == 0), if any, // but skip the very first row std::reverse(m_ranked_points.begin() + 1, it); for (typename container_type::iterator fit = m_ranked_points.begin(); fit != it; ++fit) { - BOOST_ASSERT(fit->main_rank == 0); + BOOST_ASSERT(fit->rank == 0); } } @@ -325,11 +329,41 @@ struct side_sorter std::reverse(it, m_ranked_points.end()); for (; it != m_ranked_points.end(); ++it) { - BOOST_ASSERT(it->main_rank > 0); - it->main_rank = last - it->main_rank; + BOOST_ASSERT(it->rank > 0); + it->rank = last - it->rank; } } + //! Check how many open spaces there are + template <typename Turns> + std::size_t open_count(Turns const& turns) const + { + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + std::size_t result = 0; + std::size_t last_rank = 0; + for (std::size_t i = 0; i < m_ranked_points.size(); i++) + { + rp const& ranked_point = m_ranked_points[i]; + + if (ranked_point.rank > last_rank + && ranked_point.direction == sort_by_side::dir_to) + { + // TODO: take count-left / count_right from rank itself + turn_type const& ranked_turn = turns[ranked_point.turn_index]; + turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index]; + if (ranked_op.enriched.count_left == 0 + && ranked_op.enriched.count_right > 0) + { + result++; + last_rank = ranked_point.rank; + } + } + } + return result; + } + //protected : typedef std::vector<rp> container_type; @@ -366,19 +400,19 @@ private : // if min=5,max=2: assign from 5,6,7,1,2 bool const in_range = max_rank >= min_rank - ? ranked.main_rank >= min_rank && ranked.main_rank <= max_rank - : ranked.main_rank >= min_rank || ranked.main_rank <= max_rank + ? ranked.rank >= min_rank && ranked.rank <= max_rank + : ranked.rank >= min_rank || ranked.rank <= max_rank ; if (in_range) { if (side_index == 1) { - ranked.left_count++; + ranked.count_left++; } else if (side_index == 2) { - ranked.right_count++; + ranked.count_right++; } } } @@ -389,8 +423,8 @@ private : std::size_t start_index) { int state = 1; // 'closed', because start_index is "from", arrives at the turn - std::size_t last_from_rank = m_ranked_points[start_index].main_rank; - std::size_t previous_rank = m_ranked_points[start_index].main_rank; + std::size_t last_from_rank = m_ranked_points[start_index].rank; + std::size_t previous_rank = m_ranked_points[start_index].rank; for (std::size_t index = move<Member>(the_index, start_index); ; @@ -398,7 +432,7 @@ private : { rp& ranked = m_ranked_points[index]; - if (ranked.main_rank != previous_rank && state == 0) + if (ranked.rank != previous_rank && state == 0) { assign_ranks(last_from_rank, previous_rank - 1, 1); assign_ranks(last_from_rank + 1, previous_rank, 2); @@ -409,19 +443,91 @@ private : return; } - if (ranked.index == index_from) + if (ranked.direction == dir_from) { - last_from_rank = ranked.main_rank; + last_from_rank = ranked.rank; state++; } - else if (ranked.index == index_to) + else if (ranked.direction == dir_to) { state--; } - previous_rank = ranked.main_rank; + previous_rank = ranked.rank; } } + + //! Find closed zones and assign it + void assign_zones() + { + // Find a starting point (the first rank after an outgoing rank + // with no polygons on the left side) + std::size_t start_rank = m_ranked_points.size() + 1; + std::size_t start_index = 0; + std::size_t max_rank = 0; + for (std::size_t i = 0; i < m_ranked_points.size(); i++) + { + rp const& ranked_point = m_ranked_points[i]; + if (ranked_point.rank > max_rank) + { + max_rank = ranked_point.rank; + } + if (ranked_point.direction == sort_by_side::dir_to + && ranked_point.count_left == 0 + && ranked_point.count_right > 0) + { + start_rank = ranked_point.rank + 1; + } + if (ranked_point.rank == start_rank && start_index == 0) + { + start_index = i; + } + } + + // Assign the zones + std::size_t const undefined_rank = max_rank + 1; + std::size_t zone_id = 0; + std::size_t last_rank = 0; + std::size_t rank_at_next_zone = undefined_rank; + std::size_t index = start_index; + for (std::size_t i = 0; i < m_ranked_points.size(); i++) + { + rp& ranked_point = m_ranked_points[index]; + + // Implement cyclic behavior + index++; + if (index == m_ranked_points.size()) + { + index = 0; + } + + if (ranked_point.rank != last_rank) + { + if (ranked_point.rank == rank_at_next_zone) + { + zone_id++; + rank_at_next_zone = undefined_rank; + } + + if (ranked_point.direction == sort_by_side::dir_to + && ranked_point.count_left == 0 + && ranked_point.count_right > 0) + { + rank_at_next_zone = ranked_point.rank + 1; + if (rank_at_next_zone > max_rank) + { + rank_at_next_zone = 0; + } + } + + last_rank = ranked_point.rank; + } + + ranked_point.zone = zone_id; + } + } + + }; diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp new file mode 100644 index 0000000000..1156644bc3 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -0,0 +1,672 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP + +#include <cstddef> + +#include <boost/range.hpp> + +#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/assert.hpp> + +#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \ + || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \ + || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) +# include <string> +# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> +# include <boost/geometry/io/wkt/wkt.hpp> +#endif + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +template <typename Turn, typename Operation> +#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE +inline void debug_traverse(Turn const& turn, Operation op, + std::string const& header) +{ + std::cout << header + << " at " << op.seg_id + << " meth: " << method_char(turn.method) + << " op: " << operation_char(op.operation) + << " vis: " << visited_char(op.visited) + << " of: " << operation_char(turn.operations[0].operation) + << operation_char(turn.operations[1].operation) + << " " << geometry::wkt(turn.point) + << std::endl; + + if (boost::contains(header, "Finished")) + { + std::cout << std::endl; + } +} +#else +inline void debug_traverse(Turn const& , Operation, const char*) +{ +} +#endif + + +//! Metafunction to define side_order (clockwise, ccw) by operation_type +template <operation_type OpType> +struct side_compare {}; + +template <> +struct side_compare<operation_union> +{ + typedef std::greater<int> type; +}; + +template <> +struct side_compare<operation_intersection> +{ + typedef std::less<int> type; +}; + + +template +< + bool Reverse1, + bool Reverse2, + overlay_type OverlayType, + typename Geometry1, + typename Geometry2, + typename Turns, + typename Clusters, + typename RobustPolicy, + typename Visitor +> +struct traversal +{ + static const operation_type target_operation = operation_from_overlay<OverlayType>::value; + + typedef typename side_compare<target_operation>::type side_compare_type; + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + typedef typename geometry::point_type<Geometry1>::type point_type; + typedef sort_by_side::side_sorter + < + Reverse1, Reverse2, + point_type, side_compare_type + > sbs_type; + + inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2, + Turns& turns, Clusters const& clusters, + RobustPolicy const& robust_policy, Visitor& visitor) + : m_geometry1(geometry1) + , m_geometry2(geometry2) + , m_turns(turns) + , m_clusters(clusters) + , m_robust_policy(robust_policy) + , m_visitor(visitor) + { + } + + inline void finalize_visit_info() + { + for (typename boost::range_iterator<Turns>::type + it = boost::begin(m_turns); + it != boost::end(m_turns); + ++it) + { + turn_type& turn = *it; + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + op.visited.finalize(); + } + } + } + + inline void set_visited(turn_type& turn, turn_operation_type& op) + { + // On "continue", set "visited" for ALL directions in this turn + if (op.operation == detail::overlay::operation_continue) + { + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + if (op.visited.none()) + { + op.visited.set_visited(); + } + } + } + else + { + op.visited.set_visited(); + } + } + + inline bool is_visited(turn_type const& turn, turn_operation_type const& op, + signed_size_type turn_index, int op_index) const + { + return op.visited.visited(); + } + + inline bool select_source(signed_size_type turn_index, + segment_identifier const& seg_id1, + segment_identifier const& seg_id2) const + { + if (target_operation == operation_intersection) + { + // For intersections always switch sources + return seg_id1.source_index != seg_id2.source_index; + } + else if (target_operation == operation_union) + { + // For uu, only switch sources if indicated + turn_type const& turn = m_turns[turn_index]; + + if (OverlayType == overlay_buffer) + { + // Buffer does not use source_index (always 0) + return turn.switch_source + ? seg_id1.multi_index != seg_id2.multi_index + : seg_id1.multi_index == seg_id2.multi_index; + } + +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + if (turn.switch_source == 1) + { + std::cout << "Switch source at " << turn_index << std::endl; + } + else + { + std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl; + } +#endif + return turn.switch_source + ? seg_id1.source_index != seg_id2.source_index + : seg_id1.source_index == seg_id2.source_index; + } + return false; + } + + inline + signed_size_type get_next_turn_index(turn_operation_type const& op) const + { + return op.enriched.next_ip_index == -1 + ? op.enriched.travels_to_ip_index + : op.enriched.next_ip_index; + } + + inline bool traverse_possible(signed_size_type turn_index) const + { + if (turn_index == -1) + { + return false; + } + + turn_type const& turn = m_turns[turn_index]; + + // It is not a dead end if there is an operation to continue, or of + // there is a cluster (assuming for now we can get out of the cluster) + return turn.cluster_id >= 0 + || turn.has(target_operation) + || turn.has(operation_continue); + } + + inline + bool select_cc_operation(turn_type const& turn, + signed_size_type start_turn_index, + int& selected_op_index) const + { + // For "cc", take either one, but if there is a starting one, + // take that one. If next is dead end, skip that one. + + bool result = false; + + typename turn_operation_type::comparable_distance_type + max_remaining_distance = 0; + + for (int i = 0; i < 2; i++) + { + turn_operation_type const& op = turn.operations[i]; + + signed_size_type const next_turn_index = get_next_turn_index(op); + + if (! result && traverse_possible(next_turn_index)) + { + max_remaining_distance = op.remaining_distance; + selected_op_index = i; + debug_traverse(turn, op, " Candidate"); + result = true; + } + + if (result) + { + if (next_turn_index == start_turn_index) + { + selected_op_index = i; + debug_traverse(turn, op, " Candidate cc override (start)"); + } + else if (op.remaining_distance > max_remaining_distance) + { + max_remaining_distance = op.remaining_distance; + selected_op_index = i; + debug_traverse(turn, op, " Candidate cc override (remaining)"); + } + } + } + + return result; + } + + inline + bool select_noncc_operation(turn_type const& turn, + signed_size_type turn_index, + segment_identifier const& seg_id, + int& selected_op_index) const + { + // For "ii", take the other one (alternate) + // UNLESS the other one is already visited + // For "uu", take the same one (see above); + + bool result = false; + + for (int i = 0; i < 2; i++) + { + turn_operation_type const& op = turn.operations[i]; + + if (op.operation == target_operation + && ! op.visited.finished() + && (! result || select_source(turn_index, op.seg_id, seg_id))) + { + selected_op_index = i; + debug_traverse(turn, op, " Candidate"); + result = true; + } + } + + return result; + } + + inline + bool select_operation(const turn_type& turn, + signed_size_type turn_index, + signed_size_type start_turn_index, + segment_identifier const& previous_seg_id, + int& selected_op_index) const + { + bool result = false; + selected_op_index = -1; + if (turn.both(operation_continue)) + { + result = select_cc_operation(turn, start_turn_index, + selected_op_index); + } + else + { + result = select_noncc_operation(turn, turn_index, + previous_seg_id, selected_op_index); + } + if (result) + { + debug_traverse(turn, turn.operations[selected_op_index], " Accepted"); + } + + return result; + } + + inline int starting_operation_index(const turn_type& turn) const + { + for (int i = 0; i < 2; i++) + { + if (turn.operations[i].visited.started()) + { + return i; + } + } + return -1; + } + + inline bool both_finished(const turn_type& turn) const + { + for (int i = 0; i < 2; i++) + { + if (! turn.operations[i].visited.finished()) + { + return false; + } + } + return true; + } + + inline bool select_from_cluster(signed_size_type& turn_index, + int& op_index, signed_size_type start_turn_index, + sbs_type const& sbs, bool is_touching) const + { + bool const is_union = target_operation == operation_union; + bool const is_intersection = target_operation == operation_intersection; + + std::size_t selected_rank = 0; + std::size_t min_rank = 0; + bool result = false; + for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + { + typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; + if (result && ranked_point.rank > selected_rank) + { + return result; + } + + turn_type const& ranked_turn = m_turns[ranked_point.turn_index]; + turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index]; + + if (result && ranked_op.visited.finalized()) + { + // One of the arcs in the same direction as the selected result + // is already traversed. + return false; + } + + if (! is_touching && ranked_op.visited.finalized()) + { + // Skip this one, go to next + min_rank = ranked_point.rank; + continue; + } + + if (ranked_point.direction == sort_by_side::dir_to + && (ranked_point.rank > min_rank + || ranked_turn.both(operation_continue))) + { + if ((is_union + && ranked_op.enriched.count_left == 0 + && ranked_op.enriched.count_right > 0) + || (is_intersection + && ranked_op.enriched.count_right == 2)) + { + if (result && ranked_point.turn_index != start_turn_index) + { + // Don't override - only override if arrive at start + continue; + } + + turn_index = ranked_point.turn_index; + op_index = ranked_point.operation_index; + + if (is_intersection + && ranked_turn.both(operation_intersection) + && ranked_op.visited.finalized()) + { + // Override: + // For a ii turn, even though one operation might be selected, + // it should take the other one if the first one is used in a completed ring + op_index = 1 - ranked_point.operation_index; + } + + result = true; + selected_rank = ranked_point.rank; + } + else if (! is_touching) + { + return result; + } + } + } + return result; + } + + inline bool select_turn_from_cluster(signed_size_type& turn_index, + int& op_index, bool& is_touching, + signed_size_type start_turn_index, + segment_identifier const& previous_seg_id) const + { + bool const is_union = target_operation == operation_union; + + turn_type const& turn = m_turns[turn_index]; + BOOST_ASSERT(turn.cluster_id >= 0); + + typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id); + BOOST_ASSERT(mit != m_clusters.end()); + + cluster_info const& cinfo = mit->second; + std::set<signed_size_type> const& ids = cinfo.turn_indices; + + sbs_type sbs; + + bool has_origin = false; + + for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); + sit != ids.end(); ++sit) + { + signed_size_type cluster_turn_index = *sit; + turn_type const& cluster_turn = m_turns[cluster_turn_index]; + if (cluster_turn.discarded) + { + // Defensive check, discarded turns should not be in cluster + continue; + } + + for (int i = 0; i < 2; i++) + { + turn_operation_type const& op = cluster_turn.operations[i]; + bool is_origin = false; + if (cluster_turn_index == turn_index) + { + // Check if this is the origin + if (OverlayType == overlay_buffer) + { + is_origin = op.seg_id.multi_index == previous_seg_id.multi_index; + } + else + { + is_origin = op.seg_id.source_index + == previous_seg_id.source_index; + } + if (is_origin) + { + has_origin = true; + } + } + + sbs.add(op, cluster_turn_index, i, m_geometry1, m_geometry2, + is_origin); + } + } + + if (! has_origin) + { + return false; + } + + sbs.apply(turn.point); + +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + is_touching = is_union && cinfo.open_count > 1; + if (is_touching) + { + if (cinfo.switch_source) + { + is_touching = false; + std::cout << "CLUSTER: SWITCH SOURCES at " << turn_index << std::endl; + } + else + { + std::cout << "CLUSTER: CONTINUE at " << turn_index << std::endl; + } + } +#else + is_touching = is_union && cinfo.open_count > 1 && ! cinfo.switch_source; +#endif + if (is_touching) + { + sbs.reverse(); + } + + return select_from_cluster(turn_index, op_index, start_turn_index, sbs, + is_touching); + } + + inline void change_index_for_self_turn(signed_size_type& to_vertex_index, + turn_type const& start_turn, + turn_operation_type const& start_op, + int start_op_index) const + { + if (OverlayType != overlay_buffer) + { + return; + } + + // It travels to itself, can happen. If this is a buffer, it can + // sometimes travel to itself in the following configuration: + // + // +---->--+ + // | | + // | +---*----+ *: one turn, with segment index 2/7 + // | | | | + // | +---C | C: closing point (start/end) + // | | + // +------------+ + // + // If it starts on segment 2 and travels to itself on segment 2, that + // should be corrected to 7 because that is the shortest path + // + // Also a uu turn (touching with another buffered ring) might have this + // apparent configuration, but there it should + // always travel the whole ring + + turn_operation_type const& other_op + = start_turn.operations[1 - start_op_index]; + + bool const correct + = ! start_turn.both(operation_union) + && start_op.seg_id.segment_index == to_vertex_index; + +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) + std::cout << " WARNING: self-buffer " + << " correct=" << correct + << " turn=" << operation_char(start_turn.operations[0].operation) + << operation_char(start_turn.operations[1].operation) + << " start=" << start_op.seg_id.segment_index + << " from=" << to_vertex_index + << " to=" << other_op.enriched.travels_to_vertex_index + << std::endl; +#endif + + if (correct) + { + to_vertex_index = other_op.enriched.travels_to_vertex_index; + } + } + + bool select_turn_from_enriched(signed_size_type& turn_index, + segment_identifier& previous_seg_id, + signed_size_type& to_vertex_index, + signed_size_type start_turn_index, + int start_op_index, + turn_type const& previous_turn, + turn_operation_type const& previous_op, + bool is_start) const + { + to_vertex_index = -1; + + if (previous_op.enriched.next_ip_index < 0) + { + // There is no next IP on this segment + if (previous_op.enriched.travels_to_vertex_index < 0 + || previous_op.enriched.travels_to_ip_index < 0) + { + return false; + } + + to_vertex_index = previous_op.enriched.travels_to_vertex_index; + + if (is_start && + previous_op.enriched.travels_to_ip_index == start_turn_index) + { + change_index_for_self_turn(to_vertex_index, previous_turn, + previous_op, start_op_index); + } + + turn_index = previous_op.enriched.travels_to_ip_index; + previous_seg_id = previous_op.seg_id; + } + else + { + // Take the next IP on this segment + turn_index = previous_op.enriched.next_ip_index; + previous_seg_id = previous_op.seg_id; + } + return true; + } + + bool select_turn(signed_size_type start_turn_index, + signed_size_type& turn_index, + int& op_index, + bool& is_touching, + int previous_op_index, + signed_size_type previous_turn_index, + segment_identifier const& previous_seg_id, + bool is_start) + { + if (m_turns[turn_index].cluster_id >= 0) + { + if (! select_turn_from_cluster(turn_index, op_index, is_touching, + start_turn_index, previous_seg_id)) + { + return false; + } + + if (is_start && turn_index == previous_turn_index) + { + op_index = previous_op_index; + } + } + else + { + turn_type const& current_turn = m_turns[turn_index]; + + op_index = starting_operation_index(current_turn); + if (op_index == -1) + { + if (both_finished(current_turn)) + { + return false; + } + + if (! select_operation(current_turn, turn_index, + start_turn_index, + previous_seg_id, + op_index)) + { + return false; + } + } + } + return true; + } + +private : + Geometry1 const& m_geometry1; + Geometry2 const& m_geometry2; + Turns& m_turns; + Clusters const& m_clusters; + RobustPolicy const& m_robust_policy; + Visitor& m_visitor; +}; + + + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp new file mode 100644 index 0000000000..104bd6b8e7 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp @@ -0,0 +1,347 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP + +#include <cstddef> + +#include <boost/range.hpp> + +#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/algorithms/detail/overlay/traversal.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> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + + +template +< + bool Reverse1, + bool Reverse2, + overlay_type OverlayType, + typename Geometry1, + typename Geometry2, + typename Turns, + typename Clusters, + typename RobustPolicy, + typename Visitor, + typename Backtrack +> +struct traversal_ring_creator +{ + typedef traversal<Reverse1, Reverse2, OverlayType, + Geometry1, Geometry2, Turns, Clusters, RobustPolicy, Visitor> + traversal_type; + + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + static const operation_type target_operation + = operation_from_overlay<OverlayType>::value; + + inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2, + Turns& turns, Clusters const& clusters, + RobustPolicy const& robust_policy, Visitor& visitor) + : m_trav(geometry1, geometry2, turns, clusters, robust_policy,visitor) + , m_geometry1(geometry1) + , m_geometry2(geometry2) + , m_turns(turns) + , m_clusters(clusters) + , m_robust_policy(robust_policy) + , m_visitor(visitor) + , m_has_uu(false) + { + + } + + template <typename Ring> + inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index, + int start_op_index, + signed_size_type& turn_index, + int& op_index, + Ring& current_ring, + bool is_start) + { + int const previous_op_index = op_index; + signed_size_type const previous_turn_index = turn_index; + turn_type& previous_turn = m_turns[turn_index]; + turn_operation_type& previous_op = previous_turn.operations[op_index]; + segment_identifier previous_seg_id; + + signed_size_type to_vertex_index = -1; + if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id, + to_vertex_index, start_turn_index, start_op_index, + previous_turn, previous_op, is_start)) + { + return is_start + ? traverse_error_no_next_ip_at_start + : traverse_error_no_next_ip; + } + if (to_vertex_index >= 0) + { + if (previous_op.seg_id.source_index == 0) + { + geometry::copy_segments<Reverse1>(m_geometry1, + previous_op.seg_id, to_vertex_index, + m_robust_policy, current_ring); + } + else + { + geometry::copy_segments<Reverse2>(m_geometry2, + previous_op.seg_id, to_vertex_index, + m_robust_policy, current_ring); + } + } + + if (m_turns[turn_index].discarded) + { + return is_start + ? traverse_error_dead_end_at_start + : traverse_error_dead_end; + } + + if (is_start) + { + // Register the start + previous_op.visited.set_started(); + m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); + } + + bool is_touching = false; + if (! m_trav.select_turn(start_turn_index, turn_index, op_index, + is_touching, + previous_op_index, previous_turn_index, previous_seg_id, + is_start)) + { + return is_start + ? traverse_error_no_next_ip_at_start + : traverse_error_no_next_ip; + } + + { + // Check operation (TODO: this might be redundant or should be catched before) + const turn_type& current_turn = m_turns[turn_index]; + const turn_operation_type& op = current_turn.operations[op_index]; + if (op.visited.finalized() + || m_trav.is_visited(current_turn, op, turn_index, op_index)) + { + return traverse_error_visit_again; + } + } + + // Update registration and append point + turn_type& current_turn = m_turns[turn_index]; + turn_operation_type& op = current_turn.operations[op_index]; + detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point, + m_robust_policy); + + // Register the visit + m_trav.set_visited(current_turn, op); + m_visitor.visit_traverse(m_turns, current_turn, op, "Visit"); + + return traverse_error_none; + } + + template <typename Ring> + inline traverse_error_type traverse(Ring& ring, + signed_size_type start_turn_index, int start_op_index) + { + turn_type const& start_turn = m_turns[start_turn_index]; + turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; + + detail::overlay::append_no_dups_or_spikes(ring, start_turn.point, + m_robust_policy); + + signed_size_type current_turn_index = start_turn_index; + int current_op_index = start_op_index; + + traverse_error_type error = travel_to_next_turn(start_turn_index, + start_op_index, + current_turn_index, current_op_index, + ring, true); + + if (error != traverse_error_none) + { + // This is not necessarily a problem, it happens for clustered turns + // which are "build in" or otherwise point inwards + return error; + } + + if (current_turn_index == start_turn_index) + { + start_op.visited.set_finished(); + m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish"); + return traverse_error_none; + } + + std::size_t const max_iterations = 2 + 2 * m_turns.size(); + for (std::size_t i = 0; i <= max_iterations; i++) + { + // We assume clockwise polygons only, non self-intersecting, closed. + // However, the input might be different, and checking validity + // is up to the library user. + + // Therefore we make here some sanity checks. If the input + // violates the assumptions, the output polygon will not be correct + // but the routine will stop and output the current polygon, and + // will continue with the next one. + + // Below three reasons to stop. + error = travel_to_next_turn(start_turn_index, start_op_index, + current_turn_index, current_op_index, + ring, false); + + if (error != traverse_error_none) + { + return error; + } + + if (current_turn_index == start_turn_index + && current_op_index == start_op_index) + { + start_op.visited.set_finished(); + m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish"); + return traverse_error_none; + } + } + + return traverse_error_endless_loop; + } + + template <typename Rings> + void traverse_with_operation(turn_type const& start_turn, + std::size_t turn_index, int op_index, + Rings& rings, std::size_t& finalized_ring_size, + typename Backtrack::state_type& state) + { + typedef typename boost::range_value<Rings>::type ring_type; + + turn_operation_type const& start_op = start_turn.operations[op_index]; + + if (! start_op.visited.none() + || ! start_op.enriched.startable + || start_op.visited.rejected() + || ! (start_op.operation == target_operation + || start_op.operation == detail::overlay::operation_continue)) + { + return; + } + + ring_type ring; + traverse_error_type traverse_error = traverse(ring, turn_index, op_index); + + if (traverse_error == traverse_error_none) + { + std::size_t const min_num_points + = core_detail::closure::minimum_ring_size + < + geometry::closure<ring_type>::value + >::value; + + if (geometry::num_points(ring) >= min_num_points) + { + clean_closing_dups_and_spikes(ring, m_robust_policy); + rings.push_back(ring); + + m_trav.finalize_visit_info(); + finalized_ring_size++; + } + } + else + { + Backtrack::apply( + finalized_ring_size, + rings, ring, m_turns, start_turn, + m_turns[turn_index].operations[op_index], + traverse_error, + m_geometry1, m_geometry2, m_robust_policy, + state, m_visitor); + } + } + + template <typename Rings> + void iterate(Rings& rings, std::size_t& finalized_ring_size, + typename Backtrack::state_type& state, + int pass) + { + if (pass == 1) + { + if (target_operation == operation_intersection) + { + // Second pass currently only used for uu + return; + } + if (! m_has_uu) + { + // There is no uu found in first pass + return; + } + } + + // Iterate through all unvisited points + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type const& start_turn = m_turns[turn_index]; + + if (start_turn.discarded || start_turn.blocked()) + { + // Skip discarded and blocked turns + continue; + } + if (target_operation == operation_union) + { + if (start_turn.both(operation_union)) + { + // Start with a uu-turn only in the second pass + m_has_uu = true; + if (pass == 0) + { + continue; + } + } + } + + for (int op_index = 0; op_index < 2; op_index++) + { + traverse_with_operation(start_turn, turn_index, op_index, + rings, finalized_ring_size, state); + } + } + } + +private: + traversal_type m_trav; + + Geometry1 const& m_geometry1; + Geometry2 const& m_geometry2; + Turns& m_turns; + Clusters const& m_clusters; + RobustPolicy const& m_robust_policy; + Visitor& m_visitor; + + // Next member is only used for operation union + bool m_has_uu; + +}; + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp new file mode 100644 index 0000000000..9381c66e0e --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp @@ -0,0 +1,291 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015-2016 Barend Gehrels, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP + +#include <cstddef> + +#include <boost/range.hpp> + +#include <boost/geometry/algorithms/detail/ring_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> +#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/assert.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + +// Generic function (is this used somewhere else too?) +inline ring_identifier ring_id_by_seg_id(segment_identifier const& seg_id) +{ + return ring_identifier(seg_id.source_index, seg_id.multi_index, seg_id.ring_index); +} + +template +< + bool Reverse1, + bool Reverse2, + overlay_type OverlayType, + typename Geometry1, + typename Geometry2, + typename Turns, + typename Clusters, + typename RobustPolicy, + typename Visitor +> +struct traversal_switch_detector +{ + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + // For convenience + typedef std::set<signed_size_type>::const_iterator set_iterator; + + inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2, + Turns& turns, Clusters& clusters, + RobustPolicy const& robust_policy, Visitor& visitor) + : m_geometry1(geometry1) + , m_geometry2(geometry2) + , m_turns(turns) + , m_clusters(clusters) + , m_robust_policy(robust_policy) + , m_visitor(visitor) + , m_region_id(0) + { + + } + + static inline bool connects_same_zone(turn_type const& turn) + { + if (turn.cluster_id == -1) + { + // If it is a uu-turn (non clustered), it is never same zone + return ! turn.both(operation_union); + } + + // It is a cluster, check zones of both operations + return turn.operations[0].enriched.zone + == turn.operations[1].enriched.zone; + } + + inline int get_region_id(turn_operation_type const& op) const + { + std::map<ring_identifier, int>::const_iterator it + = m_regions.find(ring_id_by_seg_id(op.seg_id)); + return it == m_regions.end() ? -1 : it->second; + } + + void create_region(ring_identifier const& ring_id, std::set<signed_size_type> const& ring_turn_indices, int region_id = -1) + { + std::map<ring_identifier, int>::const_iterator it = m_regions.find(ring_id); + if (it != m_regions.end()) + { + // The ring is already gathered in a region, quit + return; + } + if (region_id == -1) + { + region_id = m_region_id++; + } + + // Assign this ring to specified region + m_regions[ring_id] = region_id; +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl; +#endif + + // Find connecting rings, recursively + for (set_iterator sit = ring_turn_indices.begin(); + sit != ring_turn_indices.end(); ++sit) + { + int const turn_index = *sit; + turn_type const& turn = m_turns[turn_index]; + if (! connects_same_zone(turn)) + { + // This is a non clustered uu-turn, or a cluster connecting different 'zones' + continue; + } + + // This turn connects two rings (interior connected), create the + // same region + for (int op_index = 0; op_index < 2; op_index++) + { + turn_operation_type const& op = turn.operations[op_index]; + ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id); + if (connected_ring_id != ring_id) + { + propagate_region(connected_ring_id, region_id); + } + } + } + } + + void propagate_region(ring_identifier const& ring_id, int region_id) + { + std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it = m_turns_per_ring.find(ring_id); + if (it != m_turns_per_ring.end()) + { + create_region(ring_id, it->second, region_id); + } + } + + void iterate() + { +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + std::cout << "SWITCH BEGIN ITERATION" << std::endl; +#endif + + // Collect turns per ring + m_turns_per_ring.clear(); + m_regions.clear(); + m_region_id = 1; + + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type const& turn = m_turns[turn_index]; + + for (int op_index = 0; op_index < 2; op_index++) + { + turn_operation_type const& op = turn.operations[op_index]; + m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].insert(turn_index); + } + } + + // All rings having turns are in the map. Now iterate them + for (std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it + = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) + { + create_region(it->first, it->second); + } + + // Now that all regions are filled, assign switch_source property + // Iterate through all clusters + for (typename Clusters::iterator it = m_clusters.begin(); it != m_clusters.end(); ++it) + { + cluster_info& cinfo = it->second; + if (cinfo.open_count <= 1) + { + // Not a touching cluster + continue; + } + + // A touching cluster, gather regions + std::set<int> regions; + + std::set<signed_size_type> const& ids = cinfo.turn_indices; + +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl; +#endif + + for (set_iterator sit = ids.begin(); sit != ids.end(); ++sit) + { + signed_size_type turn_index = *sit; + turn_type const& turn = m_turns[turn_index]; + for (int oi = 0; oi < 2; oi++) + { + int const region = get_region_id(turn.operations[oi]); + regions.insert(region); + } + } + // Switch source if this cluster connects the same region + cinfo.switch_source = regions.size() == 1; + } + + // Iterate through all uu turns (non-clustered) + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type& turn = m_turns[turn_index]; + + if (turn.discarded + || turn.blocked() + || turn.cluster_id >= 0 + || ! turn.both(operation_union)) + { + // Skip discarded, blocked, non-uu and clustered turns + continue; + } + + if (OverlayType == overlay_buffer) + { + // For deflate, the region approach does not work because many + // pieces are outside the real polygons + // TODO: implement this in another way for buffer + // (because now buffer might output invalid geometries) + continue; + } + + int const region0 = get_region_id(turn.operations[0]); + int const region1 = get_region_id(turn.operations[1]); + + // Switch sources for same region + turn.switch_source = region0 == region1; + } + + +#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + std::cout << "SWITCH END ITERATION" << std::endl; + + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type const& turn = m_turns[turn_index]; + + if (turn.both(operation_union) && turn.cluster_id < 0) + { + std::cout << "UU SWITCH RESULT " + << turn_index << " -> " + << turn.switch_source << std::endl; + } + } + + for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it) + { + cluster_info const& cinfo = it->second; + if (cinfo.open_count > 1) + { + std::cout << "CL SWITCH RESULT " << it->first + << " -> " << cinfo.switch_source << std::endl; + } + else + { + std::cout << "CL SWITCH RESULT " << it->first + << " is not registered as open" << std::endl; + } + } +#endif + + } + +private: + + Geometry1 const& m_geometry1; + Geometry2 const& m_geometry2; + Turns& m_turns; + Clusters& m_clusters; + RobustPolicy const& m_robust_policy; + Visitor& m_visitor; + + std::map<ring_identifier, int> m_regions; + std::map<ring_identifier, std::set<signed_size_type> > m_turns_per_ring; + int m_region_id; + +}; + +}} // namespace detail::overlay +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index a8f4232124..2d2933ebdd 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -11,26 +11,10 @@ #include <cstddef> -#include <boost/range.hpp> - #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp> -#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> -#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> -#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> +#include <boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp> +#include <boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp> -#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \ - || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \ - || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) -# include <string> -# include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> -# include <boost/geometry/io/wkt/wkt.hpp> -#endif namespace boost { namespace geometry { @@ -39,783 +23,38 @@ namespace boost { namespace geometry namespace detail { namespace overlay { -template <typename Turn, typename Operation> -#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE -inline void debug_traverse(Turn const& turn, Operation op, - std::string const& header) -{ - std::cout << header - << " at " << op.seg_id - << " meth: " << method_char(turn.method) - << " op: " << operation_char(op.operation) - << " vis: " << visited_char(op.visited) - << " of: " << operation_char(turn.operations[0].operation) - << operation_char(turn.operations[1].operation) - << " " << geometry::wkt(turn.point) - << std::endl; - - if (boost::contains(header, "Finished")) - { - std::cout << std::endl; - } -} -#else -inline void debug_traverse(Turn const& , Operation, const char*) -{ -} -#endif - - -//! Metafunction to define side_order (clockwise, ccw) by operation_type -template <operation_type OpType> -struct side_compare {}; - -template <> -struct side_compare<operation_union> -{ - typedef std::greater<int> type; -}; - -template <> -struct side_compare<operation_intersection> -{ - typedef std::less<int> type; -}; - +/*! + \brief Traverses through intersection points / geometries + \ingroup overlay + */ template < - bool Reverse1, - bool Reverse2, - operation_type OperationType, + bool Reverse1, bool Reverse2, typename Geometry1, typename Geometry2, - typename Turns, - typename Clusters, - typename RobustPolicy, - typename Visitor, - typename Backtrack + overlay_type OverlayType, + typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2> > -struct traversal +class traverse { - typedef typename side_compare<OperationType>::type side_compare_type; - typedef typename boost::range_value<Turns>::type turn_type; - typedef typename turn_type::turn_operation_type turn_operation_type; - - typedef typename geometry::point_type<Geometry1>::type point_type; - typedef sort_by_side::side_sorter - < - Reverse1, Reverse2, - point_type, side_compare_type - > sbs_type; - - inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2, - Turns& turns, Clusters const& clusters, - RobustPolicy const& robust_policy, Visitor& visitor) - : m_geometry1(geometry1) - , m_geometry2(geometry2) - , m_turns(turns) - , m_clusters(clusters) - , m_robust_policy(robust_policy) - , m_visitor(visitor) - , m_has_uu(false) - , m_has_only_uu(true) - , m_switch_at_uu(true) - {} - - - inline bool select_source(signed_size_type turn_index, - segment_identifier const& seg_id1, - segment_identifier const& seg_id2) - { - if (OperationType == operation_intersection) - { - // For intersections always switch sources - return seg_id1.source_index != seg_id2.source_index; - } - else if (OperationType == operation_union) - { - // For uu, only switch sources if indicated - turn_type const& turn = m_turns[turn_index]; - - // TODO: pass this information - bool const is_buffer - = turn.operations[0].seg_id.source_index - == turn.operations[1].seg_id.source_index; - - if (is_buffer) - { - // Buffer does not use source_index (always 0) - return turn.switch_source - ? seg_id1.multi_index != seg_id2.multi_index - : seg_id1.multi_index == seg_id2.multi_index; - } - - // Temporarily use m_switch_at_uu, which does not solve all cases, - // but the majority of the more simple cases, making the interior - // rings valid - return m_switch_at_uu // turn.switch_source - ? seg_id1.source_index != seg_id2.source_index - : seg_id1.source_index == seg_id2.source_index; - } - return false; - } - - inline - signed_size_type get_next_turn_index(turn_operation_type const& op) const - { - return op.enriched.next_ip_index == -1 - ? op.enriched.travels_to_ip_index - : op.enriched.next_ip_index; - } - - inline bool traverse_possible(signed_size_type turn_index) const - { - if (turn_index == -1) - { - return false; - } - - turn_type const& turn = m_turns[turn_index]; - - // It is not a dead end if there is an operation to continue, or of - // there is a cluster (assuming for now we can get out of the cluster) - return turn.cluster_id >= 0 - || turn.has(OperationType) - || turn.has(operation_continue); - } - - inline bool select_operation(turn_type& turn, - signed_size_type start_turn_index, - segment_identifier const& seg_id, - int& selected_op_index) - { - if (turn.discarded) - { - return false; - } - - bool result = false; - - typename turn_operation_type::comparable_distance_type - max_remaining_distance = 0; - - selected_op_index = -1; - for (int i = 0; i < 2; i++) - { - turn_operation_type const& op = turn.operations[i]; - if (op.visited.started()) - { - selected_op_index = i; - return true; - } - - signed_size_type const next_turn_index = get_next_turn_index(op); - - // In some cases there are two alternatives. - // For "ii", take the other one (alternate) - // UNLESS the other one is already visited - // For "uu", take the same one (see above); - // For "cc", take either one, but if there is a starting one, - // take that one. If next is dead end, skip that one. - if ( (op.operation == operation_continue - && traverse_possible(next_turn_index) - && ! result) - || (op.operation == OperationType - && ! op.visited.finished() - && (! result - || select_source(next_turn_index, op.seg_id, seg_id) - ) - ) - ) - { - if (op.operation == operation_continue) - { - max_remaining_distance = op.remaining_distance; - } - selected_op_index = i; - debug_traverse(turn, op, " Candidate"); - result = true; - } - - if (op.operation == operation_continue && result) - { - if (next_turn_index == start_turn_index) - { - selected_op_index = i; - debug_traverse(turn, op, " Candidate override (start)"); - } - else if (op.remaining_distance > max_remaining_distance) - { - max_remaining_distance = op.remaining_distance; - selected_op_index = i; - debug_traverse(turn, op, " Candidate override (remaining)"); - } - } - } - - if (result) - { - debug_traverse(turn, turn.operations[selected_op_index], " Accepted"); - } - - return result; - } - - inline bool select_from_cluster(signed_size_type& turn_index, - int& op_index, signed_size_type start_turn_index, - sbs_type const& sbs, bool allow_pass_rank) - { - bool const is_union = OperationType == operation_union; - bool const is_intersection = OperationType == operation_intersection; - - std::size_t selected_rank = 0; - std::size_t min_rank = 0; - bool result = false; - for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) - { - typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; - if (result && ranked_point.main_rank > selected_rank) - { - return result; - } - - turn_type const& ranked_turn = m_turns[ranked_point.turn_index]; - turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.op_index]; - - if (result && ranked_op.visited.finalized()) - { - // One of the arcs in the same direction as the selected result - // is already traversed. - return false; - } - - if (! allow_pass_rank && ranked_op.visited.finalized()) - { - // Skip this one, go to next - min_rank = ranked_point.main_rank; - continue; - } - - if (ranked_point.index == sort_by_side::index_to - && (ranked_point.main_rank > min_rank - || ranked_turn.both(operation_continue))) - { - if ((is_union - && ranked_op.enriched.count_left == 0 - && ranked_op.enriched.count_right > 0) - || (is_intersection - && ranked_op.enriched.count_right == 2)) - { - if (result && ranked_point.turn_index != start_turn_index) - { - // Don't override - only override if arrive at start - continue; - } - - turn_index = ranked_point.turn_index; - op_index = ranked_point.op_index; - - if (is_intersection - && ranked_turn.both(operation_intersection) - && ranked_op.visited.finalized()) - { - // Override: - // For a ii turn, even though one operation might be selected, - // it should take the other one if the first one is used in a completed ring - op_index = 1 - ranked_point.op_index; - } - - result = true; - selected_rank = ranked_point.main_rank; - } - else if (! allow_pass_rank) - { - return result; - } - } - } - return result; - } - - inline bool select_turn_from_cluster(signed_size_type& turn_index, - int& op_index, signed_size_type start_turn_index, - point_type const& point) - { - bool const is_union = OperationType == operation_union; - - turn_type const& turn = m_turns[turn_index]; - BOOST_ASSERT(turn.cluster_id >= 0); - - typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id); - BOOST_ASSERT(mit != m_clusters.end()); - - std::set<signed_size_type> const& ids = mit->second; - - sbs_type sbs; - sbs.set_origin(point); - - for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); - sit != ids.end(); ++sit) - { - signed_size_type cluster_turn_index = *sit; - turn_type const& cluster_turn = m_turns[cluster_turn_index]; - if (cluster_turn.discarded) - { - // Defensive check, discarded turns should not be in cluster - continue; - } - - for (int i = 0; i < 2; i++) - { - sbs.add(cluster_turn.operations[i], cluster_turn_index, i, - m_geometry1, m_geometry2, false); - } - } - - sbs.apply(turn.point); - - int open_count = 0; - if (is_union) - { - // Check how many open spaces there are. - // TODO: might be moved to sbs itself, though it also uses turns - - std::size_t last_rank = 0; - for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) - { - typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; - - if (ranked_point.main_rank > last_rank - && ranked_point.index == sort_by_side::index_to) - { - turn_type const& ranked_turn = m_turns[ranked_point.turn_index]; - turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.op_index]; - if (ranked_op.enriched.count_left == 0 - && ranked_op.enriched.count_right > 0) - { - open_count++; - last_rank = ranked_point.main_rank; - } - } - } - } - - bool allow = false; - if (open_count > 1) - { - sbs.reverse(); - allow = true; - } - - return select_from_cluster(turn_index, op_index, start_turn_index, sbs, allow); - } - - inline void change_index_for_self_turn(signed_size_type& to_vertex_index, - turn_type const& start_turn, - turn_operation_type const& start_op, - int start_op_index) - { - turn_operation_type const& other_op - = start_turn.operations[1 - start_op_index]; - if (start_op.seg_id.source_index != other_op.seg_id.source_index) - { - // Not a buffer/self-turn - return; - } - - // It travels to itself, can happen. If this is a buffer, it can - // sometimes travel to itself in the following configuration: - // - // +---->--+ - // | | - // | +---*----+ *: one turn, with segment index 2/7 - // | | | | - // | +---C | C: closing point (start/end) - // | | - // +------------+ - // - // If it starts on segment 2 and travels to itself on segment 2, that - // should be corrected to 7 because that is the shortest path - // - // Also a uu turn (touching with another buffered ring) might have this - // apparent configuration, but there it should - // always travel the whole ring - - bool const correct - = ! start_turn.both(operation_union) - && start_op.seg_id.segment_index == to_vertex_index; - -#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) - std::cout << " WARNING: self-buffer " - << " correct=" << correct - << " turn=" << operation_char(start_turn.operations[0].operation) - << operation_char(start_turn.operations[1].operation) - << " start=" << start_op.seg_id.segment_index - << " from=" << to_vertex_index - << " to=" << other_op.enriched.travels_to_vertex_index - << std::endl; -#endif - - if (correct) - { - to_vertex_index = other_op.enriched.travels_to_vertex_index; - } - } - - template <typename Ring> - inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index, - int start_op_index, - signed_size_type& turn_index, - int& op_index, - segment_identifier& seg_id, - Ring& current_ring, - bool is_start) - { - int const previous_op_index = op_index; - signed_size_type const previous_turn_index = turn_index; - turn_type& previous_turn = m_turns[turn_index]; - turn_operation_type& previous_op = previous_turn.operations[op_index]; - - // If there is no next IP on this segment - if (previous_op.enriched.next_ip_index < 0) - { - if (previous_op.enriched.travels_to_vertex_index < 0 - || previous_op.enriched.travels_to_ip_index < 0) - { - return is_start - ? traverse_error_no_next_ip_at_start - : traverse_error_no_next_ip; - } - - signed_size_type to_vertex_index = previous_op.enriched.travels_to_vertex_index; - - if (is_start && - previous_op.enriched.travels_to_ip_index == start_turn_index) - { - change_index_for_self_turn(to_vertex_index, previous_turn, - previous_op, start_op_index); - } - - if (previous_op.seg_id.source_index == 0) - { - geometry::copy_segments<Reverse1>(m_geometry1, - previous_op.seg_id, to_vertex_index, - m_robust_policy, current_ring); - } - else - { - geometry::copy_segments<Reverse2>(m_geometry2, - previous_op.seg_id, to_vertex_index, - m_robust_policy, current_ring); - } - seg_id = previous_op.seg_id; - turn_index = previous_op.enriched.travels_to_ip_index; - } - else - { - turn_index = previous_op.enriched.next_ip_index; - seg_id = previous_op.seg_id; - } - - // turn_index is not yet finally selected, can change for clusters - bool const has_cluster = m_turns[turn_index].cluster_id >= 0; - if (has_cluster) - { - - if (! select_turn_from_cluster(turn_index, op_index, - start_turn_index, current_ring.back())) - { - return is_start - ? traverse_error_no_next_ip_at_start - : traverse_error_no_next_ip; - } - if (is_start && turn_index == previous_turn_index) - { - op_index = previous_op_index; - } - } - - turn_type& current_turn = m_turns[turn_index]; - detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point, - m_robust_policy); - - if (is_start) - { - // Register the start - previous_op.visited.set_started(); - m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); - } - - if (! has_cluster) - { - if (! select_operation(current_turn, - start_turn_index, - seg_id, - op_index)) - { - return is_start - ? traverse_error_dead_end_at_start - : traverse_error_dead_end; - } - } - - turn_operation_type& op = current_turn.operations[op_index]; - if (op.visited.finalized() || op.visited.visited()) - { - return traverse_error_visit_again; - } - - // Register the visit - set_visited(current_turn, op); - m_visitor.visit_traverse(m_turns, current_turn, op, "Visit"); - - return traverse_error_none; - } - - inline void finalize_visit_info() + template <typename Turns> + static void reset_visits(Turns& turns) { for (typename boost::range_iterator<Turns>::type - it = boost::begin(m_turns); - it != boost::end(m_turns); + it = boost::begin(turns); + it != boost::end(turns); ++it) { - turn_type& turn = *it; for (int i = 0; i < 2; i++) { - turn_operation_type& op = turn.operations[i]; - op.visited.finalize(); - } - } - } - - inline void set_visited(turn_type& turn, turn_operation_type& op) - { - // On "continue", set "visited" for ALL directions in this turn - if (op.operation == detail::overlay::operation_continue) - { - for (int i = 0; i < 2; i++) - { - turn_operation_type& op = turn.operations[i]; - if (op.visited.none()) - { - op.visited.set_visited(); - } - } - } - else - { - op.visited.set_visited(); - } - } - - - template <typename Ring> - inline traverse_error_type traverse(Ring& ring, - signed_size_type start_turn_index, int start_op_index) - { - turn_type const& start_turn = m_turns[start_turn_index]; - turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; - - detail::overlay::append_no_dups_or_spikes(ring, start_turn.point, - m_robust_policy); - - signed_size_type current_turn_index = start_turn_index; - int current_op_index = start_op_index; - segment_identifier current_seg_id; - - traverse_error_type error = travel_to_next_turn(start_turn_index, - start_op_index, - current_turn_index, current_op_index, current_seg_id, - ring, true); - - if (error != traverse_error_none) - { - // This is not necessarily a problem, it happens for clustered turns - // which are "build in" or otherwise point inwards - return error; - } - - if (current_turn_index == start_turn_index) - { - start_op.visited.set_finished(); - m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish"); - return traverse_error_none; - } - - std::size_t const max_iterations = 2 + 2 * m_turns.size(); - for (std::size_t i = 0; i <= max_iterations; i++) - { - // We assume clockwise polygons only, non self-intersecting, closed. - // However, the input might be different, and checking validity - // is up to the library user. - - // Therefore we make here some sanity checks. If the input - // violates the assumptions, the output polygon will not be correct - // but the routine will stop and output the current polygon, and - // will continue with the next one. - - // Below three reasons to stop. - error = travel_to_next_turn(start_turn_index, start_op_index, - current_turn_index, current_op_index, current_seg_id, - ring, false); - - if (error != traverse_error_none) - { - return error; - } - - if (current_turn_index == start_turn_index - && current_op_index == start_op_index) - { - start_op.visited.set_finished(); - m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish"); - return traverse_error_none; - } - } - - return traverse_error_endless_loop; - } - - template <typename Rings> - void traverse_with_operation(turn_type const& start_turn, - std::size_t turn_index, int op_index, - Rings& rings, std::size_t& finalized_ring_size, - typename Backtrack::state_type& state) - { - typedef typename boost::range_value<Rings>::type ring_type; - - turn_operation_type const& start_op = start_turn.operations[op_index]; - - if (! start_op.visited.none() - || ! start_op.enriched.startable - || start_op.visited.rejected() - || ! (start_op.operation == OperationType - || start_op.operation == detail::overlay::operation_continue)) - { - return; - } - - ring_type ring; - traverse_error_type traverse_error = traverse(ring, turn_index, op_index); - - if (traverse_error == traverse_error_none) - { - std::size_t const min_num_points - = core_detail::closure::minimum_ring_size - < - geometry::closure<ring_type>::value - >::value; - - if (geometry::num_points(ring) >= min_num_points) - { - clean_closing_dups_and_spikes(ring, m_robust_policy); - rings.push_back(ring); - - finalize_visit_info(); - finalized_ring_size++; + it->operations[i].visited.reset(); } } - else - { - Backtrack::apply( - finalized_ring_size, - rings, ring, m_turns, start_turn, - m_turns[turn_index].operations[op_index], - traverse_error, - m_geometry1, m_geometry2, m_robust_policy, - state, m_visitor); - } } - template <typename Rings> - void iterate(Rings& rings, std::size_t& finalized_ring_size, - typename Backtrack::state_type& state, - int pass) - { - if (pass == 1) - { - if (OperationType == operation_intersection) - { - // Second pass currently only used for uu - return; - } - if (! m_has_uu) - { - // There is no uu found in first pass - return; - } - if (m_has_only_uu) - { - m_switch_at_uu = false; - } - } - - // Iterate through all unvisited points - for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) - { - turn_type const& start_turn = m_turns[turn_index]; - if (start_turn.discarded || start_turn.blocked()) - { - // Skip discarded and blocked turns - continue; - } - if (OperationType == operation_union) - { - if (start_turn.both(operation_union)) - { - // Start with a uu-turn only in the second pass - m_has_uu = true; - if (pass == 0) - { - continue; - } - } - else - { - m_has_only_uu = false; - } - } - - for (int op_index = 0; op_index < 2; op_index++) - { - traverse_with_operation(start_turn, turn_index, op_index, - rings, finalized_ring_size, state); - } - } - } - -private : - Geometry1 const& m_geometry1; - Geometry2 const& m_geometry2; - Turns& m_turns; - Clusters const& m_clusters; - RobustPolicy const& m_robust_policy; - Visitor& m_visitor; - - // Next members are only used for operation union - bool m_has_uu; - bool m_has_only_uu; - bool m_switch_at_uu; -}; - - -/*! - \brief Traverses through intersection points / geometries - \ingroup overlay - */ -template -< - bool Reverse1, bool Reverse2, - typename Geometry1, - typename Geometry2, - operation_type OperationType, - typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2> -> -class traverse -{ public : template < @@ -829,12 +68,24 @@ public : Geometry2 const& geometry2, RobustPolicy const& robust_policy, Turns& turns, Rings& rings, - Clusters const& clusters, + Clusters& clusters, Visitor& visitor) { - traversal + traversal_switch_detector + < + Reverse1, Reverse2, OverlayType, + Geometry1, Geometry2, + Turns, Clusters, + RobustPolicy, Visitor + > switch_detector(geometry1, geometry2, turns, clusters, + robust_policy, visitor); + + switch_detector.iterate(); + reset_visits(turns); + + traversal_ring_creator < - Reverse1, Reverse2, OperationType, + Reverse1, Reverse2, OverlayType, Geometry1, Geometry2, Turns, Clusters, RobustPolicy, Visitor, diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index 699997fc38..73f266a04a 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -14,6 +14,7 @@ #include <boost/geometry/core/coordinate_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> namespace boost { namespace geometry { @@ -22,18 +23,6 @@ namespace boost { namespace geometry namespace detail { namespace overlay { - -enum operation_type -{ - operation_none, - operation_union, - operation_intersection, - operation_blocked, - operation_continue, - operation_opposite -}; - - enum method_type { method_none, diff --git a/boost/geometry/algorithms/detail/overlay/visit_info.hpp b/boost/geometry/algorithms/detail/overlay/visit_info.hpp index 9e1e6b9056..e401fbbb49 100644 --- a/boost/geometry/algorithms/detail/overlay/visit_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/visit_info.hpp @@ -61,6 +61,11 @@ public: } } + inline void reset() + { + *this = visit_info(); + } + inline void finalize() { if (visited() || started() || finished() ) diff --git a/boost/geometry/algorithms/detail/point_on_border.hpp b/boost/geometry/algorithms/detail/point_on_border.hpp index 24b88a8d19..1c751c23e4 100644 --- a/boost/geometry/algorithms/detail/point_on_border.hpp +++ b/boost/geometry/algorithms/detail/point_on_border.hpp @@ -286,8 +286,8 @@ inline bool point_on_border(Point& point, Geometry const& geometry, bool midpoint = false) { - concept::check<Point>(); - concept::check<Geometry const>(); + concepts::check<Point>(); + concepts::check<Geometry const>(); return dispatch::point_on_border < diff --git a/boost/geometry/algorithms/detail/recalculate.hpp b/boost/geometry/algorithms/detail/recalculate.hpp index fd3ed6b8da..b75dd135e0 100644 --- a/boost/geometry/algorithms/detail/recalculate.hpp +++ b/boost/geometry/algorithms/detail/recalculate.hpp @@ -219,8 +219,8 @@ struct recalculate<Polygon1, Polygon2, polygon_tag, polygon_tag> template <typename Geometry1, typename Geometry2, typename Strategy> inline void recalculate(Geometry1& geometry1, Geometry2 const& geometry2, Strategy const& strategy) { - concept::check<Geometry1>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1>(); + concepts::check<Geometry2 const>(); // static assert dimensions (/types) are the same diff --git a/boost/geometry/algorithms/detail/relate/interface.hpp b/boost/geometry/algorithms/detail/relate/interface.hpp index e2c067b68d..95d452931c 100644 --- a/boost/geometry/algorithms/detail/relate/interface.hpp +++ b/boost/geometry/algorithms/detail/relate/interface.hpp @@ -199,8 +199,8 @@ struct relate Geometry2 const& geometry2, Mask const& mask) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); assert_dimension_equal<Geometry1, Geometry2>(); typename detail::relate::result_handler_type diff --git a/boost/geometry/algorithms/detail/relate/linear_areal.hpp b/boost/geometry/algorithms/detail/relate/linear_areal.hpp index e7cbf6f6c2..58ba7bd1af 100644 --- a/boost/geometry/algorithms/detail/relate/linear_areal.hpp +++ b/boost/geometry/algorithms/detail/relate/linear_areal.hpp @@ -1149,6 +1149,8 @@ struct linear_areal Geometry2 const& geometry2, Turn const& turn) { + typedef typename cs_tag<typename Turn::point_type>::type cs_tag; + if ( turn.operations[op_id].position == overlay::position_front ) return false; @@ -1192,7 +1194,7 @@ struct linear_areal boost::end(range2)); // Will this sequence of points be always correct? - overlay::side_calculator<point1_type, point2_type> side_calc(qi_conv, new_pj, pi, qi, qj, *qk_it); + overlay::side_calculator<cs_tag, point1_type, point2_type> side_calc(qi_conv, new_pj, pi, qi, qj, *qk_it); return calculate_from_inside_sides(side_calc); } @@ -1201,7 +1203,7 @@ struct linear_areal point1_type new_qj; geometry::convert(turn.point, new_qj); - overlay::side_calculator<point1_type, point2_type> side_calc(qi_conv, new_pj, pi, qi, new_qj, qj); + overlay::side_calculator<cs_tag, point1_type, point2_type> side_calc(qi_conv, new_pj, pi, qi, new_qj, qj); return calculate_from_inside_sides(side_calc); } @@ -1414,10 +1416,14 @@ struct linear_areal template <typename Geometry1, typename Geometry2> struct areal_linear { + typedef linear_areal<Geometry2, Geometry1, true> linear_areal_type; + + static const bool interruption_enabled = linear_areal_type::interruption_enabled; + template <typename Result> static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Result & result) { - linear_areal<Geometry2, Geometry1, true>::apply(geometry2, geometry1, result); + linear_areal_type::apply(geometry2, geometry1, result); } }; diff --git a/boost/geometry/algorithms/detail/relation/interface.hpp b/boost/geometry/algorithms/detail/relation/interface.hpp index 73737cf2c2..e9a9474551 100644 --- a/boost/geometry/algorithms/detail/relation/interface.hpp +++ b/boost/geometry/algorithms/detail/relation/interface.hpp @@ -46,8 +46,8 @@ struct relation static inline Matrix apply(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); assert_dimension_equal<Geometry1, Geometry2>(); typename detail::relate::result_handler_type diff --git a/boost/geometry/algorithms/detail/ring_identifier.hpp b/boost/geometry/algorithms/detail/ring_identifier.hpp index 9ba39e4a8b..4a7e717cf7 100644 --- a/boost/geometry/algorithms/detail/ring_identifier.hpp +++ b/boost/geometry/algorithms/detail/ring_identifier.hpp @@ -56,6 +56,11 @@ struct ring_identifier ; } + inline bool operator!=(ring_identifier const& other) const + { + return ! operator==(other); + } + #if defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER) friend std::ostream& operator<<(std::ostream &os, ring_identifier const& ring_id) { diff --git a/boost/geometry/algorithms/detail/sections/range_by_section.hpp b/boost/geometry/algorithms/detail/sections/range_by_section.hpp index 02cec6cb48..611ad172d2 100644 --- a/boost/geometry/algorithms/detail/sections/range_by_section.hpp +++ b/boost/geometry/algorithms/detail/sections/range_by_section.hpp @@ -177,7 +177,7 @@ template <typename Geometry, typename Section> inline typename ring_return_type<Geometry const>::type range_by_section(Geometry const& geometry, Section const& section) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::range_by_section < diff --git a/boost/geometry/algorithms/detail/sections/sectionalize.hpp b/boost/geometry/algorithms/detail/sections/sectionalize.hpp index 6443965e95..3ed5b8db07 100644 --- a/boost/geometry/algorithms/detail/sections/sectionalize.hpp +++ b/boost/geometry/algorithms/detail/sections/sectionalize.hpp @@ -31,6 +31,7 @@ #include <boost/static_assert.hpp> #include <boost/geometry/algorithms/assign.hpp> +#include <boost/geometry/algorithms/envelope.hpp> #include <boost/geometry/algorithms/expand.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> @@ -268,6 +269,49 @@ struct assign_loop<T, Count, Count> } }; +template <typename CSTag> +struct box_first_in_section +{ + template <typename Box, typename Point> + static inline void apply(Box & box, Point const& prev, Point const& curr) + { + geometry::model::referring_segment<Point const> seg(prev, curr); + geometry::envelope(seg, box); + } +}; + +template <> +struct box_first_in_section<cartesian_tag> +{ + template <typename Box, typename Point> + static inline void apply(Box & box, Point const& prev, Point const& curr) + { + geometry::envelope(prev, box); + geometry::expand(box, curr); + } +}; + +template <typename CSTag> +struct box_next_in_section +{ + template <typename Box, typename Point> + static inline void apply(Box & box, Point const& prev, Point const& curr) + { + geometry::model::referring_segment<Point const> seg(prev, curr); + geometry::expand(box, seg); + } +}; + +template <> +struct box_next_in_section<cartesian_tag> +{ + template <typename Box, typename Point> + static inline void apply(Box & box, Point const& , Point const& curr) + { + geometry::expand(box, curr); + } +}; + /// @brief Helper class to create sections of a part of a range, on the fly template < @@ -402,10 +446,19 @@ struct sectionalize_part int, 0, dimension_count >::apply(direction_classes, section.directions); - geometry::expand(section.bounding_box, previous_robust_point); + // In cartesian this is envelope of previous point expanded with current point + // in non-cartesian this is envelope of a segment + box_first_in_section<typename cs_tag<robust_point_type>::type> + ::apply(section.bounding_box, previous_robust_point, current_robust_point); + } + else + { + // In cartesian this is expand with current point + // in non-cartesian this is expand with a segment + box_next_in_section<typename cs_tag<robust_point_type>::type> + ::apply(section.bounding_box, previous_robust_point, current_robust_point); } - geometry::expand(section.bounding_box, current_robust_point); section.end_index = index + 1; section.count++; if (! duplicate) @@ -769,7 +822,7 @@ inline void sectionalize(Geometry const& geometry, int source_index = 0, std::size_t max_count = 10) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); typedef typename boost::range_value<Sections>::type section_type; diff --git a/boost/geometry/algorithms/detail/within/point_in_geometry.hpp b/boost/geometry/algorithms/detail/within/point_in_geometry.hpp index 68e74a8c5c..a73364c333 100644 --- a/boost/geometry/algorithms/detail/within/point_in_geometry.hpp +++ b/boost/geometry/algorithms/detail/within/point_in_geometry.hpp @@ -400,7 +400,7 @@ namespace detail { namespace within { template <typename Point, typename Geometry, typename Strategy> inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy) { - concept::within::check + concepts::within::check < typename tag<Point>::type, typename tag<Geometry>::type, |