polygonsimplifier.cpp 1.89 KB
 Volker Krause committed Apr 19, 2021 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ``````/* SPDX-FileCopyrightText: 2021 Volker Krause SPDX-License-Identifier: LGPL-2.0-or-later */ #include "polygonsimplifier.h" #include #include #include static QPolygonF douglasPeucker(const QPolygonF::const_iterator &begin, const QPolygonF::const_iterator &end, double threshold) { QPolygonF result; if (std::distance(begin, end) < 3) { std::copy(begin, end, std::back_inserter(result)); return result; } double maxDistance = 0.0; auto maxDistIt = std::next(begin); for (auto it = maxDistIt; it != end; ++it) { const auto d = OSM::distance(OSM::Coordinate((*begin).y(), (*begin).x()), OSM::Coordinate((*std::prev(end)).y(), (*std::prev(end)).x()), OSM::Coordinate((*it).y(), (*it).x())); if (d > maxDistance) { maxDistance = d; maxDistIt = it; } } if (maxDistance >= threshold) { result += douglasPeucker(begin, std::next(maxDistIt), threshold); result.pop_back(); result += douglasPeucker(maxDistIt, end, threshold); return result; } return QPolygonF(QVector({*begin, (*std::prev(end))})); } `````` Volker Krause committed Apr 20, 2021 42 ``````QPolygonF PolygonSimplifier::douglasPeucker(const QPolygonF &poly, double threshold) `````` Volker Krause committed Apr 19, 2021 43 ``````{ `````` Volker Krause committed Apr 20, 2021 44 45 46 47 48 49 50 51 52 53 54 `````` auto result = douglasPeucker(poly.begin(), poly.end(), threshold); qDebug() << "got" << poly.size() << "dropped" << poly.size() - result.size() << "remaining" << result.size(); // if the polygon itself is smaller than the threshold, the result can deteriorate into // an area-less structure, take the bounding rect in that case if (result.size() < 4) { qDebug() << " result deteriorated, taking bounding rect instead"; const auto bbox = poly.boundingRect(); return QPolygonF({ bbox.topLeft(), bbox.topRight(), bbox.bottomRight(), bbox.bottomLeft(), bbox.topLeft() }); } `````` Volker Krause committed Apr 19, 2021 55 56 `````` return result; }``````