diff options
Diffstat (limited to 'boost/geometry/algorithms/simplify.hpp')
| -rw-r--r-- | boost/geometry/algorithms/simplify.hpp | 250 |
1 files changed, 192 insertions, 58 deletions
diff --git a/boost/geometry/algorithms/simplify.hpp b/boost/geometry/algorithms/simplify.hpp index cfeb542220..298f9c640a 100644 --- a/boost/geometry/algorithms/simplify.hpp +++ b/boost/geometry/algorithms/simplify.hpp @@ -36,9 +36,13 @@ #include <boost/geometry/strategies/default_strategy.hpp> #include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/clear.hpp> #include <boost/geometry/algorithms/convert.hpp> +#include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/algorithms/not_implemented.hpp> +#include <boost/geometry/algorithms/is_empty.hpp> +#include <boost/geometry/algorithms/perimeter.hpp> #include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> @@ -49,6 +53,14 @@ namespace boost { namespace geometry namespace detail { namespace simplify { +template <typename Range> +inline bool is_degenerate(Range const& range) +{ + return boost::size(range) == 2 + && detail::equals::equals_point_point(geometry::range::front(range), + geometry::range::back(range)); +} + struct simplify_range_insert { template<typename Range, typename Strategy, typename OutputIterator, typename Distance> @@ -57,7 +69,11 @@ struct simplify_range_insert { boost::ignore_unused(strategy); - if (boost::size(range) <= 2 || max_distance < 0) + if (is_degenerate(range)) + { + std::copy(boost::begin(range), boost::begin(range) + 1, out); + } + else if (boost::size(range) <= 2 || max_distance < 0) { std::copy(boost::begin(range), boost::end(range), out); } @@ -71,41 +87,32 @@ struct simplify_range_insert struct simplify_copy { - template <typename Range, typename Strategy, typename Distance> - static inline void apply(Range const& range, Range& out, + template <typename RangeIn, typename RangeOut, typename Strategy, typename Distance> + static inline void apply(RangeIn const& range, RangeOut& out, Distance const& , Strategy const& ) { std::copy ( - boost::begin(range), boost::end(range), geometry::range::back_inserter(out) + boost::begin(range), boost::end(range), + geometry::range::back_inserter(out) ); } }; -template<std::size_t Minimum> +template <std::size_t MinimumToUseStrategy> struct simplify_range { - template <typename Range, typename Strategy, typename Distance> - static inline void apply(Range const& range, Range& out, + template <typename RangeIn, typename RangeOut, typename Strategy, typename Distance> + static inline void apply(RangeIn const& range, RangeOut& out, Distance const& max_distance, Strategy const& strategy) { - // Call do_container for a linestring / ring - - /* For a RING: - The first/last point (the closing point of the ring) should maybe - be excluded because it lies on a line with second/one but last. - Here it is never excluded. + // For a RING: + // Note that, especially if max_distance is too large, + // the output ring might be self intersecting while the input ring is + // not, although chances are low in normal polygons - Note also that, especially if max_distance is too large, - the output ring might be self intersecting while the input ring is - not, although chances are low in normal polygons - - Finally the inputring might have 3 (open) or 4 (closed) points (=correct), - the output < 3 or 4(=wrong) - */ - - if (boost::size(range) <= int(Minimum) || max_distance < 0.0) + if (boost::size(range) <= MinimumToUseStrategy || max_distance < 0) { simplify_copy::apply(range, out, max_distance, strategy); } @@ -116,34 +123,172 @@ struct simplify_range range, geometry::range::back_inserter(out), max_distance, strategy ); } + + // Verify the two remaining points are equal. If so, remove one of them. + // This can cause the output being under the minimum size + if (is_degenerate(out)) + { + range::resize(out, 1); + } + } +}; + +struct simplify_ring +{ +private : + template <typename Area> + static inline int area_sign(Area const& area) + { + return area > 0 ? 1 : area < 0 ? -1 : 0; + } + + template <typename Strategy, typename Ring> + static std::size_t get_opposite(std::size_t index, Ring const& ring) + { + typename Strategy::distance_strategy_type distance_strategy; + + // Verify if it is NOT the case that all points are less than the + // simplifying distance. If so, output is empty. + typename Strategy::distance_type max_distance(-1); + + typename geometry::point_type<Ring>::type point = range::at(ring, index); + std::size_t i = 0; + for (typename boost::range_iterator<Ring const>::type + it = boost::begin(ring); it != boost::end(ring); ++it, ++i) + { + // This actually is point-segment distance but will result + // in point-point distance + typename Strategy::distance_type dist = distance_strategy.apply(*it, point, point); + if (dist > max_distance) + { + max_distance = dist; + index = i; + } + } + return index; + } + +public : + template <typename Ring, typename Strategy, typename Distance> + static inline void apply(Ring const& ring, Ring& out, + Distance const& max_distance, Strategy const& strategy) + { + std::size_t const size = boost::size(ring); + if (size == 0) + { + return; + } + + int const input_sign = area_sign(geometry::area(ring)); + + std::set<std::size_t> visited_indexes; + + // Rotate it into a copied vector + // (vector, because source type might not support rotation) + // (duplicate end point will be simplified away) + typedef typename geometry::point_type<Ring>::type point_type; + + std::vector<point_type> rotated(size); + + // Closing point (but it will not start here) + std::size_t index = 0; + + // Iterate (usually one iteration is enough) + for (std::size_t iteration = 0; iteration < 4u; iteration++) + { + // Always take the opposite. Opposite guarantees that no point + // "halfway" is chosen, creating an artefact (very narrow triangle) + // Iteration 0: opposite to closing point (1/2, = on convex hull) + // (this will start simplification with that point + // and its opposite ~0) + // Iteration 1: move a quarter on that ring, then opposite to 1/4 + // (with its opposite 3/4) + // Iteration 2: move an eight on that ring, then opposite (1/8) + // Iteration 3: again move a quarter, then opposite (7/8) + // So finally 8 "sides" of the ring have been examined (if it were + // a semi-circle). Most probably, there are only 0 or 1 iterations. + switch (iteration) + { + case 1 : index = (index + size / 4) % size; break; + case 2 : index = (index + size / 8) % size; break; + case 3 : index = (index + size / 4) % size; break; + } + index = get_opposite<Strategy>(index, ring); + + if (visited_indexes.count(index) > 0) + { + // Avoid trying the same starting point more than once + continue; + } + + std::rotate_copy(boost::begin(ring), range::pos(ring, index), + boost::end(ring), rotated.begin()); + + // Close the rotated copy + rotated.push_back(range::at(ring, index)); + + simplify_range<0>::apply(rotated, out, max_distance, strategy); + + // Verify that what was positive, stays positive (or goes to 0) + // and what was negative stays negative (or goes to 0) + int const output_sign = area_sign(geometry::area(out)); + if (output_sign == input_sign) + { + // Result is considered as satisfactory (usually this is the + // first iteration - only for small rings, having a scale + // similar to simplify_distance, next iterations are tried + return; + } + + // Original is simplified away. Possibly there is a solution + // when another starting point is used + geometry::clear(out); + + if (iteration == 0 + && geometry::perimeter(ring) < 3 * max_distance) + { + // Check if it is useful to iterate. A minimal triangle has a + // perimeter of a bit more than 3 times the simplify distance + return; + } + + // Prepare next try + visited_indexes.insert(index); + rotated.resize(size); + } } }; + struct simplify_polygon { private: template < - std::size_t Minimum, typename IteratorIn, - typename IteratorOut, + typename InteriorRingsOut, typename Distance, typename Strategy > static inline void iterate(IteratorIn begin, IteratorIn end, - IteratorOut it_out, + InteriorRingsOut& interior_rings_out, Distance const& max_distance, Strategy const& strategy) { - for (IteratorIn it_in = begin; it_in != end; ++it_in, ++it_out) + typedef typename boost::range_value<InteriorRingsOut>::type single_type; + for (IteratorIn it = begin; it != end; ++it) { - simplify_range<Minimum>::apply(*it_in, *it_out, max_distance, strategy); + single_type out; + simplify_ring::apply(*it, out, max_distance, strategy); + if (! geometry::is_empty(out)) + { + range::push_back(interior_rings_out, out); + } } } template < - std::size_t Minimum, typename InteriorRingsIn, typename InteriorRingsOut, typename Distance, @@ -154,12 +299,11 @@ private: InteriorRingsOut& interior_rings_out, Distance const& max_distance, Strategy const& strategy) { - traits::resize<InteriorRingsOut>::apply(interior_rings_out, - boost::size(interior_rings_in)); + range::clear(interior_rings_out); - iterate<Minimum>( + iterate( boost::begin(interior_rings_in), boost::end(interior_rings_in), - boost::begin(interior_rings_out), + interior_rings_out, max_distance, strategy); } @@ -168,21 +312,14 @@ public: static inline void apply(Polygon const& poly_in, Polygon& poly_out, Distance const& max_distance, Strategy const& strategy) { - std::size_t const minimum = core_detail::closure::minimum_ring_size - < - geometry::closure<Polygon>::value - >::value; - // Note that if there are inner rings, and distance is too large, // they might intersect with the outer ring in the output, // while it didn't in the input. - simplify_range<minimum>::apply(exterior_ring(poly_in), - exterior_ring(poly_out), - max_distance, strategy); + simplify_ring::apply(exterior_ring(poly_in), exterior_ring(poly_out), + max_distance, strategy); - apply_interior_rings<minimum>(interior_rings(poly_in), - interior_rings(poly_out), - max_distance, strategy); + apply_interior_rings(interior_rings(poly_in), + interior_rings(poly_out), max_distance, strategy); } }; @@ -194,16 +331,19 @@ struct simplify_multi static inline void apply(MultiGeometry const& multi, MultiGeometry& out, Distance const& max_distance, Strategy const& strategy) { - traits::resize<MultiGeometry>::apply(out, boost::size(multi)); + range::clear(out); + + typedef typename boost::range_value<MultiGeometry>::type single_type; - typename boost::range_iterator<MultiGeometry>::type it_out - = boost::begin(out); for (typename boost::range_iterator<MultiGeometry const>::type - it_in = boost::begin(multi); - it_in != boost::end(multi); - ++it_in, ++it_out) + it = boost::begin(multi); it != boost::end(multi); ++it) { - Policy::apply(*it_in, *it_out, max_distance, strategy); + single_type single_out; + Policy::apply(*it, single_out, max_distance, strategy); + if (! geometry::is_empty(single_out)) + { + range::push_back(out, single_out); + } } } }; @@ -236,7 +376,7 @@ struct simplify<Point, point_tag> } }; - +// Linestring, keep 2 points (unless those points are the same) template <typename Linestring> struct simplify<Linestring, linestring_tag> : detail::simplify::simplify_range<2> @@ -244,13 +384,7 @@ struct simplify<Linestring, linestring_tag> template <typename Ring> struct simplify<Ring, ring_tag> - : detail::simplify::simplify_range - < - core_detail::closure::minimum_ring_size - < - geometry::closure<Ring>::value - >::value - > + : detail::simplify::simplify_ring {}; template <typename Polygon> |