File indexing completed on 2024-07-14 14:25:31

0001 // SPDX-License-Identifier: LGPL-2.1-or-later
0002 //
0003 // SPDX-FileCopyrightText: 2016 Akshat Tandon <akshat.tandon@research.iiit.ac.in>
0004 //
0005 
0006 #ifndef MARBLE_NODEREDUCER_H
0007 #define MARBLE_NODEREDUCER_H
0008 
0009 #include "OsmPlacemarkData.h"
0010 #include "VectorClipper.h"
0011 
0012 namespace Marble {
0013 
0014 class NodeReducer {
0015 public:
0016     NodeReducer(GeoDataDocument* document, const TileId &tileId);
0017 
0018     qint64 removedNodes() const;
0019     qint64 remainingNodes() const;
0020 
0021 private:
0022     qreal epsilonFor(qreal multiplier) const;
0023     qreal perpendicularDistance(const GeoDataCoordinates &a, const GeoDataCoordinates &b, const GeoDataCoordinates &c) const;
0024     bool touchesTileBorder(const GeoDataCoordinates &coordinates) const;
0025 
0026     GeoDataLinearRing* reducedRing(const GeoDataLinearRing& prevRing,
0027                                    GeoDataPlacemark* placemark,
0028                                    const GeoDataPlacemark::GeoDataVisualCategory& visualCategory);
0029     GeoDataPolygon* reducedPolygon(const GeoDataPolygon& prevPolygon,
0030                                    GeoDataPlacemark* placemark,
0031                                    const GeoDataPlacemark::GeoDataVisualCategory& visualCategory);
0032 
0033     template<class T>
0034     void reduce(T const & lineString, OsmPlacemarkData& osmData, GeoDataPlacemark::GeoDataVisualCategory visualCategory, T* reducedLine)
0035     {
0036         bool const isArea = lineString.isClosed() && VectorClipper::canBeArea(visualCategory);
0037         qreal const epsilon = epsilonFor(isArea ? 45.0 : 30.0);
0038         *reducedLine = douglasPeucker(lineString, osmData, epsilon);
0039 
0040         qint64 prevSize = lineString.size();
0041         qint64 reducedSize = reducedLine->size();
0042         m_removedNodes += (prevSize - reducedSize);
0043         m_remainingNodes += reducedSize;
0044     }
0045 
0046     template<class T>
0047     T extract(T const & lineString, int start, int end) const
0048     {
0049         T result;
0050         for (int i=start; i<=end; ++i) {
0051             result << lineString[i];
0052         }
0053         return result;
0054     }
0055 
0056     template<class T>
0057     T merge(T const & a, T const &b) const
0058     {
0059         T result = a;
0060         int const index = a.size();
0061         result << b;
0062         result.remove(index);
0063         return result;
0064     }
0065 
0066     template<class T>
0067     T douglasPeucker(T const & lineString, const OsmPlacemarkData &osmData, qreal epsilon) const
0068     {
0069         if (lineString.size() < 3) {
0070             return lineString;
0071         }
0072 
0073         double maxDistance = 0.0;
0074         int index = 1;
0075         int const end = lineString.size()-1;
0076         for (int i = 1; i<end; ++i) {
0077             double const distance = perpendicularDistance(lineString[i], lineString[0], lineString[end]);
0078             if (distance > maxDistance) {
0079                 index = i;
0080                 maxDistance = distance;
0081             }
0082         }
0083 
0084         if (maxDistance >= epsilon) {
0085             T const left = douglasPeucker(extract(lineString, 0, index), osmData, epsilon);
0086             T const right = douglasPeucker(extract(lineString, index, end), osmData, epsilon);
0087             return merge(left, right);
0088         }
0089 
0090         T result;
0091         result << lineString[0];
0092         for (int i=1; i<end; ++i) {
0093             // even if under the Douglas Peucker threshold, we keep the following nodes:
0094             // - nodes at a tile border
0095             // - nodes containing any OSM tag themselves
0096             // - nodes adjacent to synthetic nodes introduced by clipping. This is to avoid
0097             //   synthetic only line segments that geometry reassembly on the client might
0098             //   remove entirely and thus distort the original geometry.
0099             bool const keepNode = touchesTileBorder(lineString[i]) || !osmData.nodeReference(lineString[i]).isEmpty()
0100                 || osmData.nodeReference(lineString[i-1]).id() < 0 || ((i + 1) < end && osmData.nodeReference(lineString[i+1]).id() < 0);
0101             if (keepNode) {
0102                 result << lineString[i];
0103             }
0104         }
0105         result << lineString[end];
0106         return result;
0107     }
0108 
0109     qint64 m_removedNodes;
0110     qint64 m_remainingNodes;
0111 
0112     int m_zoomLevel;
0113     double m_tileBoundary[4];
0114     enum Boundary {
0115         West = 0,
0116         North = 1,
0117         East = 2,
0118         South = 3
0119     };
0120 };
0121 
0122 }
0123 
0124 #endif