1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the QtLocation module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL3$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPLv3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or later as published by the Free
28 ** Software Foundation and appearing in the file LICENSE.GPL included in
29 ** the packaging of this file. Please review the following information to
30 ** ensure the GNU General Public License version 2.0 requirements will be
31 ** met: http://www.gnu.org/licenses/gpl-2.0.html.
32 **
33 ** $QT_END_LICENSE$
34 **
35 ****************************************************************************/
36 #include "qgeocameratiles_p.h"
37 #include "qgeocameratiles_p_p.h"
38 #include "qgeocameradata_p.h"
39 #include "qgeotilespec_p.h"
40 #include "qgeomaptype_p.h"
41
42 #include <QtPositioning/private/qwebmercator_p.h>
43 #include <QtPositioning/private/qdoublevector2d_p.h>
44 #include <QtPositioning/private/qdoublevector3d_p.h>
45 #include <QtPositioning/private/qlocationutils_p.h>
46 #include <QtGui/QMatrix4x4>
47 #include <QVector>
48 #include <QMap>
49 #include <QPair>
50 #include <QSet>
51 #include <QSize>
52 #include <cmath>
53 #include <limits>
54
toVector3D(const QDoubleVector3D & in)55 static QVector3D toVector3D(const QDoubleVector3D& in)
56 {
57 return QVector3D(in.x(), in.y(), in.z());
58 }
59
toDoubleVector3D(const QVector3D & in)60 static QDoubleVector3D toDoubleVector3D(const QVector3D& in)
61 {
62 return QDoubleVector3D(in.x(), in.y(), in.z());
63 }
64
65 QT_BEGIN_NAMESPACE
66
QGeoCameraTiles()67 QGeoCameraTiles::QGeoCameraTiles()
68 : d_ptr(new QGeoCameraTilesPrivate()) {}
69
~QGeoCameraTiles()70 QGeoCameraTiles::~QGeoCameraTiles()
71 {
72 }
73
setCameraData(const QGeoCameraData & camera)74 void QGeoCameraTiles::setCameraData(const QGeoCameraData &camera)
75 {
76 if (d_ptr->m_camera == camera)
77 return;
78
79 d_ptr->m_dirtyGeometry = true;
80 d_ptr->m_camera = camera;
81 d_ptr->m_intZoomLevel = static_cast<int>(std::floor(d_ptr->m_camera.zoomLevel()));
82 d_ptr->m_sideLength = 1 << d_ptr->m_intZoomLevel;
83 }
84
cameraData() const85 QGeoCameraData QGeoCameraTiles::cameraData() const
86 {
87 return d_ptr->m_camera;
88 }
89
setVisibleArea(const QRectF & visibleArea)90 void QGeoCameraTiles::setVisibleArea(const QRectF &visibleArea)
91 {
92 if (d_ptr->m_visibleArea == visibleArea)
93 return;
94
95 d_ptr->m_visibleArea = visibleArea;
96 d_ptr->m_dirtyGeometry = true;
97 }
98
setScreenSize(const QSize & size)99 void QGeoCameraTiles::setScreenSize(const QSize &size)
100 {
101 if (d_ptr->m_screenSize == size)
102 return;
103
104 d_ptr->m_dirtyGeometry = true;
105 d_ptr->m_screenSize = size;
106 }
107
setPluginString(const QString & pluginString)108 void QGeoCameraTiles::setPluginString(const QString &pluginString)
109 {
110 if (d_ptr->m_pluginString == pluginString)
111 return;
112
113 d_ptr->m_dirtyMetadata = true;
114 d_ptr->m_pluginString = pluginString;
115 }
116
setMapType(const QGeoMapType & mapType)117 void QGeoCameraTiles::setMapType(const QGeoMapType &mapType)
118 {
119 if (d_ptr->m_mapType == mapType)
120 return;
121
122 d_ptr->m_dirtyMetadata = true;
123 d_ptr->m_mapType = mapType;
124 }
125
activeMapType() const126 QGeoMapType QGeoCameraTiles::activeMapType() const
127 {
128 return d_ptr->m_mapType;
129 }
130
setMapVersion(int mapVersion)131 void QGeoCameraTiles::setMapVersion(int mapVersion)
132 {
133 if (d_ptr->m_mapVersion == mapVersion)
134 return;
135
136 d_ptr->m_dirtyMetadata = true;
137 d_ptr->m_mapVersion = mapVersion;
138 }
139
setTileSize(int tileSize)140 void QGeoCameraTiles::setTileSize(int tileSize)
141 {
142 if (d_ptr->m_tileSize == tileSize)
143 return;
144
145 d_ptr->m_dirtyGeometry = true;
146 d_ptr->m_tileSize = tileSize;
147 }
148
setViewExpansion(double viewExpansion)149 void QGeoCameraTiles::setViewExpansion(double viewExpansion)
150 {
151 d_ptr->m_viewExpansion = viewExpansion;
152 d_ptr->m_dirtyGeometry = true;
153 }
154
tileSize() const155 int QGeoCameraTiles::tileSize() const
156 {
157 return d_ptr->m_tileSize;
158 }
159
createTiles()160 const QSet<QGeoTileSpec>& QGeoCameraTiles::createTiles()
161 {
162 if (d_ptr->m_dirtyGeometry) {
163 d_ptr->m_tiles.clear();
164 d_ptr->updateGeometry();
165 d_ptr->m_dirtyGeometry = false;
166 }
167
168 if (d_ptr->m_dirtyMetadata) {
169 d_ptr->updateMetadata();
170 d_ptr->m_dirtyMetadata = false;
171 }
172
173 return d_ptr->m_tiles;
174 }
175
QGeoCameraTilesPrivate()176 QGeoCameraTilesPrivate::QGeoCameraTilesPrivate()
177 : m_mapVersion(-1),
178 m_tileSize(0),
179 m_intZoomLevel(0),
180 m_sideLength(0),
181 m_dirtyGeometry(false),
182 m_dirtyMetadata(false),
183 m_viewExpansion(1.0)
184 {
185 }
186
~QGeoCameraTilesPrivate()187 QGeoCameraTilesPrivate::~QGeoCameraTilesPrivate() {}
188
updateMetadata()189 void QGeoCameraTilesPrivate::updateMetadata()
190 {
191 typedef QSet<QGeoTileSpec>::const_iterator iter;
192
193 QSet<QGeoTileSpec> newTiles;
194
195 iter i = m_tiles.constBegin();
196 iter end = m_tiles.constEnd();
197
198 for (; i != end; ++i) {
199 QGeoTileSpec tile = *i;
200 newTiles.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), tile.zoom(), tile.x(), tile.y(), m_mapVersion));
201 }
202
203 m_tiles = newTiles;
204 }
205
updateGeometry()206 void QGeoCameraTilesPrivate::updateGeometry()
207 {
208 // Find the frustum from the camera / screen / viewport information
209 // The larger frustum when stationary is a form of prefetching
210 Frustum f = createFrustum(m_viewExpansion);
211 #ifdef QT_LOCATION_DEBUG
212 m_frustum = f;
213 #endif
214
215 // Find the polygon where the frustum intersects the plane of the map
216 PolygonVector footprint = frustumFootprint(f);
217 #ifdef QT_LOCATION_DEBUG
218 m_frustumFootprint = footprint;
219 #endif
220
221 // Clip the polygon to the map, split it up if it cross the dateline
222 ClippedFootprint polygons = clipFootprintToMap(footprint);
223 #ifdef QT_LOCATION_DEBUG
224 m_clippedFootprint = polygons;
225 #endif
226
227
228 if (!polygons.left.isEmpty()) {
229 QSet<QGeoTileSpec> tilesLeft = tilesFromPolygon(polygons.left);
230 m_tiles.unite(tilesLeft);
231 }
232
233 if (!polygons.right.isEmpty()) {
234 QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.right);
235 m_tiles.unite(tilesRight);
236 }
237
238 if (!polygons.mid.isEmpty()) {
239 QSet<QGeoTileSpec> tilesRight = tilesFromPolygon(polygons.mid);
240 m_tiles.unite(tilesRight);
241 }
242 }
243
createFrustum(double viewExpansion) const244 Frustum QGeoCameraTilesPrivate::createFrustum(double viewExpansion) const
245 {
246 double apertureSize = 1.0;
247 if (m_camera.fieldOfView() != 90.0) //aperture(90 / 2) = 1
248 apertureSize = tan(QLocationUtils::radians(m_camera.fieldOfView()) * 0.5);
249 QDoubleVector3D center = m_sideLength * QWebMercator::coordToMercator(m_camera.center());
250 #ifdef QT_LOCATION_DEBUG
251 m_createFrustum_center = center;
252 #endif
253
254
255 double f = m_screenSize.height();
256
257 double z = std::pow(2.0, m_camera.zoomLevel() - m_intZoomLevel) * m_tileSize; // between 1 and 2 * m_tileSize
258
259 double altitude = (f / (2.0 * z)) / apertureSize;
260 QDoubleVector3D eye = center;
261 eye.setZ(altitude);
262
263 QDoubleVector3D view = eye - center;
264 QDoubleVector3D side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0));
265 QDoubleVector3D up = QDoubleVector3D::normal(side, view);
266
267 QMatrix4x4 mBearing;
268 // The rotation direction here is the opposite of QGeoTiledMapScene::setupCamera,
269 // as this is basically rotating the map against a fixed view frustum.
270 mBearing.rotate(1.0 * m_camera.bearing(), toVector3D(view));
271 up = toDoubleVector3D(mBearing * toVector3D(up));
272
273 // same for tilting
274 QDoubleVector3D side2 = QDoubleVector3D::normal(up, view);
275 QMatrix4x4 mTilt;
276 mTilt.rotate(-1.0 * m_camera.tilt(), toVector3D(side2));
277 eye = toDoubleVector3D((mTilt * toVector3D(view)) + toVector3D(center));
278
279 view = eye - center;
280 side = QDoubleVector3D::normal(view, QDoubleVector3D(0.0, 1.0, 0.0));
281 up = QDoubleVector3D::normal(view, side2);
282
283 double nearPlane = 1.0 / 32.0; // The denominator used to be (4.0 * m_tileSize ), which produces an extremely narrow and tiny near plane.
284 // farPlane plays a role on how much gets clipped when the map gets tilted. It used to be altitude + 1.0
285 // The value of 8.0 has been chosen as an acceptable compromise.
286 // TODO: use m_camera.clipDistance(); when this will be introduced
287 double farPlane = altitude + 8.0;
288
289 double aspectRatio = 1.0 * m_screenSize.width() / m_screenSize.height();
290
291 // Half values. Half width near, far, height near, far.
292 double hhn,hwn,hhf,hwf = 0.0;
293
294 // This used to fix the (half) field of view at 45 degrees
295 // half because this assumed that viewSize = 2*nearPlane x 2*nearPlane
296 viewExpansion *= apertureSize;
297
298 hhn = viewExpansion * nearPlane;
299 hwn = hhn * aspectRatio;
300
301 hhf = viewExpansion * farPlane;
302 hwf = hhf * aspectRatio;
303
304 QDoubleVector3D d = center - eye;
305 d.normalize();
306 up.normalize();
307 QDoubleVector3D right = QDoubleVector3D::normal(d, up);
308
309 QDoubleVector3D cf = eye + d * farPlane;
310 QDoubleVector3D cn = eye + d * nearPlane;
311
312 Frustum frustum;
313
314 frustum.apex = eye;
315 #ifdef QT_LOCATION_DEBUG
316 m_createFrustum_eye = eye;
317 #endif
318
319 QRectF va = m_visibleArea;
320 if (va.isNull())
321 va = QRectF(0, 0, m_screenSize.width(), m_screenSize.height());
322 QRectF screen = QRectF(QPointF(0,0),m_screenSize);
323 QPointF vaCenter = va.center();
324 QPointF screenCenter = screen.center();
325 QPointF diff = screenCenter - vaCenter;
326 double xdiffpct = diff.x() / m_screenSize.width();
327 double ydiffpct = -(diff.y() / m_screenSize.height());
328
329 double wn = (2 * hwn) * xdiffpct;
330 double hn = (2 * hhn) * ydiffpct;
331 double wf = (2 * hwf) * xdiffpct;
332 double hf = (2 * hhf) * ydiffpct;
333
334 // TODO: fix eye
335
336 frustum.topLeftFar = cf - (up * (hhf + hf)) - (right * (hwf + wf));
337 frustum.topRightFar = cf - (up * (hhf + hf)) + (right * (hwf + wf));
338 frustum.bottomLeftFar = cf + (up * (hhf + hf)) - (right * (hwf + wf));
339 frustum.bottomRightFar = cf + (up * (hhf + hf)) + (right * (hwf + wf));
340
341 frustum.topLeftNear = cn - (up * (hhn + hn)) - (right * (hwn + wn));
342 frustum.topRightNear = cn - (up * (hhn + hn)) + (right * (hwn + wn));
343 frustum.bottomLeftNear = cn + (up * (hhn + hn)) - (right * (hwn + wn));
344 frustum.bottomRightNear = cn + (up * (hhn + hn)) + (right * (hwn + wn));
345
346 return frustum;
347 }
348
appendZIntersects(const QDoubleVector3D & start,const QDoubleVector3D & end,double z,QVector<QDoubleVector3D> & results)349 static bool appendZIntersects(const QDoubleVector3D &start,
350 const QDoubleVector3D &end,
351 double z,
352 QVector<QDoubleVector3D> &results)
353 {
354 if (start.z() == end.z()) {
355 return false;
356 } else {
357 double f = (start.z() - z) / (start.z() - end.z());
358 if ((f >= 0) && (f <= 1.0)) {
359 results.append((1 - f) * start + f * end);
360 return true;
361 }
362 }
363 return false;
364 }
365
366 // Returns the intersection of the plane of the map and the camera frustum as a right handed polygon
frustumFootprint(const Frustum & frustum) const367 PolygonVector QGeoCameraTilesPrivate::frustumFootprint(const Frustum &frustum) const
368 {
369 PolygonVector points;
370 points.reserve(4);
371
372 // The camera is always upright. Tilting angle never reach 90degrees.
373 // Meaning: bottom frustum edges always intersect the map plane, top ones may not.
374
375 // Top Right
376 if (!appendZIntersects(frustum.apex, frustum.topRightFar, 0.0, points))
377 appendZIntersects(frustum.topRightFar, frustum.bottomRightFar, 0.0, points);
378
379 // Bottom Right
380 appendZIntersects(frustum.apex, frustum.bottomRightFar, 0.0, points);
381
382 // Bottom Left
383 appendZIntersects(frustum.apex, frustum.bottomLeftFar, 0.0, points);
384
385 // Top Left
386 if (!appendZIntersects(frustum.apex, frustum.topLeftFar, 0.0, points))
387 appendZIntersects(frustum.topLeftFar, frustum.bottomLeftFar, 0.0, points);
388
389 return points;
390 }
391
splitPolygonAtAxisValue(const PolygonVector & polygon,int axis,double value) const392 QPair<PolygonVector, PolygonVector> QGeoCameraTilesPrivate::splitPolygonAtAxisValue(const PolygonVector &polygon, int axis, double value) const
393 {
394 PolygonVector polygonBelow;
395 PolygonVector polygonAbove;
396
397 int size = polygon.size();
398
399 if (size == 0) {
400 return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove);
401 }
402
403 QVector<int> comparisons = QVector<int>(polygon.size());
404
405 for (int i = 0; i < size; ++i) {
406 double v = polygon.at(i).get(axis);
407 if (qFuzzyCompare(v - value + 1.0, 1.0)) {
408 comparisons[i] = 0;
409 } else {
410 if (v < value) {
411 comparisons[i] = -1;
412 } else if (value < v) {
413 comparisons[i] = 1;
414 }
415 }
416 }
417
418 for (int index = 0; index < size; ++index) {
419 int prevIndex = index - 1;
420 if (prevIndex < 0)
421 prevIndex += size;
422 int nextIndex = (index + 1) % size;
423
424 int prevComp = comparisons[prevIndex];
425 int comp = comparisons[index];
426 int nextComp = comparisons[nextIndex];
427
428 if (comp == 0) {
429 if (prevComp == -1) {
430 polygonBelow.append(polygon.at(index));
431 if (nextComp == 1) {
432 polygonAbove.append(polygon.at(index));
433 }
434 } else if (prevComp == 1) {
435 polygonAbove.append(polygon.at(index));
436 if (nextComp == -1) {
437 polygonBelow.append(polygon.at(index));
438 }
439 } else if (prevComp == 0) {
440 if (nextComp == -1) {
441 polygonBelow.append(polygon.at(index));
442 } else if (nextComp == 1) {
443 polygonAbove.append(polygon.at(index));
444 } else if (nextComp == 0) {
445 // do nothing
446 }
447 }
448 } else {
449 if (comp == -1) {
450 polygonBelow.append(polygon.at(index));
451 } else if (comp == 1) {
452 polygonAbove.append(polygon.at(index));
453 }
454
455 // there is a point between this and the next point
456 // on the polygon that lies on the splitting line
457 // and should be added to both the below and above
458 // polygons
459 if ((nextComp != 0) && (nextComp != comp)) {
460 QDoubleVector3D p1 = polygon.at(index);
461 QDoubleVector3D p2 = polygon.at(nextIndex);
462
463 double p1v = p1.get(axis);
464 double p2v = p2.get(axis);
465
466 double f = (p1v - value) / (p1v - p2v);
467
468 if (((0 <= f) && (f <= 1.0))
469 || qFuzzyCompare(f + 1.0, 1.0)
470 || qFuzzyCompare(f + 1.0, 2.0) ) {
471 QDoubleVector3D midPoint = (1.0 - f) * p1 + f * p2;
472 polygonBelow.append(midPoint);
473 polygonAbove.append(midPoint);
474 }
475 }
476 }
477 }
478
479 return QPair<PolygonVector, PolygonVector>(polygonBelow, polygonAbove);
480 }
481
addXOffset(PolygonVector & footprint,double xoff)482 static void addXOffset(PolygonVector &footprint, double xoff)
483 {
484 for (QDoubleVector3D &v: footprint)
485 v.setX(v.x() + xoff);
486 }
487
clipFootprintToMap(const PolygonVector & footprint) const488 QGeoCameraTilesPrivate::ClippedFootprint QGeoCameraTilesPrivate::clipFootprintToMap(const PolygonVector &footprint) const
489 {
490 bool clipX0 = false;
491 bool clipX1 = false;
492 bool clipY0 = false;
493 bool clipY1 = false;
494
495 double side = 1.0 * m_sideLength;
496 double minX = std::numeric_limits<double>::max();
497 double maxX = std::numeric_limits<double>::lowest();
498
499 for (const QDoubleVector3D &p: footprint) {
500 if (p.y() < 0.0)
501 clipY0 = true;
502 if (p.y() > side)
503 clipY1 = true;
504 }
505
506 PolygonVector results = footprint;
507
508 if (clipY0) {
509 results = splitPolygonAtAxisValue(results, 1, 0.0).second;
510 }
511
512 if (clipY1) {
513 results = splitPolygonAtAxisValue(results, 1, side).first;
514 }
515
516 for (const QDoubleVector3D &p: results) {
517 if ((p.x() < 0.0) || (qFuzzyIsNull(p.x())))
518 clipX0 = true;
519 if ((p.x() > side) || (qFuzzyCompare(side, p.x())))
520 clipX1 = true;
521 }
522
523 for (const QDoubleVector3D &v : results) {
524 minX = qMin(v.x(), minX);
525 maxX = qMax(v.x(), maxX);
526 }
527
528 double footprintWidth = maxX - minX;
529
530 if (clipX0) {
531 if (clipX1) {
532 if (footprintWidth > side) {
533 PolygonVector rightPart = splitPolygonAtAxisValue(results, 0, side).second;
534 addXOffset(rightPart, -side);
535 rightPart = splitPolygonAtAxisValue(rightPart, 0, side).first; // clip it again, should it tend to infinite or so
536
537 PolygonVector leftPart = splitPolygonAtAxisValue(results, 0, 0).first;
538 addXOffset(leftPart, side);
539 leftPart = splitPolygonAtAxisValue(leftPart, 0, 0).second; // same here
540
541 results = splitPolygonAtAxisValue(results, 0, 0.0).second;
542 results = splitPolygonAtAxisValue(results, 0, side).first;
543 return ClippedFootprint(leftPart, results, rightPart);
544 } else { // fitting the WebMercator square exactly?
545 results = splitPolygonAtAxisValue(results, 0, 0.0).second;
546 results = splitPolygonAtAxisValue(results, 0, side).first;
547 return ClippedFootprint(PolygonVector(), results, PolygonVector());
548 }
549 } else {
550 QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, 0.0);
551 if (pair.first.isEmpty()) {
552 // if we touched the line but didn't cross it...
553 for (int i = 0; i < pair.second.size(); ++i) {
554 if (qFuzzyIsNull(pair.second.at(i).x()))
555 pair.first.append(pair.second.at(i));
556 }
557 if (pair.first.size() == 2) {
558 double y0 = pair.first[0].y();
559 double y1 = pair.first[1].y();
560 pair.first.clear();
561 pair.first.append(QDoubleVector3D(side, y0, 0.0));
562 pair.first.append(QDoubleVector3D(side - 0.001, y0, 0.0));
563 pair.first.append(QDoubleVector3D(side - 0.001, y1, 0.0));
564 pair.first.append(QDoubleVector3D(side, y1, 0.0));
565 } else if (pair.first.size() == 1) {
566 // FIXME this is trickier
567 // - touching at one point on the tile boundary
568 // - probably need to build a triangular polygon across the edge
569 // - don't want to add another y tile if we can help it
570 // - initial version doesn't care
571 double y = pair.first.at(0).y();
572 pair.first.clear();
573 pair.first.append(QDoubleVector3D(side - 0.001, y, 0.0));
574 pair.first.append(QDoubleVector3D(side, y + 0.001, 0.0));
575 pair.first.append(QDoubleVector3D(side, y - 0.001, 0.0));
576 }
577 } else {
578 addXOffset(pair.first, side);
579 if (footprintWidth > side)
580 pair.first = splitPolygonAtAxisValue(pair.first, 0, 0).second;
581 }
582 return ClippedFootprint(pair.first, pair.second, PolygonVector());
583 }
584 } else {
585 if (clipX1) {
586 QPair<PolygonVector, PolygonVector> pair = splitPolygonAtAxisValue(results, 0, side);
587 if (pair.second.isEmpty()) {
588 // if we touched the line but didn't cross it...
589 for (int i = 0; i < pair.first.size(); ++i) {
590 if (qFuzzyCompare(side, pair.first.at(i).x()))
591 pair.second.append(pair.first.at(i));
592 }
593 if (pair.second.size() == 2) {
594 double y0 = pair.second[0].y();
595 double y1 = pair.second[1].y();
596 pair.second.clear();
597 pair.second.append(QDoubleVector3D(0, y0, 0.0));
598 pair.second.append(QDoubleVector3D(0.001, y0, 0.0));
599 pair.second.append(QDoubleVector3D(0.001, y1, 0.0));
600 pair.second.append(QDoubleVector3D(0, y1, 0.0));
601 } else if (pair.second.size() == 1) {
602 // FIXME this is trickier
603 // - touching at one point on the tile boundary
604 // - probably need to build a triangular polygon across the edge
605 // - don't want to add another y tile if we can help it
606 // - initial version doesn't care
607 double y = pair.second.at(0).y();
608 pair.second.clear();
609 pair.second.append(QDoubleVector3D(0.001, y, 0.0));
610 pair.second.append(QDoubleVector3D(0.0, y - 0.001, 0.0));
611 pair.second.append(QDoubleVector3D(0.0, y + 0.001, 0.0));
612 }
613 } else {
614 addXOffset(pair.second, -side);
615 if (footprintWidth > side)
616 pair.second = splitPolygonAtAxisValue(pair.second, 0, side).first;
617 }
618 return ClippedFootprint(PolygonVector(), pair.first, pair.second);
619 } else {
620 return ClippedFootprint(PolygonVector(), results, PolygonVector());
621 }
622 }
623
624 }
625
tileIntersections(double p1,int t1,double p2,int t2) const626 QList<QPair<double, int> > QGeoCameraTilesPrivate::tileIntersections(double p1, int t1, double p2, int t2) const
627 {
628 if (t1 == t2) {
629 QList<QPair<double, int> > results = QList<QPair<double, int> >();
630 results.append(QPair<double, int>(0.0, t1));
631 return results;
632 }
633
634 int step = 1;
635 if (t1 > t2) {
636 step = -1;
637 }
638
639 int size = 1 + ((t2 - t1) / step);
640
641 QList<QPair<double, int> > results = QList<QPair<double, int> >();
642
643 results.append(QPair<double, int>(0.0, t1));
644
645 if (step == 1) {
646 for (int i = 1; i < size; ++i) {
647 double f = (t1 + i - p1) / (p2 - p1);
648 results.append(QPair<double, int>(f, t1 + i));
649 }
650 } else {
651 for (int i = 1; i < size; ++i) {
652 double f = (t1 - i + 1 - p1) / (p2 - p1);
653 results.append(QPair<double, int>(f, t1 - i));
654 }
655 }
656
657 return results;
658 }
659
tilesFromPolygon(const PolygonVector & polygon) const660 QSet<QGeoTileSpec> QGeoCameraTilesPrivate::tilesFromPolygon(const PolygonVector &polygon) const
661 {
662 int numPoints = polygon.size();
663
664 if (numPoints == 0)
665 return QSet<QGeoTileSpec>();
666
667 QVector<int> tilesX(polygon.size());
668 QVector<int> tilesY(polygon.size());
669
670 // grab tiles at the corners of the polygon
671 for (int i = 0; i < numPoints; ++i) {
672
673 QDoubleVector2D p = polygon.at(i).toVector2D();
674
675 int x = 0;
676 int y = 0;
677
678 if (qFuzzyCompare(p.x(), m_sideLength * 1.0))
679 x = m_sideLength - 1;
680 else {
681 x = static_cast<int>(p.x()) % m_sideLength;
682 if ( !qFuzzyCompare(p.x(), 1.0 * x) && qFuzzyCompare(p.x(), 1.0 * (x + 1)) )
683 x++;
684 }
685
686 if (qFuzzyCompare(p.y(), m_sideLength * 1.0))
687 y = m_sideLength - 1;
688 else {
689 y = static_cast<int>(p.y()) % m_sideLength;
690 if ( !qFuzzyCompare(p.y(), 1.0 * y) && qFuzzyCompare(p.y(), 1.0 * (y + 1)) )
691 y++;
692 }
693
694 tilesX[i] = x;
695 tilesY[i] = y;
696 }
697
698 QGeoCameraTilesPrivate::TileMap map;
699
700 // walk along the edges of the polygon and add all tiles covered by them
701 for (int i1 = 0; i1 < numPoints; ++i1) {
702 int i2 = (i1 + 1) % numPoints;
703
704 double x1 = polygon.at(i1).get(0);
705 double x2 = polygon.at(i2).get(0);
706
707 bool xFixed = qFuzzyCompare(x1, x2);
708 bool xIntegral = qFuzzyCompare(x1, std::floor(x1)) || qFuzzyCompare(x1 + 1.0, std::floor(x1 + 1.0));
709
710 QList<QPair<double, int> > xIntersects
711 = tileIntersections(x1,
712 tilesX.at(i1),
713 x2,
714 tilesX.at(i2));
715
716 double y1 = polygon.at(i1).get(1);
717 double y2 = polygon.at(i2).get(1);
718
719 bool yFixed = qFuzzyCompare(y1, y2);
720 bool yIntegral = qFuzzyCompare(y1, std::floor(y1)) || qFuzzyCompare(y1 + 1.0, std::floor(y1 + 1.0));
721
722 QList<QPair<double, int> > yIntersects
723 = tileIntersections(y1,
724 tilesY.at(i1),
725 y2,
726 tilesY.at(i2));
727
728 int x = xIntersects.takeFirst().second;
729 int y = yIntersects.takeFirst().second;
730
731
732 /*
733 If the polygon coincides with the tile edges we must be
734 inclusive and grab all tiles on both sides. We also need
735 to handle tiles with corners coindent with the
736 corners of the polygon.
737 e.g. all tiles marked with 'x' will be added
738
739 "+" - tile boundaries
740 "O" - polygon boundary
741
742 + + + + + + + + + + + + + + + + + + + + +
743 + + + + + +
744 + + x + x + x + +
745 + + + + + +
746 + + + + + + + + O O O O O + + + + + + + +
747 + + O 0 + +
748 + + x O x 0 x + +
749 + + O 0 + +
750 + + + + + + + + O 0 0 0 0 + + + + + + + +
751 + + + + + +
752 + + x + x + x + +
753 + + + + + +
754 + + + + + + + + + + + + + + + + + + + + +
755 */
756
757
758 int xOther = x;
759 int yOther = y;
760
761 if (xFixed && xIntegral) {
762 if (y2 < y1) {
763 xOther = qMax(0, x - 1);
764 }
765 }
766
767 if (yFixed && yIntegral) {
768 if (x1 < x2) {
769 yOther = qMax(0, y - 1);
770
771 }
772 }
773
774 if (xIntegral) {
775 map.add(xOther, y);
776 if (yIntegral)
777 map.add(xOther, yOther);
778
779 }
780
781 if (yIntegral)
782 map.add(x, yOther);
783
784 map.add(x,y);
785
786 // top left corner
787 int iPrev = (i1 + numPoints - 1) % numPoints;
788 double xPrevious = polygon.at(iPrev).get(0);
789 double yPrevious = polygon.at(iPrev).get(1);
790 bool xPreviousFixed = qFuzzyCompare(xPrevious, x1);
791 if (xIntegral && xPreviousFixed && yIntegral && yFixed) {
792 if ((x2 > x1) && (yPrevious > y1)) {
793 if ((x - 1) > 0 && (y - 1) > 0)
794 map.add(x - 1, y - 1);
795 } else if ((x2 < x1) && (yPrevious < y1)) {
796 // what?
797 }
798 }
799
800 // for the simple case where intersections do not coincide with
801 // the boundaries, we move along the edge and add tiles until
802 // the x and y intersection lists are exhausted
803
804 while (!xIntersects.isEmpty() && !yIntersects.isEmpty()) {
805 QPair<double, int> nextX = xIntersects.first();
806 QPair<double, int> nextY = yIntersects.first();
807 if (nextX.first < nextY.first) {
808 x = nextX.second;
809 map.add(x, y);
810 xIntersects.removeFirst();
811
812 } else if (nextX.first > nextY.first) {
813 y = nextY.second;
814 map.add(x, y);
815 yIntersects.removeFirst();
816
817 } else {
818 map.add(x, nextY.second);
819 map.add(nextX.second, y);
820 x = nextX.second;
821 y = nextY.second;
822 map.add(x, y);
823 xIntersects.removeFirst();
824 yIntersects.removeFirst();
825 }
826 }
827
828 while (!xIntersects.isEmpty()) {
829 x = xIntersects.takeFirst().second;
830 map.add(x, y);
831 if (yIntegral && yFixed)
832 map.add(x, yOther);
833
834 }
835
836 while (!yIntersects.isEmpty()) {
837 y = yIntersects.takeFirst().second;
838 map.add(x, y);
839 if (xIntegral && xFixed)
840 map.add(xOther, y);
841 }
842 }
843
844 QSet<QGeoTileSpec> results;
845
846 int z = m_intZoomLevel;
847
848 typedef QMap<int, QPair<int, int> >::const_iterator iter;
849 iter i = map.data.constBegin();
850 iter end = map.data.constEnd();
851
852 for (; i != end; ++i) {
853 int y = i.key();
854 int minX = i->first;
855 int maxX = i->second;
856 for (int x = minX; x <= maxX; ++x) {
857 results.insert(QGeoTileSpec(m_pluginString, m_mapType.mapId(), z, x, y, m_mapVersion));
858 }
859 }
860
861 return results;
862 }
863
TileMap()864 QGeoCameraTilesPrivate::TileMap::TileMap() {}
865
add(int tileX,int tileY)866 void QGeoCameraTilesPrivate::TileMap::add(int tileX, int tileY)
867 {
868 if (data.contains(tileY)) {
869 int oldMinX = data.value(tileY).first;
870 int oldMaxX = data.value(tileY).second;
871 data.insert(tileY, QPair<int, int>(qMin(tileX, oldMinX), qMax(tileX, oldMaxX)));
872 } else {
873 data.insert(tileY, QPair<int, int>(tileX, tileX));
874 }
875 }
876
877 QT_END_NAMESPACE
878