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 | |
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')
144 files changed, 4172 insertions, 2188 deletions
diff --git a/boost/geometry/algorithms/append.hpp b/boost/geometry/algorithms/append.hpp index 894f52c68b..5cfad0c520 100644 --- a/boost/geometry/algorithms/append.hpp +++ b/boost/geometry/algorithms/append.hpp @@ -284,7 +284,7 @@ struct append int ring_index, int multi_index) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::append<Geometry, RangeOrPoint>::apply(geometry, range_or_point, ring_index, diff --git a/boost/geometry/algorithms/area.hpp b/boost/geometry/algorithms/area.hpp index cb1501d8c9..4751d4e742 100644 --- a/boost/geometry/algorithms/area.hpp +++ b/boost/geometry/algorithms/area.hpp @@ -82,7 +82,7 @@ struct ring_area static inline typename Strategy::return_type apply(Ring const& ring, Strategy const& strategy) { - BOOST_CONCEPT_ASSERT( (geometry::concept::AreaStrategy<Strategy>) ); + BOOST_CONCEPT_ASSERT( (geometry::concepts::AreaStrategy<Strategy>) ); assert_dimension<Ring, 2>(); // Ignore warning (because using static method sometimes) on strategy @@ -266,7 +266,7 @@ and Geographic as well. template <typename Geometry> inline typename default_area_result<Geometry>::type area(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); // TODO put this into a resolve_strategy stage // (and take the return type from resolve_variant) @@ -310,7 +310,7 @@ template <typename Geometry, typename Strategy> inline typename Strategy::return_type area( Geometry const& geometry, Strategy const& strategy) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); // detail::throw_on_empty_input(geometry); diff --git a/boost/geometry/algorithms/assign.hpp b/boost/geometry/algorithms/assign.hpp index e3d664de38..589a5c545b 100644 --- a/boost/geometry/algorithms/assign.hpp +++ b/boost/geometry/algorithms/assign.hpp @@ -69,7 +69,7 @@ namespace boost { namespace geometry template <typename Geometry, typename Range> inline void assign_points(Geometry& geometry, Range const& range) { - concept::check<Geometry>(); + concepts::check<Geometry>(); clear(geometry); geometry::append(geometry, range, -1, 0); @@ -96,7 +96,7 @@ collect the minimum bounding box of a geometry. template <typename Geometry> inline void assign_inverse(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::assign_inverse < @@ -116,7 +116,7 @@ inline void assign_inverse(Geometry& geometry) template <typename Geometry> inline void assign_zero(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::assign_zero < @@ -146,7 +146,7 @@ inline void assign_zero(Geometry& geometry) template <typename Geometry, typename Type> inline void assign_values(Geometry& geometry, Type const& c1, Type const& c2) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::assign < @@ -179,7 +179,7 @@ template <typename Geometry, typename Type> inline void assign_values(Geometry& geometry, Type const& c1, Type const& c2, Type const& c3) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::assign < @@ -206,7 +206,7 @@ template <typename Geometry, typename Type> inline void assign_values(Geometry& geometry, Type const& c1, Type const& c2, Type const& c3, Type const& c4) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::assign < @@ -227,9 +227,9 @@ struct assign static inline void apply(Geometry1& geometry1, const Geometry2& geometry2) { - concept::check<Geometry1>(); - concept::check<Geometry2 const>(); - concept::check_concepts_and_equal_dimensions<Geometry1, Geometry2 const>(); + concepts::check<Geometry1>(); + concepts::check<Geometry2 const>(); + concepts::check_concepts_and_equal_dimensions<Geometry1, Geometry2 const>(); static bool const same_point_order = point_order<Geometry1>::value == point_order<Geometry2>::value; diff --git a/boost/geometry/algorithms/buffer.hpp b/boost/geometry/algorithms/buffer.hpp index 5dfe9d8846..e1d3c20e44 100644 --- a/boost/geometry/algorithms/buffer.hpp +++ b/boost/geometry/algorithms/buffer.hpp @@ -182,8 +182,8 @@ template <typename Input, typename Output, typename Distance> inline void buffer(Input const& geometry_in, Output& geometry_out, Distance const& distance, Distance const& chord_length = -1) { - concept::check<Input const>(); - concept::check<Output>(); + concepts::check<Input const>(); + concepts::check<Output>(); resolve_variant::buffer<Input>::apply(geometry_in, distance, chord_length, geometry_out); } @@ -204,8 +204,8 @@ inline void buffer(Input const& geometry_in, Output& geometry_out, template <typename Output, typename Input, typename Distance> Output return_buffer(Input const& geometry, Distance const& distance, Distance const& chord_length = -1) { - concept::check<Input const>(); - concept::check<Output>(); + concepts::check<Input const>(); + concepts::check<Output>(); Output geometry_out; @@ -256,8 +256,8 @@ inline void buffer(GeometryIn const& geometry_in, PointStrategy const& point_strategy) { typedef typename boost::range_value<MultiPolygon>::type polygon_type; - concept::check<GeometryIn const>(); - concept::check<polygon_type>(); + concepts::check<GeometryIn const>(); + concepts::check<polygon_type>(); typedef typename point_type<GeometryIn>::type point_type; typedef typename rescale_policy_type<point_type>::type rescale_policy_type; diff --git a/boost/geometry/algorithms/centroid.hpp b/boost/geometry/algorithms/centroid.hpp index 8ef017a3f1..fc2908ab1c 100644 --- a/boost/geometry/algorithms/centroid.hpp +++ b/boost/geometry/algorithms/centroid.hpp @@ -545,7 +545,7 @@ struct centroid template <typename Point, typename Strategy> static inline void apply(Geometry const& geometry, Point& out, Strategy const& strategy) { - concept::check_concepts_and_equal_dimensions<Point, Geometry const>(); + concepts::check_concepts_and_equal_dimensions<Point, Geometry const>(); resolve_strategy::centroid<Geometry>::apply(geometry, out, strategy); } }; diff --git a/boost/geometry/algorithms/clear.hpp b/boost/geometry/algorithms/clear.hpp index 54b2162767..97f5efa451 100644 --- a/boost/geometry/algorithms/clear.hpp +++ b/boost/geometry/algorithms/clear.hpp @@ -185,7 +185,7 @@ struct clear<variant<BOOST_VARIANT_ENUM_PARAMS(T)> > template <typename Geometry> inline void clear(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); resolve_variant::clear<Geometry>::apply(geometry); } diff --git a/boost/geometry/algorithms/convert.hpp b/boost/geometry/algorithms/convert.hpp index 78618aed2d..6a8ba1acb6 100644 --- a/boost/geometry/algorithms/convert.hpp +++ b/boost/geometry/algorithms/convert.hpp @@ -494,7 +494,7 @@ struct convert { static inline void apply(Geometry1 const& geometry1, Geometry2& geometry2) { - concept::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2>(); + concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2>(); dispatch::convert<Geometry1, Geometry2>::apply(geometry1, geometry2); } }; diff --git a/boost/geometry/algorithms/convex_hull.hpp b/boost/geometry/algorithms/convex_hull.hpp index 19d28bc7b5..26bb8509e3 100644 --- a/boost/geometry/algorithms/convex_hull.hpp +++ b/boost/geometry/algorithms/convex_hull.hpp @@ -154,7 +154,7 @@ struct convex_hull OutputGeometry& out, Strategy const& strategy) { - BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); + BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) ); dispatch::convex_hull<Geometry>::apply(geometry, out, strategy); } @@ -179,7 +179,7 @@ struct convex_hull_insert OutputIterator& out, Strategy const& strategy) { - BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); + BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) ); return dispatch::convex_hull_insert< geometry::point_order<Geometry>::value, @@ -212,7 +212,7 @@ struct convex_hull template <typename OutputGeometry, typename Strategy> static inline void apply(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy) { - concept::check_concepts_and_equal_dimensions< + concepts::check_concepts_and_equal_dimensions< const Geometry, OutputGeometry >(); @@ -258,8 +258,8 @@ struct convex_hull_insert static inline OutputIterator apply(Geometry const& geometry, OutputIterator& out, Strategy const& strategy) { // Concept: output point type = point type of input geometry - concept::check<Geometry const>(); - concept::check<typename point_type<Geometry>::type>(); + concepts::check<Geometry const>(); + concepts::check<typename point_type<Geometry>::type>(); return resolve_strategy::convex_hull_insert::apply(geometry, out, strategy); } diff --git a/boost/geometry/algorithms/correct.hpp b/boost/geometry/algorithms/correct.hpp index 11ed6ecff9..5d3b6939af 100644 --- a/boost/geometry/algorithms/correct.hpp +++ b/boost/geometry/algorithms/correct.hpp @@ -283,7 +283,7 @@ struct correct { static inline void apply(Geometry& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); dispatch::correct<Geometry>::apply(geometry); } }; diff --git a/boost/geometry/algorithms/covered_by.hpp b/boost/geometry/algorithms/covered_by.hpp index eb8e732409..2001d5810c 100644 --- a/boost/geometry/algorithms/covered_by.hpp +++ b/boost/geometry/algorithms/covered_by.hpp @@ -260,15 +260,15 @@ struct covered_by Geometry2 const& geometry2, Strategy const& strategy) { - concept::within::check + concepts::within::check < typename tag<Geometry1>::type, typename tag<Geometry2>::type, typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type, Strategy >(); - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); assert_dimension_equal<Geometry1, Geometry2>(); return dispatch::covered_by<Geometry1, Geometry2>::apply(geometry1, diff --git a/boost/geometry/algorithms/crosses.hpp b/boost/geometry/algorithms/crosses.hpp index 9546a5335b..73d86ef529 100644 --- a/boost/geometry/algorithms/crosses.hpp +++ b/boost/geometry/algorithms/crosses.hpp @@ -72,8 +72,8 @@ namespace resolve_variant const Geometry1& geometry1, const Geometry2& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return dispatch::crosses<Geometry1, Geometry2>::apply(geometry1, geometry2); } 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, diff --git a/boost/geometry/algorithms/difference.hpp b/boost/geometry/algorithms/difference.hpp index dc31c7db4d..f7ca48cbe6 100644 --- a/boost/geometry/algorithms/difference.hpp +++ b/boost/geometry/algorithms/difference.hpp @@ -54,9 +54,9 @@ inline OutputIterator difference_insert(Geometry1 const& geometry1, OutputIterator out, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - concept::check<GeometryOut>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); + concepts::check<GeometryOut>(); return geometry::dispatch::intersection_insert < @@ -97,11 +97,11 @@ inline OutputIterator difference_insert(Geometry1 const& geometry1, RobustPolicy const& robust_policy, OutputIterator out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - concept::check<GeometryOut>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); + concepts::check<GeometryOut>(); - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<GeometryOut>::type, Geometry1, @@ -142,11 +142,11 @@ template inline void difference(Geometry1 const& geometry1, Geometry2 const& geometry2, Collection& output_collection) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename boost::range_value<Collection>::type geometry_out; - concept::check<geometry_out>(); + concepts::check<geometry_out>(); typedef typename geometry::rescale_overlay_policy_type < diff --git a/boost/geometry/algorithms/equals.hpp b/boost/geometry/algorithms/equals.hpp index 0f0bdde584..d04d5c7f3a 100644 --- a/boost/geometry/algorithms/equals.hpp +++ b/boost/geometry/algorithms/equals.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2014, 2015. -// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015, 2016. +// Modifications copyright (c) 2014-2016 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -161,8 +161,13 @@ struct equals_by_collection double >::type calculation_type; - typedef std::vector<collected_vector<calculation_type> > v; - v c1, c2; + typedef geometry::collected_vector + < + calculation_type, + Geometry1 + > collected_vector; + + std::vector<collected_vector> c1, c2; geometry::collect_vectors(c1, geometry1); geometry::collect_vectors(c2, geometry2); @@ -323,6 +328,17 @@ struct equals : detail::equals::equals_by_collection<detail::equals::area_check> {}; +template <typename MultiPolygon, typename Ring, bool Reverse> +struct equals + < + MultiPolygon, Ring, + multi_polygon_tag, ring_tag, + 2, + Reverse + > + : detail::equals::equals_by_collection<detail::equals::area_check> +{}; + } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH @@ -336,7 +352,7 @@ struct equals 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/for_each.hpp b/boost/geometry/algorithms/for_each.hpp index c5c099b1ad..741dc359fe 100644 --- a/boost/geometry/algorithms/for_each.hpp +++ b/boost/geometry/algorithms/for_each.hpp @@ -337,7 +337,7 @@ struct for_each_segment<MultiGeometry, multi_tag> template<typename Geometry, typename Functor> inline Functor for_each_point(Geometry& geometry, Functor f) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::for_each_point<Geometry>::apply(geometry, f); return f; @@ -360,7 +360,7 @@ inline Functor for_each_point(Geometry& geometry, Functor f) template<typename Geometry, typename Functor> inline Functor for_each_segment(Geometry& geometry, Functor f) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::for_each_segment<Geometry>::apply(geometry, f); return f; diff --git a/boost/geometry/algorithms/intersects.hpp b/boost/geometry/algorithms/intersects.hpp index 1bb85aa3bb..5349db76bb 100644 --- a/boost/geometry/algorithms/intersects.hpp +++ b/boost/geometry/algorithms/intersects.hpp @@ -49,7 +49,7 @@ namespace boost { namespace geometry template <typename Geometry> inline bool intersects(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); typedef typename geometry::point_type<Geometry>::type point_type; typedef detail::no_rescale_policy rescale_policy_type; @@ -93,8 +93,8 @@ inline bool intersects(Geometry const& geometry) template <typename Geometry1, typename Geometry2> inline bool intersects(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return ! geometry::disjoint(geometry1, geometry2); } diff --git a/boost/geometry/algorithms/is_empty.hpp b/boost/geometry/algorithms/is_empty.hpp index 02c295eaba..8dab69c879 100644 --- a/boost/geometry/algorithms/is_empty.hpp +++ b/boost/geometry/algorithms/is_empty.hpp @@ -157,7 +157,7 @@ struct is_empty { static inline bool apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::is_empty<Geometry>::apply(geometry); } diff --git a/boost/geometry/algorithms/length.hpp b/boost/geometry/algorithms/length.hpp index cf5234da1a..39a567a26b 100644 --- a/boost/geometry/algorithms/length.hpp +++ b/boost/geometry/algorithms/length.hpp @@ -251,7 +251,7 @@ template<typename Geometry> inline typename default_length_result<Geometry>::type length(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); // detail::throw_on_empty_input(geometry); @@ -283,7 +283,7 @@ template<typename Geometry, typename Strategy> inline typename default_length_result<Geometry>::type length(Geometry const& geometry, Strategy const& strategy) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); // detail::throw_on_empty_input(geometry); diff --git a/boost/geometry/algorithms/make.hpp b/boost/geometry/algorithms/make.hpp index d0e3092492..899d5489b7 100644 --- a/boost/geometry/algorithms/make.hpp +++ b/boost/geometry/algorithms/make.hpp @@ -45,7 +45,7 @@ namespace detail { namespace make template <typename Geometry, typename Range> inline Geometry make_points(Range const& range) { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; geometry::append(geometry, range); @@ -78,7 +78,7 @@ inline Geometry make_points(Range const& range) template <typename Geometry, typename Type> inline Geometry make(Type const& c1, Type const& c2) { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; dispatch::assign @@ -112,7 +112,7 @@ inline Geometry make(Type const& c1, Type const& c2) template <typename Geometry, typename Type> inline Geometry make(Type const& c1, Type const& c2, Type const& c3) { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; dispatch::assign @@ -127,7 +127,7 @@ inline Geometry make(Type const& c1, Type const& c2, Type const& c3) template <typename Geometry, typename Type> inline Geometry make(Type const& c1, Type const& c2, Type const& c3, Type const& c4) { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; dispatch::assign @@ -163,7 +163,7 @@ inline Geometry make(Type const& c1, Type const& c2, Type const& c3, Type const& template <typename Geometry> inline Geometry make_inverse() { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; dispatch::assign_inverse @@ -184,7 +184,7 @@ inline Geometry make_inverse() template <typename Geometry> inline Geometry make_zero() { - concept::check<Geometry>(); + concepts::check<Geometry>(); Geometry geometry; dispatch::assign_zero diff --git a/boost/geometry/algorithms/num_geometries.hpp b/boost/geometry/algorithms/num_geometries.hpp index 8144c22ab0..e122241fea 100644 --- a/boost/geometry/algorithms/num_geometries.hpp +++ b/boost/geometry/algorithms/num_geometries.hpp @@ -90,7 +90,7 @@ struct num_geometries { static inline std::size_t apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::num_geometries<Geometry>::apply(geometry); } diff --git a/boost/geometry/algorithms/num_interior_rings.hpp b/boost/geometry/algorithms/num_interior_rings.hpp index 04b4eb2a7c..b7531a3dd0 100644 --- a/boost/geometry/algorithms/num_interior_rings.hpp +++ b/boost/geometry/algorithms/num_interior_rings.hpp @@ -88,7 +88,7 @@ struct num_interior_rings { static inline std::size_t apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::num_interior_rings<Geometry>::apply(geometry); } diff --git a/boost/geometry/algorithms/num_points.hpp b/boost/geometry/algorithms/num_points.hpp index 214fe9c8b0..9ef77f271d 100644 --- a/boost/geometry/algorithms/num_points.hpp +++ b/boost/geometry/algorithms/num_points.hpp @@ -149,7 +149,7 @@ struct num_points static inline std::size_t apply(Geometry const& geometry, bool add_for_open) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return add_for_open ? dispatch::num_points<Geometry, true>::apply(geometry) diff --git a/boost/geometry/algorithms/num_segments.hpp b/boost/geometry/algorithms/num_segments.hpp index 08af226caf..86eb63fad5 100644 --- a/boost/geometry/algorithms/num_segments.hpp +++ b/boost/geometry/algorithms/num_segments.hpp @@ -150,7 +150,7 @@ struct num_segments { static inline std::size_t apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return dispatch::num_segments<Geometry>::apply(geometry); } diff --git a/boost/geometry/algorithms/overlaps.hpp b/boost/geometry/algorithms/overlaps.hpp index 9b5abdb2a0..32738c294c 100644 --- a/boost/geometry/algorithms/overlaps.hpp +++ b/boost/geometry/algorithms/overlaps.hpp @@ -184,8 +184,8 @@ struct overlaps<Box1, Box2, box_tag, box_tag> template <typename Geometry1, typename Geometry2> inline bool overlaps(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return dispatch::overlaps < diff --git a/boost/geometry/algorithms/perimeter.hpp b/boost/geometry/algorithms/perimeter.hpp index 1b5ccacf9c..47b0649727 100644 --- a/boost/geometry/algorithms/perimeter.hpp +++ b/boost/geometry/algorithms/perimeter.hpp @@ -142,7 +142,7 @@ struct perimeter static inline typename default_length_result<Geometry>::type apply(Geometry const& geometry, Strategy const& strategy) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return resolve_strategy::perimeter::apply(geometry, strategy); } }; diff --git a/boost/geometry/algorithms/point_on_surface.hpp b/boost/geometry/algorithms/point_on_surface.hpp index 3fa83bfe6f..e9041f937b 100644 --- a/boost/geometry/algorithms/point_on_surface.hpp +++ b/boost/geometry/algorithms/point_on_surface.hpp @@ -295,8 +295,8 @@ inline bool calculate_point_on_surface(Geometry const& geometry, Point& point) template <typename Geometry, typename Point> inline void point_on_surface(Geometry const& geometry, Point & point) { - concept::check<Point>(); - concept::check<Geometry const>(); + concepts::check<Point>(); + concepts::check<Geometry const>(); // First try in Y-direction (which should always succeed for valid polygons) if (! detail::point_on_surface::calculate_point_on_surface<1>(geometry, point)) diff --git a/boost/geometry/algorithms/remove_spikes.hpp b/boost/geometry/algorithms/remove_spikes.hpp index 080db92f6d..caa7fed9be 100644 --- a/boost/geometry/algorithms/remove_spikes.hpp +++ b/boost/geometry/algorithms/remove_spikes.hpp @@ -241,7 +241,7 @@ struct remove_spikes { static void apply(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::remove_spikes<Geometry>::apply(geometry); } }; diff --git a/boost/geometry/algorithms/reverse.hpp b/boost/geometry/algorithms/reverse.hpp index 578771bfe3..dc7d2de42c 100644 --- a/boost/geometry/algorithms/reverse.hpp +++ b/boost/geometry/algorithms/reverse.hpp @@ -137,7 +137,7 @@ struct reverse { static void apply(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); dispatch::reverse<Geometry>::apply(geometry); } }; diff --git a/boost/geometry/algorithms/simplify.hpp b/boost/geometry/algorithms/simplify.hpp index 0b28eb7d15..cfeb542220 100644 --- a/boost/geometry/algorithms/simplify.hpp +++ b/boost/geometry/algorithms/simplify.hpp @@ -333,7 +333,7 @@ struct simplify > strategy_type; BOOST_CONCEPT_ASSERT( - (concept::SimplifyStrategy<strategy_type, point_type>) + (concepts::SimplifyStrategy<strategy_type, point_type>) ); apply(geometry, out, max_distance, strategy_type()); @@ -376,7 +376,7 @@ struct simplify_insert > strategy_type; BOOST_CONCEPT_ASSERT( - (concept::SimplifyStrategy<strategy_type, point_type>) + (concepts::SimplifyStrategy<strategy_type, point_type>) ); apply(geometry, out, max_distance, strategy_type()); @@ -461,7 +461,7 @@ template<typename Geometry, typename Distance, typename Strategy> inline void simplify(Geometry const& geometry, Geometry& out, Distance const& max_distance, Strategy const& strategy) { - concept::check<Geometry>(); + concepts::check<Geometry>(); geometry::clear(out); @@ -489,7 +489,7 @@ template<typename Geometry, typename Distance> inline void simplify(Geometry const& geometry, Geometry& out, Distance const& max_distance) { - concept::check<Geometry>(); + concepts::check<Geometry>(); geometry::simplify(geometry, out, max_distance, default_strategy()); } @@ -519,7 +519,7 @@ template<typename Geometry, typename OutputIterator, typename Distance, typename inline void simplify_insert(Geometry const& geometry, OutputIterator out, Distance const& max_distance, Strategy const& strategy) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); resolve_strategy::simplify_insert::apply(geometry, out, max_distance, strategy); } @@ -540,8 +540,8 @@ inline void simplify_insert(Geometry const& geometry, OutputIterator out, Distance const& max_distance) { // Concept: output point type = point type of input geometry - concept::check<Geometry const>(); - concept::check<typename point_type<Geometry>::type>(); + concepts::check<Geometry const>(); + concepts::check<typename point_type<Geometry>::type>(); simplify_insert(geometry, out, max_distance, default_strategy()); } diff --git a/boost/geometry/algorithms/sym_difference.hpp b/boost/geometry/algorithms/sym_difference.hpp index 77a20c0885..33f94c9321 100644 --- a/boost/geometry/algorithms/sym_difference.hpp +++ b/boost/geometry/algorithms/sym_difference.hpp @@ -235,9 +235,9 @@ inline OutputIterator sym_difference_insert(Geometry1 const& geometry1, OutputIterator out, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - concept::check<GeometryOut>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); + concepts::check<GeometryOut>(); return dispatch::sym_difference_insert < @@ -272,11 +272,11 @@ inline OutputIterator sym_difference_insert(Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, OutputIterator out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - concept::check<GeometryOut>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); + concepts::check<GeometryOut>(); - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<GeometryOut>::type, Geometry1, @@ -315,11 +315,11 @@ template inline void sym_difference(Geometry1 const& geometry1, Geometry2 const& geometry2, Collection& output_collection) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename boost::range_value<Collection>::type geometry_out; - concept::check<geometry_out>(); + concepts::check<geometry_out>(); typedef typename geometry::rescale_overlay_policy_type < diff --git a/boost/geometry/algorithms/touches.hpp b/boost/geometry/algorithms/touches.hpp index 570c54797f..6384cc2a88 100644 --- a/boost/geometry/algorithms/touches.hpp +++ b/boost/geometry/algorithms/touches.hpp @@ -373,7 +373,7 @@ struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false> // A/L template <typename Linear, typename Areal, typename Tag1, typename Tag2> -struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, true> +struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false> : detail::relate::relate_impl < detail::de9im::static_mask_touches_type, @@ -410,8 +410,8 @@ struct touches { static bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); return dispatch::touches<Geometry1, Geometry2> ::apply(geometry1, geometry2); @@ -494,7 +494,7 @@ struct self_touches { static bool apply(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); typedef detail::no_rescale_policy rescale_policy_type; typedef typename geometry::point_type<Geometry>::type point_type; diff --git a/boost/geometry/algorithms/transform.hpp b/boost/geometry/algorithms/transform.hpp index f6748b11e3..b514c1dacf 100644 --- a/boost/geometry/algorithms/transform.hpp +++ b/boost/geometry/algorithms/transform.hpp @@ -349,8 +349,8 @@ struct transform Geometry2& geometry2, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2>(); return dispatch::transform<Geometry1, Geometry2>::apply( geometry1, diff --git a/boost/geometry/algorithms/union.hpp b/boost/geometry/algorithms/union.hpp index d15ee7655f..f0e55ec981 100644 --- a/boost/geometry/algorithms/union.hpp +++ b/boost/geometry/algorithms/union.hpp @@ -204,9 +204,9 @@ inline OutputIterator union_insert(Geometry1 const& geometry1, Geometry2 const& geometry2, OutputIterator out) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - concept::check<GeometryOut>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); + concepts::check<GeometryOut>(); typedef typename geometry::rescale_overlay_policy_type < @@ -214,7 +214,7 @@ inline OutputIterator union_insert(Geometry1 const& geometry1, Geometry2 >::type rescale_policy_type; - typedef strategy_intersection + typedef intersection_strategies < typename cs_tag<GeometryOut>::type, Geometry1, @@ -264,11 +264,11 @@ inline void union_(Geometry1 const& geometry1, Geometry2 const& geometry2, Collection& output_collection) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); typedef typename boost::range_value<Collection>::type geometry_out; - concept::check<geometry_out>(); + concepts::check<geometry_out>(); detail::union_::union_insert<geometry_out>(geometry1, geometry2, range::back_inserter(output_collection)); diff --git a/boost/geometry/algorithms/unique.hpp b/boost/geometry/algorithms/unique.hpp index fed9f8af4b..f57f4505ba 100644 --- a/boost/geometry/algorithms/unique.hpp +++ b/boost/geometry/algorithms/unique.hpp @@ -166,7 +166,7 @@ struct unique<MultiPolygon, multi_polygon_tag> template <typename Geometry> inline void unique(Geometry& geometry) { - concept::check<Geometry>(); + concepts::check<Geometry>(); // Default strategy is the default point-comparison policy typedef geometry::equal_to diff --git a/boost/geometry/algorithms/within.hpp b/boost/geometry/algorithms/within.hpp index 35f9396ba6..a1e6a58f8d 100644 --- a/boost/geometry/algorithms/within.hpp +++ b/boost/geometry/algorithms/within.hpp @@ -284,7 +284,7 @@ struct within Geometry2 const& geometry2, Strategy const& strategy) { - concept::within::check + concepts::within::check < typename tag<Geometry1>::type, typename tag<Geometry2>::type, @@ -339,8 +339,8 @@ struct within Geometry2 const& geometry2, Strategy const& strategy) { - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); + concepts::check<Geometry1 const>(); + concepts::check<Geometry2 const>(); assert_dimension_equal<Geometry1, Geometry2>(); return resolve_strategy::within::apply(geometry1, diff --git a/boost/geometry/arithmetic/arithmetic.hpp b/boost/geometry/arithmetic/arithmetic.hpp index fbc3ca443e..3ab66b27f5 100644 --- a/boost/geometry/arithmetic/arithmetic.hpp +++ b/boost/geometry/arithmetic/arithmetic.hpp @@ -139,7 +139,7 @@ struct point_assignment template <typename Point> inline void add_value(Point& p, typename detail::param<Point>::type value) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); for_each_coordinate(p, detail::value_operation @@ -162,8 +162,8 @@ inline void add_value(Point& p, typename detail::param<Point>::type value) template <typename Point1, typename Point2> inline void add_point(Point1& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); for_each_coordinate(p1, detail::point_operation<Point2, std::plus>(p2)); } @@ -179,7 +179,7 @@ inline void add_point(Point1& p1, Point2 const& p2) template <typename Point> inline void subtract_value(Point& p, typename detail::param<Point>::type value) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); for_each_coordinate(p, detail::value_operation @@ -202,8 +202,8 @@ inline void subtract_value(Point& p, typename detail::param<Point>::type value) template <typename Point1, typename Point2> inline void subtract_point(Point1& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); for_each_coordinate(p1, detail::point_operation<Point2, std::minus>(p2)); } @@ -219,7 +219,7 @@ inline void subtract_point(Point1& p1, Point2 const& p2) template <typename Point> inline void multiply_value(Point& p, typename detail::param<Point>::type value) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); for_each_coordinate(p, detail::value_operation @@ -243,8 +243,8 @@ inline void multiply_value(Point& p, typename detail::param<Point>::type value) template <typename Point1, typename Point2> inline void multiply_point(Point1& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); for_each_coordinate(p1, detail::point_operation<Point2, std::multiplies>(p2)); } @@ -260,7 +260,7 @@ inline void multiply_point(Point1& p1, Point2 const& p2) template <typename Point> inline void divide_value(Point& p, typename detail::param<Point>::type value) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); for_each_coordinate(p, detail::value_operation @@ -283,8 +283,8 @@ inline void divide_value(Point& p, typename detail::param<Point>::type value) template <typename Point1, typename Point2> inline void divide_point(Point1& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); for_each_coordinate(p1, detail::point_operation<Point2, std::divides>(p2)); } @@ -300,7 +300,7 @@ inline void divide_point(Point1& p1, Point2 const& p2) template <typename Point> inline void assign_value(Point& p, typename detail::param<Point>::type value) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); for_each_coordinate(p, detail::value_assignment @@ -322,8 +322,8 @@ inline void assign_value(Point& p, typename detail::param<Point>::type value) template <typename Point1, typename Point2> inline void assign_point(Point1& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); for_each_coordinate(p1, detail::point_assignment<Point2>(p2)); } diff --git a/boost/geometry/arithmetic/cross_product.hpp b/boost/geometry/arithmetic/cross_product.hpp new file mode 100644 index 0000000000..485c2123b6 --- /dev/null +++ b/boost/geometry/arithmetic/cross_product.hpp @@ -0,0 +1,128 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// Copyright (c) 2008-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2012 Bruno Lalande, Paris, France. + +// This file was modified by Oracle on 2016. +// Modifications copyright (c) 2016, Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ARITHMETIC_CROSS_PRODUCT_HPP +#define BOOST_GEOMETRY_ARITHMETIC_CROSS_PRODUCT_HPP + + +#include <cstddef> + +#include <boost/mpl/assert.hpp> +#include <boost/mpl/size_t.hpp> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> + +#include <boost/geometry/geometries/concepts/point_concept.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail +{ + +template <std::size_t Dimension> +struct cross_product +{ + // We define cross product only for 2d (see Wolfram) and 3d. + // In Math, it is also well-defined for 7-dimension. + // Generalisation of cross product to n-dimension is defined as + // wedge product but it is not direct analogue to binary cross product. + BOOST_MPL_ASSERT_MSG((false), + NOT_IMPLEMENTED_FOR_THIS_DIMENSION, + (mpl::size_t<Dimension>)); +}; + +template <> +struct cross_product<2> +{ + template <typename P1, typename P2, typename ResultP> + static inline void apply(P1 const& p1, P2 const& p2, ResultP& result) + { + assert_dimension<P1, 2>(); + assert_dimension<P2, 2>(); + assert_dimension<ResultP, 2>(); + + // For 2-dimensions, analog of the cross product U(x,y) and V(x,y) is + // Ux * Vy - Uy * Vx + // which is returned as 0-component (or X) of 2d vector, 1-component is undefined. + set<0>(result, get<0>(p1) * get<1>(p2) - get<1>(p1) * get<0>(p2)); + } +}; + +template <> +struct cross_product<3> +{ + template <typename P1, typename P2, typename ResultP> + static inline void apply(P1 const& p1, P2 const& p2, ResultP& result) + { + assert_dimension<P1, 3>(); + assert_dimension<P2, 3>(); + assert_dimension<ResultP, 3>(); + + set<0>(result, get<1>(p1) * get<2>(p2) - get<2>(p1) * get<1>(p2)); + set<1>(result, get<2>(p1) * get<0>(p2) - get<0>(p1) * get<2>(p2)); + set<2>(result, get<0>(p1) * get<1>(p2) - get<1>(p1) * get<0>(p2)); + } +}; + +} // namespace detail +#endif // DOXYGEN_NO_DETAIL + + +/*! +\brief Computes the cross product of two vectors. +\details All vectors should have the same dimension, 3 or 2. +\ingroup arithmetic +\param p1 first vector +\param p2 second vector +\return the cross product vector + */ +template <typename ResultP, typename P1, typename P2> +inline ResultP cross_product(P1 const& p1, P2 const& p2) +{ + BOOST_CONCEPT_ASSERT( (concepts::Point<ResultP>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<P1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<P2>) ); + + ResultP result; + detail::cross_product<dimension<ResultP>::value>::apply(p1, p2, result); + return result; +} + +/*! +\brief Computes the cross product of two vectors. +\details All vectors should have the same dimension, 3 or 2. +\ingroup arithmetic +\param p1 first vector +\param p2 second vector +\return the cross product vector +*/ +template <typename P> +inline P cross_product(P const& p1, P const& p2) +{ + BOOST_CONCEPT_ASSERT((concepts::Point<P>)); + BOOST_CONCEPT_ASSERT((concepts::ConstPoint<P>)); + + P result; + detail::cross_product<dimension<P>::value>::apply(p1, p2, result); + return result; +} + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ARITHMETIC_CROSS_PRODUCT_HPP diff --git a/boost/geometry/arithmetic/determinant.hpp b/boost/geometry/arithmetic/determinant.hpp index a8e46ca9a0..59c596b124 100644 --- a/boost/geometry/arithmetic/determinant.hpp +++ b/boost/geometry/arithmetic/determinant.hpp @@ -59,8 +59,8 @@ inline ReturnType determinant(U const& ux, U const& uy template <typename ReturnType, typename U, typename V> inline ReturnType determinant(U const& u, V const& v) { - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<U>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<V>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<U>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<V>) ); return calculate_determinant < diff --git a/boost/geometry/arithmetic/dot_product.hpp b/boost/geometry/arithmetic/dot_product.hpp index fc2b3844e6..747bd01ab0 100644 --- a/boost/geometry/arithmetic/dot_product.hpp +++ b/boost/geometry/arithmetic/dot_product.hpp @@ -69,8 +69,8 @@ template <typename Point1, typename Point2> inline typename select_coordinate_type<Point1, Point2>::type dot_product( Point1 const& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); return detail::dot_product_maker < diff --git a/boost/geometry/formulas/spherical.hpp b/boost/geometry/formulas/spherical.hpp new file mode 100644 index 0000000000..2195bbbe10 --- /dev/null +++ b/boost/geometry/formulas/spherical.hpp @@ -0,0 +1,96 @@ +// Boost.Geometry + +// Copyright (c) 2016, Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_FORMULAS_SPHERICAL_HPP +#define BOOST_GEOMETRY_FORMULAS_SPHERICAL_HPP + +#include <boost/geometry/core/coordinate_system.hpp> +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/radian_access.hpp> + +//#include <boost/geometry/arithmetic/arithmetic.hpp> +#include <boost/geometry/arithmetic/cross_product.hpp> +#include <boost/geometry/arithmetic/dot_product.hpp> + +#include <boost/geometry/util/math.hpp> +#include <boost/geometry/util/normalize_spheroidal_coordinates.hpp> +#include <boost/geometry/util/select_coordinate_type.hpp> + +namespace boost { namespace geometry { + +namespace formula { + +template <typename Point3d, typename PointSph> +static inline Point3d sph_to_cart3d(PointSph const& point_sph) +{ + typedef typename coordinate_type<Point3d>::type calc_t; + + Point3d res; + + calc_t lon = get_as_radian<0>(point_sph); + calc_t lat = get_as_radian<1>(point_sph); + + calc_t const cos_lat = cos(lat); + set<0>(res, cos_lat * cos(lon)); + set<1>(res, cos_lat * sin(lon)); + set<2>(res, sin(lat)); + + return res; +} + +template <typename PointSph, typename Point3d> +static inline PointSph cart3d_to_sph(Point3d const& point_3d) +{ + typedef typename coordinate_type<PointSph>::type coord_t; + typedef typename coordinate_type<Point3d>::type calc_t; + + PointSph res; + + calc_t const x = get<0>(point_3d); + calc_t const y = get<1>(point_3d); + calc_t const z = get<2>(point_3d); + + set_from_radian<0>(res, atan2(y, x)); + set_from_radian<1>(res, asin(z)); + + coord_t lon = get<0>(res); + coord_t lat = get<1>(res); + + math::normalize_spheroidal_coordinates + < + typename coordinate_system<PointSph>::type::units, + coord_t + >(lon, lat); + + set<0>(res, lon); + set<1>(res, lat); + + return res; +} + +// -1 right +// 1 left +// 0 on +template <typename Point3d1, typename Point3d2> +static inline int sph_side_value(Point3d1 const& norm, Point3d2 const& pt) +{ + typedef typename select_coordinate_type<Point3d1, Point3d2>::type calc_t; + calc_t c0 = 0; + calc_t d = dot_product(norm, pt); + return math::equals(d, c0) ? 0 + : d > c0 ? 1 + : -1; // d < 0 +} + +} // namespace formula + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_FORMULAS_SPHERICAL_HPP diff --git a/boost/geometry/geometries/box.hpp b/boost/geometry/geometries/box.hpp index 97a4ba06da..23fd098f65 100644 --- a/boost/geometry/geometries/box.hpp +++ b/boost/geometry/geometries/box.hpp @@ -53,7 +53,7 @@ The box can also take a latlong point type as template parameter. template<typename Point> class box { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); public: diff --git a/boost/geometry/geometries/concepts/box_concept.hpp b/boost/geometry/geometries/concepts/box_concept.hpp index ea0d84cf31..816a90f63e 100644 --- a/boost/geometry/geometries/concepts/box_concept.hpp +++ b/boost/geometry/geometries/concepts/box_concept.hpp @@ -26,7 +26,7 @@ #include <boost/geometry/core/point_type.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -130,7 +130,7 @@ public : #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_BOX_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/check.hpp b/boost/geometry/geometries/concepts/check.hpp index 07ef84f4a4..f609d5f131 100644 --- a/boost/geometry/geometries/concepts/check.hpp +++ b/boost/geometry/geometries/concepts/check.hpp @@ -71,108 +71,108 @@ struct check : not_implemented<GeometryTag> template <typename Geometry> struct check<Geometry, point_tag, true> - : detail::concept_check::check<concept::ConstPoint<Geometry> > + : detail::concept_check::check<concepts::ConstPoint<Geometry> > {}; template <typename Geometry> struct check<Geometry, point_tag, false> - : detail::concept_check::check<concept::Point<Geometry> > + : detail::concept_check::check<concepts::Point<Geometry> > {}; template <typename Geometry> struct check<Geometry, linestring_tag, true> - : detail::concept_check::check<concept::ConstLinestring<Geometry> > + : detail::concept_check::check<concepts::ConstLinestring<Geometry> > {}; template <typename Geometry> struct check<Geometry, linestring_tag, false> - : detail::concept_check::check<concept::Linestring<Geometry> > + : detail::concept_check::check<concepts::Linestring<Geometry> > {}; template <typename Geometry> struct check<Geometry, ring_tag, true> - : detail::concept_check::check<concept::ConstRing<Geometry> > + : detail::concept_check::check<concepts::ConstRing<Geometry> > {}; template <typename Geometry> struct check<Geometry, ring_tag, false> - : detail::concept_check::check<concept::Ring<Geometry> > + : detail::concept_check::check<concepts::Ring<Geometry> > {}; template <typename Geometry> struct check<Geometry, polygon_tag, true> - : detail::concept_check::check<concept::ConstPolygon<Geometry> > + : detail::concept_check::check<concepts::ConstPolygon<Geometry> > {}; template <typename Geometry> struct check<Geometry, polygon_tag, false> - : detail::concept_check::check<concept::Polygon<Geometry> > + : detail::concept_check::check<concepts::Polygon<Geometry> > {}; template <typename Geometry> struct check<Geometry, box_tag, true> - : detail::concept_check::check<concept::ConstBox<Geometry> > + : detail::concept_check::check<concepts::ConstBox<Geometry> > {}; template <typename Geometry> struct check<Geometry, box_tag, false> - : detail::concept_check::check<concept::Box<Geometry> > + : detail::concept_check::check<concepts::Box<Geometry> > {}; template <typename Geometry> struct check<Geometry, segment_tag, true> - : detail::concept_check::check<concept::ConstSegment<Geometry> > + : detail::concept_check::check<concepts::ConstSegment<Geometry> > {}; template <typename Geometry> struct check<Geometry, segment_tag, false> - : detail::concept_check::check<concept::Segment<Geometry> > + : detail::concept_check::check<concepts::Segment<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_point_tag, true> - : detail::concept_check::check<concept::ConstMultiPoint<Geometry> > + : detail::concept_check::check<concepts::ConstMultiPoint<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_point_tag, false> - : detail::concept_check::check<concept::MultiPoint<Geometry> > + : detail::concept_check::check<concepts::MultiPoint<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_linestring_tag, true> - : detail::concept_check::check<concept::ConstMultiLinestring<Geometry> > + : detail::concept_check::check<concepts::ConstMultiLinestring<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_linestring_tag, false> - : detail::concept_check::check<concept::MultiLinestring<Geometry> > + : detail::concept_check::check<concepts::MultiLinestring<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_polygon_tag, true> - : detail::concept_check::check<concept::ConstMultiPolygon<Geometry> > + : detail::concept_check::check<concepts::ConstMultiPolygon<Geometry> > {}; template <typename Geometry> struct check<Geometry, multi_polygon_tag, false> - : detail::concept_check::check<concept::MultiPolygon<Geometry> > + : detail::concept_check::check<concepts::MultiPolygon<Geometry> > {}; @@ -182,7 +182,7 @@ struct check<Geometry, multi_polygon_tag, false> -namespace concept +namespace concepts { @@ -234,7 +234,7 @@ inline void check_concepts_and_equal_dimensions() } -} // namespace concept +} // namespace concepts }} // namespace boost::geometry diff --git a/boost/geometry/geometries/concepts/linestring_concept.hpp b/boost/geometry/geometries/concepts/linestring_concept.hpp index 091336fe30..6775239d05 100644 --- a/boost/geometry/geometries/concepts/linestring_concept.hpp +++ b/boost/geometry/geometries/concepts/linestring_concept.hpp @@ -28,7 +28,7 @@ -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -76,7 +76,7 @@ class Linestring #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename point_type<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::Point<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<point_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); public : @@ -105,7 +105,7 @@ class ConstLinestring #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename point_type<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point_type>) ); //BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); // Relaxed the concept. BOOST_CONCEPT_ASSERT( (boost::ForwardRangeConcept<Geometry>) ); @@ -119,7 +119,7 @@ public : #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_LINESTRING_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/multi_linestring_concept.hpp b/boost/geometry/geometries/concepts/multi_linestring_concept.hpp index f13f7ac7e8..7931670903 100644 --- a/boost/geometry/geometries/concepts/multi_linestring_concept.hpp +++ b/boost/geometry/geometries/concepts/multi_linestring_concept.hpp @@ -24,7 +24,7 @@ #include <boost/geometry/geometries/concepts/linestring_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -45,7 +45,7 @@ class MultiLinestring #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type linestring_type; - BOOST_CONCEPT_ASSERT( (concept::Linestring<linestring_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Linestring<linestring_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -73,7 +73,7 @@ class ConstMultiLinestring #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type linestring_type; - BOOST_CONCEPT_ASSERT( (concept::ConstLinestring<linestring_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstLinestring<linestring_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -85,7 +85,7 @@ public : #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_MULTI_LINESTRING_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/multi_point_concept.hpp b/boost/geometry/geometries/concepts/multi_point_concept.hpp index 81c087166f..9e205f1635 100644 --- a/boost/geometry/geometries/concepts/multi_point_concept.hpp +++ b/boost/geometry/geometries/concepts/multi_point_concept.hpp @@ -24,7 +24,7 @@ #include <boost/geometry/geometries/concepts/point_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -44,7 +44,7 @@ class MultiPoint #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::Point<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<point_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -72,7 +72,7 @@ class ConstMultiPoint #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -84,7 +84,7 @@ public : #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_MULTI_POINT_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/multi_polygon_concept.hpp b/boost/geometry/geometries/concepts/multi_polygon_concept.hpp index b13d330f3c..63de6e5bfc 100644 --- a/boost/geometry/geometries/concepts/multi_polygon_concept.hpp +++ b/boost/geometry/geometries/concepts/multi_polygon_concept.hpp @@ -23,7 +23,7 @@ #include <boost/geometry/geometries/concepts/polygon_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -44,7 +44,7 @@ class MultiPolygon #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type polygon_type; - BOOST_CONCEPT_ASSERT( (concept::Polygon<polygon_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Polygon<polygon_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -72,7 +72,7 @@ class ConstMultiPolygon #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename boost::range_value<Geometry>::type polygon_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPolygon<polygon_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPolygon<polygon_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -85,7 +85,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_MULTI_POLYGON_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/point_concept.hpp b/boost/geometry/geometries/concepts/point_concept.hpp index 52f8d038ea..4001f4e06b 100644 --- a/boost/geometry/geometries/concepts/point_concept.hpp +++ b/boost/geometry/geometries/concepts/point_concept.hpp @@ -30,7 +30,7 @@ -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { /*! @@ -187,6 +187,6 @@ public: #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_POINT_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/polygon_concept.hpp b/boost/geometry/geometries/concepts/polygon_concept.hpp index b478a2274e..58b780009b 100644 --- a/boost/geometry/geometries/concepts/polygon_concept.hpp +++ b/boost/geometry/geometries/concepts/polygon_concept.hpp @@ -27,7 +27,7 @@ #include <boost/geometry/geometries/concepts/ring_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { /*! @@ -48,8 +48,8 @@ class Polygon typedef typename point_type<PolygonType>::type point_type; typedef typename ring_type<PolygonType>::type ring_type; - BOOST_CONCEPT_ASSERT( (concept::Point<point_type>) ); - BOOST_CONCEPT_ASSERT( (concept::Ring<ring_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Ring<ring_type>) ); //BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<interior_type>) ); @@ -101,8 +101,8 @@ class ConstPolygon typedef typename point_type<const_polygon_type>::type point_type; typedef typename ring_type<const_polygon_type>::type ring_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<point_type>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstRing<ring_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstRing<ring_type>) ); ////BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<interior_type>) ); @@ -130,6 +130,6 @@ public: #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_POLYGON_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/ring_concept.hpp b/boost/geometry/geometries/concepts/ring_concept.hpp index 02a36c96f1..d75d428438 100644 --- a/boost/geometry/geometries/concepts/ring_concept.hpp +++ b/boost/geometry/geometries/concepts/ring_concept.hpp @@ -27,7 +27,7 @@ #include <boost/geometry/geometries/concepts/point_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -52,7 +52,7 @@ class Ring #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename point_type<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::Point<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<point_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); public : @@ -81,7 +81,7 @@ class ConstRing #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename point_type<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point_type>) ); BOOST_CONCEPT_ASSERT( (boost::RandomAccessRangeConcept<Geometry>) ); @@ -93,7 +93,7 @@ public : #endif }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_RING_CONCEPT_HPP diff --git a/boost/geometry/geometries/concepts/segment_concept.hpp b/boost/geometry/geometries/concepts/segment_concept.hpp index 8d2d300153..6a1c80486f 100644 --- a/boost/geometry/geometries/concepts/segment_concept.hpp +++ b/boost/geometry/geometries/concepts/segment_concept.hpp @@ -23,7 +23,7 @@ #include <boost/geometry/core/point_type.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -51,7 +51,7 @@ class Segment #ifndef DOXYGEN_NO_CONCEPT_MEMBERS typedef typename point_type<Geometry>::type point_type; - BOOST_CONCEPT_ASSERT( (concept::Point<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<point_type>) ); template <size_t Index, size_t Dimension, size_t DimensionCount> @@ -96,7 +96,7 @@ class ConstSegment typedef typename point_type<Geometry>::type point_type; typedef typename coordinate_type<Geometry>::type coordinate_type; - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<point_type>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point_type>) ); template <size_t Index, size_t Dimension, size_t DimensionCount> @@ -129,7 +129,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_GEOMETRIES_CONCEPTS_SEGMENT_CONCEPT_HPP diff --git a/boost/geometry/geometries/linestring.hpp b/boost/geometry/geometries/linestring.hpp index 22c9c99de9..280c4be7a6 100644 --- a/boost/geometry/geometries/linestring.hpp +++ b/boost/geometry/geometries/linestring.hpp @@ -59,7 +59,7 @@ template > class linestring : public Container<Point, Allocator<Point> > { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); typedef Container<Point, Allocator<Point> > base_type; diff --git a/boost/geometry/geometries/multi_linestring.hpp b/boost/geometry/geometries/multi_linestring.hpp index cd08fdbe14..67003522b0 100644 --- a/boost/geometry/geometries/multi_linestring.hpp +++ b/boost/geometry/geometries/multi_linestring.hpp @@ -55,7 +55,7 @@ template > class multi_linestring : public Container<LineString, Allocator<LineString> > { - BOOST_CONCEPT_ASSERT( (concept::Linestring<LineString>) ); + BOOST_CONCEPT_ASSERT( (concepts::Linestring<LineString>) ); #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST diff --git a/boost/geometry/geometries/multi_point.hpp b/boost/geometry/geometries/multi_point.hpp index ab4cd88177..9579f4f602 100644 --- a/boost/geometry/geometries/multi_point.hpp +++ b/boost/geometry/geometries/multi_point.hpp @@ -58,7 +58,7 @@ template > class multi_point : public Container<Point, Allocator<Point> > { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); typedef Container<Point, Allocator<Point> > base_type; diff --git a/boost/geometry/geometries/multi_polygon.hpp b/boost/geometry/geometries/multi_polygon.hpp index 9db74b4ec4..94cd922719 100644 --- a/boost/geometry/geometries/multi_polygon.hpp +++ b/boost/geometry/geometries/multi_polygon.hpp @@ -54,7 +54,7 @@ template > class multi_polygon : public Container<Polygon, Allocator<Polygon> > { - BOOST_CONCEPT_ASSERT( (concept::Polygon<Polygon>) ); + BOOST_CONCEPT_ASSERT( (concepts::Polygon<Polygon>) ); #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST diff --git a/boost/geometry/geometries/pointing_segment.hpp b/boost/geometry/geometries/pointing_segment.hpp index 2c4284d10a..f865a8a8c1 100644 --- a/boost/geometry/geometries/pointing_segment.hpp +++ b/boost/geometry/geometries/pointing_segment.hpp @@ -44,8 +44,8 @@ class pointing_segment typename boost::mpl::if_ < boost::is_const<ConstOrNonConstPoint>, - concept::Point<ConstOrNonConstPoint>, - concept::ConstPoint<ConstOrNonConstPoint> + concepts::Point<ConstOrNonConstPoint>, + concepts::ConstPoint<ConstOrNonConstPoint> > ) ); diff --git a/boost/geometry/geometries/polygon.hpp b/boost/geometry/geometries/polygon.hpp index 5e6064e893..5d8a0f21f7 100644 --- a/boost/geometry/geometries/polygon.hpp +++ b/boost/geometry/geometries/polygon.hpp @@ -75,7 +75,7 @@ template > class polygon { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); public: diff --git a/boost/geometry/geometries/ring.hpp b/boost/geometry/geometries/ring.hpp index 01bcf58cf5..fda0be40b4 100644 --- a/boost/geometry/geometries/ring.hpp +++ b/boost/geometry/geometries/ring.hpp @@ -63,7 +63,7 @@ template > class ring : public Container<Point, Allocator<Point> > { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); typedef Container<Point, Allocator<Point> > base_type; diff --git a/boost/geometry/geometries/segment.hpp b/boost/geometry/geometries/segment.hpp index af406aa09f..aeb275b858 100644 --- a/boost/geometry/geometries/segment.hpp +++ b/boost/geometry/geometries/segment.hpp @@ -45,7 +45,7 @@ namespace model template<typename Point> class segment : public std::pair<Point, Point> { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); public : @@ -89,8 +89,8 @@ class referring_segment typename boost::mpl::if_ < boost::is_const<ConstOrNonConstPoint>, - concept::Point<ConstOrNonConstPoint>, - concept::ConstPoint<ConstOrNonConstPoint> + concepts::Point<ConstOrNonConstPoint>, + concepts::ConstPoint<ConstOrNonConstPoint> > ) ); diff --git a/boost/geometry/geometry.hpp b/boost/geometry/geometry.hpp index d96facb340..aa80701104 100644 --- a/boost/geometry/geometry.hpp +++ b/boost/geometry/geometry.hpp @@ -4,8 +4,8 @@ // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2014, 2015. -// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014, 2015, 2016. +// Modifications copyright (c) 2014-2016 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -110,7 +110,7 @@ #include <boost/geometry/io/io.hpp> #include <boost/geometry/io/dsv/write.hpp> #include <boost/geometry/io/svg/svg_mapper.hpp> -#include <boost/geometry/io/svg/write_svg.hpp> +#include <boost/geometry/io/svg/write.hpp> #include <boost/geometry/io/wkt/read.hpp> #include <boost/geometry/io/wkt/write.hpp> diff --git a/boost/geometry/index/detail/algorithms/bounds.hpp b/boost/geometry/index/detail/algorithms/bounds.hpp index 4d2416e98d..a62fda070c 100644 --- a/boost/geometry/index/detail/algorithms/bounds.hpp +++ b/boost/geometry/index/detail/algorithms/bounds.hpp @@ -44,7 +44,7 @@ struct bounds<Geometry, Bounds, segment_tag, box_tag> template <typename Geometry, typename Bounds> inline void bounds(Geometry const& g, Bounds & b) { - concept::check_concepts_and_equal_dimensions<Geometry const, Bounds>(); + concepts::check_concepts_and_equal_dimensions<Geometry const, Bounds>(); dispatch::bounds<Geometry, Bounds>::apply(g, b); } diff --git a/boost/geometry/index/detail/algorithms/intersection_content.hpp b/boost/geometry/index/detail/algorithms/intersection_content.hpp index 4afb40479c..04dd4728be 100644 --- a/boost/geometry/index/detail/algorithms/intersection_content.hpp +++ b/boost/geometry/index/detail/algorithms/intersection_content.hpp @@ -2,7 +2,7 @@ // // boxes union/intersection area/volume // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2016 Adam Wulkiewicz, Lodz, Poland. // // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -12,7 +12,7 @@ #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_INTERSECTION_CONTENT_HPP #include <boost/geometry/algorithms/intersection.hpp> -#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_strategies.hpp> #include <boost/geometry/index/detail/algorithms/content.hpp> namespace boost { namespace geometry { namespace index { namespace detail { diff --git a/boost/geometry/index/detail/predicates.hpp b/boost/geometry/index/detail/predicates.hpp index 01afd16ba6..227939c96d 100644 --- a/boost/geometry/index/detail/predicates.hpp +++ b/boost/geometry/index/detail/predicates.hpp @@ -298,7 +298,7 @@ struct predicate_check<predicates::satisfies<Fun, Negated>, bounds_tag> // NOT NEGATED // value_tag bounds_tag // --------------------------- -// contains(I,G) contains(I,G) +// contains(I,G) covers(I,G) // covered_by(I,G) intersects(I,G) // covers(I,G) covers(I,G) // disjoint(I,G) !covered_by(I,G) @@ -329,7 +329,7 @@ struct predicate_check<predicates::spatial_predicate<Geometry, predicates::conta template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return spatial_predicate_call<predicates::contains_tag>::apply(i, p.geometry); + return spatial_predicate_call<predicates::covers_tag>::apply(i, p.geometry); } }; diff --git a/boost/geometry/io/dsv/write.hpp b/boost/geometry/io/dsv/write.hpp index f39a2489ad..f74ae7f95d 100644 --- a/boost/geometry/io/dsv/write.hpp +++ b/boost/geometry/io/dsv/write.hpp @@ -418,7 +418,7 @@ inline detail::dsv::dsv_manipulator<Geometry> dsv(Geometry const& geometry , std::string const& list_separator = ", " ) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return detail::dsv::dsv_manipulator<Geometry>(geometry, detail::dsv::dsv_settings(coordinate_separator, diff --git a/boost/geometry/io/io.hpp b/boost/geometry/io/io.hpp index 9340060776..caafccf2bf 100644 --- a/boost/geometry/io/io.hpp +++ b/boost/geometry/io/io.hpp @@ -47,7 +47,7 @@ struct read<format_wkt, Geometry> template <typename Format, typename Geometry> inline void read(Geometry& geometry, std::string const& wkt) { - geometry::concept::check<Geometry>(); + geometry::concepts::check<Geometry>(); dispatch::read<Format, Geometry>::apply(geometry, wkt); } diff --git a/boost/geometry/io/svg/svg_mapper.hpp b/boost/geometry/io/svg/svg_mapper.hpp index e06f2acc24..6302fd43ba 100644 --- a/boost/geometry/io/svg/svg_mapper.hpp +++ b/boost/geometry/io/svg/svg_mapper.hpp @@ -43,30 +43,22 @@ #include <boost/geometry/strategies/transform/map_transformer.hpp> #include <boost/geometry/views/segment_view.hpp> -#include <boost/geometry/io/svg/write_svg.hpp> +#include <boost/geometry/io/svg/write.hpp> -// Helper geometries (all points are transformed to integer-points) +// Helper geometries (all points are transformed to svg-points) #include <boost/geometry/geometries/geometries.hpp> namespace boost { namespace geometry { -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace svg -{ - typedef model::point<int, 2, cs::cartesian> svg_point_type; -}} -#endif - #ifndef DOXYGEN_NO_DISPATCH namespace dispatch { - -template <typename GeometryTag, typename Geometry> +template <typename GeometryTag, typename Geometry, typename SvgPoint> struct svg_map { BOOST_MPL_ASSERT_MSG @@ -77,26 +69,26 @@ struct svg_map }; -template <typename Point> -struct svg_map<point_tag, Point> +template <typename Point, typename SvgPoint> +struct svg_map<point_tag, Point, SvgPoint> { template <typename TransformStrategy> static inline void apply(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, Point const& point, TransformStrategy const& strategy) { - detail::svg::svg_point_type ipoint; + SvgPoint ipoint; geometry::transform(point, ipoint, strategy); stream << geometry::svg(ipoint, style, size) << std::endl; } }; -template <typename BoxSeg1, typename BoxSeg2> +template <typename BoxSeg1, typename BoxSeg2, typename SvgPoint> struct svg_map_box_seg { template <typename TransformStrategy> static inline void apply(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, BoxSeg1 const& box_seg, TransformStrategy const& strategy) { BoxSeg2 ibox_seg; @@ -111,23 +103,23 @@ struct svg_map_box_seg } }; -template <typename Box> -struct svg_map<box_tag, Box> - : svg_map_box_seg<Box, model::box<detail::svg::svg_point_type> > +template <typename Box, typename SvgPoint> +struct svg_map<box_tag, Box, SvgPoint> + : svg_map_box_seg<Box, model::box<SvgPoint>, SvgPoint> {}; -template <typename Segment> -struct svg_map<segment_tag, Segment> - : svg_map_box_seg<Segment, model::segment<detail::svg::svg_point_type> > +template <typename Segment, typename SvgPoint> +struct svg_map<segment_tag, Segment, SvgPoint> + : svg_map_box_seg<Segment, model::segment<SvgPoint>, SvgPoint> {}; -template <typename Range1, typename Range2> +template <typename Range1, typename Range2, typename SvgPoint> struct svg_map_range { template <typename TransformStrategy> static inline void apply(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, Range1 const& range, TransformStrategy const& strategy) { Range2 irange; @@ -136,35 +128,35 @@ struct svg_map_range } }; -template <typename Ring> -struct svg_map<ring_tag, Ring> - : svg_map_range<Ring, model::ring<detail::svg::svg_point_type> > +template <typename Ring, typename SvgPoint> +struct svg_map<ring_tag, Ring, SvgPoint> + : svg_map_range<Ring, model::ring<SvgPoint>, SvgPoint> {}; -template <typename Linestring> -struct svg_map<linestring_tag, Linestring> - : svg_map_range<Linestring, model::linestring<detail::svg::svg_point_type> > +template <typename Linestring, typename SvgPoint> +struct svg_map<linestring_tag, Linestring, SvgPoint> + : svg_map_range<Linestring, model::linestring<SvgPoint>, SvgPoint> {}; -template <typename Polygon> -struct svg_map<polygon_tag, Polygon> +template <typename Polygon, typename SvgPoint> +struct svg_map<polygon_tag, Polygon, SvgPoint> { template <typename TransformStrategy> static inline void apply(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, Polygon const& polygon, TransformStrategy const& strategy) { - model::polygon<detail::svg::svg_point_type> ipoly; + model::polygon<SvgPoint> ipoly; geometry::transform(polygon, ipoly, strategy); stream << geometry::svg(ipoly, style, size) << std::endl; } }; -template <typename Multi> -struct svg_map<multi_tag, Multi> +template <typename Multi, typename SvgPoint> +struct svg_map<multi_tag, Multi, SvgPoint> { typedef typename single_tag_of < @@ -173,7 +165,7 @@ struct svg_map<multi_tag, Multi> template <typename TransformStrategy> static inline void apply(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, Multi const& multi, TransformStrategy const& strategy) { for (typename boost::range_iterator<Multi const>::type it @@ -184,31 +176,88 @@ struct svg_map<multi_tag, Multi> svg_map < stag, - typename boost::range_value<Multi>::type + typename boost::range_value<Multi>::type, + SvgPoint >::apply(stream, style, size, *it, strategy); } } }; +template <typename SvgPoint, typename Geometry> +struct devarianted_svg_map +{ + template <typename TransformStrategy> + static inline void apply(std::ostream& stream, + std::string const& style, + double size, + Geometry const& geometry, + TransformStrategy const& strategy) + { + svg_map + < + typename tag_cast + < + typename tag<Geometry>::type, + multi_tag + >::type, + typename boost::remove_const<Geometry>::type, + SvgPoint + >::apply(stream, style, size, geometry, strategy); + } +}; + +template <typename SvgPoint, BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct devarianted_svg_map<SvgPoint, variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename TransformStrategy> + struct visitor: static_visitor<void> + { + std::ostream& m_os; + std::string const& m_style; + double m_size; + TransformStrategy const& m_strategy; + + visitor(std::ostream& os, + std::string const& style, + double size, + TransformStrategy const& strategy) + : m_os(os) + , m_style(style) + , m_size(size) + , m_strategy(strategy) + {} + + template <typename Geometry> + inline void operator()(Geometry const& geometry) const + { + devarianted_svg_map<SvgPoint, Geometry>::apply(m_os, m_style, m_size, geometry, m_strategy); + } + }; + + template <typename TransformStrategy> + static inline void apply(std::ostream& stream, + std::string const& style, + double size, + variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, + TransformStrategy const& strategy) + { + boost::apply_visitor(visitor<TransformStrategy>(stream, style, size, strategy), geometry); + } +}; + + } // namespace dispatch #endif -template <typename Geometry, typename TransformStrategy> +template <typename SvgPoint, typename Geometry, typename TransformStrategy> inline void svg_map(std::ostream& stream, - std::string const& style, int size, + std::string const& style, double size, Geometry const& geometry, TransformStrategy const& strategy) { - dispatch::svg_map - < - typename tag_cast - < - typename tag<Geometry>::type, - multi_tag - >::type, - typename boost::remove_const<Geometry>::type - >::apply(stream, style, size, geometry, strategy); + dispatch::devarianted_svg_map<SvgPoint, Geometry>::apply(stream, + style, size, geometry, strategy); } @@ -217,13 +266,22 @@ inline void svg_map(std::ostream& stream, \tparam Point Point type, for input geometries. \tparam SameScale Boolean flag indicating if horizontal and vertical scale should be the same. The default value is true +\tparam SvgCoordinateType Coordinate type of SVG points. SVG is capable to + use floating point coordinates. Therefore the default value is double \ingroup svg \qbk{[include reference/io/svg.qbk]} */ -template <typename Point, bool SameScale = true> +template +< + typename Point, + bool SameScale = true, + typename SvgCoordinateType = double +> class svg_mapper : boost::noncopyable { + typedef model::point<SvgCoordinateType, 2, cs::cartesian> svg_point_type; + typedef typename geometry::select_most_precise < typename coordinate_type<Point>::type, @@ -242,7 +300,7 @@ class svg_mapper : boost::noncopyable model::box<Point> m_bounding_box; boost::scoped_ptr<transformer_type> m_matrix; std::ostream& m_stream; - int m_width, m_height; + SvgCoordinateType m_width, m_height; std::string m_width_height; // for <svg> tag only, defaults to 2x 100% void init_matrix() @@ -279,7 +337,9 @@ public : \param height Height of the SVG map (in SVG pixels) \param width_height Optional information to increase width and/or height */ - explicit svg_mapper(std::ostream& stream, int width, int height + svg_mapper(std::ostream& stream + , SvgCoordinateType width + , SvgCoordinateType height , std::string const& width_height = "width=\"100%\" height=\"100%\"") : m_stream(stream) , m_width(width) @@ -326,10 +386,10 @@ public : */ template <typename Geometry> void map(Geometry const& geometry, std::string const& style, - int size = -1) + double size = -1.0) { init_matrix(); - svg_map(m_stream, style, size, geometry, *m_matrix); + svg_map<svg_point_type>(m_stream, style, size, geometry, *m_matrix); } /*! @@ -345,10 +405,11 @@ public : template <typename TextPoint> void text(TextPoint const& point, std::string const& s, std::string const& style, - int offset_x = 0, int offset_y = 0, int lineheight = 10) + double offset_x = 0.0, double offset_y = 0.0, + double lineheight = 10.0) { init_matrix(); - detail::svg::svg_point_type map_point; + svg_point_type map_point; transform(point, map_point, *m_matrix); m_stream << "<text style=\"" << style << "\"" diff --git a/boost/geometry/io/svg/write.hpp b/boost/geometry/io/svg/write.hpp new file mode 100644 index 0000000000..70858021fc --- /dev/null +++ b/boost/geometry/io/svg/write.hpp @@ -0,0 +1,418 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2009-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2016. +// Modifications copyright (c) 2016, Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, 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_IO_SVG_WRITE_HPP +#define BOOST_GEOMETRY_IO_SVG_WRITE_HPP + +#include <ostream> +#include <string> + +#include <boost/config.hpp> +#include <boost/mpl/assert.hpp> +#include <boost/range.hpp> + +#include <boost/variant/apply_visitor.hpp> +#include <boost/variant/static_visitor.hpp> +#include <boost/variant/variant_fwd.hpp> + +#include <boost/geometry/algorithms/detail/interior_iterator.hpp> + +#include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/interior_rings.hpp> +#include <boost/geometry/core/ring_type.hpp> + +#include <boost/geometry/geometries/concepts/check.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace svg +{ + + +template <typename Point> +struct svg_point +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + Point const& p, std::string const& style, double size) + { + os << "<circle cx=\"" << geometry::get<0>(p) + << "\" cy=\"" << geometry::get<1>(p) + << "\" r=\"" << (size < 0 ? 5 : size) + << "\" style=\"" << style << "\"/>"; + } +}; + + +template <typename Box> +struct svg_box +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + Box const& box, std::string const& style, double) + { + // Prevent invisible boxes, making them >=1, using "max" + BOOST_USING_STD_MAX(); + + typedef typename coordinate_type<Box>::type ct; + ct x = geometry::get<geometry::min_corner, 0>(box); + ct y = geometry::get<geometry::min_corner, 1>(box); + ct width = max BOOST_PREVENT_MACRO_SUBSTITUTION (ct(1), + geometry::get<geometry::max_corner, 0>(box) - x); + ct height = max BOOST_PREVENT_MACRO_SUBSTITUTION (ct(1), + geometry::get<geometry::max_corner, 1>(box) - y); + + os << "<rect x=\"" << x << "\" y=\"" << y + << "\" width=\"" << width << "\" height=\"" << height + << "\" style=\"" << style << "\"/>"; + } +}; + +template <typename Segment> +struct svg_segment +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + Segment const& segment, std::string const& style, double) + { + typedef typename coordinate_type<Segment>::type ct; + ct x1 = geometry::get<0, 0>(segment); + ct y1 = geometry::get<0, 1>(segment); + ct x2 = geometry::get<1, 0>(segment); + ct y2 = geometry::get<1, 1>(segment); + + os << "<line x1=\"" << x1 << "\" y1=\"" << y1 + << "\" x2=\"" << x2 << "\" y2=\"" << y2 + << "\" style=\"" << style << "\"/>"; + } +}; + +/*! +\brief Stream ranges as SVG +\note policy is used to select type (polyline/polygon) +*/ +template <typename Range, typename Policy> +struct svg_range +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + Range const& range, std::string const& style, double) + { + typedef typename boost::range_iterator<Range const>::type iterator; + + bool first = true; + + os << "<" << Policy::prefix() << " points=\""; + + for (iterator it = boost::begin(range); + it != boost::end(range); + ++it, first = false) + { + os << (first ? "" : " " ) + << geometry::get<0>(*it) + << "," + << geometry::get<1>(*it); + } + os << "\" style=\"" << style << Policy::style() << "\"/>"; + } +}; + + + +template <typename Polygon> +struct svg_poly +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + Polygon const& polygon, std::string const& style, double) + { + typedef typename geometry::ring_type<Polygon>::type ring_type; + typedef typename boost::range_iterator<ring_type const>::type iterator_type; + + bool first = true; + os << "<g fill-rule=\"evenodd\"><path d=\""; + + ring_type const& ring = geometry::exterior_ring(polygon); + for (iterator_type it = boost::begin(ring); + it != boost::end(ring); + ++it, first = false) + { + os << (first ? "M" : " L") << " " + << geometry::get<0>(*it) + << "," + << geometry::get<1>(*it); + } + + // Inner rings: + { + typename interior_return_type<Polygon const>::type + rings = interior_rings(polygon); + for (typename detail::interior_iterator<Polygon const>::type + rit = boost::begin(rings); rit != boost::end(rings); ++rit) + { + first = true; + for (typename detail::interior_ring_iterator<Polygon const>::type + it = boost::begin(*rit); it != boost::end(*rit); + ++it, first = false) + { + os << (first ? "M" : " L") << " " + << geometry::get<0>(*it) + << "," + << geometry::get<1>(*it); + } + } + } + os << " z \" style=\"" << style << "\"/></g>"; + + } +}; + + + +struct prefix_linestring +{ + static inline const char* prefix() { return "polyline"; } + static inline const char* style() { return ";fill:none"; } +}; + + +struct prefix_ring +{ + static inline const char* prefix() { return "polygon"; } + static inline const char* style() { return ""; } +}; + + +template <typename MultiGeometry, typename Policy> +struct svg_multi +{ + template <typename Char, typename Traits> + static inline void apply(std::basic_ostream<Char, Traits>& os, + MultiGeometry const& multi, std::string const& style, double size) + { + for (typename boost::range_iterator<MultiGeometry const>::type + it = boost::begin(multi); + it != boost::end(multi); + ++it) + { + Policy::apply(os, *it, style, size); + } + + } + +}; + + +}} // namespace detail::svg +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +/*! +\brief Dispatching base struct for SVG streaming, specialized below per geometry type +\details Specializations should implement a static method "stream" to stream a geometry +The static method should have the signature: + +template <typename Char, typename Traits> +static inline void apply(std::basic_ostream<Char, Traits>& os, G const& geometry) +*/ +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct svg +{ + BOOST_MPL_ASSERT_MSG + ( + false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE + , (Geometry) + ); +}; + +template <typename Point> +struct svg<Point, point_tag> : detail::svg::svg_point<Point> {}; + +template <typename Segment> +struct svg<Segment, segment_tag> : detail::svg::svg_segment<Segment> {}; + +template <typename Box> +struct svg<Box, box_tag> : detail::svg::svg_box<Box> {}; + +template <typename Linestring> +struct svg<Linestring, linestring_tag> + : detail::svg::svg_range<Linestring, detail::svg::prefix_linestring> {}; + +template <typename Ring> +struct svg<Ring, ring_tag> + : detail::svg::svg_range<Ring, detail::svg::prefix_ring> {}; + +template <typename Polygon> +struct svg<Polygon, polygon_tag> + : detail::svg::svg_poly<Polygon> {}; + +template <typename MultiPoint> +struct svg<MultiPoint, multi_point_tag> + : detail::svg::svg_multi + < + MultiPoint, + detail::svg::svg_point + < + typename boost::range_value<MultiPoint>::type + > + + > +{}; + +template <typename MultiLinestring> +struct svg<MultiLinestring, multi_linestring_tag> + : detail::svg::svg_multi + < + MultiLinestring, + detail::svg::svg_range + < + typename boost::range_value<MultiLinestring>::type, + detail::svg::prefix_linestring + > + + > +{}; + +template <typename MultiPolygon> +struct svg<MultiPolygon, multi_polygon_tag> + : detail::svg::svg_multi + < + MultiPolygon, + detail::svg::svg_poly + < + typename boost::range_value<MultiPolygon>::type + > + + > +{}; + + +template <typename Geometry> +struct devarianted_svg +{ + template <typename OutputStream> + static inline void apply(OutputStream& os, + Geometry const& geometry, + std::string const& style, + double size) + { + svg<Geometry>::apply(os, geometry, style, size); + } +}; + +template <BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct devarianted_svg<variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename OutputStream> + struct visitor: static_visitor<void> + { + OutputStream& m_os; + std::string const& m_style; + double m_size; + + visitor(OutputStream& os, std::string const& style, double size) + : m_os(os) + , m_style(style) + , m_size(size) + {} + + template <typename Geometry> + inline void operator()(Geometry const& geometry) const + { + devarianted_svg<Geometry>::apply(m_os, geometry, m_style, m_size); + } + }; + + template <typename OutputStream> + static inline void apply( + OutputStream& os, + variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, + std::string const& style, + double size + ) + { + boost::apply_visitor(visitor<OutputStream>(os, style, size), geometry); + } +}; + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +/*! +\brief Generic geometry template manipulator class, takes corresponding output class from traits class +\ingroup svg +\details Stream manipulator, streams geometry classes as SVG (Scalable Vector Graphics) +*/ +template <typename Geometry> +class svg_manipulator +{ +public: + + inline svg_manipulator(Geometry const& g, std::string const& style, double size) + : m_geometry(g) + , m_style(style) + , m_size(size) + {} + + template <typename Char, typename Traits> + inline friend std::basic_ostream<Char, Traits>& operator<<( + std::basic_ostream<Char, Traits>& os, svg_manipulator const& m) + { + dispatch::devarianted_svg<Geometry>::apply(os, + m.m_geometry, + m.m_style, + m.m_size); + os.flush(); + return os; + } + +private: + Geometry const& m_geometry; + std::string const& m_style; + double m_size; +}; + +/*! +\brief Manipulator to stream geometries as SVG +\tparam Geometry \tparam_geometry +\param geometry \param_geometry +\param style String containing verbatim SVG style information +\param size Optional size (used for SVG points) in SVG pixels. For linestrings, + specify linewidth in the SVG style information +\ingroup svg +*/ +template <typename Geometry> +inline svg_manipulator<Geometry> svg(Geometry const& geometry, + std::string const& style, double size = -1.0) +{ + concepts::check<Geometry const>(); + + return svg_manipulator<Geometry>(geometry, style, size); +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_IO_SVG_WRITE_HPP diff --git a/boost/geometry/io/svg/write_svg.hpp b/boost/geometry/io/svg/write_svg.hpp index 4a518a0815..371a80bc69 100644 --- a/boost/geometry/io/svg/write_svg.hpp +++ b/boost/geometry/io/svg/write_svg.hpp @@ -18,288 +18,11 @@ #ifndef BOOST_GEOMETRY_IO_SVG_WRITE_SVG_HPP #define BOOST_GEOMETRY_IO_SVG_WRITE_SVG_HPP -#include <ostream> -#include <string> -#include <boost/config.hpp> -#include <boost/mpl/assert.hpp> -#include <boost/range.hpp> +// THIS FILE WAS LEFT HERE FOR BACKWARD COMPATIBILITY -#include <boost/geometry/algorithms/detail/interior_iterator.hpp> -#include <boost/geometry/core/exterior_ring.hpp> -#include <boost/geometry/core/interior_rings.hpp> -#include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/io/svg/write.hpp> -#include <boost/geometry/geometries/concepts/check.hpp> - - -namespace boost { namespace geometry -{ - - -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace svg -{ - - -template <typename Point> -struct svg_point -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - Point const& p, std::string const& style, int size) - { - os << "<circle cx=\"" << geometry::get<0>(p) - << "\" cy=\"" << geometry::get<1>(p) - << "\" r=\"" << (size < 0 ? 5 : size) - << "\" style=\"" << style << "\"/>"; - } -}; - - -template <typename Box> -struct svg_box -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - Box const& box, std::string const& style, int ) - { - // Prevent invisible boxes, making them >=1, using "max" - BOOST_USING_STD_MAX(); - - typedef typename coordinate_type<Box>::type ct; - ct x = geometry::get<geometry::min_corner, 0>(box); - ct y = geometry::get<geometry::min_corner, 1>(box); - ct width = max BOOST_PREVENT_MACRO_SUBSTITUTION (ct(1), - geometry::get<geometry::max_corner, 0>(box) - x); - ct height = max BOOST_PREVENT_MACRO_SUBSTITUTION (ct(1), - geometry::get<geometry::max_corner, 1>(box) - y); - - os << "<rect x=\"" << x << "\" y=\"" << y - << "\" width=\"" << width << "\" height=\"" << height - << "\" style=\"" << style << "\"/>"; - } -}; - -template <typename Segment> -struct svg_segment -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - Segment const& segment, std::string const& style, int) - { - typedef typename coordinate_type<Segment>::type ct; - ct x1 = geometry::get<0, 0>(segment); - ct y1 = geometry::get<0, 1>(segment); - ct x2 = geometry::get<1, 0>(segment); - ct y2 = geometry::get<1, 1>(segment); - - os << "<line x1=\"" << x1 << "\" y1=\"" << y1 - << "\" x2=\"" << x2 << "\" y2=\"" << y2 - << "\" style=\"" << style << "\"/>"; - } -}; - -/*! -\brief Stream ranges as SVG -\note policy is used to select type (polyline/polygon) -*/ -template <typename Range, typename Policy> -struct svg_range -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - Range const& range, std::string const& style, int ) - { - typedef typename boost::range_iterator<Range const>::type iterator; - - bool first = true; - - os << "<" << Policy::prefix() << " points=\""; - - for (iterator it = boost::begin(range); - it != boost::end(range); - ++it, first = false) - { - os << (first ? "" : " " ) - << geometry::get<0>(*it) - << "," - << geometry::get<1>(*it); - } - os << "\" style=\"" << style << Policy::style() << "\"/>"; - } -}; - - - -template <typename Polygon> -struct svg_poly -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - Polygon const& polygon, std::string const& style, int ) - { - typedef typename geometry::ring_type<Polygon>::type ring_type; - typedef typename boost::range_iterator<ring_type const>::type iterator_type; - - bool first = true; - os << "<g fill-rule=\"evenodd\"><path d=\""; - - ring_type const& ring = geometry::exterior_ring(polygon); - for (iterator_type it = boost::begin(ring); - it != boost::end(ring); - ++it, first = false) - { - os << (first ? "M" : " L") << " " - << geometry::get<0>(*it) - << "," - << geometry::get<1>(*it); - } - - // Inner rings: - { - typename interior_return_type<Polygon const>::type - rings = interior_rings(polygon); - for (typename detail::interior_iterator<Polygon const>::type - rit = boost::begin(rings); rit != boost::end(rings); ++rit) - { - first = true; - for (typename detail::interior_ring_iterator<Polygon const>::type - it = boost::begin(*rit); it != boost::end(*rit); - ++it, first = false) - { - os << (first ? "M" : " L") << " " - << geometry::get<0>(*it) - << "," - << geometry::get<1>(*it); - } - } - } - os << " z \" style=\"" << style << "\"/></g>"; - - } -}; - - - -struct prefix_linestring -{ - static inline const char* prefix() { return "polyline"; } - static inline const char* style() { return ";fill:none"; } -}; - - -struct prefix_ring -{ - static inline const char* prefix() { return "polygon"; } - static inline const char* style() { return ""; } -}; - - - -}} // namespace detail::svg -#endif // DOXYGEN_NO_DETAIL - - -#ifndef DOXYGEN_NO_DISPATCH -namespace dispatch -{ - -/*! -\brief Dispatching base struct for SVG streaming, specialized below per geometry type -\details Specializations should implement a static method "stream" to stream a geometry -The static method should have the signature: - -template <typename Char, typename Traits> -static inline void apply(std::basic_ostream<Char, Traits>& os, G const& geometry) -*/ -template <typename GeometryTag, typename Geometry> -struct svg -{ - BOOST_MPL_ASSERT_MSG - ( - false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE - , (Geometry) - ); -}; - -template <typename Point> -struct svg<point_tag, Point> : detail::svg::svg_point<Point> {}; - -template <typename Segment> -struct svg<segment_tag, Segment> : detail::svg::svg_segment<Segment> {}; - -template <typename Box> -struct svg<box_tag, Box> : detail::svg::svg_box<Box> {}; - -template <typename Linestring> -struct svg<linestring_tag, Linestring> - : detail::svg::svg_range<Linestring, detail::svg::prefix_linestring> {}; - -template <typename Ring> -struct svg<ring_tag, Ring> - : detail::svg::svg_range<Ring, detail::svg::prefix_ring> {}; - -template <typename Polygon> -struct svg<polygon_tag, Polygon> - : detail::svg::svg_poly<Polygon> {}; - -} // namespace dispatch -#endif // DOXYGEN_NO_DISPATCH - - -/*! -\brief Generic geometry template manipulator class, takes corresponding output class from traits class -\ingroup svg -\details Stream manipulator, streams geometry classes as SVG (Scalable Vector Graphics) -*/ -template <typename G> -class svg_manipulator -{ -public: - - inline svg_manipulator(G const& g, std::string const& style, int size) - : m_geometry(g) - , m_style(style) - , m_size(size) - {} - - template <typename Char, typename Traits> - inline friend std::basic_ostream<Char, Traits>& operator<<( - std::basic_ostream<Char, Traits>& os, svg_manipulator const& m) - { - dispatch::svg - < - typename tag<G>::type, G - >::apply(os, m.m_geometry, m.m_style, m.m_size); - os.flush(); - return os; - } - -private: - G const& m_geometry; - std::string const& m_style; - int m_size; -}; - -/*! -\brief Manipulator to stream geometries as SVG -\tparam Geometry \tparam_geometry -\param geometry \param_geometry -\param style String containing verbatim SVG style information -\param size Optional size (used for SVG points) in SVG pixels. For linestrings, - specify linewidth in the SVG style information -\ingroup svg -*/ -template <typename Geometry> -inline svg_manipulator<Geometry> svg(Geometry const& geometry, std::string const& style, int size = -1) -{ - concept::check<Geometry const>(); - - return svg_manipulator<Geometry>(geometry, style, size); -} - -}} // namespace boost::geometry #endif // BOOST_GEOMETRY_IO_SVG_WRITE_SVG_HPP diff --git a/boost/geometry/io/svg/write_svg_multi.hpp b/boost/geometry/io/svg/write_svg_multi.hpp index ff349ebd75..d07a2c204e 100644 --- a/boost/geometry/io/svg/write_svg_multi.hpp +++ b/boost/geometry/io/svg/write_svg_multi.hpp @@ -18,92 +18,10 @@ #define BOOST_GEOMETRY_IO_SVG_WRITE_SVG_MULTI_HPP -#include <boost/geometry/io/svg/write_svg.hpp> +// THIS FILE WAS LEFT HERE FOR BACKWARD COMPATIBILITY -namespace boost { namespace geometry -{ - -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace svg -{ - - -template <typename MultiGeometry, typename Policy> -struct svg_multi -{ - template <typename Char, typename Traits> - static inline void apply(std::basic_ostream<Char, Traits>& os, - MultiGeometry const& multi, std::string const& style, int size) - { - for (typename boost::range_iterator<MultiGeometry const>::type - it = boost::begin(multi); - it != boost::end(multi); - ++it) - { - Policy::apply(os, *it, style, size); - } - - } - -}; - - - -}} // namespace detail::svg -#endif // DOXYGEN_NO_DETAIL - - -#ifndef DOXYGEN_NO_DISPATCH -namespace dispatch -{ - -template <typename MultiPoint> -struct svg<multi_point_tag, MultiPoint> - : detail::svg::svg_multi - < - MultiPoint, - detail::svg::svg_point - < - typename boost::range_value<MultiPoint>::type - > - - > -{}; - -template <typename MultiLinestring> -struct svg<multi_linestring_tag, MultiLinestring> - : detail::svg::svg_multi - < - MultiLinestring, - detail::svg::svg_range - < - typename boost::range_value<MultiLinestring>::type, - detail::svg::prefix_linestring - > - - > -{}; - -template <typename MultiPolygon> -struct svg<multi_polygon_tag, MultiPolygon> - : detail::svg::svg_multi - < - MultiPolygon, - detail::svg::svg_poly - < - typename boost::range_value<MultiPolygon>::type - > - - > -{}; - - -} // namespace dispatch -#endif // DOXYGEN_NO_DISPATCH - - -}} // namespace boost::geometry +#include <boost/geometry/io/svg/write.hpp> #endif // BOOST_GEOMETRY_IO_SVG_WRITE_SVG_MULTI_HPP diff --git a/boost/geometry/io/wkt/read.hpp b/boost/geometry/io/wkt/read.hpp index 7924b70283..148a5769dd 100644 --- a/boost/geometry/io/wkt/read.hpp +++ b/boost/geometry/io/wkt/read.hpp @@ -894,7 +894,7 @@ struct read_wkt<segment_tag, Segment> template <typename Geometry> inline void read_wkt(std::string const& wkt, Geometry& geometry) { - geometry::concept::check<Geometry>(); + geometry::concepts::check<Geometry>(); dispatch::read_wkt<typename tag<Geometry>::type, Geometry>::apply(wkt, geometry); } diff --git a/boost/geometry/io/wkt/write.hpp b/boost/geometry/io/wkt/write.hpp index a556aa440f..b98c894b38 100644 --- a/boost/geometry/io/wkt/write.hpp +++ b/boost/geometry/io/wkt/write.hpp @@ -501,7 +501,7 @@ private: template <typename Geometry> inline wkt_manipulator<Geometry> wkt(Geometry const& geometry) { - concept::check<Geometry const>(); + concepts::check<Geometry const>(); return wkt_manipulator<Geometry>(geometry); } diff --git a/boost/geometry/policies/relate/intersection_points.hpp b/boost/geometry/policies/relate/intersection_points.hpp index 50f9b43122..2ca84ac028 100644 --- a/boost/geometry/policies/relate/intersection_points.hpp +++ b/boost/geometry/policies/relate/intersection_points.hpp @@ -2,6 +2,10 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2016. +// Modifications copyright (c) 2016 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -13,17 +17,10 @@ #include <algorithm> #include <string> -#include <boost/concept_check.hpp> -#include <boost/numeric/conversion/cast.hpp> - #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> #include <boost/geometry/strategies/side_info.hpp> -#include <boost/geometry/util/promote_integral.hpp> -#include <boost/geometry/util/select_calculation_type.hpp> -#include <boost/geometry/util/select_most_precise.hpp> -#include <boost/geometry/util/math.hpp> namespace boost { namespace geometry { @@ -45,45 +42,6 @@ struct segments_intersection_points template < - typename Point, - typename Segment, - typename SegmentRatio, - typename T - > - static inline void assign(Point& point, - Segment const& segment, - SegmentRatio const& ratio, - T const& dx, T const& dy) - { - typedef typename geometry::coordinate_type<Point>::type coordinate_type; - - // Calculate the intersection point based on segment_ratio - // Up to now, division was postponed. Here we divide using numerator/ - // denominator. In case of integer this results in an integer - // division. - BOOST_GEOMETRY_ASSERT(ratio.denominator() != 0); - - typedef typename promote_integral<coordinate_type>::type promoted_type; - - promoted_type const numerator - = boost::numeric_cast<promoted_type>(ratio.numerator()); - promoted_type const denominator - = boost::numeric_cast<promoted_type>(ratio.denominator()); - promoted_type const dx_promoted = boost::numeric_cast<promoted_type>(dx); - promoted_type const dy_promoted = boost::numeric_cast<promoted_type>(dy); - - set<0>(point, get<0, 0>(segment) + boost::numeric_cast - < - coordinate_type - >(numerator * dx_promoted / denominator)); - set<1>(point, get<0, 1>(segment) + boost::numeric_cast - < - coordinate_type - >(numerator * dy_promoted / denominator)); - } - - template - < typename Segment1, typename Segment2, typename SegmentIntersectionInfo @@ -112,8 +70,8 @@ struct segments_intersection_points { // Prefer shorter segment typedef typename SegmentIntersectionInfo::promoted_type ptype; - ptype const len_a = sinfo.dx_a * sinfo.dx_a + sinfo.dy_a * sinfo.dy_a; - ptype const len_b = sinfo.dx_b * sinfo.dx_b + sinfo.dy_b * sinfo.dy_b; + ptype const len_a = sinfo.comparable_length_a(); + ptype const len_b = sinfo.comparable_length_b(); if (len_b < len_a) { use_a = false; @@ -123,13 +81,11 @@ struct segments_intersection_points if (use_a) { - assign(result.intersections[0], s1, sinfo.robust_ra, - sinfo.dx_a, sinfo.dy_a); + sinfo.assign_a(result.intersections[0], s1, s2); } else { - assign(result.intersections[0], s2, sinfo.robust_rb, - sinfo.dx_b, sinfo.dy_b); + sinfo.assign_b(result.intersections[0], s1, s2); } result.fractions[0].assign(sinfo); diff --git a/boost/geometry/policies/robustness/segment_ratio.hpp b/boost/geometry/policies/robustness/segment_ratio.hpp index ec659257a2..f3dbabe70a 100644 --- a/boost/geometry/policies/robustness/segment_ratio.hpp +++ b/boost/geometry/policies/robustness/segment_ratio.hpp @@ -2,6 +2,10 @@ // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands. +// This file was modified by Oracle on 2016. +// Modifications copyright (c) 2016 Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) @@ -190,7 +194,7 @@ public : inline bool close_to(thistype const& other) const { - return geometry::math::abs(m_approximation - other.m_approximation) < 2; + return geometry::math::abs(m_approximation - other.m_approximation) < 50; } inline bool operator< (thistype const& other) const diff --git a/boost/geometry/strategies/cartesian/cart_intersect.hpp b/boost/geometry/strategies/cartesian/cart_intersect.hpp index 8a9857376a..0cb5d75457 100644 --- a/boost/geometry/strategies/cartesian/cart_intersect.hpp +++ b/boost/geometry/strategies/cartesian/cart_intersect.hpp @@ -3,8 +3,8 @@ // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2013-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. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -30,6 +30,7 @@ #include <boost/geometry/algorithms/detail/recalculate.hpp> #include <boost/geometry/util/math.hpp> +#include <boost/geometry/util/promote_integral.hpp> #include <boost/geometry/util/select_calculation_type.hpp> // Temporary / will be Strategy as template parameter @@ -37,6 +38,7 @@ #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp> #include <boost/geometry/strategies/side_info.hpp> +#include <boost/geometry/strategies/intersection.hpp> #include <boost/geometry/strategies/intersection_result.hpp> #include <boost/geometry/policies/robustness/robust_point_type.hpp> @@ -64,6 +66,69 @@ struct relate_cartesian_segments { typedef typename Policy::return_type return_type; + template <typename CoordinateType, typename SegmentRatio> + struct segment_intersection_info + { + typedef typename select_most_precise + < + CoordinateType, double + >::type promoted_type; + + promoted_type comparable_length_a() const + { + return dx_a * dx_a + dy_a * dy_a; + } + + promoted_type comparable_length_b() const + { + return dx_b * dx_b + dy_b * dy_b; + } + + template <typename Point, typename Segment1, typename Segment2> + void assign_a(Point& point, Segment1 const& a, Segment2 const& ) const + { + assign(point, a, dx_a, dy_a, robust_ra); + } + template <typename Point, typename Segment1, typename Segment2> + void assign_b(Point& point, Segment1 const& , Segment2 const& b) const + { + assign(point, b, dx_b, dy_b, robust_rb); + } + + template <typename Point, typename Segment> + void assign(Point& point, Segment const& segment, CoordinateType const& dx, CoordinateType const& dy, SegmentRatio const& ratio) const + { + // Calculate the intersection point based on segment_ratio + // Up to now, division was postponed. Here we divide using numerator/ + // denominator. In case of integer this results in an integer + // division. + BOOST_GEOMETRY_ASSERT(ratio.denominator() != 0); + + typedef typename promote_integral<CoordinateType>::type promoted_type; + + promoted_type const numerator + = boost::numeric_cast<promoted_type>(ratio.numerator()); + promoted_type const denominator + = boost::numeric_cast<promoted_type>(ratio.denominator()); + promoted_type const dx_promoted = boost::numeric_cast<promoted_type>(dx); + promoted_type const dy_promoted = boost::numeric_cast<promoted_type>(dy); + + set<0>(point, get<0, 0>(segment) + boost::numeric_cast + < + CoordinateType + >(numerator * dx_promoted / denominator)); + set<1>(point, get<0, 1>(segment) + boost::numeric_cast + < + CoordinateType + >(numerator * dy_promoted / denominator)); + } + + CoordinateType dx_a, dy_a; + CoordinateType dx_b, dy_b; + SegmentRatio robust_ra; + SegmentRatio robust_rb; + }; + template <typename D, typename W, typename ResultType> static inline void cramers_rule(D const& dx_a, D const& dy_a, D const& dx_b, D const& dy_b, W const& wx, W const& wy, @@ -108,16 +173,17 @@ struct relate_cartesian_segments } // The main entry-routine, calculating intersections of segments a / b - template <typename Segment1, typename Segment2, typename RobustPolicy, typename RobustPoint> + // NOTE: Robust* types may be the same as Segments' point types + template <typename Segment1, typename Segment2, + typename RobustPolicy, + typename RobustPoint1, typename RobustPoint2> static inline return_type apply(Segment1 const& a, Segment2 const& b, - RobustPolicy const& robust_policy, - RobustPoint const& robust_a1, RobustPoint const& robust_a2, - RobustPoint const& robust_b1, RobustPoint const& robust_b2) + RobustPolicy const& /*robust_policy*/, + RobustPoint1 const& robust_a1, RobustPoint1 const& robust_a2, + RobustPoint2 const& robust_b1, RobustPoint2 const& robust_b2) { - BOOST_CONCEPT_ASSERT( (concept::ConstSegment<Segment1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstSegment<Segment2>) ); - - boost::ignore_unused_variable_warning(robust_policy); + BOOST_CONCEPT_ASSERT( (concepts::ConstSegment<Segment1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstSegment<Segment2>) ); using geometry::detail::equals::equals_point_point; bool const a_is_point = equals_point_point(robust_a1, robust_a2); @@ -159,12 +225,8 @@ struct relate_cartesian_segments typedef typename select_most_precise < - coordinate_type, double - >::type promoted_type; - - typedef typename geometry::coordinate_type - < - RobustPoint + typename geometry::coordinate_type<RobustPoint1>::type, + typename geometry::coordinate_type<RobustPoint2>::type >::type robust_coordinate_type; typedef typename segment_ratio_type @@ -176,7 +238,6 @@ struct relate_cartesian_segments segment_intersection_info < coordinate_type, - promoted_type, ratio_type > sinfo; @@ -300,12 +361,13 @@ private: typename RatioType, typename Segment1, typename Segment2, - typename RobustPoint + typename RobustPoint1, + typename RobustPoint2 > static inline return_type relate_collinear(Segment1 const& a, Segment2 const& b, - RobustPoint const& robust_a1, RobustPoint const& robust_a2, - RobustPoint const& robust_b1, RobustPoint const& robust_b2, + RobustPoint1 const& robust_a1, RobustPoint1 const& robust_a2, + RobustPoint2 const& robust_b1, RobustPoint2 const& robust_b2, bool a_is_point, bool b_is_point) { if (a_is_point) @@ -335,12 +397,13 @@ private: typename RatioType, typename Segment1, typename Segment2, - typename RobustType + typename RobustType1, + typename RobustType2 > static inline return_type relate_collinear(Segment1 const& a , Segment2 const& b - , RobustType oa_1, RobustType oa_2 - , RobustType ob_1, RobustType ob_2 + , RobustType1 oa_1, RobustType1 oa_2 + , RobustType2 ob_1, RobustType2 ob_2 ) { // Calculate the ratios where a starts in b, b starts in a @@ -373,8 +436,8 @@ private: // b2 is located w.r.t. a at ratio: (5-2)/5=3/5 (on a) // a1 is located w.r.t. b at ratio: (2-8)/-3=6/3 (after b ends) // a2 is located w.r.t. b at ratio: (7-8)/-3=1/3 (on b) - RobustType const length_a = oa_2 - oa_1; // no abs, see above - RobustType const length_b = ob_2 - ob_1; + RobustType1 const length_a = oa_2 - oa_1; // no abs, see above + RobustType2 const length_b = ob_2 - ob_1; RatioType ra_from(oa_1 - ob_1, length_b); RatioType ra_to(oa_2 - ob_1, length_b); @@ -435,12 +498,13 @@ private: < typename RatioType, typename DegenerateSegment, - typename RobustType + typename RobustType1, + typename RobustType2 > static inline return_type relate_one_degenerate( DegenerateSegment const& degenerate_segment - , RobustType d - , RobustType s1, RobustType s2 + , RobustType1 d + , RobustType2 s1, RobustType2 s2 , bool a_degenerate ) { @@ -478,6 +542,20 @@ private: }; +#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS +namespace services +{ + +template <typename Policy, typename CalculationType> +struct default_strategy<cartesian_tag, Policy, CalculationType> +{ + typedef relate_cartesian_segments<Policy, CalculationType> type; +}; + +} // namespace services +#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS + + }} // namespace strategy::intersection }} // namespace boost::geometry diff --git a/boost/geometry/strategies/cartesian/distance_pythagoras.hpp b/boost/geometry/strategies/cartesian/distance_pythagoras.hpp index 665426ecb0..8a8889dc99 100644 --- a/boost/geometry/strategies/cartesian/distance_pythagoras.hpp +++ b/boost/geometry/strategies/cartesian/distance_pythagoras.hpp @@ -91,8 +91,8 @@ public : static inline typename calculation_type<Point1, Point2>::type apply(Point1 const& p1, Point2 const& p2) { - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point1>) ); - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point2>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point2>) ); // Calculate distance using Pythagoras // (Leave comment above for Doxygen) diff --git a/boost/geometry/strategies/cartesian/distance_pythagoras_box_box.hpp b/boost/geometry/strategies/cartesian/distance_pythagoras_box_box.hpp index 8a4234282e..4c1b6539be 100644 --- a/boost/geometry/strategies/cartesian/distance_pythagoras_box_box.hpp +++ b/boost/geometry/strategies/cartesian/distance_pythagoras_box_box.hpp @@ -115,9 +115,9 @@ public : apply(Box1 const& box1, Box2 const& box2) { BOOST_CONCEPT_ASSERT - ( (concept::ConstPoint<typename point_type<Box1>::type>) ); + ( (concepts::ConstPoint<typename point_type<Box1>::type>) ); BOOST_CONCEPT_ASSERT - ( (concept::ConstPoint<typename point_type<Box2>::type>) ); + ( (concepts::ConstPoint<typename point_type<Box2>::type>) ); // Calculate distance using Pythagoras // (Leave comment above for Doxygen) diff --git a/boost/geometry/strategies/cartesian/distance_pythagoras_point_box.hpp b/boost/geometry/strategies/cartesian/distance_pythagoras_point_box.hpp index 0ce1d422ee..8423d16a63 100644 --- a/boost/geometry/strategies/cartesian/distance_pythagoras_point_box.hpp +++ b/boost/geometry/strategies/cartesian/distance_pythagoras_point_box.hpp @@ -109,9 +109,9 @@ public : static inline typename calculation_type<Point, Box>::type apply(Point const& point, Box const& box) { - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point>) ); BOOST_CONCEPT_ASSERT - ( (concept::ConstPoint<typename point_type<Box>::type>) ); + ( (concepts::ConstPoint<typename point_type<Box>::type>) ); // Calculate distance using Pythagoras // (Leave comment above for Doxygen) diff --git a/boost/geometry/strategies/concepts/area_concept.hpp b/boost/geometry/strategies/concepts/area_concept.hpp index 75821b52a1..4eec6d1fc3 100644 --- a/boost/geometry/strategies/concepts/area_concept.hpp +++ b/boost/geometry/strategies/concepts/area_concept.hpp @@ -18,7 +18,7 @@ #include <boost/concept_check.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -69,7 +69,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_AREA_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/centroid_concept.hpp b/boost/geometry/strategies/concepts/centroid_concept.hpp index f493ef6810..0bbe94ba77 100644 --- a/boost/geometry/strategies/concepts/centroid_concept.hpp +++ b/boost/geometry/strategies/concepts/centroid_concept.hpp @@ -19,7 +19,7 @@ #include <boost/concept_check.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -72,7 +72,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_CENTROID_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/convex_hull_concept.hpp b/boost/geometry/strategies/concepts/convex_hull_concept.hpp index d6e42e95a3..d4295ce47b 100644 --- a/boost/geometry/strategies/concepts/convex_hull_concept.hpp +++ b/boost/geometry/strategies/concepts/convex_hull_concept.hpp @@ -25,7 +25,7 @@ #include <boost/concept_check.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -74,7 +74,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_CONVEX_HULL_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/distance_concept.hpp b/boost/geometry/strategies/concepts/distance_concept.hpp index 6e75fa95a6..0064d438d5 100644 --- a/boost/geometry/strategies/concepts/distance_concept.hpp +++ b/boost/geometry/strategies/concepts/distance_concept.hpp @@ -36,7 +36,7 @@ #include <boost/geometry/strategies/tags.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -206,7 +206,7 @@ public : }; -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_DISTANCE_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/segment_intersect_concept.hpp b/boost/geometry/strategies/concepts/segment_intersect_concept.hpp index 43bcccf374..87d901eb93 100644 --- a/boost/geometry/strategies/concepts/segment_intersect_concept.hpp +++ b/boost/geometry/strategies/concepts/segment_intersect_concept.hpp @@ -20,7 +20,7 @@ #include <boost/concept_check.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -73,6 +73,6 @@ public : -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_SEGMENT_INTERSECT_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/simplify_concept.hpp b/boost/geometry/strategies/concepts/simplify_concept.hpp index d7f596cfe7..06600bafcb 100644 --- a/boost/geometry/strategies/concepts/simplify_concept.hpp +++ b/boost/geometry/strategies/concepts/simplify_concept.hpp @@ -24,7 +24,7 @@ #include <boost/geometry/strategies/concepts/distance_concept.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -63,7 +63,7 @@ private : BOOST_CONCEPT_ASSERT ( - (concept::PointSegmentDistanceStrategy<ds_type, Point, Point>) + (concepts::PointSegmentDistanceStrategy<ds_type, Point, Point>) ); Strategy *str = 0; @@ -91,6 +91,6 @@ public : -}}} // namespace boost::geometry::concept +}}} // namespace boost::geometry::concepts #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_SIMPLIFY_CONCEPT_HPP diff --git a/boost/geometry/strategies/concepts/within_concept.hpp b/boost/geometry/strategies/concepts/within_concept.hpp index 8786403712..ab712ccd5e 100644 --- a/boost/geometry/strategies/concepts/within_concept.hpp +++ b/boost/geometry/strategies/concepts/within_concept.hpp @@ -22,7 +22,7 @@ #include <boost/geometry/util/parameter_type_of.hpp> -namespace boost { namespace geometry { namespace concept +namespace boost { namespace geometry { namespace concepts { @@ -55,12 +55,12 @@ class WithinStrategyPolygonal // CHECK: apply-arguments should both fulfill point concept BOOST_CONCEPT_ASSERT ( - (concept::ConstPoint<point_type>) + (concepts::ConstPoint<point_type>) ); BOOST_CONCEPT_ASSERT ( - (concept::ConstPoint<segment_point_type>) + (concepts::ConstPoint<segment_point_type>) ); // CHECK: return types (result: int, apply: bool) @@ -130,12 +130,12 @@ class WithinStrategyPointBox // CHECK: apply-arguments should fulfill point/box concept BOOST_CONCEPT_ASSERT ( - (concept::ConstPoint<point_type>) + (concepts::ConstPoint<point_type>) ); BOOST_CONCEPT_ASSERT ( - (concept::ConstBox<box_type>) + (concepts::ConstBox<box_type>) ); // CHECK: return types (apply: bool) @@ -194,12 +194,12 @@ class WithinStrategyBoxBox // CHECK: apply-arguments should both fulfill box concept BOOST_CONCEPT_ASSERT ( - (concept::ConstBox<box_type1>) + (concepts::ConstBox<box_type1>) ); BOOST_CONCEPT_ASSERT ( - (concept::ConstBox<box_type2>) + (concepts::ConstBox<box_type2>) ); // CHECK: return types (apply: bool) @@ -236,7 +236,7 @@ public : #endif }; -// So now: boost::geometry::concept::within +// So now: boost::geometry::concepts::within namespace within { @@ -285,7 +285,7 @@ inline void check() } -}}}} // namespace boost::geometry::concept::within +}}}} // namespace boost::geometry::concepts::within #endif // BOOST_GEOMETRY_STRATEGIES_CONCEPTS_WITHIN_CONCEPT_HPP diff --git a/boost/geometry/strategies/intersection.hpp b/boost/geometry/strategies/intersection.hpp index ef1b676fda..f51c5cb206 100644 --- a/boost/geometry/strategies/intersection.hpp +++ b/boost/geometry/strategies/intersection.hpp @@ -1,92 +1,52 @@ -// Boost.Geometry (aka GGL, Generic Geometry Library) +// Boost.Geometry -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2016, Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -#ifndef BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP -#define BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP +#ifndef BOOST_GEOMETRY_STRATEGIES_SEGMENT_INTERSECTION_HPP +#define BOOST_GEOMETRY_STRATEGIES_SEGMENT_INTERSECTION_HPP -#include <boost/geometry/core/point_type.hpp> -#include <boost/geometry/geometries/segment.hpp> -#include <boost/geometry/policies/relate/intersection_points.hpp> -#include <boost/geometry/policies/relate/direction.hpp> -#include <boost/geometry/policies/relate/tupled.hpp> +#include <boost/geometry/strategies/tags.hpp> -#include <boost/geometry/strategies/side.hpp> -#include <boost/geometry/strategies/intersection_result.hpp> -#include <boost/geometry/strategies/cartesian/cart_intersect.hpp> -#include <boost/geometry/policies/robustness/segment_ratio_type.hpp> +#include <boost/mpl/assert.hpp> namespace boost { namespace geometry { +namespace strategy { namespace intersection +{ + +namespace services +{ /*! -\brief "compound strategy", containing a segment-intersection-strategy - and a side-strategy - */ -template -< - typename Tag, - typename Geometry1, - typename Geometry2, - typename IntersectionPoint, - typename RobustPolicy, - typename CalculationType = void -> -struct strategy_intersection +\brief Traits class binding a segments intersection strategy to a coordinate system +\ingroup util +\tparam CSTag tag of coordinate system of point-type +\tparam Policy intersection policy +\tparam CalculationType \tparam_calculation +*/ +template <typename CSTag, typename Policy, typename CalculationType = void> +struct default_strategy { -private : - // for development BOOST_STATIC_ASSERT((! boost::is_same<RobustPolicy, void>::type::value)); - - typedef typename geometry::point_type<Geometry1>::type point1_type; - typedef typename geometry::point_type<Geometry2>::type point2_type; - typedef typename model::referring_segment<point1_type const> segment1_type; - typedef typename model::referring_segment<point2_type const> segment2_type; - - typedef segment_intersection_points - < - IntersectionPoint, - typename geometry::segment_ratio_type - < - IntersectionPoint, RobustPolicy - >::type - > ip_type; - -public: - typedef strategy::intersection::relate_cartesian_segments - < - policies::relate::segments_tupled - < - policies::relate::segments_intersection_points - < - ip_type - > , - policies::relate::segments_direction - >, - CalculationType - > segment_intersection_strategy_type; - - typedef typename strategy::side::services::default_strategy - < - Tag, - CalculationType - >::type side_strategy_type; - - typedef RobustPolicy rescale_policy_type; + BOOST_MPL_ASSERT_MSG + ( + false, NOT_IMPLEMENTED_FOR_THIS_TYPE + , (types<CSTag>) + ); }; -// Version for box_box intersection or other detail calls not needing a strategy -struct strategy_intersection_empty {}; +} // namespace services +}} // namespace strategy::intersection }} // namespace boost::geometry - -#endif // BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP +#endif // BOOST_GEOMETRY_STRATEGIES_SEGMENT_INTERSECTION_HPP diff --git a/boost/geometry/strategies/intersection_result.hpp b/boost/geometry/strategies/intersection_result.hpp index 9c6d17ec5e..db2a46e6a3 100644 --- a/boost/geometry/strategies/intersection_result.hpp +++ b/boost/geometry/strategies/intersection_result.hpp @@ -2,9 +2,8 @@ // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2015. -// Modifications copyright (c) 2015 Oracle and/or its affiliates. - +// This file was modified by Oracle on 2015, 2016. +// Modifications copyright (c) 2015-2016 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, @@ -73,19 +72,6 @@ struct segment_intersection_points {} }; -// All assigned in cart_intersect, passed to intersection_points -template <typename CoordinateType, typename PromotedType, typename SegmentRatio> -struct segment_intersection_info -{ - typedef PromotedType promoted_type; - - CoordinateType dx_a, dy_a; - CoordinateType dx_b, dy_b; - SegmentRatio robust_ra; - SegmentRatio robust_rb; -}; - - }} // namespace boost::geometry diff --git a/boost/geometry/strategies/intersection_strategies.hpp b/boost/geometry/strategies/intersection_strategies.hpp new file mode 100644 index 0000000000..0452c4692c --- /dev/null +++ b/boost/geometry/strategies/intersection_strategies.hpp @@ -0,0 +1,100 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. + +// This file was modified by Oracle on 2016. +// Modifications copyright (c) 2016, Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP +#define BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP + + +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/geometries/segment.hpp> + +#include <boost/geometry/policies/relate/intersection_points.hpp> +#include <boost/geometry/policies/relate/direction.hpp> +#include <boost/geometry/policies/relate/tupled.hpp> + +#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/side.hpp> +#include <boost/geometry/strategies/intersection_result.hpp> + +#include <boost/geometry/strategies/cartesian/cart_intersect.hpp> +#include <boost/geometry/strategies/cartesian/side_by_triangle.hpp> +#include <boost/geometry/strategies/spherical/intersection.hpp> +#include <boost/geometry/strategies/spherical/ssf.hpp> + +#include <boost/geometry/policies/robustness/segment_ratio_type.hpp> + + +namespace boost { namespace geometry +{ + + +/*! +\brief "compound strategy", containing a segment-intersection-strategy + and a side-strategy + */ +template +< + typename Tag, + typename Geometry1, + typename Geometry2, + typename IntersectionPoint, + typename RobustPolicy, + typename CalculationType = void +> +struct intersection_strategies +{ +private : + // for development BOOST_STATIC_ASSERT((! boost::is_same<RobustPolicy, void>::type::value)); + + typedef typename geometry::point_type<Geometry1>::type point1_type; + typedef typename geometry::point_type<Geometry2>::type point2_type; + typedef typename model::referring_segment<point1_type const> segment1_type; + typedef typename model::referring_segment<point2_type const> segment2_type; + + typedef segment_intersection_points + < + IntersectionPoint, + typename geometry::segment_ratio_type + < + IntersectionPoint, RobustPolicy + >::type + > ip_type; + +public: + typedef typename strategy::intersection::services::default_strategy + < + Tag, + policies::relate::segments_tupled + < + policies::relate::segments_intersection_points + < + ip_type + > , + policies::relate::segments_direction + >, + CalculationType + >::type segment_intersection_strategy_type; + + typedef typename strategy::side::services::default_strategy + < + Tag, + CalculationType + >::type side_strategy_type; + + typedef RobustPolicy rescale_policy_type; +}; + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_STRATEGIES_INTERSECTION_HPP diff --git a/boost/geometry/strategies/spherical/distance_cross_track.hpp b/boost/geometry/strategies/spherical/distance_cross_track.hpp index 31b59e77ff..7daafa4a16 100644 --- a/boost/geometry/strategies/spherical/distance_cross_track.hpp +++ b/boost/geometry/strategies/spherical/distance_cross_track.hpp @@ -367,7 +367,7 @@ public : #if !defined(BOOST_MSVC) BOOST_CONCEPT_ASSERT ( - (concept::PointDistanceStrategy<Strategy, Point, PointOfSegment>) + (concepts::PointDistanceStrategy<Strategy, Point, PointOfSegment>) ); #endif @@ -521,7 +521,7 @@ public : #if !defined(BOOST_MSVC) BOOST_CONCEPT_ASSERT ( - (concept::PointDistanceStrategy<Strategy, Point, PointOfSegment>) + (concepts::PointDistanceStrategy<Strategy, Point, PointOfSegment>) ); #endif typedef typename return_type<Point, PointOfSegment>::type return_type; diff --git a/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp b/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp index 59be3645f5..ee805c36d1 100644 --- a/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp +++ b/boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp @@ -96,7 +96,7 @@ public: #if !defined(BOOST_MSVC) BOOST_CONCEPT_ASSERT ( - (concept::PointSegmentDistanceStrategy + (concepts::PointSegmentDistanceStrategy < Strategy, Point, typename point_type<Box>::type >) diff --git a/boost/geometry/strategies/spherical/intersection.hpp b/boost/geometry/strategies/spherical/intersection.hpp new file mode 100644 index 0000000000..4ffc853aad --- /dev/null +++ b/boost/geometry/strategies/spherical/intersection.hpp @@ -0,0 +1,701 @@ +// Boost.Geometry + +// Copyright (c) 2016, Oracle and/or its affiliates. +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_STRATEGIES_SPHERICAL_INTERSECTION_HPP +#define BOOST_GEOMETRY_STRATEGIES_SPHERICAL_INTERSECTION_HPP + +#include <algorithm> + +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/radian_access.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/algorithms/detail/assign_values.hpp> +#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> +#include <boost/geometry/algorithms/detail/equals/point_point.hpp> +#include <boost/geometry/algorithms/detail/recalculate.hpp> + +#include <boost/geometry/arithmetic/arithmetic.hpp> +#include <boost/geometry/arithmetic/cross_product.hpp> +#include <boost/geometry/arithmetic/dot_product.hpp> +#include <boost/geometry/formulas/spherical.hpp> + +#include <boost/geometry/geometries/concepts/point_concept.hpp> +#include <boost/geometry/geometries/concepts/segment_concept.hpp> + +#include <boost/geometry/policies/robustness/segment_ratio.hpp> + +#include <boost/geometry/strategies/side_info.hpp> +#include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_result.hpp> + +#include <boost/geometry/util/math.hpp> +#include <boost/geometry/util/select_calculation_type.hpp> + + +namespace boost { namespace geometry +{ + +namespace strategy { namespace intersection +{ + +// NOTE: +// The coordinates of crossing IP may be calculated with small precision in some cases. +// For double, near the equator noticed error ~1e-9 so far greater than +// machine epsilon which is ~1e-16. This error is ~0.04m. +// E.g. consider two cases, one near the origin and the second one rotated by 90 deg around Z or SN axis. +// After the conversion from spherical degrees to cartesian 3d the following coordinates +// are calculated: +// for sph (-1 -1, 1 1) deg cart3d ys are -0.017449748351250485 and 0.017449748351250485 +// for sph (89 -1, 91 1) deg cart3d xs are 0.017449748351250571 and -0.017449748351250450 +// During the conversion degrees must first be converted to radians and then radians +// are passed into trigonometric functions. The error may have several causes: +// 1. Radians cannot represent exactly the same angles as degrees. +// 2. Different longitudes are passed into sin() for x, corresponding to cos() for y, +// and for different angle the error of the result may be different. +// 3. These non-corresponding cartesian coordinates are used in calculation, +// e.g. multiplied several times in cross and dot products. +// If it was a problem this strategy could e.g. "normalize" longitudes before the conversion using the source units +// by rotating the globe around Z axis, so moving longitudes always the same way towards the origin, +// assuming this could help which is not clear. +// For now, intersection points near the endpoints are checked explicitly if needed (if the IP is near the endpoint) +// to generate precise result for them. Only the crossing (i) case may suffer from lower precision. + +template <typename Policy, typename CalculationType = void> +struct relate_spherical_segments +{ + typedef typename Policy::return_type return_type; + + enum intersection_point_flag { ipi_inters = 0, ipi_at_a1, ipi_at_a2, ipi_at_b1, ipi_at_b2 }; + + template <typename CoordinateType, typename SegmentRatio, typename Vector3d> + struct segment_intersection_info + { + typedef typename select_most_precise + < + CoordinateType, double + >::type promoted_type; + + promoted_type comparable_length_a() const + { + return robust_ra.denominator(); + } + + promoted_type comparable_length_b() const + { + return robust_rb.denominator(); + } + + template <typename Point, typename Segment1, typename Segment2> + void assign_a(Point& point, Segment1 const& a, Segment2 const& b) const + { + assign(point, a, b); + } + template <typename Point, typename Segment1, typename Segment2> + void assign_b(Point& point, Segment1 const& a, Segment2 const& b) const + { + assign(point, a, b); + } + + template <typename Point, typename Segment1, typename Segment2> + void assign(Point& point, Segment1 const& a, Segment2 const& b) const + { + if (ip_flag == ipi_inters) + { + // TODO: assign the rest of coordinates + point = formula::cart3d_to_sph<Point>(intersection_point); + } + else if (ip_flag == ipi_at_a1) + { + detail::assign_point_from_index<0>(a, point); + } + else if (ip_flag == ipi_at_a2) + { + detail::assign_point_from_index<1>(a, point); + } + else if (ip_flag == ipi_at_b1) + { + detail::assign_point_from_index<0>(b, point); + } + else // ip_flag == ipi_at_b2 + { + detail::assign_point_from_index<1>(b, point); + } + } + + Vector3d intersection_point; + SegmentRatio robust_ra; + SegmentRatio robust_rb; + intersection_point_flag ip_flag; + }; + + // Relate segments a and b + template <typename Segment1, typename Segment2, typename RobustPolicy> + static inline return_type apply(Segment1 const& a, Segment2 const& b, + RobustPolicy const& robust_policy) + { + typedef typename point_type<Segment1>::type point1_t; + typedef typename point_type<Segment2>::type point2_t; + point1_t a1, a2; + point2_t b1, b2; + + // TODO: use indexed_point_view if possible? + detail::assign_point_from_index<0>(a, a1); + detail::assign_point_from_index<1>(a, a2); + detail::assign_point_from_index<0>(b, b1); + detail::assign_point_from_index<1>(b, b2); + + return apply(a, b, robust_policy, a1, a2, b1, b2); + } + + // Relate segments a and b + template <typename Segment1, typename Segment2, typename RobustPolicy, typename Point1, typename Point2> + static inline return_type apply(Segment1 const& a, Segment2 const& b, + RobustPolicy const&, + Point1 const& a1, Point1 const& a2, Point2 const& b1, Point2 const& b2) + { + BOOST_CONCEPT_ASSERT( (concepts::ConstSegment<Segment1>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstSegment<Segment2>) ); + + // TODO: check only 2 first coordinates here? + using geometry::detail::equals::equals_point_point; + bool a_is_point = equals_point_point(a1, a2); + bool b_is_point = equals_point_point(b1, b2); + + if(a_is_point && b_is_point) + { + return equals_point_point(a1, b2) + ? Policy::degenerate(a, true) + : Policy::disjoint() + ; + } + + typedef typename select_calculation_type + <Segment1, Segment2, CalculationType>::type calc_t; + + calc_t const c0 = 0; + calc_t const c1 = 1; + + typedef model::point<calc_t, 3, cs::cartesian> vec3d_t; + + using namespace formula; + vec3d_t const a1v = sph_to_cart3d<vec3d_t>(a1); + vec3d_t const a2v = sph_to_cart3d<vec3d_t>(a2); + vec3d_t const b1v = sph_to_cart3d<vec3d_t>(b1); + vec3d_t const b2v = sph_to_cart3d<vec3d_t>(b2); + + vec3d_t norm1 = cross_product(a1v, a2v); + vec3d_t norm2 = cross_product(b1v, b2v); + + side_info sides; + // not normalized normals, the same as in SSF + sides.set<0>(sph_side_value(norm2, a1v), sph_side_value(norm2, a2v)); + if (sides.same<0>()) + { + // Both points are at same side of other segment, we can leave + return Policy::disjoint(); + } + // not normalized normals, the same as in SSF + sides.set<1>(sph_side_value(norm1, b1v), sph_side_value(norm1, b2v)); + if (sides.same<1>()) + { + // Both points are at same side of other segment, we can leave + return Policy::disjoint(); + } + + // NOTE: at this point the segments may still be disjoint + + bool collinear = sides.collinear(); + + calc_t const len1 = math::sqrt(dot_product(norm1, norm1)); + calc_t const len2 = math::sqrt(dot_product(norm2, norm2)); + + // point or opposite sides of a sphere, assume point + if (math::equals(len1, c0)) + { + a_is_point = true; + if (sides.get<0, 0>() == 0 || sides.get<0, 1>() == 0) + { + sides.set<0>(0, 0); + } + } + else + { + // normalize + divide_value(norm1, len1); + } + + if (math::equals(len2, c0)) + { + b_is_point = true; + if (sides.get<1, 0>() == 0 || sides.get<1, 1>() == 0) + { + sides.set<1>(0, 0); + } + } + else + { + // normalize + divide_value(norm2, len2); + } + + // check both degenerated once more + if (a_is_point && b_is_point) + { + return equals_point_point(a1, b2) + ? Policy::degenerate(a, true) + : Policy::disjoint() + ; + } + + // NOTE: at this point one of the segments may be degenerated + // and the segments may still be disjoint + + calc_t dot_n1n2 = dot_product(norm1, norm2); + + // NOTE: this is technically not needed since theoretically above sides + // are calculated, but just in case check the normals. + // Have in mind that SSF side strategy doesn't check this. + // collinear if normals are equal or opposite: cos(a) in {-1, 1} + if (!collinear && math::equals(math::abs(dot_n1n2), c1)) + { + collinear = true; + sides.set<0>(0, 0); + sides.set<1>(0, 0); + } + + if (collinear) + { + if (a_is_point) + { + return collinear_one_degenerted<calc_t>(a, true, b1, b2, a1, a2, b1v, b2v, norm2, a1v); + } + else if (b_is_point) + { + // b2 used to be consistent with (degenerated) checks above (is it needed?) + return collinear_one_degenerted<calc_t>(b, false, a1, a2, b1, b2, a1v, a2v, norm1, b1v); + } + else + { + calc_t dist_a1_a2, dist_a1_b1, dist_a1_b2; + calc_t dist_b1_b2, dist_b1_a1, dist_b1_a2; + // use shorter segment + if (len1 <= len2) + { + calculate_collinear_data(a1, a2, b1, b2, a1v, a2v, norm1, b1v, dist_a1_a2, dist_a1_b1); + calculate_collinear_data(a1, a2, b1, b2, a1v, a2v, norm1, b2v, dist_a1_a2, dist_a1_b2); + dist_b1_b2 = dist_a1_b2 - dist_a1_b1; + dist_b1_a1 = -dist_a1_b1; + dist_b1_a2 = dist_a1_a2 - dist_a1_b1; + } + else + { + calculate_collinear_data(b1, b2, a1, a2, b1v, b2v, norm2, a1v, dist_b1_b2, dist_b1_a1); + calculate_collinear_data(b1, b2, a1, a2, b1v, b2v, norm2, a2v, dist_b1_b2, dist_b1_a2); + dist_a1_a2 = dist_b1_a2 - dist_b1_a1; + dist_a1_b1 = -dist_b1_a1; + dist_a1_b2 = dist_b1_b2 - dist_b1_a1; + } + + segment_ratio<calc_t> ra_from(dist_b1_a1, dist_b1_b2); + segment_ratio<calc_t> ra_to(dist_b1_a2, dist_b1_b2); + segment_ratio<calc_t> rb_from(dist_a1_b1, dist_a1_a2); + segment_ratio<calc_t> rb_to(dist_a1_b2, dist_a1_a2); + + // NOTE: this is probably not needed + int const a1_wrt_b = position_value(c0, dist_a1_b1, dist_a1_b2); + int const a2_wrt_b = position_value(dist_a1_a2, dist_a1_b1, dist_a1_b2); + int const b1_wrt_a = position_value(c0, dist_b1_a1, dist_b1_a2); + int const b2_wrt_a = position_value(dist_b1_b2, dist_b1_a1, dist_b1_a2); + + if (a1_wrt_b == 1) + { + ra_from.assign(0, dist_b1_b2); + rb_from.assign(0, dist_a1_a2); + } + else if (a1_wrt_b == 3) + { + ra_from.assign(dist_b1_b2, dist_b1_b2); + rb_to.assign(0, dist_a1_a2); + } + + if (a2_wrt_b == 1) + { + ra_to.assign(0, dist_b1_b2); + rb_from.assign(dist_a1_a2, dist_a1_a2); + } + else if (a2_wrt_b == 3) + { + ra_to.assign(dist_b1_b2, dist_b1_b2); + rb_to.assign(dist_a1_a2, dist_a1_a2); + } + + if ((a1_wrt_b < 1 && a2_wrt_b < 1) || (a1_wrt_b > 3 && a2_wrt_b > 3)) + { + return Policy::disjoint(); + } + + bool const opposite = dot_n1n2 < c0; + + return Policy::segments_collinear(a, b, opposite, + a1_wrt_b, a2_wrt_b, b1_wrt_a, b2_wrt_a, + ra_from, ra_to, rb_from, rb_to); + } + } + else // crossing + { + if (a_is_point || b_is_point) + { + return Policy::disjoint(); + } + + vec3d_t i1; + intersection_point_flag ip_flag; + calc_t dist_a1_a2, dist_a1_i1, dist_b1_b2, dist_b1_i1; + if (calculate_ip_data(a1, a2, b1, b2, a1v, a2v, b1v, b2v, norm1, norm2, sides, + i1, dist_a1_a2, dist_a1_i1, dist_b1_b2, dist_b1_i1, ip_flag)) + { + // intersects + segment_intersection_info + < + calc_t, + segment_ratio<calc_t>, + vec3d_t + > sinfo; + + sinfo.robust_ra.assign(dist_a1_i1, dist_a1_a2); + sinfo.robust_rb.assign(dist_b1_i1, dist_b1_b2); + sinfo.intersection_point = i1; + sinfo.ip_flag = ip_flag; + + return Policy::segments_crosses(sides, sinfo, a, b); + } + else + { + return Policy::disjoint(); + } + } + } + +private: + template <typename CalcT, typename Segment, typename Point1, typename Point2, typename Vec3d> + static inline return_type collinear_one_degenerted(Segment const& segment, bool degenerated_a, + Point1 const& a1, Point1 const& a2, + Point2 const& b1, Point2 const& b2, + Vec3d const& v1, Vec3d const& v2, Vec3d const& norm, + Vec3d const& vother) + { + CalcT dist_1_2, dist_1_o; + return ! calculate_collinear_data(a1, a2, b1, b2, v1, v2, norm, vother, dist_1_2, dist_1_o) + ? Policy::disjoint() + : Policy::one_degenerate(segment, segment_ratio<CalcT>(dist_1_o, dist_1_2), degenerated_a); + } + + template <typename Point1, typename Point2, typename Vec3d, typename CalcT> + static inline bool calculate_collinear_data(Point1 const& a1, Point1 const& a2, + Point2 const& b1, Point2 const& b2, + Vec3d const& a1v, // in + Vec3d const& a2v, // in + Vec3d const& norm1, // in + Vec3d const& b1v_or_b2v, // in + CalcT& dist_a1_a2, CalcT& dist_a1_i1) // out + { + // calculate dist_a1_a2 and dist_a1_i1 + calculate_dists(a1v, a2v, norm1, b1v_or_b2v, dist_a1_a2, dist_a1_i1); + + // if i1 is close to a1 and b1 or b2 is equal to a1 + if (is_endpoint_equal(dist_a1_i1, a1, b1, b2)) + { + dist_a1_i1 = 0; + return true; + } + // or i1 is close to a2 and b1 or b2 is equal to a2 + else if (is_endpoint_equal(dist_a1_a2 - dist_a1_i1, a2, b1, b2)) + { + dist_a1_i1 = dist_a1_a2; + return true; + } + + // or i1 is on b + return segment_ratio<CalcT>(dist_a1_i1, dist_a1_a2).on_segment(); + } + + template <typename Point1, typename Point2, typename Vec3d, typename CalcT> + static inline bool calculate_ip_data(Point1 const& a1, Point1 const& a2, // in + Point2 const& b1, Point2 const& b2, // in + Vec3d const& a1v, Vec3d const& a2v, // in + Vec3d const& b1v, Vec3d const& b2v, // in + Vec3d const& norm1, Vec3d const& norm2, // in + side_info const& sides, // in + Vec3d & i1, // in-out + CalcT& dist_a1_a2, CalcT& dist_a1_i1, // out + CalcT& dist_b1_b2, CalcT& dist_b1_i1, // out + intersection_point_flag& ip_flag) // out + { + // great circles intersections + i1 = cross_product(norm1, norm2); + // NOTE: the length should be greater than 0 at this point + // if the normals were not normalized and their dot product + // not checked before this function is called the length + // should be checked here (math::equals(len, c0)) + CalcT const len = math::sqrt(dot_product(i1, i1)); + divide_value(i1, len); // normalize i1 + + calculate_dists(a1v, a2v, norm1, i1, dist_a1_a2, dist_a1_i1); + + // choose the opposite side of the globe if the distance is shorter + { + CalcT const d = abs_distance(dist_a1_a2, dist_a1_i1); + if (d > CalcT(0)) + { + CalcT const dist_a1_i2 = dist_of_i2(dist_a1_i1); + CalcT const d2 = abs_distance(dist_a1_a2, dist_a1_i2); + if (d2 < d) + { + dist_a1_i1 = dist_a1_i2; + multiply_value(i1, CalcT(-1)); // the opposite intersection + } + } + } + + bool is_on_a = false, is_near_a1 = false, is_near_a2 = false; + if (! is_potentially_crossing(dist_a1_a2, dist_a1_i1, is_on_a, is_near_a1, is_near_a2)) + { + return false; + } + + calculate_dists(b1v, b2v, norm2, i1, dist_b1_b2, dist_b1_i1); + + bool is_on_b = false, is_near_b1 = false, is_near_b2 = false; + if (! is_potentially_crossing(dist_b1_b2, dist_b1_i1, is_on_b, is_near_b1, is_near_b2)) + { + return false; + } + + // reassign the IP if some endpoints overlap + using geometry::detail::equals::equals_point_point; + if (is_near_a1) + { + if (is_near_b1 && equals_point_point(a1, b1)) + { + dist_a1_i1 = 0; + dist_b1_i1 = 0; + //i1 = a1v; + ip_flag = ipi_at_a1; + return true; + } + + if (is_near_b2 && equals_point_point(a1, b2)) + { + dist_a1_i1 = 0; + dist_b1_i1 = dist_b1_b2; + //i1 = a1v; + ip_flag = ipi_at_a1; + return true; + } + } + + if (is_near_a2) + { + if (is_near_b1 && equals_point_point(a2, b1)) + { + dist_a1_i1 = dist_a1_a2; + dist_b1_i1 = 0; + //i1 = a2v; + ip_flag = ipi_at_a2; + return true; + } + + if (is_near_b2 && equals_point_point(a2, b2)) + { + dist_a1_i1 = dist_a1_a2; + dist_b1_i1 = dist_b1_b2; + //i1 = a2v; + ip_flag = ipi_at_a2; + return true; + } + } + + // at this point we know that the endpoints doesn't overlap + // reassign IP and distance if the IP is on a segment and one of + // the endpoints of the other segment lies on the former segment + if (is_on_a) + { + if (is_near_b1 && sides.template get<1, 0>() == 0) // b1 wrt a + { + dist_b1_i1 = 0; + //i1 = b1v; + ip_flag = ipi_at_b1; + return true; + } + + if (is_near_b2 && sides.template get<1, 1>() == 0) // b2 wrt a + { + dist_b1_i1 = dist_b1_b2; + //i1 = b2v; + ip_flag = ipi_at_b2; + return true; + } + } + + if (is_on_b) + { + if (is_near_a1 && sides.template get<0, 0>() == 0) // a1 wrt b + { + dist_a1_i1 = 0; + //i1 = a1v; + ip_flag = ipi_at_a1; + return true; + } + + if (is_near_a2 && sides.template get<0, 1>() == 0) // a2 wrt b + { + dist_a1_i1 = dist_a1_a2; + //i1 = a2v; + ip_flag = ipi_at_a2; + return true; + } + } + + ip_flag = ipi_inters; + + return is_on_a && is_on_b; + } + + template <typename Vec3d, typename CalcT> + static inline void calculate_dists(Vec3d const& a1v, // in + Vec3d const& a2v, // in + Vec3d const& norm1, // in + Vec3d const& i1, // in + CalcT& dist_a1_a2, CalcT& dist_a1_i1) // out + { + CalcT const c0 = 0; + CalcT const c1 = 1; + CalcT const c2 = 2; + CalcT const c4 = 4; + + CalcT cos_a1_a2 = dot_product(a1v, a2v); + dist_a1_a2 = -cos_a1_a2 + c1; // [1, -1] -> [0, 2] representing [0, pi] + + CalcT cos_a1_i1 = dot_product(a1v, i1); + dist_a1_i1 = -cos_a1_i1 + c1; // [0, 2] representing [0, pi] + if (dot_product(norm1, cross_product(a1v, i1)) < c0) // left or right of a1 on a + { + dist_a1_i1 = -dist_a1_i1; // [0, 2] -> [0, -2] representing [0, -pi] + } + if (dist_a1_i1 <= -c2) // <= -pi + { + dist_a1_i1 += c4; // += 2pi + } + } + + // the dist of the ip on the other side of the sphere + template <typename CalcT> + static inline CalcT dist_of_i2(CalcT const& dist_a1_i1) + { + CalcT const c2 = 2; + CalcT const c4 = 4; + + CalcT dist_a1_i2 = dist_a1_i1 - c2; // dist_a1_i2 = dist_a1_i1 - pi; + if (dist_a1_i2 <= -c2) // <= -pi + { + dist_a1_i2 += c4; // += 2pi; + } + return dist_a1_i2; + } + + template <typename CalcT> + static inline CalcT abs_distance(CalcT const& dist_a1_a2, CalcT const& dist_a1_i1) + { + if (dist_a1_i1 < CalcT(0)) + return -dist_a1_i1; + else if (dist_a1_i1 > dist_a1_a2) + return dist_a1_i1 - dist_a1_a2; + else + return CalcT(0); + } + + template <typename CalcT> + static inline bool is_potentially_crossing(CalcT const& dist_a1_a2, CalcT const& dist_a1_i1, // in + bool& is_on_a, bool& is_near_a1, bool& is_near_a2) // out + { + is_on_a = segment_ratio<CalcT>(dist_a1_i1, dist_a1_a2).on_segment(); + is_near_a1 = is_near(dist_a1_i1); + is_near_a2 = is_near(dist_a1_a2 - dist_a1_i1); + return is_on_a || is_near_a1 || is_near_a2; + } + + template <typename CalcT, typename P1, typename P2> + static inline bool is_endpoint_equal(CalcT const& dist, + P1 const& ai, P2 const& b1, P2 const& b2) + { + using geometry::detail::equals::equals_point_point; + return is_near(dist) && (equals_point_point(ai, b1) || equals_point_point(ai, b2)); + } + + template <typename CalcT> + static inline bool is_near(CalcT const& dist) + { + CalcT const small_number = CalcT(boost::is_same<CalcT, float>::value ? 0.0001 : 0.00000001); + return math::abs(dist) <= small_number; + } + + template <typename ProjCoord1, typename ProjCoord2> + static inline int position_value(ProjCoord1 const& ca1, + ProjCoord2 const& cb1, + ProjCoord2 const& cb2) + { + // S1x 0 1 2 3 4 + // S2 |----------> + return math::equals(ca1, cb1) ? 1 + : math::equals(ca1, cb2) ? 3 + : cb1 < cb2 ? + ( ca1 < cb1 ? 0 + : ca1 > cb2 ? 4 + : 2 ) + : ( ca1 > cb1 ? 0 + : ca1 < cb2 ? 4 + : 2 ); + } +}; + + +#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS +namespace services +{ + +/*template <typename Policy, typename CalculationType> +struct default_strategy<spherical_polar_tag, Policy, CalculationType> +{ + typedef relate_spherical_segments<Policy, CalculationType> type; +};*/ + +template <typename Policy, typename CalculationType> +struct default_strategy<spherical_equatorial_tag, Policy, CalculationType> +{ + typedef relate_spherical_segments<Policy, CalculationType> type; +}; + +template <typename Policy, typename CalculationType> +struct default_strategy<geographic_tag, Policy, CalculationType> +{ + typedef relate_spherical_segments<Policy, CalculationType> type; +}; + +} // namespace services +#endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS + + +}} // namespace strategy::intersection + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_STRATEGIES_SPHERICAL_INTERSECTION_HPP diff --git a/boost/geometry/strategies/strategies.hpp b/boost/geometry/strategies/strategies.hpp index 28850020af..342485cc4c 100644 --- a/boost/geometry/strategies/strategies.hpp +++ b/boost/geometry/strategies/strategies.hpp @@ -4,8 +4,8 @@ // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. -// This file was modified by Oracle on 2014, 2015. -// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates. +// This file was modified by Oracle on 2014-2016. +// Modifications copyright (c) 2014-2016 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -29,6 +29,7 @@ #include <boost/geometry/strategies/convex_hull.hpp> #include <boost/geometry/strategies/distance.hpp> #include <boost/geometry/strategies/intersection.hpp> +#include <boost/geometry/strategies/intersection_strategies.hpp> // for backward compatibility #include <boost/geometry/strategies/side.hpp> #include <boost/geometry/strategies/transform.hpp> #include <boost/geometry/strategies/within.hpp> @@ -61,6 +62,7 @@ #include <boost/geometry/strategies/spherical/distance_cross_track.hpp> #include <boost/geometry/strategies/spherical/distance_cross_track_point_box.hpp> #include <boost/geometry/strategies/spherical/compare_circular.hpp> +#include <boost/geometry/strategies/spherical/intersection.hpp> #include <boost/geometry/strategies/spherical/ssf.hpp> #include <boost/geometry/strategies/geographic/distance_andoyer.hpp> diff --git a/boost/geometry/util/for_each_coordinate.hpp b/boost/geometry/util/for_each_coordinate.hpp index 7a1f55b00b..fb1e31856a 100644 --- a/boost/geometry/util/for_each_coordinate.hpp +++ b/boost/geometry/util/for_each_coordinate.hpp @@ -66,7 +66,7 @@ struct coordinates_scanner<Point, DimensionCount, DimensionCount, IsConst> template <typename Point, typename Op> inline void for_each_coordinate(Point& point, Op operation) { - BOOST_CONCEPT_ASSERT( (concept::Point<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::Point<Point>) ); typedef typename detail::coordinates_scanner < @@ -79,7 +79,7 @@ inline void for_each_coordinate(Point& point, Op operation) template <typename Point, typename Op> inline Op for_each_coordinate(Point const& point, Op operation) { - BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point>) ); + BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<Point>) ); typedef typename detail::coordinates_scanner < |