algorithms/detail/has_self_intersections.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2011-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2020.
0007 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
0016
0017 #include <deque>
0018
0019 #include <boost/range/begin.hpp>
0020 #include <boost/range/end.hpp>
0021 #include <boost/throw_exception.hpp>
0022
0023 #include <boost/geometry/core/point_type.hpp>
0024 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0026 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
0027
0028 #include <boost/geometry/policies/disjoint_interrupt_policy.hpp>
0029 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
0030 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
0031 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
0032
0033 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
0034 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0035 #  include <boost/geometry/io/dsv/write.hpp>
0036 #endif
0037
0038
0039 namespace boost { namespace geometry
0040 {
0041
0042
0043 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
0044
0045 /*!
0046 \brief Overlay Invalid Input Exception
0047 \ingroup overlay
0048 \details The overlay_invalid_input_exception is thrown at invalid input
0049  */
0050 class overlay_invalid_input_exception : public geometry::exception
0051 {
0052 public:
0053
0054     inline overlay_invalid_input_exception() {}
0055
0056     char const* what() const noexcept override
0057     {
0058         return "Boost.Geometry Overlay invalid input exception";
0059     }
0060 };
0061
0062 #endif
0063
0064
0065 #ifndef DOXYGEN_NO_DETAIL
0066 namespace detail { namespace overlay
0067 {
0068
0069
0070 template <typename Geometry, typename Strategy, typename RobustPolicy>
0071 inline bool has_self_intersections(Geometry const& geometry,
0072         Strategy const& strategy,
0073         RobustPolicy const& robust_policy,
0074         bool throw_on_self_intersection = true)
0075 {
0076     typedef typename point_type<Geometry>::type point_type;
0077     typedef turn_info
0078     <
0079         point_type,
0080         typename segment_ratio_type<point_type, RobustPolicy>::type
0081     > turn_info;
0082     std::deque<turn_info> turns;
0083     detail::disjoint::disjoint_interrupt_policy policy;
0084
0085     detail::self_get_turn_points::self_turns
0086         <
0087             false,
0088             detail::overlay::assign_null_policy
0089         >(geometry, strategy, robust_policy, turns, policy, 0, false);
0090
0091 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
0092     bool first = true;
0093 #endif
0094     for (auto const& info : turns)
0095     {
0096         bool const both_union_turn =
0097             info.operations[0].operation == detail::overlay::operation_union
0098             && info.operations[1].operation == detail::overlay::operation_union;
0099         bool const both_intersection_turn =
0100             info.operations[0].operation == detail::overlay::operation_intersection
0101             && info.operations[1].operation == detail::overlay::operation_intersection;
0102
0103         bool const valid = (both_union_turn || both_intersection_turn)
0104             && (info.method == detail::overlay::method_touch
0105                 || info.method == detail::overlay::method_touch_interior);
0106
0107         if (! valid)
0108         {
0109 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
0110             if (first)
0111             {
0112                 std::cout << "turn points: " << std::endl;
0113                 first = false;
0114             }
0115             std::cout << method_char(info.method);
0116             for (int i = 0; i < 2; i++)
0117             {
0118                 std::cout << " " << operation_char(info.operations[i].operation);
0119                 std::cout << " " << info.operations[i].seg_id;
0120             }
0121             std::cout << " " << geometry::dsv(info.point) << std::endl;
0122 #endif
0123
0124 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
0125             if (throw_on_self_intersection)
0126             {
0127                 BOOST_THROW_EXCEPTION(overlay_invalid_input_exception());
0128             }
0129 #endif
0130             return true;
0131         }
0132
0133     }
0134     return false;
0135 }
0136
0137
0138 }} // namespace detail::overlay
0139 #endif // DOXYGEN_NO_DETAIL
0140
0141
0142 }} // namespace boost::geometry
0143
0144
0145 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
0146