diff options
author | Alex Zolotarev <deathbaba@gmail.com> | 2010-12-05 19:24:16 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-22 22:33:57 +0300 |
commit | d6e12b7ce4bcbf0ccd1c07eb25de143422913c34 (patch) | |
tree | a7e910c330ce4da9b4f2d8be76067adece2561c4 /geometry/simplification.hpp |
One Month In Minsk. Made in Belarus.
Diffstat (limited to 'geometry/simplification.hpp')
-rw-r--r-- | geometry/simplification.hpp | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/geometry/simplification.hpp b/geometry/simplification.hpp new file mode 100644 index 0000000000..33e2934557 --- /dev/null +++ b/geometry/simplification.hpp @@ -0,0 +1,112 @@ +#pragma once +#include "../base/base.hpp" +#include "../base/stl_add.hpp" +#include "../base/logging.hpp" +#include "../std/algorithm.hpp" +#include "../std/utility.hpp" +#include "../std/vector.hpp" + +// Polyline simplification algorithms. +// +// SimplifyXXX() should be used to simplify polyline for a given epsilon. +// (!) They do not include the last point to the simplification, the calling side should do it. + +namespace impl +{ + +template <typename DistanceF, typename IterT> +pair<double, IterT> MaxDistance(IterT first, IterT last) +{ + if (last - first <= 1) + return pair<double, IterT>(0.0, first); + + pair<double, IterT> res(0.0, first); + DistanceF distanceF(*first, *last); + for (IterT i = first + 1; i != last; ++i) + { + double const dist = distanceF(*i); + if (dist > res.first) + { + res.first = dist; + res.second = i; + } + } + return res; +} + +// Actual SimplifyDP implementation. Takes OutT by reference. +template <typename DistanceF, typename IterT, typename OutT> +void SimplifyDP(IterT first, IterT last, double epsilon, OutT & out) +{ + pair<double, IterT> maxDist = impl::MaxDistance<DistanceF>(first, last); + if (maxDist.first < epsilon) + { + out(*first); + return; + } + impl::SimplifyDP<DistanceF>(first, maxDist.second, epsilon, out); + impl::SimplifyDP<DistanceF>(maxDist.second, last, epsilon, out); +} + +struct SimplifyOptimalRes +{ + SimplifyOptimalRes() : m_PointCount(-1) {} + SimplifyOptimalRes(int32_t nextPoint, uint32_t pointCount) + : m_NextPoint(nextPoint), m_PointCount(pointCount) {} + + int32_t m_NextPoint; + uint32_t m_PointCount; +}; + +} + +// Douglas-Peucker algorithm. +// Iteratively includes the point with max distance form the current simplification. +// Average O(n log n), worst case O(n^2). +template <typename DistanceF, typename IterT, typename OutT> +void SimplifyDP(IterT first, IterT last, double epsilon, OutT out) +{ + impl::SimplifyDP<DistanceF>(first, last, epsilon, out); +} + +// Dynamic programming near-optimal simplification. +// Uses O(n) additional memory. +// Worst case O(n^3) performance, average O(n*k^2), where k is kMaxFalseLookAhead - parameter, +// which limits the number of points to try, that produce error > epsilon. +// Essentially, it's a trade-off between optimality and performance. +// Values around 20 - 200 are reasonable. +template <typename DistanceF, typename IterT, typename OutT> +void SimplifyNearOptimal(int kMaxFalseLookAhead, IterT first, IterT last, double epsilon, OutT out) +{ + int32_t const n = last - first + 1; + if (n <= 2) + { + out(*first); + return; + } + + vector<impl::SimplifyOptimalRes> F(n); + F[n - 1] = impl::SimplifyOptimalRes(n, 1); + for (int32_t i = n - 2; i >= 0; --i) + { + for (int32_t falseCount = 0, j = i + 1; j < n && falseCount < kMaxFalseLookAhead; ++j) + { + uint32_t const newPointCount = F[j].m_PointCount + 1; + if (newPointCount < F[i].m_PointCount) + { + if (impl::MaxDistance<DistanceF>(first + i, first + j).first < epsilon) + { + F[i].m_NextPoint = j; + F[i].m_PointCount = newPointCount; + } + else + { + ++falseCount; + } + } + } + } + + for (int32_t i = 0; i < n - 1; i = F[i].m_NextPoint) + out(*(first + i)); +} |