ViewOSMMap/lodsimplifier.cpp at main · tigerlet/ViewOSMMap · GitHub

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include "lodsimplifier.h"
#include <cmath>

QVector<int> LodSimplifier::simplifyDouglasPeucker(const QVector<QPointF> &points, double tolerance)
{
    if (points.size() <= 2) {
        QVector<int> result;
        for (int i = 0; i < points.size(); ++i) {
            result.append(i);
        }
        return result;
    }

    QVector<bool> keep(points.size(), false);
    keep[0] = true;
    keep[points.size() - 1] = true;

    simplifyRecursive(points, 0, points.size() - 1, tolerance, keep);

    QVector<int> result;
    for (int i = 0; i < keep.size(); ++i) {
        if (keep[i]) {
            result.append(i);
        }
    }

    return result;
}

QVector<int> LodSimplifier::simplifyDouglasPeucker(const QVector<QPointF> &points, int lodLevel)
{
    double tolerance = toleranceForLod(lodLevel);
    return simplifyDouglasPeucker(points, tolerance);
}

double LodSimplifier::toleranceForLod(int lodLevel)
{
    switch (lodLevel) {
    case LOD_COARSE: return 0.01;    // ~1km precision
    case LOD_MEDIUM: return 0.001;   // ~100m precision
    case LOD_FINE: return 0.0001;    // ~10m precision
    case LOD_FULL: return 0.00001;   // ~1m precision
    default: return 0.001;
    }
}

void LodSimplifier::simplifyRecursive(const QVector<QPointF> &points, int start, int end,
                                      double tolerance, QVector<bool> &keep)
{
    if (end - start <= 1) {
        return;
    }

    double maxDist = 0;
    int maxIdx = -1;

    const QPointF &lineStart = points[start];
    const QPointF &lineEnd = points[end];

    for (int i = start + 1; i < end; ++i) {
        double dist = pointToLineDistance(points[i], lineStart, lineEnd);
        if (dist > maxDist) {
            maxDist = dist;
            maxIdx = i;
        }
    }

    if (maxDist > tolerance && maxIdx != -1) {
        keep[maxIdx] = true;
        simplifyRecursive(points, start, maxIdx, tolerance, keep);
        simplifyRecursive(points, maxIdx, end, tolerance, keep);
    }
}

double LodSimplifier::pointToLineDistance(const QPointF &point, const QPointF &lineStart, const QPointF &lineEnd)
{
    double A = point.x() - lineStart.x();
    double B = point.y() - lineStart.y();
    double C = lineEnd.x() - lineStart.x();
    double D = lineEnd.y() - lineStart.y();

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = -1;

    if (len_sq != 0) {
        param = dot / len_sq;
    }

    double xx, yy;

    if (param < 0) {
        xx = lineStart.x();
        yy = lineStart.y();
    } else if (param > 1) {
        xx = lineEnd.x();
        yy = lineEnd.y();
    } else {
        xx = lineStart.x() + param * C;
        yy = lineStart.y() + param * D;
    }

    double dx = point.x() - xx;
    double dy = point.y() - yy;
    return sqrt(dx * dx + dy * dy);
}