123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
- // This file was modified by Oracle on 2013, 2014, 2018.
- // Modifications copyright (c) 2013-2018 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_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
- #include <vector>
- #include <boost/core/ignore_unused.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
- #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
- #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
- #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp>
- #include <boost/geometry/algorithms/not_implemented.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/util/condition.hpp>
- #include <boost/geometry/util/range.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace relate {
- // NOTE: This iterates through single geometries for which turns were not generated.
- // It doesn't mean that the geometry is disjoint, only that no turns were detected.
- template <std::size_t OpId,
- typename Geometry,
- typename Tag = typename geometry::tag<Geometry>::type,
- bool IsMulti = boost::is_base_of<multi_tag, Tag>::value
- >
- struct for_each_disjoint_geometry_if
- : public not_implemented<Tag>
- {};
- template <std::size_t OpId, typename Geometry, typename Tag>
- struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, false>
- {
- template <typename TurnIt, typename Pred>
- static inline bool apply(TurnIt first, TurnIt last,
- Geometry const& geometry,
- Pred & pred)
- {
- if ( first != last )
- return false;
- pred(geometry);
- return true;
- }
- };
- template <std::size_t OpId, typename Geometry, typename Tag>
- struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, true>
- {
- template <typename TurnIt, typename Pred>
- static inline bool apply(TurnIt first, TurnIt last,
- Geometry const& geometry,
- Pred & pred)
- {
- if ( first != last )
- return for_turns(first, last, geometry, pred);
- else
- return for_empty(geometry, pred);
- }
- template <typename Pred>
- static inline bool for_empty(Geometry const& geometry,
- Pred & pred)
- {
- typedef typename boost::range_iterator<Geometry const>::type iterator;
- // O(N)
- // check predicate for each contained geometry without generated turn
- for ( iterator it = boost::begin(geometry) ;
- it != boost::end(geometry) ; ++it )
- {
- bool cont = pred(*it);
- if ( !cont )
- break;
- }
-
- return !boost::empty(geometry);
- }
- template <typename TurnIt, typename Pred>
- static inline bool for_turns(TurnIt first, TurnIt last,
- Geometry const& geometry,
- Pred & pred)
- {
- BOOST_GEOMETRY_ASSERT(first != last);
- const std::size_t count = boost::size(geometry);
- boost::ignore_unused(count);
- // O(I)
- // gather info about turns generated for contained geometries
- std::vector<bool> detected_intersections(count, false);
- for ( TurnIt it = first ; it != last ; ++it )
- {
- signed_size_type multi_index = it->operations[OpId].seg_id.multi_index;
- BOOST_GEOMETRY_ASSERT(multi_index >= 0);
- std::size_t const index = static_cast<std::size_t>(multi_index);
- BOOST_GEOMETRY_ASSERT(index < count);
- detected_intersections[index] = true;
- }
- bool found = false;
- // O(N)
- // check predicate for each contained geometry without generated turn
- for ( std::vector<bool>::iterator it = detected_intersections.begin() ;
- it != detected_intersections.end() ; ++it )
- {
- // if there were no intersections for this multi_index
- if ( *it == false )
- {
- found = true;
- std::size_t const index = std::size_t(std::distance(detected_intersections.begin(), it));
- bool cont = pred(range::at(geometry, index));
- if ( !cont )
- break;
- }
- }
-
- return found;
- }
- };
- // WARNING! This class stores pointers!
- // Passing a reference to local variable will result in undefined behavior!
- template <typename Point>
- class point_info
- {
- public:
- point_info() : sid_ptr(NULL), pt_ptr(NULL) {}
- point_info(Point const& pt, segment_identifier const& sid)
- : sid_ptr(boost::addressof(sid))
- , pt_ptr(boost::addressof(pt))
- {}
- segment_identifier const& seg_id() const
- {
- BOOST_GEOMETRY_ASSERT(sid_ptr);
- return *sid_ptr;
- }
- Point const& point() const
- {
- BOOST_GEOMETRY_ASSERT(pt_ptr);
- return *pt_ptr;
- }
- //friend bool operator==(point_identifier const& l, point_identifier const& r)
- //{
- // return l.seg_id() == r.seg_id()
- // && detail::equals::equals_point_point(l.point(), r.point());
- //}
- private:
- const segment_identifier * sid_ptr;
- const Point * pt_ptr;
- };
- // WARNING! This class stores pointers!
- // Passing a reference to local variable will result in undefined behavior!
- class same_single
- {
- public:
- same_single(segment_identifier const& sid)
- : sid_ptr(boost::addressof(sid))
- {}
- bool operator()(segment_identifier const& sid) const
- {
- return sid.multi_index == sid_ptr->multi_index;
- }
- template <typename Point>
- bool operator()(point_info<Point> const& pid) const
- {
- return operator()(pid.seg_id());
- }
- private:
- const segment_identifier * sid_ptr;
- };
- class same_ring
- {
- public:
- same_ring(segment_identifier const& sid)
- : sid_ptr(boost::addressof(sid))
- {}
- bool operator()(segment_identifier const& sid) const
- {
- return sid.multi_index == sid_ptr->multi_index
- && sid.ring_index == sid_ptr->ring_index;
- }
- private:
- const segment_identifier * sid_ptr;
- };
- // WARNING! This class stores pointers!
- // Passing a reference to local variable will result in undefined behavior!
- template <typename SameRange = same_single>
- class segment_watcher
- {
- public:
- segment_watcher()
- : m_seg_id_ptr(NULL)
- {}
- bool update(segment_identifier const& seg_id)
- {
- bool result = m_seg_id_ptr == 0 || !SameRange(*m_seg_id_ptr)(seg_id);
- m_seg_id_ptr = boost::addressof(seg_id);
- return result;
- }
- private:
- const segment_identifier * m_seg_id_ptr;
- };
- // WARNING! This class stores pointers!
- // Passing a reference to local variable will result in undefined behavior!
- template <typename TurnInfo, std::size_t OpId>
- class exit_watcher
- {
- static const std::size_t op_id = OpId;
- static const std::size_t other_op_id = (OpId + 1) % 2;
- typedef typename TurnInfo::point_type point_type;
- typedef detail::relate::point_info<point_type> point_info;
- public:
- exit_watcher()
- : m_exit_operation(overlay::operation_none)
- , m_exit_turn_ptr(NULL)
- {}
- void enter(TurnInfo const& turn)
- {
- m_other_entry_points.push_back(
- point_info(turn.point, turn.operations[other_op_id].seg_id) );
- }
- // TODO: exit_per_geometry parameter looks not very safe
- // wrong value may be easily passed
- void exit(TurnInfo const& turn, bool exit_per_geometry = true)
- {
- //segment_identifier const& seg_id = turn.operations[op_id].seg_id;
- segment_identifier const& other_id = turn.operations[other_op_id].seg_id;
- overlay::operation_type exit_op = turn.operations[op_id].operation;
- typedef typename std::vector<point_info>::iterator point_iterator;
- // search for the entry point in the same range of other geometry
- point_iterator entry_it = std::find_if(m_other_entry_points.begin(),
- m_other_entry_points.end(),
- same_single(other_id));
- // this end point has corresponding entry point
- if ( entry_it != m_other_entry_points.end() )
- {
- // erase the corresponding entry point
- m_other_entry_points.erase(entry_it);
- if ( exit_per_geometry || m_other_entry_points.empty() )
- {
- // here we know that we possibly left LS
- // we must still check if we didn't get back on the same point
- m_exit_operation = exit_op;
- m_exit_turn_ptr = boost::addressof(turn);
- }
- }
- }
- bool is_outside() const
- {
- // if we didn't entered anything in the past, we're outside
- return m_other_entry_points.empty();
- }
- bool is_outside(TurnInfo const& turn) const
- {
- return m_other_entry_points.empty()
- || std::find_if(m_other_entry_points.begin(),
- m_other_entry_points.end(),
- same_single(
- turn.operations[other_op_id].seg_id))
- == m_other_entry_points.end();
- }
- overlay::operation_type get_exit_operation() const
- {
- return m_exit_operation;
- }
- point_type const& get_exit_point() const
- {
- BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
- BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
- return m_exit_turn_ptr->point;
- }
- TurnInfo const& get_exit_turn() const
- {
- BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
- BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
- return *m_exit_turn_ptr;
- }
- void reset_detected_exit()
- {
- m_exit_operation = overlay::operation_none;
- }
- void reset()
- {
- m_exit_operation = overlay::operation_none;
- m_other_entry_points.clear();
- }
- private:
- overlay::operation_type m_exit_operation;
- const TurnInfo * m_exit_turn_ptr;
- std::vector<point_info> m_other_entry_points; // TODO: use map here or sorted vector?
- };
- template <std::size_t OpId, typename Turn, typename EqPPStrategy>
- inline bool turn_on_the_same_ip(Turn const& prev_turn, Turn const& curr_turn,
- EqPPStrategy const& strategy)
- {
- segment_identifier const& prev_seg_id = prev_turn.operations[OpId].seg_id;
- segment_identifier const& curr_seg_id = curr_turn.operations[OpId].seg_id;
- if ( prev_seg_id.multi_index != curr_seg_id.multi_index
- || prev_seg_id.ring_index != curr_seg_id.ring_index )
- {
- return false;
- }
- // TODO: will this work if between segments there will be some number of degenerated ones?
- if ( prev_seg_id.segment_index != curr_seg_id.segment_index
- && ( ! curr_turn.operations[OpId].fraction.is_zero()
- || prev_seg_id.segment_index + 1 != curr_seg_id.segment_index ) )
- {
- return false;
- }
- return detail::equals::equals_point_point(prev_turn.point, curr_turn.point, strategy);
- }
- template <boundary_query BoundaryQuery,
- typename Point,
- typename BoundaryChecker>
- static inline bool is_endpoint_on_boundary(Point const& pt,
- BoundaryChecker & boundary_checker)
- {
- return boundary_checker.template is_endpoint_boundary<BoundaryQuery>(pt);
- }
- template <boundary_query BoundaryQuery,
- typename IntersectionPoint,
- typename OperationInfo,
- typename BoundaryChecker>
- static inline bool is_ip_on_boundary(IntersectionPoint const& ip,
- OperationInfo const& operation_info,
- BoundaryChecker & boundary_checker,
- segment_identifier const& seg_id)
- {
- boost::ignore_unused(seg_id);
- bool res = false;
- // IP on the last point of the linestring
- if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
- && operation_info.position == overlay::position_back )
- {
- // check if this point is a boundary
- res = boundary_checker.template is_endpoint_boundary<boundary_back>(ip);
- }
- // IP on the last point of the linestring
- else if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
- && operation_info.position == overlay::position_front )
- {
- // check if this point is a boundary
- res = boundary_checker.template is_endpoint_boundary<boundary_front>(ip);
- }
-
- return res;
- }
- }} // namespace detail::relate
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
|