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