123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands.
- // This file was modified by Oracle on 2016, 2018.
- // Modifications copyright (c) 2016-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_BUFFER_TURN_IN_ORIGINAL_VISITOR
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
- #include <boost/core/ignore_unused.hpp>
- #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
- #include <boost/geometry/algorithms/expand.hpp>
- #include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
- #include <boost/geometry/strategies/buffer.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace buffer
- {
- struct original_get_box
- {
- template <typename Box, typename Original>
- static inline void apply(Box& total, Original const& original)
- {
- geometry::expand(total, original.m_box);
- }
- };
- template <typename DisjointBoxBoxStrategy>
- struct original_ovelaps_box
- {
- template <typename Box, typename Original>
- static inline bool apply(Box const& box, Original const& original)
- {
- return ! detail::disjoint::disjoint_box_box(box, original.m_box,
- DisjointBoxBoxStrategy());
- }
- };
- struct include_turn_policy
- {
- template <typename Turn>
- static inline bool apply(Turn const& turn)
- {
- return turn.location == location_ok;
- }
- };
- template <typename DisjointPointBoxStrategy>
- struct turn_in_original_ovelaps_box
- {
- template <typename Box, typename Turn>
- static inline bool apply(Box const& box, Turn const& turn)
- {
- if (turn.location != location_ok || turn.within_original)
- {
- // Skip all points already processed
- return false;
- }
- return ! geometry::detail::disjoint::disjoint_point_box(
- turn.robust_point, box, DisjointPointBoxStrategy());
- }
- };
- //! Check if specified is in range of specified iterators
- //! Return value of strategy (true if we can bail out)
- template
- <
- typename Strategy,
- typename State,
- typename Point,
- typename Iterator
- >
- inline bool point_in_range(Strategy& strategy, State& state,
- Point const& point, Iterator begin, Iterator end)
- {
- boost::ignore_unused(strategy);
- Iterator it = begin;
- for (Iterator previous = it++; it != end; ++previous, ++it)
- {
- if (! strategy.apply(point, *previous, *it, state))
- {
- // We're probably on the boundary
- return false;
- }
- }
- return true;
- }
- template
- <
- typename Strategy,
- typename State,
- typename Point,
- typename CoordinateType,
- typename Iterator
- >
- inline bool point_in_section(Strategy& strategy, State& state,
- Point const& point, CoordinateType const& point_x,
- Iterator begin, Iterator end,
- int direction)
- {
- if (direction == 0)
- {
- // Not a monotonic section, or no change in X-direction
- return point_in_range(strategy, state, point, begin, end);
- }
- // We're in a monotonic section in x-direction
- Iterator it = begin;
- for (Iterator previous = it++; it != end; ++previous, ++it)
- {
- // Depending on sections.direction we can quit for this section
- CoordinateType const previous_x = geometry::get<0>(*previous);
- if (direction == 1 && point_x < previous_x)
- {
- // Section goes upwards, x increases, point is is below section
- return true;
- }
- else if (direction == -1 && point_x > previous_x)
- {
- // Section goes downwards, x decreases, point is above section
- return true;
- }
- if (! strategy.apply(point, *previous, *it, state))
- {
- // We're probably on the boundary
- return false;
- }
- }
- return true;
- }
- template <typename Point, typename Original, typename PointInGeometryStrategy>
- inline int point_in_original(Point const& point, Original const& original,
- PointInGeometryStrategy const& strategy)
- {
- typename PointInGeometryStrategy::state_type state;
- if (boost::size(original.m_sections) == 0
- || boost::size(original.m_ring) - boost::size(original.m_sections) < 16)
- {
- // There are no sections, or it does not profit to walk over sections
- // instead of over points. Boundary of 16 is arbitrary but can influence
- // performance
- point_in_range(strategy, state, point,
- original.m_ring.begin(), original.m_ring.end());
- return strategy.result(state);
- }
- typedef typename Original::sections_type sections_type;
- typedef typename boost::range_iterator<sections_type const>::type iterator_type;
- typedef typename boost::range_value<sections_type const>::type section_type;
- typedef typename geometry::coordinate_type<Point>::type coordinate_type;
- coordinate_type const point_x = geometry::get<0>(point);
- // Walk through all monotonic sections of this original
- for (iterator_type it = boost::begin(original.m_sections);
- it != boost::end(original.m_sections);
- ++it)
- {
- section_type const& section = *it;
- if (! section.duplicate
- && section.begin_index < section.end_index
- && point_x >= geometry::get<min_corner, 0>(section.bounding_box)
- && point_x <= geometry::get<max_corner, 0>(section.bounding_box))
- {
- // x-coordinate of point overlaps with section
- if (! point_in_section(strategy, state, point, point_x,
- boost::begin(original.m_ring) + section.begin_index,
- boost::begin(original.m_ring) + section.end_index + 1,
- section.directions[0]))
- {
- // We're probably on the boundary
- break;
- }
- }
- }
- return strategy.result(state);
- }
- template <typename Turns, typename PointInGeometryStrategy>
- class turn_in_original_visitor
- {
- public:
- turn_in_original_visitor(Turns& turns, PointInGeometryStrategy const& strategy)
- : m_mutable_turns(turns)
- , m_point_in_geometry_strategy(strategy)
- {}
- template <typename Turn, typename Original>
- inline bool apply(Turn const& turn, Original const& original, bool first = true)
- {
- boost::ignore_unused(first);
- if (turn.location != location_ok || turn.within_original)
- {
- // Skip all points already processed
- return true;
- }
- if (geometry::disjoint(turn.robust_point, original.m_box))
- {
- // Skip all disjoint
- return true;
- }
- int const code = point_in_original(turn.robust_point, original, m_point_in_geometry_strategy);
- if (code == -1)
- {
- return true;
- }
- Turn& mutable_turn = m_mutable_turns[turn.turn_index];
- if (code == 0)
- {
- // On border of original: always discard
- mutable_turn.location = location_discard;
- }
- // Point is inside an original ring
- if (original.m_is_interior)
- {
- mutable_turn.count_in_original--;
- }
- else if (original.m_has_interiors)
- {
- mutable_turn.count_in_original++;
- }
- else
- {
- // It is an exterior ring and there are no interior rings.
- // Then we are completely ready with this turn
- mutable_turn.within_original = true;
- mutable_turn.count_in_original = 1;
- }
- return true;
- }
- private :
- Turns& m_mutable_turns;
- PointInGeometryStrategy const& m_point_in_geometry_strategy;
- };
- }} // namespace detail::buffer
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
|