summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDennis Nienhüser <nienhueser@kde.org>2016-10-03 09:33:09 (GMT)
committerDennis Nienhüser <nienhueser@kde.org>2016-10-03 10:13:50 (GMT)
commitde1208749510aff11ce00d715ad075c8cd38ae0b (patch)
treedf486d91c2b8759642b064f79bb553d18152698f
parent9636c8c18d6166dbe10898f7ba5267bfde053824 (diff)
Use a tile pyramid to speed up clipping
Same approach as in GeoGraphicsScene. Placemarks are assigned a tile level that fully contains them once. When clipping to some boundary box, only those placemarks on the path towards the top of the pyramid can intersect them. Note that this is only a heuristic; checking the actual bounding box intersection again afterwards still rules out a lot of placemarks that don't actually intersect. Rough speed comparison for different approaches: A) Slow: clip all placemarks directly B) Medium: clip all placemarks based on tile pyramid C) Fast: clip all placemarks that intersect with the bounding box D) Very fast: clip all placemarks based on tile pyramid that also intersect with the bounding box C) is the old implementation, B) something I tested locally and C) the new implementation.
-rw-r--r--tools/vectorosm-tilecreator/TileDirectory.cpp9
-rw-r--r--tools/vectorosm-tilecreator/TileDirectory.h3
-rw-r--r--tools/vectorosm-tilecreator/VectorClipper.cpp49
-rw-r--r--tools/vectorosm-tilecreator/VectorClipper.h7
-rw-r--r--tools/vectorosm-tilecreator/main.cpp11
5 files changed, 64 insertions, 15 deletions
diff --git a/tools/vectorosm-tilecreator/TileDirectory.cpp b/tools/vectorosm-tilecreator/TileDirectory.cpp
index de4593b..340f461 100644
--- a/tools/vectorosm-tilecreator/TileDirectory.cpp
+++ b/tools/vectorosm-tilecreator/TileDirectory.cpp
@@ -30,7 +30,7 @@ using namespace std;
namespace Marble {
-TileDirectory::TileDirectory(TileType tileType, const QString &cacheDir, ParsingRunnerManager &manager, QString const &extension) :
+TileDirectory::TileDirectory(TileType tileType, const QString &cacheDir, ParsingRunnerManager &manager, QString const &extension, int maxZoomLevel) :
m_cacheDir(cacheDir),
m_baseDir(),
m_manager(manager),
@@ -40,7 +40,8 @@ TileDirectory::TileDirectory(TileType tileType, const QString &cacheDir, Parsing
m_tagZoomLevel(-1),
m_extension(extension),
m_tileType(tileType),
- m_landmassFile("land-polygons-split-4326.zip")
+ m_landmassFile("land-polygons-split-4326.zip"),
+ m_maxZoomLevel(maxZoomLevel)
{
if (m_tileType == Landmass) {
m_zoomLevel = 7;
@@ -124,7 +125,7 @@ GeoDataDocument* TileDirectory::clip(int zoomLevel, int tileX, int tileY)
setTagZoomLevel(zoomLevel);
GeoDataDocument* input = m_tagsFilter ? m_tagsFilter->accepted() : m_landmass.data();
if (input) {
- m_clipper = QSharedPointer<VectorClipper>(new VectorClipper(input));
+ m_clipper = QSharedPointer<VectorClipper>(new VectorClipper(input, m_maxZoomLevel));
}
}
return m_clipper ? m_clipper->clipTo(zoomLevel, tileX, tileY) : nullptr;
@@ -372,7 +373,7 @@ void TileDirectory::createTiles() const
} else {
if (!map) {
map = open(m_inputFile, m_manager);
- clipper = QSharedPointer<VectorClipper>(new VectorClipper(map.data()));
+ clipper = QSharedPointer<VectorClipper>(new VectorClipper(map.data(), m_zoomLevel));
}
auto tile = clipper->clipTo(m_zoomLevel, tileId.x(), tileId.y());
if (!GeoDataDocumentWriter::write(outputFile, *tile)) {
diff --git a/tools/vectorosm-tilecreator/TileDirectory.h b/tools/vectorosm-tilecreator/TileDirectory.h
index 9da7cdc..c2d4f2c 100644
--- a/tools/vectorosm-tilecreator/TileDirectory.h
+++ b/tools/vectorosm-tilecreator/TileDirectory.h
@@ -55,7 +55,7 @@ public:
OpenStreetMap
};
- TileDirectory(TileType tileType, const QString &cacheDir, ParsingRunnerManager &manager, const QString &extension);
+ TileDirectory(TileType tileType, const QString &cacheDir, ParsingRunnerManager &manager, const QString &extension, int maxZoomLevel);
QSharedPointer<GeoDataDocument> load(int zoomLevel, int tileX, int tileY);
void setInputFile(const QString &filename);
@@ -100,6 +100,7 @@ private:
QNetworkAccessManager m_downloadManager;
QString m_landmassFile;
QSharedPointer<Download> m_download;
+ int m_maxZoomLevel;
};
}
diff --git a/tools/vectorosm-tilecreator/VectorClipper.cpp b/tools/vectorosm-tilecreator/VectorClipper.cpp
index d307a79..4ff30a1 100644
--- a/tools/vectorosm-tilecreator/VectorClipper.cpp
+++ b/tools/vectorosm-tilecreator/VectorClipper.cpp
@@ -19,6 +19,7 @@
#include "GeoDataPlacemark.h"
#include "OsmPlacemarkData.h"
#include "OsmObjectManager.h"
+#include "TileCoordsPyramid.h"
#include "clipper/clipper.hpp"
@@ -28,10 +29,24 @@
namespace Marble {
-VectorClipper::VectorClipper(GeoDataDocument* document) :
- BaseFilter(document)
+VectorClipper::VectorClipper(GeoDataDocument* document, int maxZoomLevel) :
+ BaseFilter(document),
+ m_maxZoomLevel(maxZoomLevel)
{
-
+ foreach(auto placemark, placemarks()) {
+ // Select zoom level such that the placemark fits in a single tile
+ int zoomLevel;
+ qreal north, south, east, west;
+ placemark->geometry()->latLonAltBox().boundaries(north, south, east, west);
+ for (zoomLevel = maxZoomLevel; zoomLevel >= 0; --zoomLevel) {
+ if (TileId::fromCoordinates(GeoDataCoordinates(west, north), zoomLevel) ==
+ TileId::fromCoordinates(GeoDataCoordinates(east, south), zoomLevel)) {
+ break;
+ }
+ }
+ TileId const key = TileId::fromCoordinates(GeoDataCoordinates(west, north), zoomLevel);
+ m_items[key] << placemark;
+ }
}
GeoDataDocument *VectorClipper::clipTo(const GeoDataLatLonBox &tileBoundary)
@@ -43,9 +58,9 @@ GeoDataDocument *VectorClipper::clipTo(const GeoDataLatLonBox &tileBoundary)
GeoDataDocument* tile = new GeoDataDocument();
auto const clip = clipPath(tileBoundary);
- foreach (GeoDataPlacemark const * placemark, placemarks()) {
+ foreach (GeoDataPlacemark const * placemark, potentialIntersections(tileBoundary)) {
GeoDataGeometry const * const geometry = placemark ? placemark->geometry() : nullptr;
- if(geometry && tileBoundary.intersects(geometry->latLonAltBox())) {
+ if (geometry && tileBoundary.intersects(geometry->latLonAltBox())) {
if(geometry->nodeType() == GeoDataTypes::GeoDataPolygonType) {
clipPolygon(placemark, clip, tile);
} else if (geometry->nodeType() == GeoDataTypes::GeoDataLineStringType) {
@@ -198,6 +213,30 @@ GeoDataDocument *VectorClipper::clipToBaseClipper(const GeoDataLatLonBox &tileBo
return tile;
}
+QVector<GeoDataPlacemark *> VectorClipper::potentialIntersections(const GeoDataLatLonBox &box) const
+{
+ qreal north, south, east, west;
+ box.boundaries(north, south, east, west);
+ TileId const topLeft = TileId::fromCoordinates(GeoDataCoordinates(west, north), m_maxZoomLevel);
+ TileId const bottomRight = TileId::fromCoordinates(GeoDataCoordinates(east, south), m_maxZoomLevel);
+ QRect rect;
+ rect.setCoords(topLeft.x(), topLeft.y(), bottomRight.x(), bottomRight.y());
+
+ TileCoordsPyramid pyramid(0, m_maxZoomLevel);
+ pyramid.setBottomLevelCoords(rect);
+ QVector<GeoDataPlacemark *> result;
+ for (int level = pyramid.topLevel(), maxLevel = pyramid.bottomLevel(); level <= maxLevel; ++level) {
+ int x1, y1, x2, y2;
+ pyramid.coords(level).getCoords(&x1, &y1, &x2, &y2);
+ for (int x = x1; x <= x2; ++x) {
+ for (int y = y1; y <= y2; ++y) {
+ result << m_items.value(TileId(0, level, x, y));
+ }
+ }
+ }
+ return result;
+}
+
GeoDataDocument *VectorClipper::clipTo(unsigned int zoomLevel, unsigned int tileX, unsigned int tileY)
{
unsigned int N = pow(2, zoomLevel);
diff --git a/tools/vectorosm-tilecreator/VectorClipper.h b/tools/vectorosm-tilecreator/VectorClipper.h
index 8f53471..7143e95 100644
--- a/tools/vectorosm-tilecreator/VectorClipper.h
+++ b/tools/vectorosm-tilecreator/VectorClipper.h
@@ -16,6 +16,7 @@
#include <GeoDataLatLonBox.h>
#include "GeoDataPlacemark.h"
+#include <TileId.h>
#include "clipper/clipper.hpp"
@@ -26,13 +27,14 @@ class GeoDataLinearRing;
class VectorClipper : public BaseFilter
{
public:
- explicit VectorClipper(GeoDataDocument* document);
+ VectorClipper(GeoDataDocument* document, int maxZoomLevel);
GeoDataDocument* clipTo(const GeoDataLatLonBox &box);
GeoDataDocument* clipTo(unsigned int zoomLevel, unsigned int tileX, unsigned int tileY);
private:
GeoDataDocument* clipToBaseClipper(const GeoDataLatLonBox &box);
+ QVector<GeoDataPlacemark*> potentialIntersections(const GeoDataLatLonBox &box) const;
ClipperLib::Path clipPath(const GeoDataLatLonBox &box) const;
template<class T>
@@ -77,6 +79,9 @@ private:
void copyTags(const OsmPlacemarkData &originalPlacemarkData, OsmPlacemarkData& targetOsmData) const;
static qint64 const m_scale = 10000000;
+
+ QMap<TileId, QVector<GeoDataPlacemark*> > m_items;
+ int m_maxZoomLevel;
};
}
diff --git a/tools/vectorosm-tilecreator/main.cpp b/tools/vectorosm-tilecreator/main.cpp
index 1905d49..a81d257 100644
--- a/tools/vectorosm-tilecreator/main.cpp
+++ b/tools/vectorosm-tilecreator/main.cpp
@@ -116,8 +116,11 @@ int main(int argc, char *argv[])
QString inputFileName = args.at(0);
auto const levels = parser.value("zoom-level").split(',');
QVector<unsigned int> zoomLevels;
+ int maxZoomLevel = 0;
foreach(auto const &level, levels) {
- zoomLevels << level.toInt();
+ int const zoomLevel = level.toInt();
+ maxZoomLevel = qMax(zoomLevel, maxZoomLevel);
+ zoomLevels << zoomLevel;
}
if (zoomLevels.isEmpty()) {
@@ -145,7 +148,7 @@ int main(int argc, char *argv[])
if (*zoomLevels.cbegin() <= 9) {
auto map = TileDirectory::open(inputFileName, manager);
- VectorClipper processor(map.data());
+ VectorClipper processor(map.data(), maxZoomLevel);
GeoDataLatLonBox world(85.0, -85.0, 180.0, -180.0, GeoDataCoordinates::Degree);
foreach(auto zoomLevel, zoomLevels) {
TileIterator iter(world, zoomLevel);
@@ -171,12 +174,12 @@ int main(int argc, char *argv[])
}
}
} else {
- TileDirectory mapTiles(TileDirectory::OpenStreetMap, cacheDirectory, manager, extension);
+ TileDirectory mapTiles(TileDirectory::OpenStreetMap, cacheDirectory, manager, extension, maxZoomLevel);
mapTiles.setInputFile(inputFileName);
mapTiles.createTiles();
auto const boundingBox = mapTiles.boundingBox();
- TileDirectory loader(TileDirectory::Landmass, cacheDirectory, manager, extension);
+ TileDirectory loader(TileDirectory::Landmass, cacheDirectory, manager, extension, maxZoomLevel);
loader.setBoundingBox(boundingBox);
loader.createTiles();