polygonsimplifier.cpp 1.89 KB
Newer Older
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 <vkrause@kde.org>

    SPDX-License-Identifier: LGPL-2.0-or-later
*/

#include "polygonsimplifier.h"

#include <osm/geomath.h>

#include <QDebug>
#include <QPolygonF>

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<QPointF>({*begin, (*std::prev(end))}));
}

42
QPolygonF PolygonSimplifier::douglasPeucker(const QPolygonF &poly, double threshold)
43
{
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() });
    }

55
56
    return result;
}