| /**************************************************************************** |
| ** |
| ** Copyright (C) 2015 The Qt Company Ltd. |
| ** Contact: http://www.qt.io/licensing/ |
| ** |
| ** This file is part of the QtLocation module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL3$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see http://www.qt.io/terms-conditions. For further |
| ** information use the contact form at http://www.qt.io/contact-us. |
| ** |
| ** GNU Lesser General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU Lesser |
| ** General Public License version 3 as published by the Free Software |
| ** Foundation and appearing in the file LICENSE.LGPLv3 included in the |
| ** packaging of this file. Please review the following information to |
| ** ensure the GNU Lesser General Public License version 3 requirements |
| ** will be met: https://www.gnu.org/licenses/lgpl.html. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 2.0 or later as published by the Free |
| ** Software Foundation and appearing in the file LICENSE.GPL included in |
| ** the packaging of this file. Please review the following information to |
| ** ensure the GNU General Public License version 2.0 requirements will be |
| ** met: http://www.gnu.org/licenses/gpl-2.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| #include "qgeocameratiles_p.h" |
| #include "qgeocameratiles_p_p.h" |
| #include "qgeocameradata_p.h" |
| #include "qgeotilespec_p.h" |
| #include "qgeomaptype_p.h" |
| |
| #include <QtPositioning/private/qwebmercator_p.h> |
| #include <QtPositioning/private/qdoublevector2d_p.h> |
| #include <QtPositioning/private/qdoublevector3d_p.h> |
| #include <QtPositioning/private/qlocationutils_p.h> |
| #include <QtGui/QMatrix4x4> |
| #include <QVector> |
| #include <QMap> |
| #include <QPair> |
| #include <QSet> |
| #include <QSize> |
| #include <cmath> |
| #include <limits> |
| |
| static QVector3D toVector3D(const QDoubleVector3D& in) |
| { |
| return QVector3D(in.x(), in.y(), in.z()); |
| } |
| |
| static QDoubleVector3D toDoubleVector3D(const QVector3D& in) |
| { |
| return QDoubleVector3D(in.x(), in.y(), in.z()); |
| } |
| |
| QT_BEGIN_NAMESPACE |
| |
| QGeoCameraTiles::QGeoCameraTiles() |
| : d_ptr(new QGeoCameraTilesPrivate()) {} |
| |
| QGeoCameraTiles::~QGeoCameraTiles() |
| { |
| } |
| |
| void QGeoCameraTiles::setCameraData(const QGeoCameraData &camera) |
| { |
| if (d_ptr->m_camera == camera) |
| return; |
| |
| d_ptr->m_dirtyGeometry = true; |
| d_ptr->m_camera = camera; |
| d_ptr->m_intZoomLevel = static_cast<int>(std::floor(d_ptr->m_camera.zoomLevel())); |
| d_ptr->m_sideLength = 1 << d_ptr->m_intZoomLevel; |
| } |
| |
| QGeoCameraData QGeoCameraTiles::cameraData() const |
| { |
| return d_ptr->m_camera; |
| } |
| |
| void QGeoCameraTiles::setVisibleArea(const QRectF &visibleArea) |
| { |
| if (d_ptr->m_visibleArea == visibleArea) |
| return; |
| |
| d_ptr->m_visibleArea = visibleArea; |
| d_ptr->m_dirtyGeometry = true; |
| } |
| |
| void QGeoCameraTiles::setScreenSize(const QSize &size) |
| { |
| if (d_ptr->m_screenSize == size) |
| return; |
| |
| d_ptr->m_dirtyGeometry = true; |
| d_ptr->m_screenSize = size; |
| } |
| |
| void QGeoCameraTiles::setPluginString(const QString &pluginString) |
| { |
| if (d_ptr->m_pluginString == pluginString) |
| return; |
| |
| d_ptr->m_dirtyMetadata = true; |
| d_ptr->m_pluginString = pluginString; |
| } |
| |
| void QGeoCameraTiles::setMapType(const QGeoMapType &mapType) |
| { |
| if (d_ptr->m_mapType == mapType) |
| return; |
| |
| d_ptr->m_dirtyMetadata = true; |
| d_ptr->m_mapType = mapType; |
| } |
| |
| QGeoMapType QGeoCameraTiles::activeMapType() const |
| { |
| return d_ptr->m_mapType; |
| } |
| |
| void QGeoCameraTiles::setMapVersion(int mapVersion) |
| { |
| if (d_ptr->m_mapVersion == mapVersion) |
| return; |
| |
| d_ptr->m_dirtyMetadata = true; |
| d_ptr->m_mapVersion = mapVersion; |
| } |
| |
| void QGeoCameraTiles::setTileSize(int tileSize) |
| { |
| if (d_ptr->m_tileSize == tileSize) |
| return; |
| |
| d_ptr->m_dirtyGeometry = true; |
| d_ptr->m_tileSize = tileSize; |
| } |
| |
| void QGeoCameraTiles::setViewExpansion(double viewExpansion) |
| { |
| d_ptr->m_viewExpansion = viewExpansion; |
| d_ptr->m_dirtyGeometry = true; |
| } |
| |
| int QGeoCameraTiles::tileSize() const |
| { |
| return d_ptr->m_tileSize; |
| } |
| |
| const QSet<QGeoTileSpec>& QGeoCameraTiles::createTiles() |
| { |
| if (d_ptr->m_dirtyGeometry) { |
| d_ptr->m_tiles.clear(); |
| d_ptr->updateGeometry(); |
| d_ptr->m_dirtyGeometry = false; |
| } |
| |
| if (d_ptr->m_dirtyMetadata) { |
| d_ptr->updateMetadata(); |
| d_ptr->m_dirtyMetadata = false; |
| } |
| |
| return d_ptr->m_tiles; |
| } |
| |
| QGeoCameraTilesPrivate::QGeoCameraTilesPrivate() |
| : m_mapVersion(-1), |
| m_tileSize(0), |
| m_intZoomLevel(0), |
| m_sideLength(0), |
| m_dirtyGeometry(false), |
| m_dirtyMetadata(false), |
| m_viewExpansion(1.0) |
| { |
| } |
| |
| QGeoCameraTilesPrivate::~QGeoCameraTilesPrivate() {} |
| |
| void QGeoCameraTilesPrivate::updateMetadata() |
| { |
| typedef QSet<QGeoTileSpec>::const_iterator iter; |
| |
| QSet<QGeoTileSpec> newTiles; |
| |
| iter i = m_tiles.constBegin(); |
| iter end = m_tiles.constEnd(); |
| |
| for (; i != end; ++i) { |
| QGeoTileSpec tile = *i; |
| newTiles.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), tile.zoom(), tile.x(), tile.y(), m_mapVersion)); |
| } |
| |
| m_tiles = newTiles; |
| } |
| |
| void QGeoCameraTilesPrivate::updateGeometry() |
| { |
| // Find the frustum from the camera / screen / viewport information |
| // The larger frustum when stationary is a form of prefetching |
| Frustum f = createFrustum(m_viewExpansion); |
| #ifdef QT_LOCATION_DEBUG |
| m_frustum = f; |
| #endif |
| |
| // Find the polygon where the frustum intersects the plane of the map |
| PolygonVector footprint = frustumFootprint(f); |
| #ifdef QT_LOCATION_DEBUG |
| m_frustumFootprint = footprint; |
| #endif |
| |
| // Clip the polygon to the map, split it up if it cross the dateline |
| ClippedFootprint polygons = clipFootprintToMap(footprint); |
| #ifdef QT_LOCATION_DEBUG |
| m_clippedFootprint = polygons; |
| #endif |
| |
| |
| if (!polygons.left.isEmpty()) { |
| QSet<QGeoTileSpec> tilesLeft = tilesFromPolygon(polygons.left); |
| m_tiles.unite(tilesLeft); |
| } |
| |
| if (!polygons.right.isEmpty()) { |
| QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.right); |
| m_tiles.unite(tilesRight); |
| } |
| |
| if (!polygons.mid.isEmpty()) { |
| QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.mid); |
| m_tiles.unite(tilesRight); |
| } |
| } |
| |
| Frustum QGeoCameraTilesPrivate::createFrustum(double viewExpansion) const |
| { |
| double apertureSize = 1.0; |
| if (m_camera.fieldOfView() != 90.0) //aperture(90 / 2) = 1 |
| apertureSize = tan(QLocationUtils::radians(m_camera.fieldOfView()) * 0.5); |
| QDoubleVector3D center = m_sideLength * QWebMercator::coordToMercator(m_camera.center()); |
| #ifdef QT_LOCATION_DEBUG |
| m_createFrustum_center = center; |
| #endif |
| |
| |
| double f = m_screenSize.height(); |
| |
| double z = std::pow(2.0, m_camera.zoomLevel() - m_intZoomLevel) * m_tileSize; // between 1 and 2 * m_tileSize |
| |
| double altitude = (f / (2.0 * z)) / apertureSize; |
| QDoubleVector3D eye = center; |
| eye.setZ(altitude); |
| |
| QDoubleVector3D view = eye - center; |
| QDoubleVector3D side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0)); |
| QDoubleVector3D up = QDoubleVector3D::normal(side, view); |
| |
| QMatrix4x4 mBearing; |
| // The rotation direction here is the opposite of QGeoTiledMapScene::setupCamera, |
| // as this is basically rotating the map against a fixed view frustum. |
| mBearing.rotate(1.0 * m_camera.bearing(), toVector3D(view)); |
| up = toDoubleVector3D(mBearing * toVector3D(up)); |
| |
| // same for tilting |
| QDoubleVector3D side2 = QDoubleVector3D::normal(up, view); |
| QMatrix4x4 mTilt; |
| mTilt.rotate(-1.0 * m_camera.tilt(), toVector3D(side2)); |
| eye = toDoubleVector3D((mTilt * toVector3D(view)) + toVector3D(center)); |
| |
| view = eye - center; |
| side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0)); |
| up = QDoubleVector3D::normal(view, side2); |
| |
| double nearPlane = 1.0 / 32.0; // The denominator used to be (4.0 * m_tileSize ), which produces an extremely narrow and tiny near plane. |
| // farPlane plays a role on how much gets clipped when the map gets tilted. It used to be altitude + 1.0 |
| // The value of 8.0 has been chosen as an acceptable compromise. |
| // TODO: use m_camera.clipDistance(); when this will be introduced |
| double farPlane = altitude + 8.0; |
| |
| double aspectRatio = 1.0 * m_screenSize.width() / m_screenSize.height(); |
| |
| // Half values. Half width near, far, height near, far. |
| double hhn,hwn,hhf,hwf = 0.0; |
| |
| // This used to fix the (half) field of view at 45 degrees |
| // half because this assumed that viewSize = 2*nearPlane x 2*nearPlane |
| viewExpansion *= apertureSize; |
| |
| hhn = viewExpansion * nearPlane; |
| hwn = hhn * aspectRatio; |
| |
| hhf = viewExpansion * farPlane; |
| hwf = hhf * aspectRatio; |
| |
| QDoubleVector3D d = center - eye; |
| d.normalize(); |
| up.normalize(); |
| QDoubleVector3D right = QDoubleVector3D::normal(d, up); |
| |
| QDoubleVector3D cf = eye + d * farPlane; |
| QDoubleVector3D cn = eye + d * nearPlane; |
| |
| Frustum frustum; |
| |
| frustum.apex = eye; |
| #ifdef QT_LOCATION_DEBUG |
| m_createFrustum_eye = eye; |
| #endif |
| |
| QRectF va = m_visibleArea; |
| if (va.isNull()) |
| va = QRectF(0, 0, m_screenSize.width(), m_screenSize.height()); |
| QRectF screen = QRectF(QPointF(0,0),m_screenSize); |
| QPointF vaCenter = va.center(); |
| QPointF screenCenter = screen.center(); |
| QPointF diff = screenCenter - vaCenter; |
| double xdiffpct = diff.x() / m_screenSize.width(); |
| double ydiffpct = -(diff.y() / m_screenSize.height()); |
| |
| double wn = (2 * hwn) * xdiffpct; |
| double hn = (2 * hhn) * ydiffpct; |
| double wf = (2 * hwf) * xdiffpct; |
| double hf = (2 * hhf) * ydiffpct; |
| |
| // TODO: fix eye |
| |
| frustum.topLeftFar = cf - (up * (hhf + hf)) - (right * (hwf + wf)); |
| frustum.topRightFar = cf - (up * (hhf + hf)) + (right * (hwf + wf)); |
| frustum.bottomLeftFar = cf + (up * (hhf + hf)) - (right * (hwf + wf)); |
| frustum.bottomRightFar = cf + (up * (hhf + hf)) + (right * (hwf + wf)); |
| |
| frustum.topLeftNear = cn - (up * (hhn + hn)) - (right * (hwn + wn)); |
| frustum.topRightNear = cn - (up * (hhn + hn)) + (right * (hwn + wn)); |
| frustum.bottomLeftNear = cn + (up * (hhn + hn)) - (right * (hwn + wn)); |
| frustum.bottomRightNear = cn + (up * (hhn + hn)) + (right * (hwn + wn)); |
| |
| return frustum; |
| } |
| |
| static bool appendZIntersects(const QDoubleVector3D &start, |
| const QDoubleVector3D &end, |
| double z, |
| QVector<QDoubleVector3D> &results) |
| { |
| if (start.z() == end.z()) { |
| return false; |
| } else { |
| double f = (start.z() - z) / (start.z() - end.z()); |
| if ((f >= 0) && (f <= 1.0)) { |
| results.append((1 - f) * start + f * end); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Returns the intersection of the plane of the map and the camera frustum as a right handed polygon |
| PolygonVector QGeoCameraTilesPrivate::frustumFootprint(const Frustum &frustum) const |
| { |
| PolygonVector points; |
| points.reserve(4); |
| |
| // The camera is always upright. Tilting angle never reach 90degrees. |
| // Meaning: bottom frustum edges always intersect the map plane, top ones may not. |
| |
| // Top Right |
| if (!appendZIntersects(frustum.apex, frustum.topRightFar, 0.0, points)) |
| appendZIntersects(frustum.topRightFar, frustum.bottomRightFar, 0.0, points); |
| |
| // Bottom Right |
| appendZIntersects(frustum.apex, frustum.bottomRightFar, 0.0, points); |
| |
| // Bottom Left |
| appendZIntersects(frustum.apex, frustum.bottomLeftFar, 0.0, points); |
| |
| // Top Left |
| if (!appendZIntersects(frustum.apex, frustum.topLeftFar, 0.0, points)) |
| appendZIntersects(frustum.topLeftFar, frustum.bottomLeftFar, 0.0, points); |
| |
| return points; |
| } |
| |
| QPair<PolygonVector, PolygonVector> QGeoCameraTilesPrivate::splitPolygonAtAxisValue(const PolygonVector &polygon, int axis, double value) const |
| { |
| PolygonVector polygonBelow; |
| PolygonVector polygonAbove; |
| |
| int size = polygon.size(); |
| |
| if (size == 0) { |
| return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove); |
| } |
| |
| QVector<int> comparisons = QVector<int>(polygon.size()); |
| |
| for (int i = 0; i < size; ++i) { |
| double v = polygon.at(i).get(axis); |
| if (qFuzzyCompare(v - value + 1.0, 1.0)) { |
| comparisons[i] = 0; |
| } else { |
| if (v < value) { |
| comparisons[i] = -1; |
| } else if (value < v) { |
| comparisons[i] = 1; |
| } |
| } |
| } |
| |
| for (int index = 0; index < size; ++index) { |
| int prevIndex = index - 1; |
| if (prevIndex < 0) |
| prevIndex += size; |
| int nextIndex = (index + 1) % size; |
| |
| int prevComp = comparisons[prevIndex]; |
| int comp = comparisons[index]; |
| int nextComp = comparisons[nextIndex]; |
| |
| if (comp == 0) { |
| if (prevComp == -1) { |
| polygonBelow.append(polygon.at(index)); |
| if (nextComp == 1) { |
| polygonAbove.append(polygon.at(index)); |
| } |
| } else if (prevComp == 1) { |
| polygonAbove.append(polygon.at(index)); |
| if (nextComp == -1) { |
| polygonBelow.append(polygon.at(index)); |
| } |
| } else if (prevComp == 0) { |
| if (nextComp == -1) { |
| polygonBelow.append(polygon.at(index)); |
| } else if (nextComp == 1) { |
| polygonAbove.append(polygon.at(index)); |
| } else if (nextComp == 0) { |
| // do nothing |
| } |
| } |
| } else { |
| if (comp == -1) { |
| polygonBelow.append(polygon.at(index)); |
| } else if (comp == 1) { |
| polygonAbove.append(polygon.at(index)); |
| } |
| |
| // there is a point between this and the next point |
| // on the polygon that lies on the splitting line |
| // and should be added to both the below and above |
| // polygons |
| if ((nextComp != 0) && (nextComp != comp)) { |
| QDoubleVector3D p1 = polygon.at(index); |
| QDoubleVector3D p2 = polygon.at(nextIndex); |
| |
| double p1v = p1.get(axis); |
| double p2v = p2.get(axis); |
| |
| double f = (p1v - value) / (p1v - p2v); |
| |
| if (((0 <= f) && (f <= 1.0)) |
| || qFuzzyCompare(f + 1.0, 1.0) |
| || qFuzzyCompare(f + 1.0, 2.0) ) { |
| QDoubleVector3D midPoint = (1.0 - f) * p1 + f * p2; |
| polygonBelow.append(midPoint); |
| polygonAbove.append(midPoint); |
| } |
| } |
| } |
| } |
| |
| return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove); |
| } |
| |
| static void addXOffset(PolygonVector &footprint, double xoff) |
| { |
| for (QDoubleVector3D &v: footprint) |
| v.setX(v.x() + xoff); |
| } |
| |
| QGeoCameraTilesPrivate::ClippedFootprint QGeoCameraTilesPrivate::clipFootprintToMap(const PolygonVector &footprint) const |
| { |
| bool clipX0 = false; |
| bool clipX1 = false; |
| bool clipY0 = false; |
| bool clipY1 = false; |
| |
| double side = 1.0 * m_sideLength; |
| double minX = std::numeric_limits<double>::max(); |
| double maxX = std::numeric_limits<double>::lowest(); |
| |
| for (const QDoubleVector3D &p: footprint) { |
| if (p.y() < 0.0) |
| clipY0 = true; |
| if (p.y() > side) |
| clipY1 = true; |
| } |
| |
| PolygonVector results = footprint; |
| |
| if (clipY0) { |
| results = splitPolygonAtAxisValue(results, 1, 0.0).second; |
| } |
| |
| if (clipY1) { |
| results = splitPolygonAtAxisValue(results, 1, side).first; |
| } |
| |
| for (const QDoubleVector3D &p: results) { |
| if ((p.x() < 0.0) || (qFuzzyIsNull(p.x()))) |
| clipX0 = true; |
| if ((p.x() > side) || (qFuzzyCompare(side, p.x()))) |
| clipX1 = true; |
| } |
| |
| for (const QDoubleVector3D &v : results) { |
| minX = qMin(v.x(), minX); |
| maxX = qMax(v.x(), maxX); |
| } |
| |
| double footprintWidth = maxX - minX; |
| |
| if (clipX0) { |
| if (clipX1) { |
| if (footprintWidth > side) { |
| PolygonVector rightPart = splitPolygonAtAxisValue(results, 0, side).second; |
| addXOffset(rightPart, -side); |
| rightPart = splitPolygonAtAxisValue(rightPart, 0, side).first; // clip it again, should it tend to infinite or so |
| |
| PolygonVector leftPart = splitPolygonAtAxisValue(results, 0, 0).first; |
| addXOffset(leftPart, side); |
| leftPart = splitPolygonAtAxisValue(leftPart, 0, 0).second; // same here |
| |
| results = splitPolygonAtAxisValue(results, 0, 0.0).second; |
| results = splitPolygonAtAxisValue(results, 0, side).first; |
| return ClippedFootprint(leftPart, results, rightPart); |
| } else { // fitting the WebMercator square exactly? |
| results = splitPolygonAtAxisValue(results, 0, 0.0).second; |
| results = splitPolygonAtAxisValue(results, 0, side).first; |
| return ClippedFootprint(PolygonVector(), results, PolygonVector()); |
| } |
| } else { |
| QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, 0.0); |
| if (pair.first.isEmpty()) { |
| // if we touched the line but didn't cross it... |
| for (int i = 0; i < pair.second.size(); ++i) { |
| if (qFuzzyIsNull(pair.second.at(i).x())) |
| pair.first.append(pair.second.at(i)); |
| } |
| if (pair.first.size() == 2) { |
| double y0 = pair.first[0].y(); |
| double y1 = pair.first[1].y(); |
| pair.first.clear(); |
| pair.first.append(QDoubleVector3D(side, y0, 0.0)); |
| pair.first.append(QDoubleVector3D(side - 0.001, y0, 0.0)); |
| pair.first.append(QDoubleVector3D(side - 0.001, y1, 0.0)); |
| pair.first.append(QDoubleVector3D(side, y1, 0.0)); |
| } else if (pair.first.size() == 1) { |
| // FIXME this is trickier |
| // - touching at one point on the tile boundary |
| // - probably need to build a triangular polygon across the edge |
| // - don't want to add another y tile if we can help it |
| // - initial version doesn't care |
| double y = pair.first.at(0).y(); |
| pair.first.clear(); |
| pair.first.append(QDoubleVector3D(side - 0.001, y, 0.0)); |
| pair.first.append(QDoubleVector3D(side, y + 0.001, 0.0)); |
| pair.first.append(QDoubleVector3D(side, y - 0.001, 0.0)); |
| } |
| } else { |
| addXOffset(pair.first, side); |
| if (footprintWidth > side) |
| pair.first = splitPolygonAtAxisValue(pair.first, 0, 0).second; |
| } |
| return ClippedFootprint(pair.first, pair.second, PolygonVector()); |
| } |
| } else { |
| if (clipX1) { |
| QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, side); |
| if (pair.second.isEmpty()) { |
| // if we touched the line but didn't cross it... |
| for (int i = 0; i < pair.first.size(); ++i) { |
| if (qFuzzyCompare(side, pair.first.at(i).x())) |
| pair.second.append(pair.first.at(i)); |
| } |
| if (pair.second.size() == 2) { |
| double y0 = pair.second[0].y(); |
| double y1 = pair.second[1].y(); |
| pair.second.clear(); |
| pair.second.append(QDoubleVector3D(0, y0, 0.0)); |
| pair.second.append(QDoubleVector3D(0.001, y0, 0.0)); |
| pair.second.append(QDoubleVector3D(0.001, y1, 0.0)); |
| pair.second.append(QDoubleVector3D(0, y1, 0.0)); |
| } else if (pair.second.size() == 1) { |
| // FIXME this is trickier |
| // - touching at one point on the tile boundary |
| // - probably need to build a triangular polygon across the edge |
| // - don't want to add another y tile if we can help it |
| // - initial version doesn't care |
| double y = pair.second.at(0).y(); |
| pair.second.clear(); |
| pair.second.append(QDoubleVector3D(0.001, y, 0.0)); |
| pair.second.append(QDoubleVector3D(0.0, y - 0.001, 0.0)); |
| pair.second.append(QDoubleVector3D(0.0, y + 0.001, 0.0)); |
| } |
| } else { |
| addXOffset(pair.second, -side); |
| if (footprintWidth > side) |
| pair.second = splitPolygonAtAxisValue(pair.second, 0, side).first; |
| } |
| return ClippedFootprint(PolygonVector(), pair.first, pair.second); |
| } else { |
| return ClippedFootprint(PolygonVector(), results, PolygonVector()); |
| } |
| } |
| |
| } |
| |
| QList<QPair<double, int> > QGeoCameraTilesPrivate::tileIntersections(double p1, int t1, double p2, int t2) const |
| { |
| if (t1 == t2) { |
| QList<QPair<double, int> > results = QList<QPair<double, int> >(); |
| results.append(QPair<double, int>(0.0, t1)); |
| return results; |
| } |
| |
| int step = 1; |
| if (t1 > t2) { |
| step = -1; |
| } |
| |
| int size = 1 + ((t2 - t1) / step); |
| |
| QList<QPair<double, int> > results = QList<QPair<double, int> >(); |
| |
| results.append(QPair<double, int>(0.0, t1)); |
| |
| if (step == 1) { |
| for (int i = 1; i < size; ++i) { |
| double f = (t1 + i - p1) / (p2 - p1); |
| results.append(QPair<double, int>(f, t1 + i)); |
| } |
| } else { |
| for (int i = 1; i < size; ++i) { |
| double f = (t1 - i + 1 - p1) / (p2 - p1); |
| results.append(QPair<double, int>(f, t1 - i)); |
| } |
| } |
| |
| return results; |
| } |
| |
| QSet<QGeoTileSpec> QGeoCameraTilesPrivate::tilesFromPolygon(const PolygonVector &polygon) const |
| { |
| int numPoints = polygon.size(); |
| |
| if (numPoints == 0) |
| return QSet<QGeoTileSpec>(); |
| |
| QVector<int> tilesX(polygon.size()); |
| QVector<int> tilesY(polygon.size()); |
| |
| // grab tiles at the corners of the polygon |
| for (int i = 0; i < numPoints; ++i) { |
| |
| QDoubleVector2D p = polygon.at(i).toVector2D(); |
| |
| int x = 0; |
| int y = 0; |
| |
| if (qFuzzyCompare(p.x(), m_sideLength * 1.0)) |
| x = m_sideLength - 1; |
| else { |
| x = static_cast<int>(p.x()) % m_sideLength; |
| if ( !qFuzzyCompare(p.x(), 1.0 * x) && qFuzzyCompare(p.x(), 1.0 * (x + 1)) ) |
| x++; |
| } |
| |
| if (qFuzzyCompare(p.y(), m_sideLength * 1.0)) |
| y = m_sideLength - 1; |
| else { |
| y = static_cast<int>(p.y()) % m_sideLength; |
| if ( !qFuzzyCompare(p.y(), 1.0 * y) && qFuzzyCompare(p.y(), 1.0 * (y + 1)) ) |
| y++; |
| } |
| |
| tilesX[i] = x; |
| tilesY[i] = y; |
| } |
| |
| QGeoCameraTilesPrivate::TileMap map; |
| |
| // walk along the edges of the polygon and add all tiles covered by them |
| for (int i1 = 0; i1 < numPoints; ++i1) { |
| int i2 = (i1 + 1) % numPoints; |
| |
| double x1 = polygon.at(i1).get(0); |
| double x2 = polygon.at(i2).get(0); |
| |
| bool xFixed = qFuzzyCompare(x1, x2); |
| bool xIntegral = qFuzzyCompare(x1, std::floor(x1)) || qFuzzyCompare(x1 + 1.0, std::floor(x1 + 1.0)); |
| |
| QList<QPair<double, int> > xIntersects |
| = tileIntersections(x1, |
| tilesX.at(i1), |
| x2, |
| tilesX.at(i2)); |
| |
| double y1 = polygon.at(i1).get(1); |
| double y2 = polygon.at(i2).get(1); |
| |
| bool yFixed = qFuzzyCompare(y1, y2); |
| bool yIntegral = qFuzzyCompare(y1, std::floor(y1)) || qFuzzyCompare(y1 + 1.0, std::floor(y1 + 1.0)); |
| |
| QList<QPair<double, int> > yIntersects |
| = tileIntersections(y1, |
| tilesY.at(i1), |
| y2, |
| tilesY.at(i2)); |
| |
| int x = xIntersects.takeFirst().second; |
| int y = yIntersects.takeFirst().second; |
| |
| |
| /* |
| If the polygon coincides with the tile edges we must be |
| inclusive and grab all tiles on both sides. We also need |
| to handle tiles with corners coindent with the |
| corners of the polygon. |
| e.g. all tiles marked with 'x' will be added |
| |
| "+" - tile boundaries |
| "O" - polygon boundary |
| |
| + + + + + + + + + + + + + + + + + + + + + |
| + + + + + + |
| + + x + x + x + + |
| + + + + + + |
| + + + + + + + + O O O O O + + + + + + + + |
| + + O 0 + + |
| + + x O x 0 x + + |
| + + O 0 + + |
| + + + + + + + + O 0 0 0 0 + + + + + + + + |
| + + + + + + |
| + + x + x + x + + |
| + + + + + + |
| + + + + + + + + + + + + + + + + + + + + + |
| */ |
| |
| |
| int xOther = x; |
| int yOther = y; |
| |
| if (xFixed && xIntegral) { |
| if (y2 < y1) { |
| xOther = qMax(0, x - 1); |
| } |
| } |
| |
| if (yFixed && yIntegral) { |
| if (x1 < x2) { |
| yOther = qMax(0, y - 1); |
| |
| } |
| } |
| |
| if (xIntegral) { |
| map.add(xOther, y); |
| if (yIntegral) |
| map.add(xOther, yOther); |
| |
| } |
| |
| if (yIntegral) |
| map.add(x, yOther); |
| |
| map.add(x,y); |
| |
| // top left corner |
| int iPrev = (i1 + numPoints - 1) % numPoints; |
| double xPrevious = polygon.at(iPrev).get(0); |
| double yPrevious = polygon.at(iPrev).get(1); |
| bool xPreviousFixed = qFuzzyCompare(xPrevious, x1); |
| if (xIntegral && xPreviousFixed && yIntegral && yFixed) { |
| if ((x2 > x1) && (yPrevious > y1)) { |
| if ((x - 1) > 0 && (y - 1) > 0) |
| map.add(x - 1, y - 1); |
| } else if ((x2 < x1) && (yPrevious < y1)) { |
| // what? |
| } |
| } |
| |
| // for the simple case where intersections do not coincide with |
| // the boundaries, we move along the edge and add tiles until |
| // the x and y intersection lists are exhausted |
| |
| while (!xIntersects.isEmpty() && !yIntersects.isEmpty()) { |
| QPair<double, int> nextX = xIntersects.first(); |
| QPair<double, int> nextY = yIntersects.first(); |
| if (nextX.first < nextY.first) { |
| x = nextX.second; |
| map.add(x, y); |
| xIntersects.removeFirst(); |
| |
| } else if (nextX.first > nextY.first) { |
| y = nextY.second; |
| map.add(x, y); |
| yIntersects.removeFirst(); |
| |
| } else { |
| map.add(x, nextY.second); |
| map.add(nextX.second, y); |
| x = nextX.second; |
| y = nextY.second; |
| map.add(x, y); |
| xIntersects.removeFirst(); |
| yIntersects.removeFirst(); |
| } |
| } |
| |
| while (!xIntersects.isEmpty()) { |
| x = xIntersects.takeFirst().second; |
| map.add(x, y); |
| if (yIntegral && yFixed) |
| map.add(x, yOther); |
| |
| } |
| |
| while (!yIntersects.isEmpty()) { |
| y = yIntersects.takeFirst().second; |
| map.add(x, y); |
| if (xIntegral && xFixed) |
| map.add(xOther, y); |
| } |
| } |
| |
| QSet<QGeoTileSpec> results; |
| |
| int z = m_intZoomLevel; |
| |
| typedef QMap<int, QPair<int, int> >::const_iterator iter; |
| iter i = map.data.constBegin(); |
| iter end = map.data.constEnd(); |
| |
| for (; i != end; ++i) { |
| int y = i.key(); |
| int minX = i->first; |
| int maxX = i->second; |
| for (int x = minX; x <= maxX; ++x) { |
| results.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), z, x, y, m_mapVersion)); |
| } |
| } |
| |
| return results; |
| } |
| |
| QGeoCameraTilesPrivate::TileMap::TileMap() {} |
| |
| void QGeoCameraTilesPrivate::TileMap::add(int tileX, int tileY) |
| { |
| if (data.contains(tileY)) { |
| int oldMinX = data.value(tileY).first; |
| int oldMaxX = data.value(tileY).second; |
| data.insert(tileY, QPair<int, int>(qMin(tileX, oldMinX), qMax(tileX, oldMaxX))); |
| } else { |
| data.insert(tileY, QPair<int, int>(tileX, tileX)); |
| } |
| } |
| |
| QT_END_NAMESPACE |
