Chris@102: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@102: 
Chris@102: // Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
Chris@102: // Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
Chris@102: // Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
Chris@102: // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
Chris@102: 
Chris@102: // Use, modification and distribution is subject to the Boost Software License,
Chris@102: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: // http://www.boost.org/LICENSE_1_0.txt)
Chris@102: 
Chris@102: #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
Chris@102: #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
Chris@102: 
Chris@102: #include <deque>
Chris@102: 
Chris@102: #include <boost/range.hpp>
Chris@102: #include <boost/type_traits/remove_reference.hpp>
Chris@102: 
Chris@102: #include <boost/variant/apply_visitor.hpp>
Chris@102: #include <boost/variant/static_visitor.hpp>
Chris@102: #include <boost/variant/variant_fwd.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/core/closure.hpp>
Chris@102: #include <boost/geometry/core/coordinate_type.hpp>
Chris@102: #include <boost/geometry/core/cs.hpp>
Chris@102: #include <boost/geometry/core/interior_rings.hpp>
Chris@102: #include <boost/geometry/core/point_order.hpp>
Chris@102: #include <boost/geometry/core/tags.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
Chris@102: #include <boost/geometry/algorithms/clear.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/util/condition.hpp>
Chris@102: 
Chris@102: 
Chris@102: /*
Chris@102: Remove spikes from a ring/polygon.
Chris@102: Ring (having 8 vertices, including closing vertex)
Chris@102: +------+
Chris@102: |      |
Chris@102: |      +--+
Chris@102: |      |  ^this "spike" is removed, can be located outside/inside the ring
Chris@102: +------+
Chris@102: (the actualy determination if it is removed is done by a strategy)
Chris@102: 
Chris@102: */
Chris@102: 
Chris@102: 
Chris@102: namespace boost { namespace geometry
Chris@102: {
Chris@102: 
Chris@102: 
Chris@102: #ifndef DOXYGEN_NO_DETAIL
Chris@102: namespace detail { namespace remove_spikes
Chris@102: {
Chris@102: 
Chris@102: 
Chris@102: template <typename Range>
Chris@102: struct range_remove_spikes
Chris@102: {
Chris@102:     typedef typename strategy::side::services::default_strategy
Chris@102:     <
Chris@102:         typename cs_tag<Range>::type
Chris@102:     >::type side_strategy;
Chris@102: 
Chris@102:     typedef typename coordinate_type<Range>::type coordinate_type;
Chris@102:     typedef typename point_type<Range>::type point_type;
Chris@102: 
Chris@102: 
Chris@102:     static inline void apply(Range& range)
Chris@102:     {
Chris@102:         std::size_t n = boost::size(range);
Chris@102:         std::size_t const min_num_points = core_detail::closure::minimum_ring_size
Chris@102:             <
Chris@102:                 geometry::closure<Range>::value
Chris@102:             >::value - 1; // subtract one: a polygon with only one spike should result into one point
Chris@102:         if (n < min_num_points)
Chris@102:         {
Chris@102:             return;
Chris@102:         }
Chris@102: 
Chris@102:         std::deque<point_type> cleaned;
Chris@102:         for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
Chris@102:             it != boost::end(range); ++it)
Chris@102:         {
Chris@102:             // Add point
Chris@102:             cleaned.push_back(*it);
Chris@102: 
Chris@102:             while(cleaned.size() >= 3
Chris@102:                     && detail::point_is_spike_or_equal(cleaned.back(), *(cleaned.end() - 3), *(cleaned.end() - 2)))
Chris@102:             {
Chris@102:                 // Remove pen-ultimate point causing the spike (or which was equal)
Chris@102:                 cleaned.erase(cleaned.end() - 2);
Chris@102:             }
Chris@102:         }
Chris@102: 
Chris@102:         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
Chris@102:         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
Chris@102:         {
Chris@102:             cleaned.pop_back();
Chris@102:         }
Chris@102: 
Chris@102:         bool found = false;
Chris@102:         do
Chris@102:         {
Chris@102:             found = false;
Chris@102:             // Check for spike in first point
Chris@102:             int const penultimate = 2;
Chris@102:             while(cleaned.size() >= 3 && detail::point_is_spike_or_equal(cleaned.front(), *(cleaned.end() - penultimate), cleaned.back()))
Chris@102:             {
Chris@102:                 cleaned.pop_back();
Chris@102:                 found = true;
Chris@102:             }
Chris@102:             // Check for spike in second point
Chris@102:             while(cleaned.size() >= 3 && detail::point_is_spike_or_equal(*(cleaned.begin() + 1), cleaned.back(), cleaned.front()))
Chris@102:             {
Chris@102:                 cleaned.pop_front();
Chris@102:                 found = true;
Chris@102:             }
Chris@102:         }
Chris@102:         while (found);
Chris@102: 
Chris@102:         if (cleaned.size() == 2)
Chris@102:         {
Chris@102:             // Ticket #9871: open polygon with only two points.
Chris@102:             // the second point forms, by definition, a spike
Chris@102:             cleaned.pop_back();
Chris@102:         }
Chris@102: 
Chris@102:         // Close if necessary
Chris@102:         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
Chris@102:         {
Chris@102:             cleaned.push_back(cleaned.front());
Chris@102:         }
Chris@102: 
Chris@102:         // Copy output
Chris@102:         geometry::clear(range);
Chris@102:         std::copy(cleaned.begin(), cleaned.end(), std::back_inserter(range));
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: template <typename Polygon>
Chris@102: struct polygon_remove_spikes
Chris@102: {
Chris@102:     static inline void apply(Polygon& polygon)
Chris@102:     {
Chris@102:         typedef typename geometry::ring_type<Polygon>::type ring_type;
Chris@102: 
Chris@102:         typedef range_remove_spikes<ring_type> per_range;
Chris@102:         per_range::apply(exterior_ring(polygon));
Chris@102: 
Chris@102:         typename interior_return_type<Polygon>::type
Chris@102:             rings = interior_rings(polygon);
Chris@102: 
Chris@102:         for (typename detail::interior_iterator<Polygon>::type
Chris@102:                 it = boost::begin(rings); it != boost::end(rings); ++it)
Chris@102:         {
Chris@102:             per_range::apply(*it);
Chris@102:         }
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: template <typename MultiGeometry, typename SingleVersion>
Chris@102: struct multi_remove_spikes
Chris@102: {
Chris@102:     static inline void apply(MultiGeometry& multi)
Chris@102:     {
Chris@102:         for (typename boost::range_iterator<MultiGeometry>::type
Chris@102:                 it = boost::begin(multi);
Chris@102:             it != boost::end(multi);
Chris@102:             ++it)
Chris@102:         {
Chris@102:             SingleVersion::apply(*it);
Chris@102:         }
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: }} // namespace detail::remove_spikes
Chris@102: #endif // DOXYGEN_NO_DETAIL
Chris@102: 
Chris@102: 
Chris@102: 
Chris@102: #ifndef DOXYGEN_NO_DISPATCH
Chris@102: namespace dispatch
Chris@102: {
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename Geometry,
Chris@102:     typename Tag = typename tag<Geometry>::type
Chris@102: >
Chris@102: struct remove_spikes
Chris@102: {
Chris@102:     static inline void apply(Geometry&)
Chris@102:     {}
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: template <typename Ring>
Chris@102: struct remove_spikes<Ring, ring_tag>
Chris@102:     : detail::remove_spikes::range_remove_spikes<Ring>
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: 
Chris@102: template <typename Polygon>
Chris@102: struct remove_spikes<Polygon, polygon_tag>
Chris@102:     : detail::remove_spikes::polygon_remove_spikes<Polygon>
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: template <typename MultiPolygon>
Chris@102: struct remove_spikes<MultiPolygon, multi_polygon_tag>
Chris@102:     : detail::remove_spikes::multi_remove_spikes
Chris@102:         <
Chris@102:             MultiPolygon,
Chris@102:             detail::remove_spikes::polygon_remove_spikes
Chris@102:             <
Chris@102:                 typename boost::range_value<MultiPolygon>::type
Chris@102:             >
Chris@102:         >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: } // namespace dispatch
Chris@102: #endif
Chris@102: 
Chris@102: 
Chris@102: namespace resolve_variant {
Chris@102: 
Chris@102: template <typename Geometry>
Chris@102: struct remove_spikes
Chris@102: {
Chris@102:     static void apply(Geometry& geometry)
Chris@102:     {
Chris@102:         concept::check<Geometry>();
Chris@102:         dispatch::remove_spikes<Geometry>::apply(geometry);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
Chris@102: struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
Chris@102: {
Chris@102:     struct visitor: boost::static_visitor<void>
Chris@102:     {
Chris@102:         template <typename Geometry>
Chris@102:         void operator()(Geometry& geometry) const
Chris@102:         {
Chris@102:             remove_spikes<Geometry>::apply(geometry);
Chris@102:         }
Chris@102:     };
Chris@102: 
Chris@102:     static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry)
Chris@102:     {
Chris@102:         boost::apply_visitor(visitor(), geometry);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: } // namespace resolve_variant
Chris@102: 
Chris@102: 
Chris@102: /*!
Chris@102:     \ingroup remove_spikes
Chris@102:     \tparam Geometry geometry type
Chris@102:     \param geometry the geometry to make remove_spikes
Chris@102: */
Chris@102: template <typename Geometry>
Chris@102: inline void remove_spikes(Geometry& geometry)
Chris@102: {
Chris@102:     resolve_variant::remove_spikes<Geometry>::apply(geometry);
Chris@102: }
Chris@102: 
Chris@102: 
Chris@102: }} // namespace boost::geometry
Chris@102: 
Chris@102: 
Chris@102: #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP