diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp b/boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp new file mode 100644 index 0000000000..05fc6df8ff --- /dev/null +++ b/boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp @@ -0,0 +1,268 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands. + +// 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/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); + } +}; + +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); + } +}; + +struct include_turn_policy +{ + template <typename Turn> + static inline bool apply(Turn const& turn) + { + return turn.location == location_ok; + } +}; + +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); + } +}; + +//! 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_y, + Iterator begin, Iterator end, + int direction) +{ + if (direction == 0) + { + // Not a monotonic section, or no change in Y-direction + return point_in_range(strategy, state, point, begin, end); + } + + // We're in a monotonic section in y-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_y = geometry::get<1>(*previous); + + if (direction == 1 && point_y < previous_y) + { + // Section goes upwards, y increases, point is is below section + return true; + } + else if (direction == -1 && point_y > previous_y) + { + // Section goes downwards, y 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> +inline int point_in_original(Point const& point, Original const& original) +{ + typedef strategy::within::winding<Point> strategy_type; + + typename strategy_type::state_type state; + strategy_type strategy; + + 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_y = geometry::get<1>(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_y >= geometry::get<min_corner, 1>(section.bounding_box) + && point_y <= geometry::get<max_corner, 1>(section.bounding_box)) + { + // y-coordinate of point overlaps with section + if (! point_in_section(strategy, state, point, point_y, + 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> +class turn_in_original_visitor +{ +public: + turn_in_original_visitor(Turns& turns) + : m_mutable_turns(turns) + {} + + template <typename Turn, typename Original> + inline void apply(Turn const& turn, Original const& original, bool first = true) + { + boost::ignore_unused_variable_warning(first); + + if (turn.location != location_ok || turn.within_original) + { + // Skip all points already processed + return; + } + + if (geometry::disjoint(turn.robust_point, original.m_box)) + { + // Skip all disjoint + return; + } + + int const code = point_in_original(turn.robust_point, original); + + if (code == -1) + { + return; + } + + 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; + } + } + +private : + Turns& m_mutable_turns; +}; + + +}} // namespace detail::buffer +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR |