File indexing completed on 2024-05-26 11:34:05

0001 // SPDX-License-Identifier: LGPL-2.1-or-later
0002 //
0003 // SPDX-FileCopyrightText: 2016 Dennis Nienhüser <nienhueser@kde.org>
0004 //
0005 
0006 #include "PeakAnalyzer.h"
0007 #include "GeoDataPlacemark.h"
0008 #include "MarbleMath.h"
0009 #include "OsmPlacemarkData.h"
0010 
0011 #include <QSet>
0012 #include <QMap>
0013 
0014 namespace Marble {
0015 
0016 PeakAnalyzer::Peaks PeakAnalyzer::peaksNear(const GeoDataPlacemark* placemark, const Peaks &peaks, double maxDistance)
0017 {
0018     // If this turns out to become a bottleneck due to quadratic runtime, use kd-tree via nanoflann from
0019     // https://github.com/jlblancoc/nanoflann to speed it up.
0020     Peaks neighbors;
0021     for (auto peak: peaks) {
0022         if (peak->coordinate().sphericalDistanceTo(placemark->coordinate()) < maxDistance) {
0023             neighbors << peak;
0024         }
0025     }
0026     return neighbors;
0027 }
0028 
0029 void PeakAnalyzer::dbScan(const Peaks &peaks, double maxDistance, int minPoints)
0030 {
0031     QSet<GeoDataPlacemark*> visited;
0032     QMap<GeoDataPlacemark*, PeakCluster*> associations;
0033     Peaks noise;
0034     PeakClusters clusters;
0035     for(auto peak: peaks) {
0036         if (visited.contains(peak)) {
0037             continue;
0038         }
0039         visited << peak;
0040         auto neighbors = peaksNear(peak, peaks, maxDistance);
0041         if (neighbors.size() < minPoints) {
0042             noise << peak;
0043         } else {
0044             PeakCluster* fit = nullptr;
0045             for (auto &cluster: clusters) {
0046                 for (auto placemark: cluster) {
0047                     if (peak->coordinate().sphericalDistanceTo(placemark->coordinate()) < maxDistance) {
0048                         fit = &cluster;
0049                     }
0050                 }
0051             }
0052             if (!fit) {
0053                 clusters << PeakCluster();
0054                 fit = &clusters.last();
0055             }
0056 
0057             while (!neighbors.isEmpty()) {
0058                 auto neighbor = neighbors.front();
0059                 neighbors.pop_front();
0060                 if (!visited.contains(neighbor)) {
0061                     visited << neighbor;
0062                     auto const moreNeighbors = peaksNear(neighbor, peaks, maxDistance);
0063                     if (moreNeighbors.size() >= minPoints) {
0064                         neighbors += moreNeighbors;
0065                     }
0066                 }
0067                 if (associations[neighbor] == nullptr) {
0068                     *fit << neighbor;
0069                     associations[neighbor] = fit;
0070                 }
0071             }
0072         }
0073     }
0074 
0075     for (auto &cluster: clusters) {
0076         Q_ASSERT(!cluster.isEmpty());
0077         std::sort(cluster.begin(), cluster.end(), [](GeoDataPlacemark* a, GeoDataPlacemark* b) {
0078             return a->coordinate().altitude() > b->coordinate().altitude();
0079         });
0080         bool first = true;
0081         for (auto peak: cluster) {
0082             peak->osmData().addTag(QLatin1String("marbleZoomLevel"), first ? QLatin1String("11") : QLatin1String("13"));
0083             first = false;
0084         }
0085     }
0086     for (auto peak: noise) {
0087         peak->osmData().addTag(QLatin1String("marbleZoomLevel"), QLatin1String("11"));
0088     }
0089 }
0090 
0091 void PeakAnalyzer::determineZoomLevel(const QVector<GeoDataPlacemark*> &placemarks)
0092 {
0093     QVector<GeoDataPlacemark*> peaks;
0094     std::copy_if(placemarks.begin(), placemarks.end(), std::back_inserter(peaks), [](GeoDataPlacemark* placemark) {
0095         return placemark->visualCategory() == GeoDataPlacemark::NaturalPeak; });
0096     double const maxDistance = 3000.0 / EARTH_RADIUS;
0097     dbScan(peaks, maxDistance, 2);
0098 }
0099 
0100 
0101 
0102 
0103 }