diff options
Diffstat (limited to 'boost/geometry/policies')
-rw-r--r-- | boost/geometry/policies/is_valid/default_policy.hpp | 59 | ||||
-rw-r--r-- | boost/geometry/policies/is_valid/failing_reason_policy.hpp | 218 | ||||
-rw-r--r-- | boost/geometry/policies/is_valid/failure_type_policy.hpp | 83 | ||||
-rw-r--r-- | boost/geometry/policies/relate/direction.hpp | 55 | ||||
-rw-r--r-- | boost/geometry/policies/relate/intersection_points.hpp | 38 | ||||
-rw-r--r-- | boost/geometry/policies/relate/tupled.hpp | 17 | ||||
-rw-r--r-- | boost/geometry/policies/robustness/get_rescale_policy.hpp | 74 |
7 files changed, 480 insertions, 64 deletions
diff --git a/boost/geometry/policies/is_valid/default_policy.hpp b/boost/geometry/policies/is_valid/default_policy.hpp new file mode 100644 index 0000000000..c1bd347e11 --- /dev/null +++ b/boost/geometry/policies/is_valid/default_policy.hpp @@ -0,0 +1,59 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_POLICIES_IS_VALID_DEFAULT_POLICY_HPP +#define BOOST_GEOMETRY_POLICIES_IS_VALID_DEFAULT_POLICY_HPP + +#include <boost/geometry/algorithms/validity_failure_type.hpp> + + +namespace boost { namespace geometry +{ + + +template <bool AllowDuplicates = true, bool AllowSpikes = true> +class is_valid_default_policy +{ +protected: + static inline bool is_valid(validity_failure_type failure) + { + return failure == no_failure + || (AllowDuplicates && failure == failure_duplicate_points); + } + + static inline bool is_valid(validity_failure_type failure, bool is_linear) + { + return is_valid(failure) + || (is_linear && AllowSpikes && failure == failure_spikes); + } + +public: + template <validity_failure_type Failure> + static inline bool apply() + { + return is_valid(Failure); + } + + template <validity_failure_type Failure, typename Data> + static inline bool apply(Data const&) + { + return is_valid(Failure); + } + + template <validity_failure_type Failure, typename Data1, typename Data2> + static inline bool apply(Data1 const& data1, Data2 const&) + { + return is_valid(Failure, data1); + } +}; + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_POLICIES_IS_VALID_DEFAULT_POLICY_HPP diff --git a/boost/geometry/policies/is_valid/failing_reason_policy.hpp b/boost/geometry/policies/is_valid/failing_reason_policy.hpp new file mode 100644 index 0000000000..b99803bead --- /dev/null +++ b/boost/geometry/policies/is_valid/failing_reason_policy.hpp @@ -0,0 +1,218 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_POLICIES_IS_VALID_FAILING_REASON_POLICY_HPP +#define BOOST_GEOMETRY_POLICIES_IS_VALID_FAILING_REASON_POLICY_HPP + +#include <sstream> + +#include <boost/geometry/io/dsv/write.hpp> +#include <boost/geometry/util/range.hpp> +#include <boost/geometry/algorithms/validity_failure_type.hpp> +#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> + + +namespace boost { namespace geometry +{ + + +inline char const* validity_failure_type_message(validity_failure_type failure) +{ + switch (failure) + { + case no_failure: + return "Geometry is valid"; + case failure_few_points: + return "Geometry has too few points"; + case failure_wrong_topological_dimension: + return "Geometry has wrong topological dimension"; + case failure_not_closed: + return "Geometry is defined as closed but is open"; + case failure_spikes: + return "Geometry has spikes"; + case failure_self_intersections: + return "Geometry has invalid self-intersections"; + case failure_wrong_orientation: + return "Geometry has wrong orientation"; + case failure_interior_rings_outside: + return "Geometry has interior rings defined outside the outer boundary"; + case failure_nested_interior_rings: + return "Geometry has nested interior rings"; + case failure_disconnected_interior: + return "Geometry has disconnected interior"; + case failure_intersecting_interiors: + return "Multi-polygon has intersecting interiors"; + case failure_duplicate_points: + return "Geometry has duplicate (consecutive) points"; + case failure_wrong_corner_order: + return "Box has corners in wrong order"; + default: // to avoid -Wreturn-type warning + return ""; + } +} + + +template <bool AllowDuplicates = true, bool AllowSpikes = true> +class failing_reason_policy +{ +private: + static inline + validity_failure_type transform_failure_type(validity_failure_type failure) + { + if (AllowDuplicates && failure == failure_duplicate_points) + { + return no_failure; + } + return failure; + } + + static inline + validity_failure_type transform_failure_type(validity_failure_type failure, + bool is_linear) + { + if (is_linear && AllowSpikes && failure == failure_spikes) + { + return no_failure; + } + return transform_failure_type(failure); + } + + inline void set_failure_message(validity_failure_type failure) + { + m_oss.str(""); + m_oss.clear(); + m_oss << validity_failure_type_message(failure); + } + + template + < + validity_failure_type Failure, + typename Data1, + typename Data2 = Data1, + typename Dummy = void + > + struct process_data + { + static inline void apply(std::ostringstream&, Data1 const&) + { + } + + static inline void apply(std::ostringstream&, + Data1 const&, + Data2 const&) + { + } + }; + + template <typename SpikePoint> + struct process_data<failure_spikes, bool, SpikePoint> + { + static inline void apply(std::ostringstream& oss, + bool is_linear, + SpikePoint const& spike_point) + { + if (is_linear && AllowSpikes) + { + return; + } + + oss << ". A spike point was found with apex at " + << geometry::dsv(spike_point); + } + }; + + template <typename Turns> + struct process_data<failure_self_intersections, Turns> + { + static inline + void apply_to_segment_identifier(std::ostringstream& oss, + segment_identifier seg_id) + { + oss << "{" << seg_id.source_index + << ", " << seg_id.multi_index + << ", " << seg_id.ring_index + << ", " << seg_id.segment_index + << "}"; + } + + static inline void apply(std::ostringstream& oss, + Turns const& turns) + { + typedef typename boost::range_value<Turns>::type turn_type; + turn_type const& turn = range::front(turns); + oss << ". A self-intersection point was found at " + << geometry::dsv(turn.point); + + oss << "; method: " << method_char(turn.method) + << "; operations: " + << operation_char(turn.operations[0].operation) + << "/" + << operation_char(turn.operations[1].operation) + << "; segment IDs {source, multi, ring, segment}: "; + apply_to_segment_identifier(oss, turn.operations[0].seg_id); + oss << "/"; + apply_to_segment_identifier(oss, turn.operations[1].seg_id); + } + }; + + template <typename Point> + struct process_data<failure_duplicate_points, Point> + { + static inline void apply(std::ostringstream& oss, + Point const& point) + { + if (AllowDuplicates) + { + return; + } + oss << ". Duplicate points were found near point " + << geometry::dsv(point); + } + }; + +public: + failing_reason_policy(std::ostringstream& oss) + : m_oss(oss) + {} + + template <validity_failure_type Failure> + inline bool apply() + { + validity_failure_type const failure = transform_failure_type(Failure); + set_failure_message(failure); + return failure == no_failure; + } + + template <validity_failure_type Failure, typename Data> + inline bool apply(Data const& data) + { + validity_failure_type const failure = transform_failure_type(Failure); + set_failure_message(failure); + process_data<Failure, Data>::apply(m_oss, data); + return failure == no_failure; + } + + template <validity_failure_type Failure, typename Data1, typename Data2> + inline bool apply(Data1 const& data1, Data2 const& data2) + { + validity_failure_type const failure + = transform_failure_type(Failure, data1); + set_failure_message(failure); + process_data<Failure, Data1, Data2>::apply(m_oss, data1, data2); + return failure == no_failure; + } + +private: + std::ostringstream& m_oss; +}; + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_POLICIES_IS_VALID_FAILING_REASON_POLICY_HPP diff --git a/boost/geometry/policies/is_valid/failure_type_policy.hpp b/boost/geometry/policies/is_valid/failure_type_policy.hpp new file mode 100644 index 0000000000..9fb569e283 --- /dev/null +++ b/boost/geometry/policies/is_valid/failure_type_policy.hpp @@ -0,0 +1,83 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_POLICIES_IS_VALID_FAILURE_TYPE_POLICY_HPP +#define BOOST_GEOMETRY_POLICIES_IS_VALID_FAILURE_TYPE_POLICY_HPP + +#include <boost/geometry/algorithms/validity_failure_type.hpp> + + +namespace boost { namespace geometry +{ + + +// policy that simply keeps (and can return) the failure type +template <bool AllowDuplicates = true, bool AllowSpikes = true> +class failure_type_policy +{ +private: + static inline + validity_failure_type transform_failure_type(validity_failure_type failure) + { + if (AllowDuplicates && failure == failure_duplicate_points) + { + return no_failure; + } + return failure; + } + + static inline + validity_failure_type transform_failure_type(validity_failure_type failure, + bool is_linear) + { + if (is_linear && AllowSpikes && failure == failure_spikes) + { + return no_failure; + } + return transform_failure_type(failure); + } + +public: + failure_type_policy() + : m_failure(no_failure) + {} + + template <validity_failure_type Failure> + inline bool apply() + { + m_failure = transform_failure_type(Failure); + return m_failure == no_failure; + } + + template <validity_failure_type Failure, typename Data> + inline bool apply(Data const&) + { + return apply<Failure>(); + } + + template <validity_failure_type Failure, typename Data1, typename Data2> + inline bool apply(Data1 const& data1, Data2 const&) + { + m_failure = transform_failure_type(Failure, data1); + return m_failure == no_failure; + } + + validity_failure_type failure() const + { + return m_failure; + } + +private: + validity_failure_type m_failure; +}; + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_POLICIES_IS_VALID_FAILURE_TYPE_POLICY_HPP diff --git a/boost/geometry/policies/relate/direction.hpp b/boost/geometry/policies/relate/direction.hpp index 02fed94b10..2c903bd79f 100644 --- a/boost/geometry/policies/relate/direction.hpp +++ b/boost/geometry/policies/relate/direction.hpp @@ -206,22 +206,51 @@ struct segments_direction } } + static inline int arrival_from_position_value(int /*v_from*/, int v_to) + { + return v_to == 2 ? 1 + : v_to == 1 || v_to == 3 ? 0 + //: v_from >= 1 && v_from <= 3 ? -1 + : -1; + + // NOTE: this should be an equivalent of the above for the other order + /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1 + : v_from == 3 || v_to == 3 ? 0 + : -1;*/ + } + + static inline void analyse_position_value(int pos_val, + int & in_segment_count, + int & on_end_count, + int & outside_segment_count) + { + if ( pos_val == 1 || pos_val == 3 ) + { + on_end_count++; + } + else if ( pos_val == 2 ) + { + in_segment_count++; + } + else + { + outside_segment_count++; + } + } + template <typename Segment1, typename Segment2, typename Ratio> static inline return_type segments_collinear( - Segment1 const& , Segment2 const&, - Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b, - Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a) + Segment1 const& , Segment2 const& , bool opposite, + int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a, + Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/, + Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/) { - // If segments are opposite, the ratio of the FROM w.r.t. the other - // is larger than the ratio of the TO w.r.t. the other - bool const opposite = ra_to_wrt_b < ra_from_wrt_b; - return_type r('c', opposite); // IMPORTANT: the order of conditions is different as in intersection_points.hpp // We assign A in 0 and B in 1 - r.arrival[0] = arrival_value(ra_from_wrt_b, ra_to_wrt_b); - r.arrival[1] = arrival_value(rb_from_wrt_a, rb_to_wrt_a); + r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b); + r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a); // Analyse them int a_in_segment_count = 0; @@ -230,13 +259,13 @@ struct segments_direction int b_in_segment_count = 0; int b_on_end_count = 0; int b_outside_segment_count = 0; - analyze(ra_from_wrt_b, + analyse_position_value(a1_wrt_b, a_in_segment_count, a_on_end_count, a_outside_segment_count); - analyze(ra_to_wrt_b, + analyse_position_value(a2_wrt_b, a_in_segment_count, a_on_end_count, a_outside_segment_count); - analyze(rb_from_wrt_a, + analyse_position_value(b1_wrt_a, b_in_segment_count, b_on_end_count, b_outside_segment_count); - analyze(rb_to_wrt_a, + analyse_position_value(b2_wrt_a, b_in_segment_count, b_on_end_count, b_outside_segment_count); if (a_on_end_count == 1 diff --git a/boost/geometry/policies/relate/intersection_points.hpp b/boost/geometry/policies/relate/intersection_points.hpp index aa2f697a2a..082dc4ca7f 100644 --- a/boost/geometry/policies/relate/intersection_points.hpp +++ b/boost/geometry/policies/relate/intersection_points.hpp @@ -19,6 +19,7 @@ #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> #include <boost/geometry/core/access.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> @@ -60,12 +61,24 @@ struct segments_intersection_points // denominator. In case of integer this results in an integer // division. BOOST_ASSERT(ratio.denominator() != 0); - set<0>(point, boost::numeric_cast<coordinate_type>( - get<0, 0>(segment) - + ratio.numerator() * dx / ratio.denominator())); - set<1>(point, boost::numeric_cast<coordinate_type>( - get<0, 1>(segment) - + ratio.numerator() * dy / ratio.denominator())); + + 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)); } @@ -100,19 +113,20 @@ struct segments_intersection_points template <typename Segment1, typename Segment2, typename Ratio> static inline return_type segments_collinear( - Segment1 const& a, Segment2 const& b, + Segment1 const& a, Segment2 const& b, bool /*opposite*/, + int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a, Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b, Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a) { return_type result; - int index = 0, count_a = 0, count_b = 0; + unsigned int index = 0, count_a = 0, count_b = 0; Ratio on_a[2]; // The conditions "index < 2" are necessary for non-robust handling, // if index would be 2 this indicate an (currently uncatched) error // IMPORTANT: the order of conditions is different as in direction.hpp - if (ra_from_wrt_b.on_segment() + if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment() && index < 2) { // a1--------->a2 @@ -126,7 +140,7 @@ struct segments_intersection_points index++; count_a++; } - if (rb_from_wrt_a.in_segment() + if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment() && index < 2) { // We take the first intersection point of B @@ -143,7 +157,7 @@ struct segments_intersection_points count_b++; } - if (ra_to_wrt_b.on_segment() + if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment() && index < 2) { // Similarly, second IP (here a2) @@ -155,7 +169,7 @@ struct segments_intersection_points index++; count_a++; } - if (rb_to_wrt_a.in_segment() + if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment() && index < 2) { detail::assign_point_from_index<1>(b, result.intersections[index]); diff --git a/boost/geometry/policies/relate/tupled.hpp b/boost/geometry/policies/relate/tupled.hpp index 6da9095c4e..4b65432f20 100644 --- a/boost/geometry/policies/relate/tupled.hpp +++ b/boost/geometry/policies/relate/tupled.hpp @@ -47,13 +47,22 @@ struct segments_tupled template <typename Segment1, typename Segment2, typename Ratio> static inline return_type segments_collinear( - Segment1 const& segment1, Segment2 const& segment2, - Ratio const& ra1, Ratio const& ra2, Ratio const& rb1, Ratio const& rb2) + Segment1 const& segment1, Segment2 const& segment2, + bool opposite, + int pa1, int pa2, int pb1, int pb2, + Ratio const& ra1, Ratio const& ra2, + Ratio const& rb1, Ratio const& rb2) { return boost::make_tuple ( - Policy1::segments_collinear(segment1, segment2, ra1, ra2, rb1, rb2), - Policy2::segments_collinear(segment1, segment2, ra1, ra2, rb1, rb2) + Policy1::segments_collinear(segment1, segment2, + opposite, + pa1, pa2, pb1, pb2, + ra1, ra2, rb1, rb2), + Policy2::segments_collinear(segment1, segment2, + opposite, + pa1, pa2, pb1, pb2, + ra1, ra2, rb1, rb2) ); } diff --git a/boost/geometry/policies/robustness/get_rescale_policy.hpp b/boost/geometry/policies/robustness/get_rescale_policy.hpp index ed7c1eb94c..52570995f6 100644 --- a/boost/geometry/policies/robustness/get_rescale_policy.hpp +++ b/boost/geometry/policies/robustness/get_rescale_policy.hpp @@ -1,9 +1,14 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2014 Bruno Lalande, Paris, France. -// Copyright (c) 2014 Mateusz Loskot, London, UK. -// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2014-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2014-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2014-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -41,35 +46,52 @@ namespace boost { namespace geometry namespace detail { namespace get_rescale_policy { -template <typename Point, typename RobustPoint, typename Geometry, typename Factor> -static inline void init_rescale_policy(Geometry const& geometry, - Point& min_point, - RobustPoint& min_robust_point, - Factor& factor) +template +< + typename Box, + typename Point, + typename RobustPoint, + typename Factor +> +inline void scale_box_to_integer_range(Box const& box, + Point& min_point, + RobustPoint& min_robust_point, + Factor& factor) { - // Get bounding boxes - model::box<Point> env = geometry::return_envelope<model::box<Point> >(geometry); - - // Scale this to integer-range + // Scale box to integer-range typedef typename promote_floating_point < typename geometry::coordinate_type<Point>::type >::type num_type; - num_type const diff = boost::numeric_cast<num_type>(detail::get_max_size(env)); + num_type const diff = boost::numeric_cast<num_type>(detail::get_max_size(box)); num_type const range = 10000000.0; // Define a large range to get precise integer coordinates num_type const half = 0.5; - factor = math::equals(diff, num_type()) ? 1 + factor = math::equals(diff, num_type()) || diff >= range ? 1 : boost::numeric_cast<num_type>( boost::numeric_cast<boost::long_long_type>(half + range / diff)); + BOOST_ASSERT(factor >= 1); + // Assign input/output minimal points - detail::assign_point_from_index<0>(env, min_point); + detail::assign_point_from_index<0>(box, min_point); num_type const two = 2; boost::long_long_type const min_coordinate = boost::numeric_cast<boost::long_long_type>(-range / two); assign_values(min_robust_point, min_coordinate, min_coordinate); } +template <typename Point, typename RobustPoint, typename Geometry, typename Factor> +static inline void init_rescale_policy(Geometry const& geometry, + Point& min_point, + RobustPoint& min_robust_point, + Factor& factor) +{ + // Get bounding boxes + model::box<Point> env = geometry::return_envelope<model::box<Point> >(geometry); + + scale_box_to_integer_range(env, min_point, min_robust_point, factor); +} + template <typename Point, typename RobustPoint, typename Geometry1, typename Geometry2, typename Factor> static inline void init_rescale_policy(Geometry1 const& geometry1, Geometry2 const& geometry2, @@ -82,25 +104,7 @@ static inline void init_rescale_policy(Geometry1 const& geometry1, model::box<Point> env2 = geometry::return_envelope<model::box<Point> >(geometry2); geometry::expand(env, env2); - // TODO: merge this with implementation above - // Scale this to integer-range - typedef typename promote_floating_point - < - typename geometry::coordinate_type<Point>::type - >::type num_type; - num_type const diff = boost::numeric_cast<num_type>(detail::get_max_size(env)); - num_type const range = 10000000.0; // Define a large range to get precise integer coordinates - num_type const half = 0.5; - factor = math::equals(diff, num_type()) ? 1 - : boost::numeric_cast<num_type>( - boost::numeric_cast<boost::long_long_type>(half + range / diff)); - - // Assign input/output minimal points - detail::assign_point_from_index<0>(env, min_point); - num_type const two = 2; - boost::long_long_type const min_coordinate - = boost::numeric_cast<boost::long_long_type>(-range / two); - assign_values(min_robust_point, min_coordinate, min_coordinate); + scale_box_to_integer_range(env, min_point, min_robust_point, factor); } |