summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDennis Nienhüser <nienhueser@kde.org>2016-11-05 15:20:40 (GMT)
committerFriedrich W. H. Kossebau <kossebau@kde.org>2016-11-05 16:49:35 (GMT)
commitc22ac0db3cdbe5ecfac5694ce484f0c5deb96429 (patch)
treedf5f4d8944ccaebf1e549742125346a919703a63
parentc22ed98e26ef126f456672bad9706916e1a39f61 (diff)
Cluster mountain peaks at level 11 and only show the highest
- use dbscan to cluster mountain peaks that are not more than 3 km apart - for each cluster of peaks, show the highest peak at level 11 and all other ones at level 13 only
-rw-r--r--tools/vectorosm-tilecreator/CMakeLists.txt1
-rw-r--r--tools/vectorosm-tilecreator/PeakAnalyzer.cpp108
-rw-r--r--tools/vectorosm-tilecreator/PeakAnalyzer.h31
-rw-r--r--tools/vectorosm-tilecreator/TileDirectory.cpp4
4 files changed, 144 insertions, 0 deletions
diff --git a/tools/vectorosm-tilecreator/CMakeLists.txt b/tools/vectorosm-tilecreator/CMakeLists.txt
index 1e0cab8..f9ef4e1 100644
--- a/tools/vectorosm-tilecreator/CMakeLists.txt
+++ b/tools/vectorosm-tilecreator/CMakeLists.txt
@@ -30,6 +30,7 @@ main.cpp
BaseClipper.cpp
BaseFilter.cpp
NodeReducer.cpp
+PeakAnalyzer.cpp
TagsFilter.cpp
TileIterator.cpp
TileDirectory.cpp
diff --git a/tools/vectorosm-tilecreator/PeakAnalyzer.cpp b/tools/vectorosm-tilecreator/PeakAnalyzer.cpp
new file mode 100644
index 0000000..fc055be
--- /dev/null
+++ b/tools/vectorosm-tilecreator/PeakAnalyzer.cpp
@@ -0,0 +1,108 @@
+//
+// This file is part of the Marble Virtual Globe.
+//
+// This program is free software licensed under the GNU LGPL. You can
+// find a copy of this license in LICENSE.txt in the top directory of
+// the source code.
+//
+// Copyright 2016 Dennis Nienhüser <nienhueser@kde.org>
+//
+
+#include "PeakAnalyzer.h"
+#include "GeoDataPlacemark.h"
+#include "MarbleMath.h"
+#include "OsmPlacemarkData.h"
+
+#include <QSet>
+#include <QMap>
+
+namespace Marble {
+
+PeakAnalyzer::Peaks PeakAnalyzer::peaksNear(const GeoDataPlacemark* placemark, const Peaks &peaks, double maxDistance)
+{
+ // If this turns out to become a bottleneck due to quadratic runtime, use kd-tree via nanoflann from
+ // https://github.com/jlblancoc/nanoflann to speed it up.
+ Peaks neighbors;
+ for (auto peak: peaks) {
+ if (distanceSphere(peak->coordinate(), placemark->coordinate()) < maxDistance) {
+ neighbors << peak;
+ }
+ }
+ return neighbors;
+}
+
+void PeakAnalyzer::dbScan(const Peaks &peaks, double maxDistance, int minPoints)
+{
+ QSet<GeoDataPlacemark*> visited;
+ QMap<GeoDataPlacemark*, PeakCluster*> associations;
+ Peaks noise;
+ PeakClusters clusters;
+ for(auto peak: peaks) {
+ if (visited.contains(peak)) {
+ continue;
+ }
+ visited << peak;
+ auto neighbors = peaksNear(peak, peaks, maxDistance);
+ if (neighbors.size() < minPoints) {
+ noise << peak;
+ } else {
+ PeakCluster* fit = nullptr;
+ for (auto &cluster: clusters) {
+ for (auto placemark: cluster) {
+ if (distanceSphere(peak->coordinate(), placemark->coordinate()) < maxDistance) {
+ fit = &cluster;
+ }
+ }
+ }
+ if (!fit) {
+ clusters << PeakCluster();
+ fit = &clusters.last();
+ }
+
+ while (!neighbors.isEmpty()) {
+ auto neighbor = neighbors.front();
+ neighbors.pop_front();
+ if (!visited.contains(neighbor)) {
+ visited << neighbor;
+ auto const moreNeighbors = peaksNear(neighbor, peaks, maxDistance);
+ if (moreNeighbors.size() >= minPoints) {
+ neighbors += moreNeighbors;
+ }
+ }
+ if (associations[neighbor] == nullptr) {
+ *fit << neighbor;
+ associations[neighbor] = fit;
+ }
+ }
+ }
+ }
+
+ for (auto &cluster: clusters) {
+ Q_ASSERT(!cluster.isEmpty());
+ std::sort(cluster.begin(), cluster.end(), [](GeoDataPlacemark* a, GeoDataPlacemark* b) {
+ return a->coordinate().altitude() > b->coordinate().altitude();
+ });
+ bool first = true;
+ for (auto peak: cluster) {
+ peak->osmData().addTag(QLatin1String("marbleZoomLevel"), first ? QLatin1String("11") : QLatin1String("13"));
+ first = false;
+ }
+ }
+ for (auto peak: noise) {
+ peak->osmData().addTag(QLatin1String("marbleZoomLevel"), QLatin1String("11"));
+ }
+}
+
+void PeakAnalyzer::determineZoomLevel(const QVector<GeoDataPlacemark*> &placemarks)
+{
+ QVector<GeoDataPlacemark*> peaks;
+ std::copy_if(placemarks.begin(), placemarks.end(), std::back_inserter(peaks), [](GeoDataPlacemark* placemark) {
+ return placemark->visualCategory() == GeoDataPlacemark::NaturalPeak; });
+ double const maxDistance = 3000.0 / EARTH_RADIUS;
+ dbScan(peaks, maxDistance, 2);
+}
+
+
+
+
+}
diff --git a/tools/vectorosm-tilecreator/PeakAnalyzer.h b/tools/vectorosm-tilecreator/PeakAnalyzer.h
new file mode 100644
index 0000000..2513a9b
--- /dev/null
+++ b/tools/vectorosm-tilecreator/PeakAnalyzer.h
@@ -0,0 +1,31 @@
+//
+// This file is part of the Marble Virtual Globe.
+//
+// This program is free software licensed under the GNU LGPL. You can
+// find a copy of this license in LICENSE.txt in the top directory of
+// the source code.
+//
+// Copyright 2016 Dennis Nienhüser <nienhueser@kde.org>
+//
+
+#include <QVector>
+
+namespace Marble {
+
+class GeoDataPlacemark;
+
+class PeakAnalyzer
+{
+public:
+ static void determineZoomLevel(const QVector<GeoDataPlacemark*> &placemarks);
+
+private:
+ typedef QVector<GeoDataPlacemark*> Peaks;
+ typedef QVector<GeoDataPlacemark*> PeakCluster;
+ typedef QVector<PeakCluster> PeakClusters;
+
+ static Peaks peaksNear(const GeoDataPlacemark* placemark, const Peaks &peaks, double maxDistance);
+ static void dbScan(const Peaks &peaks, double maxDistance, int minPoints);
+};
+
+}
diff --git a/tools/vectorosm-tilecreator/TileDirectory.cpp b/tools/vectorosm-tilecreator/TileDirectory.cpp
index b9b39b6..a4b6c35 100644
--- a/tools/vectorosm-tilecreator/TileDirectory.cpp
+++ b/tools/vectorosm-tilecreator/TileDirectory.cpp
@@ -13,6 +13,7 @@
#include <GeoDataDocumentWriter.h>
#include "MarbleZipReader.h"
#include <GeoDataLatLonAltBox.h>
+#include "PeakAnalyzer.h"
#include <QFileInfo>
#include <QDebug>
@@ -86,6 +87,9 @@ QSharedPointer<GeoDataDocument> TileDirectory::load(int zoomLevel, int tileX, in
m_tileY = tile.y();
QString const filename = QString("%1/%2/%3.%4").arg(m_baseDir).arg(tile.x()).arg(tile.y()).arg("o5m");
m_landmass = open(filename, m_manager);
+ if (m_landmass) {
+ PeakAnalyzer::determineZoomLevel(m_landmass->placemarkList());
+ }
return m_landmass;
}