123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2014-2019, 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
- // Licensed under the Boost Software License version 1.0.
- // http://www.boost.org/users/license.html
- #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
- #include <algorithm>
- #include <deque>
- #include <boost/range.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/core/closure.hpp>
- #include <boost/geometry/core/coordinate_type.hpp>
- #include <boost/geometry/core/point_type.hpp>
- #include <boost/geometry/core/tag.hpp>
- #include <boost/geometry/core/tags.hpp>
- #include <boost/geometry/util/range.hpp>
- #include <boost/geometry/policies/predicate_based_interrupt_policy.hpp>
- #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
- #include <boost/geometry/policies/robustness/segment_ratio.hpp>
- #include <boost/geometry/algorithms/intersects.hpp>
- #include <boost/geometry/algorithms/not_implemented.hpp>
- #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
- #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
- #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp>
- #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
- #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
- #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
- #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp>
- #include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
- #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
- #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
- #include <boost/geometry/strategies/intersection.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace is_simple
- {
- template <typename Turn>
- inline bool check_segment_indices(Turn const& turn,
- signed_size_type last_index)
- {
- return
- (turn.operations[0].seg_id.segment_index == 0
- && turn.operations[1].seg_id.segment_index == last_index)
- ||
- (turn.operations[0].seg_id.segment_index == 0
- && turn.operations[1].seg_id.segment_index == last_index);
- }
- template
- <
- typename Geometry,
- typename EqPPStrategy,
- typename Tag = typename tag<Geometry>::type
- >
- class is_acceptable_turn
- : not_implemented<Geometry>
- {};
- template <typename Linestring, typename EqPPStrategy>
- class is_acceptable_turn<Linestring, EqPPStrategy, linestring_tag>
- {
- public:
- is_acceptable_turn(Linestring const& linestring)
- : m_linestring(linestring)
- , m_is_closed(geometry::detail::equals::equals_point_point(range::front(linestring),
- range::back(linestring),
- EqPPStrategy()))
- {}
- template <typename Turn>
- inline bool apply(Turn const& turn) const
- {
- BOOST_GEOMETRY_ASSERT(boost::size(m_linestring) > 1);
- return m_is_closed
- && turn.method == overlay::method_none
- && check_segment_indices(turn, boost::size(m_linestring) - 2)
- && turn.operations[0].fraction.is_zero();
- }
- private:
- Linestring const& m_linestring;
- bool const m_is_closed;
- };
- template <typename MultiLinestring, typename EqPPStrategy>
- class is_acceptable_turn<MultiLinestring, EqPPStrategy, multi_linestring_tag>
- {
- private:
- template <typename Point1, typename Point2>
- static inline bool equals_point_point(Point1 const& point1, Point2 const& point2)
- {
- return geometry::detail::equals::equals_point_point(point1, point2,
- EqPPStrategy());
- }
- template <typename Point, typename Linestring>
- static inline bool is_boundary_point_of(Point const& point,
- Linestring const& linestring)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
- return
- !equals_point_point(range::front(linestring), range::back(linestring))
- &&
- (equals_point_point(point, range::front(linestring))
- || equals_point_point(point, range::back(linestring)));
- }
- template <typename Turn, typename Linestring>
- static inline bool is_closing_point_of(Turn const& turn,
- Linestring const& linestring)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
- return
- turn.method == overlay::method_none
- &&
- check_segment_indices(turn, boost::size(linestring) - 2)
- &&
- equals_point_point(range::front(linestring), range::back(linestring))
- &&
- turn.operations[0].fraction.is_zero();
- ;
- }
- template <typename Linestring1, typename Linestring2>
- static inline bool have_same_boundary_points(Linestring1 const& ls1,
- Linestring2 const& ls2)
- {
- return
- equals_point_point(range::front(ls1), range::front(ls2))
- ?
- equals_point_point(range::back(ls1), range::back(ls2))
- :
- (equals_point_point(range::front(ls1), range::back(ls2))
- &&
- equals_point_point(range::back(ls1), range::front(ls2)))
- ;
- }
- public:
- is_acceptable_turn(MultiLinestring const& multilinestring)
- : m_multilinestring(multilinestring)
- {}
- template <typename Turn>
- inline bool apply(Turn const& turn) const
- {
- typedef typename boost::range_value<MultiLinestring>::type linestring_type;
-
- linestring_type const& ls1 =
- range::at(m_multilinestring, turn.operations[0].seg_id.multi_index);
- linestring_type const& ls2 =
- range::at(m_multilinestring, turn.operations[1].seg_id.multi_index);
- if (turn.operations[0].seg_id.multi_index
- == turn.operations[1].seg_id.multi_index)
- {
- return is_closing_point_of(turn, ls1);
- }
- return
- is_boundary_point_of(turn.point, ls1)
- && is_boundary_point_of(turn.point, ls2)
- &&
- ( boost::size(ls1) != 2
- || boost::size(ls2) != 2
- || ! have_same_boundary_points(ls1, ls2) );
- }
- private:
- MultiLinestring const& m_multilinestring;
- };
- template <typename Linear, typename Strategy>
- inline bool has_self_intersections(Linear const& linear, Strategy const& strategy)
- {
- typedef typename point_type<Linear>::type point_type;
- // compute self turns
- typedef detail::overlay::turn_info<point_type> turn_info;
- std::deque<turn_info> turns;
- typedef detail::overlay::get_turn_info
- <
- detail::disjoint::assign_disjoint_policy
- > turn_policy;
- typedef is_acceptable_turn
- <
- Linear,
- typename Strategy::equals_point_point_strategy_type
- > is_acceptable_turn_type;
- is_acceptable_turn_type predicate(linear);
- detail::overlay::predicate_based_interrupt_policy
- <
- is_acceptable_turn_type
- > interrupt_policy(predicate);
- // TODO: skip_adjacent should be set to false
- detail::self_get_turn_points::get_turns
- <
- false, turn_policy
- >::apply(linear,
- strategy,
- detail::no_rescale_policy(),
- turns,
- interrupt_policy, 0, true);
- detail::is_valid::debug_print_turns(turns.begin(), turns.end());
- debug_print_boundary_points(linear);
- return interrupt_policy.has_intersections;
- }
- template <typename Linestring, bool CheckSelfIntersections = true>
- struct is_simple_linestring
- {
- template <typename Strategy>
- static inline bool apply(Linestring const& linestring,
- Strategy const& strategy)
- {
- simplicity_failure_policy policy;
- return ! boost::empty(linestring)
- && ! detail::is_valid::has_duplicates
- <
- Linestring, closed, typename Strategy::cs_tag
- >::apply(linestring, policy)
- && ! detail::is_valid::has_spikes
- <
- Linestring, closed
- >::apply(linestring, policy, strategy.get_side_strategy());
- }
- };
- template <typename Linestring>
- struct is_simple_linestring<Linestring, true>
- {
- template <typename Strategy>
- static inline bool apply(Linestring const& linestring,
- Strategy const& strategy)
- {
- return is_simple_linestring
- <
- Linestring, false
- >::apply(linestring, strategy)
- && ! has_self_intersections(linestring, strategy);
- }
- };
- template <typename MultiLinestring>
- struct is_simple_multilinestring
- {
- private:
- template <typename Strategy>
- struct per_linestring
- {
- per_linestring(Strategy const& strategy)
- : m_strategy(strategy)
- {}
- template <typename Linestring>
- inline bool apply(Linestring const& linestring) const
- {
- return detail::is_simple::is_simple_linestring
- <
- Linestring,
- false // do not compute self-intersections
- >::apply(linestring, m_strategy);
- }
- Strategy const& m_strategy;
- };
- public:
- template <typename Strategy>
- static inline bool apply(MultiLinestring const& multilinestring,
- Strategy const& strategy)
- {
- typedef per_linestring<Strategy> per_ls;
- // check each of the linestrings for simplicity
- // but do not compute self-intersections yet; these will be
- // computed for the entire multilinestring
- if ( ! detail::check_iterator_range
- <
- per_ls, // do not compute self-intersections
- true // allow empty multilinestring
- >::apply(boost::begin(multilinestring),
- boost::end(multilinestring),
- per_ls(strategy))
- )
- {
- return false;
- }
- return ! has_self_intersections(multilinestring, strategy);
- }
- };
- }} // namespace detail::is_simple
- #endif // DOXYGEN_NO_DETAIL
- #ifndef DOXYGEN_NO_DISPATCH
- namespace dispatch
- {
- // A linestring is a curve.
- // A curve is simple if it does not pass through the same point twice,
- // with the possible exception of its two endpoints
- //
- // Reference: OGC 06-103r4 (6.1.6.1)
- template <typename Linestring>
- struct is_simple<Linestring, linestring_tag>
- : detail::is_simple::is_simple_linestring<Linestring>
- {};
- // A MultiLinestring is a MultiCurve
- // A MultiCurve is simple if all of its elements are simple and the
- // only intersections between any two elements occur at Points that
- // are on the boundaries of both elements.
- //
- // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
- template <typename MultiLinestring>
- struct is_simple<MultiLinestring, multi_linestring_tag>
- : detail::is_simple::is_simple_multilinestring<MultiLinestring>
- {};
- } // namespace dispatch
- #endif // DOXYGEN_NO_DISPATCH
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
|