Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
Chris@16: // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
Chris@101: // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
Chris@16: 
Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_UNIQUE_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_UNIQUE_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@101: #include <boost/type_traits/remove_reference.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
Chris@16: #include <boost/geometry/core/interior_rings.hpp>
Chris@16: #include <boost/geometry/core/mutable_range.hpp>
Chris@101: #include <boost/geometry/core/tags.hpp>
Chris@16: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@16: #include <boost/geometry/policies/compare.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace unique
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: struct range_unique
Chris@16: {
Chris@16:     template <typename Range, typename ComparePolicy>
Chris@16:     static inline void apply(Range& range, ComparePolicy const& policy)
Chris@16:     {
Chris@16:         typename boost::range_iterator<Range>::type it
Chris@16:             = std::unique
Chris@16:                 (
Chris@16:                     boost::begin(range),
Chris@16:                     boost::end(range),
Chris@16:                     policy
Chris@16:                 );
Chris@16: 
Chris@16:         traits::resize<Range>::apply(range, it - boost::begin(range));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: struct polygon_unique
Chris@16: {
Chris@16:     template <typename Polygon, typename ComparePolicy>
Chris@16:     static inline void apply(Polygon& polygon, ComparePolicy const& policy)
Chris@16:     {
Chris@16:         range_unique::apply(exterior_ring(polygon), policy);
Chris@16: 
Chris@101:         typename interior_return_type<Polygon>::type
Chris@101:             rings = interior_rings(polygon);
Chris@101: 
Chris@101:         for (typename detail::interior_iterator<Polygon>::type
Chris@101:                 it = boost::begin(rings); it != boost::end(rings); ++it)
Chris@16:         {
Chris@16:             range_unique::apply(*it, policy);
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@101: template <typename Policy>
Chris@101: struct multi_unique
Chris@101: {
Chris@101:     template <typename MultiGeometry, typename ComparePolicy>
Chris@101:     static inline void apply(MultiGeometry& multi, ComparePolicy const& compare)
Chris@101:     {
Chris@101:         for (typename boost::range_iterator<MultiGeometry>::type
Chris@101:                 it = boost::begin(multi);
Chris@101:             it != boost::end(multi);
Chris@101:             ++it)
Chris@101:         {
Chris@101:             Policy::apply(*it, compare);
Chris@101:         }
Chris@101:     }
Chris@101: };
Chris@101: 
Chris@16: 
Chris@16: }} // namespace detail::unique
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DISPATCH
Chris@16: namespace dispatch
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry,
Chris@16:     typename Tag = typename tag<Geometry>::type
Chris@16: >
Chris@16: struct unique
Chris@16: {
Chris@16:     template <typename ComparePolicy>
Chris@16:     static inline void apply(Geometry&, ComparePolicy const& )
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Ring>
Chris@16: struct unique<Ring, ring_tag>
Chris@16:     : detail::unique::range_unique
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: template <typename LineString>
Chris@16: struct unique<LineString, linestring_tag>
Chris@16:     : detail::unique::range_unique
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: template <typename Polygon>
Chris@16: struct unique<Polygon, polygon_tag>
Chris@16:     : detail::unique::polygon_unique
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@101: // For points, unique is not applicable and does nothing
Chris@101: // (Note that it is not "spatially unique" but that it removes duplicate coordinates,
Chris@101: //  like std::unique does). Spatially unique is "dissolve" which can (or will be)
Chris@101: //  possible for multi-points as well, removing points at the same location.
Chris@101: 
Chris@101: 
Chris@101: template <typename MultiLineString>
Chris@101: struct unique<MultiLineString, multi_linestring_tag>
Chris@101:     : detail::unique::multi_unique<detail::unique::range_unique>
Chris@101: {};
Chris@101: 
Chris@101: 
Chris@101: template <typename MultiPolygon>
Chris@101: struct unique<MultiPolygon, multi_polygon_tag>
Chris@101:     : detail::unique::multi_unique<detail::unique::polygon_unique>
Chris@101: {};
Chris@101: 
Chris@101: 
Chris@16: } // namespace dispatch
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16: \brief \brief_calc{minimal set}
Chris@16: \ingroup unique
Chris@16: \details \details_calc{unique,minimal set (where duplicate consecutive points are removed)}.
Chris@16: \tparam Geometry \tparam_geometry
Chris@16: \param geometry \param_geometry which will be made unique
Chris@16: 
Chris@16: \qbk{[include reference/algorithms/unique.qbk]}
Chris@16: */
Chris@16: template <typename Geometry>
Chris@16: inline void unique(Geometry& geometry)
Chris@16: {
Chris@16:     concept::check<Geometry>();
Chris@16: 
Chris@16:     // Default strategy is the default point-comparison policy
Chris@16:     typedef geometry::equal_to
Chris@16:         <
Chris@16:             typename geometry::point_type<Geometry>::type
Chris@16:         > policy;
Chris@16: 
Chris@16: 
Chris@16:     dispatch::unique<Geometry>::apply(geometry, policy());
Chris@16: }
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_UNIQUE_HPP