1 // SPDX-License-Identifier: LGPL-2.1-or-later
2 //
3 // SPDX-FileCopyrightText: 2016 Akshat Tandon <akshat.tandon@research.iiit.ac.in>
4 //
5 
6 #ifndef MARBLE_NODEREDUCER_H
7 #define MARBLE_NODEREDUCER_H
8 
9 #include "OsmPlacemarkData.h"
10 #include "VectorClipper.h"
11 
12 namespace Marble {
13 
14 class NodeReducer {
15 public:
16     NodeReducer(GeoDataDocument* document, const TileId &tileId);
17 
18     qint64 removedNodes() const;
19     qint64 remainingNodes() const;
20 
21 private:
22     qreal epsilonFor(qreal multiplier) const;
23     qreal perpendicularDistance(const GeoDataCoordinates &a, const GeoDataCoordinates &b, const GeoDataCoordinates &c) const;
24     bool touchesTileBorder(const GeoDataCoordinates &coordinates) const;
25     void setBorderPoints(OsmPlacemarkData &osmData, const QVector<int> &borderPoints, int length) const;
26 
27     GeoDataLinearRing* reducedRing(const GeoDataLinearRing& prevRing,
28                                    GeoDataPlacemark* placemark,
29                                    const GeoDataPlacemark::GeoDataVisualCategory& visualCategory);
30     GeoDataPolygon* reducedPolygon(const GeoDataPolygon& prevPolygon,
31                                    GeoDataPlacemark* placemark,
32                                    const GeoDataPlacemark::GeoDataVisualCategory& visualCategory);
33 
34     template<class T>
reduce(T const & lineString,OsmPlacemarkData & osmData,GeoDataPlacemark::GeoDataVisualCategory visualCategory,T * reducedLine)35     void reduce(T const & lineString, OsmPlacemarkData& osmData, GeoDataPlacemark::GeoDataVisualCategory visualCategory, T* reducedLine)
36     {
37         bool const isArea = lineString.isClosed() && VectorClipper::canBeArea(visualCategory);
38         qreal const epsilon = epsilonFor(isArea ? 45.0 : 30.0);
39         *reducedLine = douglasPeucker(lineString, osmData, epsilon);
40 
41         qint64 prevSize = lineString.size();
42         qint64 reducedSize = reducedLine->size();
43         m_removedNodes += (prevSize - reducedSize);
44         m_remainingNodes += reducedSize;
45 
46         QVector<int> borderPoints;
47         int index = 0;
48         for (auto const &coordinate: *reducedLine) {
49             if (touchesTileBorder(coordinate)) {
50                 borderPoints << index;
51             }
52             ++index;
53         }
54         setBorderPoints(osmData, borderPoints, reducedLine->size());
55     }
56 
57     template<class T>
extract(T const & lineString,int start,int end)58     T extract(T const & lineString, int start, int end) const
59     {
60         T result;
61         for (int i=start; i<=end; ++i) {
62             result << lineString[i];
63         }
64         return result;
65     }
66 
67     template<class T>
merge(T const & a,T const & b)68     T merge(T const & a, T const &b) const
69     {
70         T result = a;
71         int const index = a.size();
72         result << b;
73         result.remove(index);
74         return result;
75     }
76 
77     template<class T>
douglasPeucker(T const & lineString,const OsmPlacemarkData & osmData,qreal epsilon)78     T douglasPeucker(T const & lineString, const OsmPlacemarkData &osmData, qreal epsilon) const
79     {
80         if (lineString.size() < 3) {
81             return lineString;
82         }
83 
84         double maxDistance = 0.0;
85         int index = 1;
86         int const end = lineString.size()-1;
87         for (int i = 1; i<end; ++i) {
88             double const distance = perpendicularDistance(lineString[i], lineString[0], lineString[end]);
89             if (distance > maxDistance) {
90                 index = i;
91                 maxDistance = distance;
92             }
93         }
94 
95         if (maxDistance >= epsilon) {
96             T const left = douglasPeucker(extract(lineString, 0, index), osmData, epsilon);
97             T const right = douglasPeucker(extract(lineString, index, end), osmData, epsilon);
98             return merge(left, right);
99         }
100 
101         T result;
102         result << lineString[0];
103         for (int i=1; i<end; ++i) {
104             bool const keepNode = touchesTileBorder(lineString[i]) || !osmData.nodeReference(lineString[i]).isEmpty();
105             if (keepNode) {
106                 result << lineString[i];
107             }
108         }
109         result << lineString[end];
110         return result;
111     }
112 
113     qint64 m_removedNodes;
114     qint64 m_remainingNodes;
115 
116     int m_zoomLevel;
117     double m_tileBoundary[4];
118     enum Boundary {
119         West = 0,
120         North = 1,
121         East = 2,
122         South = 3
123     };
124 };
125 
126 }
127 
128 #endif
129